"Unique" Sudoku Puzzles
"Unique" Sudoku Puzzles
(OP)
This is not a "puzzle" in the normal sense. More of a programming problem that's been rattling around in my head.
While playing Sudoku the other day, I started wondering if I had ever played that exact puzzle before. I play a lot of Sudoku (it's the go-to bathroom book in our house). If you are unfamiliar with it, just hit up Google.
Anyway, I was looking at a puzzle and noticed that there are two parts to it's "uniqueness". One is which positions have a hint number revealed, and two, what the number is in those positions. Here's an example puzzle just pulled randomly from the web.
One twist, I consider this puzzle to be functionally identical to the previous example...
Even this puzzle would be functionally the same...
So, I've come up with a couple solutions for a code to uniquely identify the puzzle, but they are anything but concise. I'll save the description of my solution(s) for a bit, but I will say they use bitmaps and rely on the symmetry in the puzzle. These three example puzzles above all encode to the same code using my current best shot...
1161129923444.1234567172435123684379781933651864874823
One thing about my attempt is that the "code" gets shorter for the more difficult puzzles since there are fewer hint numbers to be encoded.
So, I guess that means there are two parts to this "puzzle" post.
Part 1: Can you come up with a way of generating a code that uniquely identifies a Sudoku puzzle, accounting for number shifts that don't affect the solution pattern?
Part 2: Can you figure out my encoding scheme? (it's pretty simple brute force actually)
While playing Sudoku the other day, I started wondering if I had ever played that exact puzzle before. I play a lot of Sudoku (it's the go-to bathroom book in our house). If you are unfamiliar with it, just hit up Google.
Anyway, I was looking at a puzzle and noticed that there are two parts to it's "uniqueness". One is which positions have a hint number revealed, and two, what the number is in those positions. Here's an example puzzle just pulled randomly from the web.
8 . . | . . 6 | 2 9 . . 1 . | 3 5 . | . . 8 . 5 6 | 9 2 . | . 1 . --------------------- . 8 . | . 6 2 | . 3 4 9 . 2 | . . . | 5 . 7 5 4 . | 8 7 . | . 2 . --------------------- . 2 . | . 3 1 | 8 4 . 3 . . | . 9 4 | . 5 . . 9 4 | 6 . . | . . 2What I was wondering was, is there a concise way to create a code to uniquely identify this puzzle? A code that could be recorded and compared with other codes to identify a repeat puzzle? (not that I would actually do that, but just wondering HOW I could do that).
One twist, I consider this puzzle to be functionally identical to the previous example...
9 . . | . . 7 | 3 1 . . 2 . | 4 6 . | . . 9 . 6 7 | 1 3 . | . 2 . --------------------- . 9 . | . 7 3 | . 4 5 1 . 3 | . . . | 6 . 8 6 5 . | 9 8 . | . 3 . --------------------- . 3 . | . 4 2 | 9 5 . 4 . . | . 1 5 | . 6 . . 1 5 | 7 . . | . . 3That is, the numbers are different (all incremented by 1, 9 wraps to 1), but the pattern the numbers present are identical to the previous puzzle, so the means of solving it are the same. This is the part that was bugging me. Are they just publishing the same puzzle with the numbers moved around?
Even this puzzle would be functionally the same...
8 . . | . . 6 | 2 1 . . 9 . | 3 5 . | . . 8 . 5 6 | 1 2 . | . 9 . --------------------- . 8 . | . 6 2 | . 3 4 1 . 2 | . . . | 5 . 7 5 4 . | 8 7 . | . 2 . --------------------- . 2 . | . 3 9 | 8 4 . 3 . . | . 1 4 | . 5 . . 1 4 | 6 . . | . . 2In this puzzle, just the 9's and 1's are swapped, but the logic of solving it is the same as the first puzzle.
So, I've come up with a couple solutions for a code to uniquely identify the puzzle, but they are anything but concise. I'll save the description of my solution(s) for a bit, but I will say they use bitmaps and rely on the symmetry in the puzzle. These three example puzzles above all encode to the same code using my current best shot...
1161129923444.1234567172435123684379781933651864874823
One thing about my attempt is that the "code" gets shorter for the more difficult puzzles since there are fewer hint numbers to be encoded.
So, I guess that means there are two parts to this "puzzle" post.
Part 1: Can you come up with a way of generating a code that uniquely identifies a Sudoku puzzle, accounting for number shifts that don't affect the solution pattern?
Part 2: Can you figure out my encoding scheme? (it's pretty simple brute force actually)
RE: "Unique" Sudoku Puzzles
The premise of your objective seems unattainable though. I've also wondered if I've solved the same puzzle more than once. The problem is that the initial values need not contain the same quantity of numbers, nor do they need to be the same values, nor do they need to be the same positions. This all but guarantees enough starting configurations for the same solution to be impossible to relate to one another by any means other than the solution. To prove my point on this, I solved the puzzle, juggled the numbers and chose different seed values. I kept the same number of seed values (40), but even this was probably not necessary. The puzzle below has the same solution to above.
Side note, if you transcribed your puzzle correctly, this is a poor example as it does not have a unique solution, it actually has 4 solutions. My example is 1 of those solutions.
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
I think the categorization should not be about the result pattern, but about a) Number of seed digits and b) their pattern both in positioning and in the given increments and permutations of the numbers. That's all you need to categorize.
I have to think about this more, I don't get the encoding, neither part of the 13.40 number.
I think of way to normalize a pattern. An idea to eleminate diffrent incrments would be to set the first digit found in a puzzle to 1 and decrement all other digits in th same manner (including the wrap around). It wouldn't make puzzles with permutations equal, though. And since geometrically mirrored and rotated puzzles would also be equal even for permutated puzzles this step of normalization would not find equal puzzles when mirrored or rotated. So it's a weak first thought only on the way to a normalized puzzle format.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
I'll explain the encoded number in a bit. This puzzle just happens to encode to 13.40 because there are 40 seed values. A puzzle with fewer hint digits, or digits in different locations, would possibly generate fewer digits in the encoded value. But, it can be used to regenerate the puzzle, or be used to identify similar puzzles.
The 13.40 code could also be expressed as: 1161129923444.ABCDEFGAGBDCEABCFHDCGIGHAICCFEAHFDHGDHBC
From this I can reconstruct the puzzle.
RE: "Unique" Sudoku Puzzles
I had another idea about normalizing that would work out for the solved puzzle only, though, eg you can normalize any permutations of digits by replacing the first row with 1 to 9 and permuating all other digits in the same manner as that replacement permutates the digits of the first row. Since increments with wraparound is indeed just a special case of permutations that's also already in it.
It's obviously not possible in that exact manner for the non solved puzzle. Your encoding starts of 1 to 7 or A to G indicate you're doing something similar anyway, but since there are still some rotations and flips to consider I wonder whether you really get all similar puzzles encoded in the same way.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
Here's a better example taken from one of my Sudoku books. This example was chosen for a reason.
This would encode to the following (11.27)...
Or, using the Alpha encoding...
And, if I wanted to actually be able to recreate this EXACT puzzle, I would use this code...
Given that 11.27 code, I can recreate the exact puzzle.
RE: "Unique" Sudoku Puzzles
Hidden:
The first 3 rows of numbers are actually 8629135856921. Each digit in the sequence is assigned a unique identifier for the order in which it appears. 8 appears first so it get a digit 1, 6 is second, 2 is 3rd, etc. The first 7 digits are unique from one another so they result in 1234567. the Eighth digit repeats the first digit so it is assigned a 1 again.
When the digits are replaced later on it does not matter which digit is chosen for each relative position. I believe there are 9! (362880) ways the numbers could be replaced and result in the same puzzle from a solving process perspective.
What this does not tell us is the positions of those numbers. Somehow I believe this is what the first 13 digits conveys but I haven't sussed that out as yet.
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Here's what the first part of the code is and how it's generated...
Spoiler:
Given this as an example...
As kwbMitel said, the second part of the code identifies the pattern of 'hint' digits that were given, but it doesn't provide information on where in the puzzle those are placed. That's the role of the first part of the code.
It's a bitmap of where in the puzzle hint digits were placed, but only of the first half. That's because the puzzle is point symetrical with the center point in the puzzle, so we don't really need to map the whole thing. I first go through the puzzle, left to right, top to bottom, and put a 0 if nothing is there, or a 1 if something is there, only down to the middle spot. That gives this (asterisks for cells I don't care about).
This gives us the binary value 1110101000111010001001000110000001, which is a decimal 15718715777, the first part of the code.
So the two parts of the code are, 1) where hints are located, and 2) what the hints are.
RE: "Unique" Sudoku Puzzles
Spoiler:
...is because there are fewer hints (which makes the second part of the code smaller) and the first row starts with seven blanks (which makes the first part of the code smaller).
RE: "Unique" Sudoku Puzzles
Hidden:
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Spoiler:
But you're right, while symmetry may be most common now, it looks like it was introduced in 1986 (according to Wikipedia).
https://en.wikipedia.org/wiki/Sudoku
I would think you'd just need to expand the first field bitmap to be 91 bits long. but that can generate a very large number. Then it's getting close to just listing out the entire puzzle like this (which I have seen online)...
One of the original goals was to produce a key of minimal size.
RE: "Unique" Sudoku Puzzles
Hidden:
I just spent the last 10 minutes looking at random printable Sudoku puzzles online and couldn't find a symmetrical one out of about 5 sites and 30 some puzzles.
Assuming your "91" to be a typo for 81.
Taking asymmetry into account, I think the effort required to covert to a shorter number is offset by the simplicity of just listing the 81 digits.
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
OK, that reveals you assign 1 or A to the first seed digit, B to the second one, etc. unless digits already have a code, of course, as same original digits have to have same code. Using letters is fine. That's what I thought of but didn't believe, when I said:
Spoiler:
I see the wikipedia link shining through (a known isssue of the spoiler TGML tag), I know it has a lot of considerations about the possible number of puzzles etc.
There are also row swap operations, that change the geometry of the digit distribution in the cells in non symmetrcal ways and still can be considered the same nature of the puzzle, for example the considerations for row 1-3 are the same, no matter how you otde them.
From the perspective of the normalization of the solution you could therefore sort each three rows to aggregate all the row permutations into one puzzle solution. You may again apply that to the unsolved seed outset considering all unfilled cells as 0, but I doubt this will lead to a real and straight forward normalization of all similar puzzles.
So to categorize puzzles we need other rules and ideas than for solution categorization.
I still haven't figured out the first digits of your encoding, they would need to tell something about the positioning of the digits. Since that is a binary pattern you may just have decoded that in a 81 digit binary number, that could be converted as up to 25 decimal places decimal number.
Your encoding scheme does not fit its purpose, but that's also why you said you were coming here to ask for inspirations and ideas. I don't yet have a better idea, though.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
I used simple substitution via a Matrix - This comes from my cipher experience
the numbers 1-9 are substituted by A-I
Numbers preceded by:
- 0 Spaces = A-I
- 1 Space = J-R
- 2 Spaces = S-Z and -
- 3 Spaces = a-i
- 4 Space = j-r
- 5 Spaces = s-z and +
- etc as needed
This results in your 40 seed values becoming HoBISLEhNFIBSZXBLDIKNPEDQGTTUAHDLiDN-DFk**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Well, just listing the 81 digits only encodes that exact puzzle. To get similar puzzles (same puzzle (pattern and hints) but with the digits in different order), it would need to look like this...
Actually, that's not bad. Then maybe to compress the zeroes out, use numeric digits. The numeric digit represents how many zeros, or blanks. Something like this...
That's pretty concise, encodes to be able to identify similar puzzles, and will allow asymmetric puzzles. It's size will vary depending on number of hints in the puzzle. It would also be very easy to code (Java, C, etc). I'm liking this one.
@kwbMitel, I don't quite understand your substitution matrix, but I assume it's something similar to this encoding.
@Olaf, wow, I hadn't considered row swap (and of course column swap). But that does make complete sense that it doesn't actually alter the puzzle topologically. I'll have to roll this one around in my head for a bit.
Actually my first encoding scheme does fit my purpose (as far as I can tell). It just seemed very clumsy and brutish, and produced a very large 'key'. I was looking to optimise it, or replace it with something more elegant or clever.
And my hidden reason for coming here was that I love the Puzzles for Programmers Forum and it's been a long time since anything was posted here to play with.
RE: "Unique" Sudoku Puzzles
Yes and no.
Using your method, the encoding length will vary depending on how the spaces are distributed. A 40 clue puzzle where each clue does not have a neighbour would result in an 81 character encoding.
My method embeds the spaces in a single character in such a way that the number of characters will always match the number of clues given. When I encoded my example, I used the actual digits for encoding so that particular one is an exact match for the puzzle. It is just as easy to encode by order of digit found much like your original dot40 code
Here is an example of a matrix for encoding
I'm not sure how many columns may be necessary in this matrix but 9 seems like a reasonable number that would cover most puzzles
Using your first puzzle(s) as an example, it would encode as follows for non-specific numbers
ETC...
AkCDWOGaPBHCW etc...
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Mine was encoding to approximately 2x the number of hints (depending on leading/trailing spaces or not).
RE: "Unique" Sudoku Puzzles
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
As far as puzzles with "vast spaces", they can never be too vast. According to the Wikipedia page...
With 81 squares, and 17 hints, the maximum blank squares is 63. With those evenly distributed above and below the midpoint, due to symmetry, the maximum possible run of blanks would be 32. Like this ('H' for Hint).
But that's not a solvable puzzle. There has to be some distribution of hints so that there aren't three blank rows on top and bottom.
I have seen puzzles with blank squares, and puzzles with individual blank rows or columns, but there is always a number of hints in that row/column group to allow you to solve the blanks. So I don't think you will ever encounter a very large number of contiguous spaces "in the wild".
RE: "Unique" Sudoku Puzzles
It doesn't need to end here, but 5 spaces isn't much, is it? So yo surley would need some more columns. And while there are more than just big and small letters
and digitsyou need 9 more characters for each further space you want to be able to encode. The overall encoding shouldn't be too unreadable, should it? Even if it's just a code you would generate to compare puzzles. The idea to use the digits to encode spaces only again would be feasable. Since you only need them to represent more than 5 digits (in the scheme so far) 0 could mean 6, up to 9 meaning 15 spaces. And if two digits are used they can of course represent all numbers up to 99, so you'd never need more.It means some puzzles code would be longer than others, but does that matter?
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
I understood Olaf's suggestion to be a modification of my method so as to simplify the matrix to usable characters on a standard keyboard.
I can easily see filling about 3 more columns with the characters `~!@#$%^&*()_=[]{}\|:;"'<,>.?/ but after that we must go into alternate character sets to achieve 9 or more spaces.
Olaf's suggestion is to use numbers to pad this value when required.
Without even extending the the matrix beyond what I already provided above, this can be done.
- If spaces are 6-14 then use a number to represent the additional spaces
- if spaces are 15-23 then use 2 numbers
After extending the matrix to 9 columns (8 Spaces)- If spaces are 9-17 then use a number to represent the additional spaces
- if spaces are 18-26 then use 2 numbers
Suffice it to say, it is a rare puzzle that will have more than 14 spaces in a row. My matrix above, with Olaf's modification should work for the majority of puzzles. after a quick search the greatest number of spaces I found was 23**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
The lowest number of hints to still give a solvable puzzle is 17 (referenced here). The example puzzle given on the reference page is not point symmetrical and it has a longest blank run of 12 spaces. I would think the rotational symmetry might make a blank run longer than that difficult, or even impossible.
That is, I can make you a puzzle that has a longer run of blanks, but it won't be solvable. I'm thinking this is another problem to solve, but I'm not a mathematician.
So I don't think the matrix needs to be overly large to be able to encode most, if not all solvable puzzles.
RE: "Unique" Sudoku Puzzles
Yes, it's just a matter of taking something like UTF-8 and you have enough chars, but the savings will be less. Since you need 9 characters in each column you can encode up to 28 spaces (256/9 is a bit higher), so you don't even need all ASCII cahracters for the max 17 spaces you found out.
Anyway the encoding stating top left ot bottom right doesn't encode rotated puzzles in the same way, so you need some preparation rules like switching lines and columns before you would start encoding. But then what rules to apply? If you sort rows for example, to get a definite order of any permutation, you still would get other orders, when other digits would be used, if you first replace digits with codes, you have to use some processing order and that will not give the same encoded symbols for rotated puzzles, so also that won't make equal puzzles comparable.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
RE: "Unique" Sudoku Puzzles
Bye, Olaf.
Spoiler:
RE: "Unique" Sudoku Puzzles
How about 4x4?
How many solutions and how many puzzles are there?
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
I'm allowed to ignore symmetry (rotational/mirror/digit substitution?) based on your statements right?
Otherwise, there would only be 1 binary solution
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Hidden:
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
Spoiler:
RE: "Unique" Sudoku Puzzles
Hidden:
I can fully appreciate that due to my method I am overlooking some duplication, but if so, I don't see where.
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
early in the thread Sam made the definition that any permutation of the symbols leads to equal puzzles, and I made the observation if you take it from the solutions a normalization would mean any puzzle starting with the first row as 1234... would take out any permutation and rotation of symbols you can do in each puzzle without changing its nature. In that sense you only have very little 4x4 sudoku solutions all starting with 1234. Perhaps even less than I though. The second row can only start with either 34 or 43 and continue with 12 or 21, the third row has less possibilities overall and the fourth always is defined by the first three.
Even enumarating all these solutions, you finally can switch row 3 and 4 and still have the same nature of puzzle. You could also switch row1 and 2, but that would violate the normalization rule. Also you could switch columns, again that would violate the normalization rule, but puzzles ending with 4321 might also be rotated 180 degrees and match with another, if not with itself.
The first ro normalization already cares for all permutations of sambols and for several other symmetries. Time is short, but maybe I'll simply enumerate all the 4x4 solutions that are truly different in their nature.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
Your elaboration is precisely why I questioned why you counted the binary puzzle as having 2 solutions.
You can't have it both ways. You either allow digit substitution or you don't.
**********************************************
What's most important is that you realise ... There is no spoon.
RE: "Unique" Sudoku Puzzles
Aside of that I now created the essential 6 solutions of 4x4 sudokus:
Spoiler:
3412 3412 3421
2143 2341 2143
4321 4123 4312
1234 1234 1234
4321 4321 4312
2143 2413 2143
3412 3142 3421
Give me any other solution and I show you how it relates to one of these 6.
Bye, Olaf.
RE: "Unique" Sudoku Puzzles
The essence of Sams question is finding essentially differing puzzles, so all symmetry solutions need to be dropped. that's the whole point. And there's more than just symmetries. I actually didn't tested my essential six 4x4 sudokus for point or axis symmetries. I just discarded puzzles with swapped row 3 and 4, as that also is essentially the same.
Bye, Olaf.