The kings move constraint confuses me. Where does N1 get checked against N5, its diagonal?
Solving the “Miracle Sudoku” in Prolog
31–36 of 36 posts
Re: Solving the “Miracle Sudoku” in Prolog
#32Earlier quoted context omitted.
It's only a single pattern. Every solution has the 1,5,9,4,8,3,7,2,6 pattern (every step is +4 mod 9) in either the rows or the columns. 9 ways to transpose; 4 rotations, 2 for flipped or not. Multiply those, you get the full 72.
Which are the "9 ways to transpose"? In general there are 8 symmetries of a matrix, but you might also count reordering of rows/columns or blocks? I agree that 1,5,9,4,8,3,7,2,6 pattern rotations is there somewhere, either in the columns or the rows of a solution, but that don't make all solutions the same.
Different people could reasonably disagree. The solutions with top rows:
159483726
594837261
Look pretty equivalent to me, which is how you get the 9 transpositions.
Re: Solving the “Miracle Sudoku” in Prolog
#33Earlier quoted context omitted.
Which are the "9 ways to transpose"? In general there are 8 symmetries of a matrix, but you might also count reordering of rows/columns or blocks? I agree that 1,5,9,4,8,3,7,2,6 pattern rotations is there somewhere, either in the columns or the rows of a solution, but that don't make all solutions the same.
Different people could reasonably disagree. The solutions with top rows: 159483726 594837261 Look pretty equivalent to me, which is how you get the 9 transpositions.
Yes, but the solutions are different if the order (permutation) of the rows with the pattern rotations are different. There is a huge number of ways the rows can be ordered (9!).
Re: Solving the “Miracle Sudoku” in Prolog
#34Very nicely done, thank you for sharing this! A CLP(FD/ℤ) solution such as this one has two parts: First, the relevant constraints are posted. Second, a search tries to find concrete solutions. In general, a search is necessary because the constraints by themselves are not sufficient to deduce the unique solution as that would be computationally prohibitive. You can therefore influence the speed of the logic program…
I recently went though a whole bunch of your Power of Prolog videos [0], solving and generating such sudokus was the first thing I thought about when watching the original video of the guy solving the Miracle Sudoku.
Thanks for those videos!
[0] https://www.youtube.com/channel/UCFFeNyzCEQDS4KCecugmotg/fea...
Re: Solving the “Miracle Sudoku” in Prolog
#35The OP says there are 6x10^21 Sudoku puzzles. If we remove rotations and reflections, there may be (far) fewer unique Sudoku puzzles than we think. In fact, there are many sub-reflections that are essentially the 'same' puzzle: Take the first three rows as a block, 'rotate' to the bottom of the puzzle - its still 'solved'. In fact permute the blocks of three rows in any order, still the 'same' puzzle in a sense. Same…
yes, the number is greatly reduced, but you're leaving out a source of more variation. A sudoku puzzle not the solution, it's the constrained choice of what is shown vs hidden in the initial state. One solution could be parent to a number of solvable puzzles of varying difficulty.
Re: Solving the “Miracle Sudoku” in Prolog
#36The OP says there are 6x10^21 Sudoku puzzles. If we remove rotations and reflections, there may be (far) fewer unique Sudoku puzzles than we think. In fact, there are many sub-reflections that are essentially the 'same' puzzle: Take the first three rows as a block, 'rotate' to the bottom of the puzzle - its still 'solved'. In fact permute the blocks of three rows in any order, still the 'same' puzzle in a sense. Same…
In 2005, Ed Russell and Frazer Jarvis calculated 5,472,730,538 "essentially different" 9x9 grids [1][2], once they've excluded valid grids that can be derived from another valid grid using relabelling, various permutations, reflection, rotation, etc. [1] http://www.afjarvis.staff.shef.ac.uk/sudoku/sudgroup.html [2] (PDF) http://www.afjarvis.staff.shef.ac.uk/sudoku/russell_jarvis_s...
OK I read that -very interesting! And now I'm positive I don't know how to prove it myself. Luckily there are smarter people who can address problems like this. Thanks for the link!