Solving the “Miracle Sudoku” in Prolog • Hacker News Board

Re: Solving the “Miracle Sudoku” in Prolog

#11

Post by carapace » Mon, May 25, 2020, 6:19 PM UTC

I said just the other day, "Adding constraints that encode the additional rules is also a little puzzle, eh?" I think I see a kind of hierarchy that reminds me of the Futamura Projections:

1. Solving Sudoku puzzles.

2. Designing new Sudoku puzzles (with additional constraints even.)

3. Designing (e.g. CLP(FD/ℤ)) programs to solve all sudoku puzzles everywhere.

- - - -

How do you pronounce "ℤ" in this context? "see el pee eff dee zed"? Seems too plain. "see el pee eff dee Zahlen" seems too fancy. :-)

Re: Solving the “Miracle Sudoku” in Prolog

#12

Post by JoeAltmaier » Mon, May 25, 2020, 6:20 PM UTC

The 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 with the first three columns.

Same with the three rows or columns in a block of three - permute them, the solution is 'unchanged'.

Relabel the digits from 1-9 as 9-1 - another 'reflection' which is the same puzzle pattern.

In fact, permute the digits all different ways - its still solved.

I'm not at all sure there isn't actually just one unique pattern to sudoku. But I don't know how to prove that one way or another.

Re: Solving the “Miracle Sudoku” in Prolog

#13

Post by carapace » Mon, May 25, 2020, 6:22 PM UTC

prezjordan wrote: post #2

This is a really nice post and I especially liked the vulnerability in the conclusion about not being able to generate puzzles quickly because of how you ordered your constraints - I get stuck there almost every time I write Prolog. One thing to nitpick is that the number operators (#>) require an import of clpfd, so some readers may not be able to get the code examples to work.

> require an import of clpfd

    :- use_module(library(clpfd)).

Yeah, always show your imports with your code snippets! :-)

Re: Solving the “Miracle Sudoku” in Prolog

#14

Post by tom_mellior » Mon, May 25, 2020, 6:41 PM UTC

techbio wrote: post #7

Very cool to see, as I'm on and off working on a Kakuro solver/generator using (almost) only SQL...when I get time to finish I'd like to put a similar article together.

Interesting, are there any specific features of SQL that make it a good tool for this? My knowledge of SQL is limited to relatively simple selects and joins, and unfortunately my take-away is that I find it clumsy and verbose. Are there advanced, expressive features that are a good fit for constraint solvers?

Re: Solving the “Miracle Sudoku” in Prolog

#15

Post by ximeng » Mon, May 25, 2020, 6:49 PM UTC

carapace wrote: post #11

I said just the other day, "Adding constraints that encode the additional rules is also a little puzzle, eh?" I think I see a kind of hierarchy that reminds me of the Futamura Projections: 1. Solving Sudoku puzzles. 2. Designing new Sudoku puzzles (with additional constraints even.) 3. Designing (e.g. CLP(FD/ℤ)) programs to solve all sudoku puzzles everywhere. - - - - How do you pronounce "ℤ" in this context? "see el…

ℤ is just the integers, so say the integers or the ring of integers to emphasise the mathematical structure

Re: Solving the “Miracle Sudoku” in Prolog

#16

Post by rscho » Mon, May 25, 2020, 7:14 PM UTC

Recursing wrote: post #10

z3 solver for comparison, from the original thread: https://gist.github.com/sielicki/fd86d68733133f654128519b3c4... I find z3 python interface much simpler, more intuitive and more powerful than prolog for this kind of things

One strong point of prolog is that all outputs are prolog terms themselves. So in terms of ease of use and reuse of results, prolog is much better.

It all depends on what you are looking for.

Re: Solving the “Miracle Sudoku” in Prolog

#17

Post by jepler » Mon, May 25, 2020, 7:29 PM UTC

JoeAltmaier wrote: post #12

The 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…

https://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerat... I believe these ways of relabeling you mention are all taken into account when numbering the "essentially different" puzzle configurations.

Re: Solving the “Miracle Sudoku” in Prolog

#18

Post by niftich » Mon, May 25, 2020, 7:39 PM UTC

JoeAltmaier wrote: post #12

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

Re: Solving the “Miracle Sudoku” in Prolog

#19

Post by maebert » Mon, May 25, 2020, 8:20 PM UTC

Absolutely wonderful puzzle. Back when I taught Prolog in college, I created a number of Sudokus for my students to solve, that and a few other prolog puzzles are here for those enjoying a lazy afternoon of logic programming: https://github.com/maebert/prolog_puzzles#sudoku

Re: Solving the “Miracle Sudoku” in Prolog

#20

Post by techbio » Mon, May 25, 2020, 8:56 PM UTC

tom_mellior wrote: post #14

techbio wrote: post #7

Very cool to see, as I'm on and off working on a Kakuro solver/generator using (almost) only SQL...when I get time to finish I'd like to put a similar article together.

Interesting, are there any specific features of SQL that make it a good tool for this? My knowledge of SQL is limited to relatively simple selects and joins, and unfortunately my take-away is that I find it clumsy and verbose. Are there advanced, expressive features that are a good fit for constraint solvers?

I can say your takeaway seems to be the correct one, as my mental model was far more compact than the actual SQL it has turned out to require. (Edit: Hope remains that proper structuring of data will obviate the need for much of this sql)

I am using joins over constraints written and read in MEMORY tables (including CROSS JOIN, generating an application of which was one of my motivations to do the project). Anything advanced is pushed to the query execution plan.

This is on MySQL; I also hope to explore a SQLite browser version. I aim to generate some performance profiling as a side product.