Contact US

Question

"Unique" Sudoku Puzzles

SamBones (Programmer)

(OP)

28 Sep 15 19:22

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.

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

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

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

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

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

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

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)

kwbMitel (TechnicalUser) · Answer 1 · 2015-09-29 00:25:11

The 40 digit part of your encoding scheme seems obvious to me. The 13 digit part not so much.

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.

. . .9| 3 . 6 | . . 8
. . . | . 8 9 | 3 . 1
3 8 6 | . . 1 | . 5 .
---------------------
9 . 5 | 8 6 . | 2 . 4
. . 7 | 5 . 4 | . 1 .
8 . 4 | 1 . . | 5 . 6
---------------------
6 7 . | 9 . . | 1 . .
. . . | . 2 . | 6 . 5
5 2 . | 6 1 8 | . . 7

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.

Olaf Doschke (Programmer) · Answer 2 · 2015-09-29 06:56:44

While differnt seeding may end up with the same result you still may consider it a different puzzle. Let alone less seed values will make the puzzle harder, they may also give more different solutions, as you found 4.

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.

SamBones (Programmer) · Answer 3 · 2015-09-29 07:42:22

If the puzzle can be solved four different ways, it may be because I got a bad puzzle. For the post I just Googled "sudoku" and copied the first puzzle I found. Plus I may have introduced typos since I was kind of hand drawing it to avoid having to insert images. I'll get a better example puzzle tomorrow.

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.

Olaf Doschke (Programmer) · Answer 4 · 2015-09-29 08:32:00

Thanks for not fully spoiling that detail puzzle about your encoding.

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.

SamBones (Programmer) · Answer 5 · 2015-09-29 18:16:02

Yeah, the second number in my code is a little obscure, just because I'm using the digits 1 through 9 to encode the digits 1 through 9, even though the 'code' digit 1 may not encode the 'solution' digit 1 and so on. That's why in the ABCD... version, the purpose of the second part of the code is a little more obvious.

Here's a better example taken from one of my Sudoku books. This example was chosen for a reason.

. . . | . . . | . 3 6
4 . 2 | . 5 . | . . 8
1 6 . | 4 . . | . 2 .
---------------------
. 7 . | . . 8 | 2 . .
. . . | . 9 . | . . .
. . 3 | 7 . . | . 4 .
---------------------
. 8 . | . . 6 | . 9 3
3 . . | . 1 . | 5 . 2
7 9 . | . . . | . . .

This would encode to the following (11.27)...

15718715777.123456723486491836291175489

Or, using the Alpha encoding...

15718715777.ABCDEFGBCDHFDIAHCFBIAAGEDHI

And, if I wanted to actually be able to recreate this EXACT puzzle, I would use this code...

15718715777.364258164278293748693315279

Given that 11.27 code, I can recreate the exact puzzle.

kwbMitel (TechnicalUser) · Answer 6 · 2015-09-29 19:36:42

Encoding second part 40 digit example)

Hidden:

The 40 digit part of the coding simply reads left to right 1 row at a time and assigns an arbitrary number/symbol to each value found.
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.

SamBones (Programmer) · Answer 7 · 2015-09-29 21:16:01

Exactly!

Here's what the first part of the code is and how it's generated...

Spoiler:

Given this as an example...

. . . | . . . | . 3 6
4 . 2 | . 5 . | . . 8
1 6 . | 4 . . | . 2 .
---------------------
. 7 . | . . 8 | 2 . .
. . . | . 9 . | . . .
. . 3 | 7 . . | . 4 .
---------------------
. 8 . | . . 6 | . 9 3
3 . . | . 1 . | 5 . 2
7 9 . | . . . | . . .

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

0 0 0 | 0 0 0 | 0 1 1
1 0 1 | 0 1 0 | 0 0 1
1 1 0 | 1 0 0 | 0 1 0
---------------------
0 1 0 | 0 0 1 | 1 0 0
0 0 0 | 0 1 * | * * *
* * * | * * * | * * *
---------------------
* * * | * * * | * * *
* * * | * * * | * * *
* * * | * * * | * * *

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.

SamBones (Programmer) · Answer 8 · 2015-09-29 21:21:40

Spoiler:

The reason this puzzle was selected as a better example...

. . . | . . . | . 3 6
4 . 2 | . 5 . | . . 8
1 6 . | 4 . . | . 2 .
---------------------
. 7 . | . . 8 | 2 . .
. . . | . 9 . | . . .
. . 3 | 7 . . | . 4 .
---------------------
. 8 . | . . 6 | . 9 3
3 . . | . 1 . | 5 . 2
7 9 . | . . . | . . .

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

kwbMitel (TechnicalUser) · Answer 9 · 2015-09-29 21:37:43

@ SamBones: Regarding the first part of the code

Hidden:

I would never have figured that out BTW. Are you limiting your method to symmetrical puzzles or are you assuming that they all are symmetrical? You might notice that my variation on your puzzle above is not symetrical. As such, your coding method will not work for that puzzle I believe. I like your method but I would allow more flexibility by using 21 digits and converting to hexidecimal

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

SamBones (Programmer) · Answer 10 · 2015-09-29 22:58:43

Spoiler:

I don't think I've ever seen an asymmetric clue Sudoku before. I know that some of the online Sudoku solvers will puke an error message if an asymmetric puzzle is input.

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

000000036402050008160400020070008200000090000003700040080006093300010502790000000

One of the original goals was to produce a key of minimal size.

kwbMitel (TechnicalUser) · Answer 11 · 2015-09-30 01:08:17

@SamBones

Hidden:

Re: I don't think I've ever seen an asymmetric clue Sudoku before.

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.

Olaf Doschke (Programmer) · Answer 12 · 2015-09-30 08:33:49

>15718715777.364258164278293748693315279

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:

Quote (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.)

Spoiler:

Your encoding will only cover same patterned puzzles, not sibling puzzles, which are just geometrically rotated, as their "first digit" would not be the same. Well, it's a weak argument, as the same applies to setting the first row of a result to 1-9 or A-I. So siblings due to geometrical symmetries have to be considered seperately anyway.

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.

kwbMitel (TechnicalUser) · Answer 13 · 2015-09-30 14:33:20

@SamBones - An Alternative Method

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.

SamBones (Programmer) · Answer 14 · 2015-09-30 17:33:00

Oops, yeah, 81, not 91. Pardon my fat fingers. bigsmile

Quote (kwbMitel)
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.

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

0000000ABC0D0E000FGB0C000D00H000FD000000I000000AH000C00F000B0IAA000G0E0DHI0000000

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

7ABC1D1E3FGB1C3D2H3FD6I6AH3C2F3B1IAA3G1E1DHI7

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.

Quote (OlafDoschke)
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.

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

kwbMitel (TechnicalUser) · Answer 15 · 2015-09-30 19:38:39

@kwbMitel, I don't quite understand your substitution matrix, but I assume it's something similar to this encoding.

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

           Spaces before digit
           0  1  2  3  4  5   6+
1st digit  A  J  S  a  j  s  etc
2nd digit  B  K  T  b  k  t   
3rd digit  C  L  U  c  l  u    
4th digit  D  M  V  d  m  v    
5th digit  E  N  W  e  n  w    
6th digit  F  O  X  f  o  x    
7th digit  G  P  Y  g  p  y    
8th digit  H  Q  Z  h  q  z   
9th digit  I  R  -  i  r  +

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

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

The 8 is the 1st digit and has 0 preceding spaces so that converts to an A
The 6 is the 2nd digit and has 4 preceding spaces so that converts to an k
The 2 is the 3rd digit and has 0 preceding spaces so that converts to an C
The 9 is the 4th digit and has 0 preceding spaces so that converts to an D
The 1 is the 5th digit and has 2 preceding spaces so that converts to an W
The 3 is the 6th digit and has 1 preceding spaces so that converts to an O
The 5 is the 7th digit and has 0 preceding spaces so that converts to an G
The 8 is the 1st digit and has 3 preceding spaces so that converts to an a
The 5 is the 7th digit and has 1 preceding spaces so that converts to an P
The 6 is the 2nd digit and has 0 preceding spaces so that converts to an B
The 9 is the 8th digit and has 0 preceding spaces so that converts to an H
The 2 is the 3rd digit and has 0 preceding spaces so that converts to an C
The 1 is the 5th digit and has 2 preceding spaces so that converts to an W

ETC...

AkCDWOGaPBHCW etc...

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

SamBones (Programmer) · Answer 16 · 2015-09-30 21:53:12

Oh, awesome! That's really clever.

Mine was encoding to approximately 2x the number of hints (depending on leading/trailing spaces or not).

bigsmile

Olaf Doschke (Programmer) · Answer 17 · 2015-10-01 15:53:05

Yes, the scheme using more encoding characters obviously wins in it's length, but less characters can be compressed, too. Sam, your encoding wouldn't need any 0, so you could encode 1 space with 0, 2 with 1 etc and go up to 10, anyway the encoding of digit+spaces in one character is even better, but makes me wonder what chars you'd need to use for puzzles with vast spaces, you'd need something to denote spaces without any digit, so eg : might mean something like 6 spaces without a digit, more spaces following, so a :A would mean first digit after 6 spaces and :J first digit after 7 spaces or ::A first digit after 12 spaces, etc. This way you can stop at the chart you already have for up to 5 spaces.

Bye, Olaf.

SamBones (Programmer) · Answer 18 · 2015-10-01 18:44:17

Olaf, read through kwbMitel's encoding. It takes into account spaces and only results in a code with as many characters as the number of hints.

As far as puzzles with "vast spaces", they can never be too vast. According to the Wikipedia page...

Quote (https://en.wikipedia.org/wiki/Sudoku)
...the fewest givens that render a solution unique—was proven to be 17 in January 2012 (confirmed in September 2013). A number of valid puzzles with 17 givens have been found for the standard variation without a symmetry constraint, by Japanese puzzle enthusiasts, and 18 with the givens in rotationally symmetric cells.

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

. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
---------------------
. . . | . . H | H H H 
H H H | H H H | H H H
H H H | H . . | . . .
---------------------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

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

Olaf Doschke (Programmer) · Answer 19 · 2015-10-01 19:56:04

Well, I have understood the schema very well.

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 digits~~ you 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.

kwbMitel (TechnicalUser) · Answer 20 · 2015-10-01 19:59:30

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

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.

SamBones (Programmer) · Answer 21 · 2015-10-03 00:34:42

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 (Programmer) · Answer 22 · 2015-10-03 09:46:22

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

Olaf Doschke (Programmer) · Answer 23 · 2015-10-15 09:32:24

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

0|
---
 |

Bye, Olaf.

Spoiler:

It has the same solution

Olaf Doschke (Programmer) · Answer 24 · 2015-10-15 17:54:34

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?

12|34
34|12
--+--
23|41
41|23

How many solutions and how many puzzles are there?

Bye, Olaf.

kwbMitel (TechnicalUser) · Answer 25 · 2015-10-15 18:04:02

@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 (TechnicalUser) · Answer 26 · 2015-10-15 18:31:09

ignoring symmetry for 4x4 I get

Hidden:

384

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

Olaf Doschke (Programmer) · Answer 27 · 2015-10-16 06:52:08

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 (Programmer) · Answer 28 · 2015-10-16 10:26:01

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 (TechnicalUser) · Answer 29 · 2015-10-16 18:18:36

@olafdosche

Hidden:

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

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.

Olaf Doschke (Programmer) · Answer 30 · 2015-10-17 12:23:56

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 (TechnicalUser) · Answer 31 · 2015-10-18 19:31:56

@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 (Programmer) · Answer 32 · 2015-10-18 20:31:52

No, reread what I said:

Quote (myself)
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.

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 (Programmer) · Answer 33 · 2015-10-18 20:46:56

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.

Contact US

Come Join Us!

Posting Guidelines

"Unique" Sudoku Puzzles

"Unique" Sudoku Puzzles

"Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Hidden:

RE: "Unique" Sudoku Puzzles

Spoiler:

RE: "Unique" Sudoku Puzzles

Spoiler:

RE: "Unique" Sudoku Puzzles

Hidden:

RE: "Unique" Sudoku Puzzles

Spoiler:

RE: "Unique" Sudoku Puzzles

Hidden:

RE: "Unique" Sudoku Puzzles

Quote (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.)

Spoiler:

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Quote (kwbMitel)

Quote (OlafDoschke)

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Quote (https://en.wikipedia.org/wiki/Sudoku)

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Spoiler:

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Hidden:

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Spoiler:

RE: "Unique" Sudoku Puzzles

Hidden:

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

RE: "Unique" Sudoku Puzzles

Quote (myself)

Spoiler:

RE: "Unique" Sudoku Puzzles

Red Flag This Post

Red Flag Submitted

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Join Tek-Tips® Today!

Join Tek-Tips^® Today!