"Unique" Sudoku Puzzles 1

[SamBones]

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.

[pre]
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 . . | . . 2
[/pre]
What 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...

[pre]
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 . . | . . 3
[/pre]
That 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...

[pre]
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 . . | . . 2
[/pre]
In 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...

[tt]1161129923444.1234567172435123684379781933651864874823[/tt]

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)

 

[kwbMitel]

@sambones

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.

[ul]
[li]If spaces are 6-14 then use a number to represent the additional spaces[/li]
[li]if spaces are 15-23 then use 2 numbers[/li]
[/ul]

After extending the matrix to 9 columns (8 Spaces)

[ul]
[li]If spaces are 9-17 then use a number to represent the additional spaces[/li]
[li]if spaces are 18-26 then use 2 numbers[/li]
[/ul]

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.

 

[SamBones]

I think I understand, but I also believe there's a limit to the number of contiguous spaces that a puzzle can have, and still be a solvable puzzle.

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.

 

[Olaf Doschke]

>I don't think the matrix needs to be overly large to be able to encode most, if not all solvable 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.

 

[SamBones]

 

[Olaf Doschke]

That's too easy, here's a harder binary sudoku:

[pre]0|
---
| [/pre]

Bye, Olaf.

Spoiler

It has the same solution

 

[Olaf Doschke]

For binary Sudoku there are exact 2 different solutions and normalizing the first row to 01 only one. You can make 3 different puzzles showing 1,2, or 3 of the four digits.

How about 4x4?

[pre]12|34
34|12
--+--
23|41
41|23[/pre]

How many solutions and how many puzzles are there?

Bye, Olaf.

 

[kwbMitel]

@Olaf

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.

 

[kwbMitel]

ignoring symmetry for 4x4 I get [hide]384[/hide]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

Yes, you are "allowed" to ignore all the symmetries. It makes it harder, if you ask me. Also the number of solutions is easier to define and get than number of puzzles is.

Bye, Olaf.

 

[Olaf Doschke]

Spoiler

I'd say you have 24 solutions, normalizing symbol permuations by starting any puzzle with 1234 you have 3!x2! possibilities for row 2 and 2! possibilities for row 3, one for row 4. All together 3x2x2x2=24 solutions, should be easy to generate them all, then see if any symmetry is missed without further normalization rules.

 

[kwbMitel]

@olafdosche

[Hide]
[pre]I get 4! unique combinations for a single cell of 4. Obviously to total would be higher than that

1 2 or 1 2 or 1 3 or 1 3 or 1 4 or 1 4
3 4 4 3 2 4 4 2 2 3 3 2

2 1 or 2 1 or 2 3 or 2 3 or 2 4 or 2 4
3 4 4 3 1 4 4 1 1 3 3 1

3 2 or 3 2 or 3 1 or 3 1 or 3 4 or 3 4
1 4 4 1 2 4 4 2 2 1 1 2

4 2 or 4 2 or 4 3 or 4 3 or 4 1 or 4 1
3 1 1 3 2 1 1 2 2 3 3 2


For each of the above there are four solutions in each of the adjacent cells

Using the first above as an example here are the 4 associated in the cell to the right

first
1 2 | 3 4
3 4 | 1 2

second
1 2 | 4 3
3 4 | 1 2

third
1 2 | 3 4
3 4 | 2 1

fourth
1 2 | 3 4
3 4 | 1 2

Again using the first here are the 4 associated in the lower Cell

1st 2nd 3rd 4th

1 2 1 2 1 2 1 2
3 4 3 4 3 4 3 4
- - - - - - - -
2 3 4 3 2 1 4 1
4 1 2 1 4 3 2 3

The last Cell has no options as all positions are determined by previous

So the total would be

4! * 4 * 4 * 1 = 384[/pre]

I can fully appreciate that due to my method I am overlooking some duplication, but if so, I don't see where.
[/hide]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

kwbmitel,

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.

 

[kwbMitel]

@Olaf, Regarding your last.

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.

 

[Olaf Doschke]

No, reread what I said:

For binary Sudoku there are exact 2 different solutions [highlight #FCE94F]and normalizing the first row to 01 only one[/highlight]. You can make 3 different puzzles showing 1,2, or 3 of the four digits.

Aside of that I now created the essential 6 solutions of 4x4 sudokus:

Spoiler

1234 1234 1234
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.

 

[Olaf Doschke]

So finally, no you are not allowed to ignore symmetries. It depends on how you define ignore, that's why I got your question wrong.

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.