The New Sudoku Players' Forum

[ThemePark]

I have come up with a way to generate all sudokus, given a pattern of whether each cell contains a clue or not.

The idea is that, given such a pattern, all unique permutations of it is made through swapping rows and columns, and then each permutation is applied to each of the essentially different sudokus and then checked for solvability and uniqueness. Then you have all essentially different sudokus possible with that bit pattern, and you can then swap the rows and columns back to assemble the original pattern. Of course, often there will be more than one way to do that with a pattern if there is any symmetry, but still all sudokus with that pattern will be represented by the collection built from this.

But here's the problem. If I want to have the top row be minlex, I gather that I should be able to skip all column swaps of the bit pattern, but I am not 100 % sure that that will truly give me all possible sudokus with that pattern, or whether I will be missing out on some.

Take this bit pattern for instance:

Code: Select all

X.X X.X X.X
X.X X.X X.X
X.X X.X X.X

X.X X.X X.X
X.X X.X X.X
X.X X.X X.X

X.X X.X X.X
X.X X.X X.X
X.X X.X X.X

Swapping rows won't change anything about the pattern, and by choosing not to swap columns there is only this possible permutation of the pattern. So I should get 5472730538 sudokus with this pattern, out of which some number will be solvable and unique. But will this really give me all the representatives of all possibly sudokus with this pattern? That is where I am in doubt.

[dobrichev]

Hi,

Maybe your interest is in generating all different (up to Validity Preserving Transformations) sudoku puzzles.

Your pattern has ehough givens (X are givens, aren't they?) to be able to generate sufficient solvable puzzles so that their solutions cover all possible grids (5472730538). But the goal is to generate puzzles, not solutions. Each solution can be defined by > 1 puzzle.

You can fix the labels for the givens in the house with most givens. In your example such house is column 1 with 9 givens. For other patterns this could be row or box.

Or, is the goal finding all sudoku solutions, which uniquely can be defined by a puzzle having givens only within the given pattern?

Cheers,
MD

[ThemePark]

"Maybe your interest is in generating all different (up to Validity Preserving Transformations) sudoku puzzles."

Yes, that is exactly right. Just as the 5472730538 solutions are representative of ALL solutions, in that any solution can be made from one of the different solutions by transformations, I want to create all representatives of all sudokus with a certain pattern, i.e. so that I'm able to generate any sudoku with the given pattern from the list of representatives through transformations.

The list of essentially different sudokus I have are generated with gsf's solver and thus the top row is 123456789. I want to keep it like that in all the representatives. But in generating all permutations from a bit pattern by using transformations, I will also be switching the columns, thus breaking the minlex top row. I could just generate all the permutations anyway, and then once I have all representations I can switch the columns again so the top row is minlex once again.

But as far as I can tell, choosing NOT to switch the columns on the bit pattern will give the same amount of representations, because the method mentioned above is about making a transformation and then undoing it. But I am not 100 % sure that I am right, and that is what I would like an answer for.

IF I choose NOT to switch the columns when generating all representations of a given bit pattern, will I still get ALL representations of ALL sudokus with that given bit pattern?

[coloin]

Challenging..... Maybe all grids will indeed have that pattern.

But even with swiching columns they might fail .....

Its hard to get 9 horizontal U4s in two vertical bands. Initially it was difficult to get >7 U4s.
But after a bit of work i found grids with these clues which wont have your pattern as a valid puzzle.....

Code: Select all

|1.5|26.|...|
|23.|1.4|...|
|.46|.53|...|
+---+---+---+
|.13|42.|...|
|52.|.16|...|
|6.4|3.5|...|
+---+---+---+
|36.|54.|...|
|4.2|.31|...|
|.51|6.2|...|
+---+---+---+  3 x 3 U4s

I dont think that the diagonally reflected morph will have 9 U4s in the 2 bands ..... so looks like
I would say aprox 30 % of all solution grids would pass first time.
Could be many more than 5e9 iterations.

perhaps the rotated version of the pattern is easier to visualize.

Code: Select all

+---+---+---+
|123|456|789|
|...|...|...|
|458|379|621|
+---+---+---+
|216|538|947|
|...|...|...|
|894|167|532|
+---+---+---+
|537|291|468|
|...|...|...|
|642|783|195|
+---+---+---+

C

[ThemePark]

coloin, read through both my posts again. You have COMPLETELY misunderstood what I asked for and what my problem is!

[dobrichev]

Is this continuation of this topic?

You are mixing Sudoku (the game with its rules) with Sudoku Solution Grid (a 9x9 matrix entirely populated according to Sudoku Rules) and Sudoku Puzzle (a partially populated grid so that it uniquely defines its only Solution Grid).

I admire Coloin's attempt in finding the correct question in your 2 posts.

Maybe the answer you need is that you must:
1) perform all VPT on the chosen template (instead on the canonical representations of all solution grids);
2) order the list alphabetically and remove duplicates;
3) perform the following nested loops

Code: Select all

for each ED grid {
  for each pattern permutation {
    mask the grid with the pattern permutation;
    check the puzzle for uniqueness;
  }
}


Note that there is no step "save the puzzle to storage with infinite capacity"

This would generate duplicate puzzles for the grids with non-trivial automorphism. Since its portion is too small, there is no need to optimize the process. If you kept the flag which grid has non-trivial automorphism, you can accumulate the puzzles for these grids in a buffer and remove duplicates by min-lexing.

Coloin mentioned that your example template will generate puzzles with multiple solutions.

Cheers,
MD

[ThemePark]

dobrichev, you would do well to also read through my posts again, since I have explained everything very clearly. To answer your question, I have found a way to solve the problem in the topic you linked to.

I have written the question once and rephrased it as well.

So I should get 5472730538 sudokus with this pattern, out of which some number will be solvable and unique. But will this really give me all the representatives of all possibly sudokus with this pattern?

IF I choose NOT to switch the columns when generating all representations of a given bit pattern, will I still get ALL representations of ALL sudokus with that given bit pattern?

As you can see, if you can read, it's a simple yes or no question. I'm not asking for methods or anything else, I want a yes or a no to a simple question.

Furthermore, I'm not mixing anything. Sudoku can mean the game, the puzzle and the solution all together. And actually reading my posts will make it clear which of them I'm using at any given point.

http://www.afjarvis.staff.shef.ac.uk/sudoku/

This uses sudoku as meaning the solutions, but it's not written anywhere, it is obvious to the reader that looks at the grids.

So I should get 5472730538 sudokus with this pattern, out of which some number will be solvable and unique.

Here I point out that I am PERFECTLY aware that not all of these sudokus will be valid. So no need to tell me that. And no need to assume I'm stupid, I am perfectly well aware that storing all sudokus will require infinite disk space, but that is NOT what I'm talking about.

So I have asked a question that can be answered simply, and I have stated exactly what I'm trying to do. Now read through it again, and if you can't understand it then don't waste my time. If nobody here are capable of understanding simple English, then I'll just have to figure this out myself through programming and brute force, and not through math which isn't my strong side, hence why I'm asking for help.

[dobrichev]

Please, be patient and reread carefully both topics. Maybe the answer is not described exactly in your language, which is common in all kinds of forums. My manner is to avoid answering "no" and then wait for the next question "why not?".

[coloin]

Sometimes i do get it completely wrong...... the use of the word "sudokus" on ts own is not obvious.

Each valid sudoku grid solution will have 27 plus 27 = 54 ways to display a pattern such as yours.

Your pattern has an average unique rate of 30% - there are on avearge around 16 different valid puzzles per ED grid solution.

If you were to iterate all the possibilities [9! allowed for] for just one of the representatives of your pattern you would get a representative of these 8e10 sudokus [puzzles] and hence all sudokus [grid solutions]. [Note the ambiguity in your question now]
You would also get isomorphic swaps [in one direction] which would be removed by min-lexing. As would puzzles from automorphic grid solutions
You would get plenty of duplicate "puzzles" with >1 sol. as you say and also invalid "puzzles".

But......... This is assuming that all grids have one valid puzzle in one of the 54 ways that the pattern occurs in a grid. This is not certain by any means although i showed you an example of solution grids which the clues make your pattern have multiple grid solutions. [The grid solutions of all the puzzles with those clues wont have at least 27 of the 54 possibles] There doesnt seem to be room for u4s in the perpendicular orientation however. Maybe a combination of U4s U6s might do it. I think you might get MD to verify that if you ask him nicely [dont know how easy it would be !!]



C

[eleven]

ThemePark,

no reason to get angry.

Ok, my English is poor, but normally i can understand, what is meant. I read your posts twice, but i did not. Coloin and dobrichev seem to have the same problem.

So let me ask two questions to clarify it. As i understood, you want to calculate all unique puzzles for a fixed pattern.

You are only talking about "swapping rows and columns", why not about diagonal reflection ?

Have you thought about, what counter examples could be ? E.g. when i have a puzzle with your sample pattern, where 2 columns are swapped. Would it be a counter example for your 2nd question, when the minlex form is a horizontal pattern like Coloin showed one ?

[ab]

I think the answer to the original question is no! You need to do all the column and row and box swapping to get every puzzle.
ab

[coloin]

Except he is wanting to generate every sudoku grid solution with the 54 clue pattern - not puzzle !

However themepark's pattern could be reduced to 48 clues by removing a clue from each full row/column.

As can this pattern

Code: Select all

+---+---+---+
|...|375|942|
|...|1.6|5.8|
|...|982|136|
+---+---+---+
|415|...|697|
|6.9|...|2.3|
|328|...|451|
+---+---+---+
|532|697|...|
|9.7|2.8|...|
|861|534|...|
+---+---+---+

It definitely will be able to represent every sudoku grid solution.
Probably more clues can be removed too

C

[ab]

It seems that each of us understands his idea differently. I think he's trying to find every puzzle for a given distribution of clues by overlaying that template over every possible solution and seeing which ones give a valid puzzle. You clearly think he's trying to generate every possible solution using one template. It's kind of ironic given how clear themepark thought his original requenst was.
ab

[coloin]

So he wants to generate all the sudoku puzzles with this pattern

Except he also asks

But will this really give me all the representatives of all possibly sudokus with this pattern? That is where I am in doubt.

If he means sudoku puzzles - the answer is yes [obviously]
If he means sudoku grid solutions - the answer is - almost certainly
I dont think the swaps make a difference - as its a representative of the puzzle that he needs to generate.

If the pattern is iterated - and reducing the duplicates produced by swapping and normalising - I estimated that there will be 16 X 5e9 valid puzzles [other automorphic puzzles not considered] produced. Each ED grid solution will have a representative because I cant really see a grid having 9UAs in two bands both horizontally and vertically - [No valid pattern in that grid solution therefore - no matter how you swap it]

Maybe Themepark can generate all the puzzles and see if any ED grid solutions dont turn up !

C

[ronk]

There are only 54 permutations (2x3^3) of this pattern that have either one one empty row in each band, or one empty column in each stack.

Code: Select all

 XXX|XXX|XXX
 ...|...|...
 XXX|XXX|XXX
----+---+----
 XXX|XXX|XXX
 ...|...|...
 XXX|XXX|XXX
----+---+----
 XXX|XXX|XXX
 ...|...|...
 XXX|XXX|XXX

Mask each essentially different solution grid, aka grid, with each of the 54 permutations of the pattern, keeping those with a single solution. Canonicalize the keeper puzzles according to their solution grids. Due to automorphism, there may be a few duplicates.

dobrichev may have been thinking 54 permutations when ...

]

Code: Select all

for each ED grid {
  for each pattern permutation {
    mask the grid with the pattern permutation;
    check the puzzle for uniqueness;
  }

}