[Haskell-cafe] Code Review: Sudoku solver

[Chris Kuklewicz]

Jared Updike wrote:
> Chris wrote:
>> You need more than 5 examples.  The truly evil puzzles are rarer than that.  Go
>> get the set of minimal puzzles and see how far your logic takes you.
> 
> Chris elucidated some of my questions before I finished writing my email...
> 
> Claus wrote:
>> (*) actually, that was a bit disappointing!-(
> 
> How much harder is the problem of generating (hard/medium/easy)
> (solvable) Sudoku puzzles? 

I pursued this line of attack as well.  I could not generate the hardest
puzzles, though I was working without studying other's approaches.

> Are all puzzles solvable (that don't break
> the rules at any point)?

All well formed problems have exactly one solution.  It is always solvable by,
at worst, brute force.

> I imagine a simple way is to start with a
> correctly saturated grid of numbers and then start randomly shooting
> holes in it and testing if it is still solvable (either unambiguously
> or ambiguously) with your Sudoku solver?

That method works poorly.

> A rough mesaure of the
> difficulty of the unsolved puzzle could be how long the solver took to
> solve it (number of steps) (and the number of possible solutions)? Are
> puzzles with multiple solutions usually considered harder or easier?
> Are these considered proper puzzles?

Proper puzzle have exactly one solution, accept no substitute.  A problem is
minimal (a partial order) if removing any single hint creates additional
solutions.  So the goal is build a minimal problem with as few hints as possible.

The smallest number of hints achieved to date is 17, but there is no proof that
a 16 hint puzzle is impossible.

> 
> Is this a more interesting problem to try to solve (generating) rather
> than solving puzzles? I haven't investigated it much but I thought
> about it when I was writing YASS (Yet Another Sudoku Solver) of my
> own. What makes a Sudoku puzzle fiendish? Just the amount of missing
> information, the amount of lookahed required?

A measure of difficulty is more subjective.  Different programs will make
luckier guesses on any specific problem.  So I consider "how many blanks are
left when the pure logic program gets stuck" to be my favorite difficulty
metric.  These were the worst from the list of 17's (left to right, top to bottom) :


>  ---------         ---------         ---------         ---------         ---------
> "....6..8..2.........1.......7....1.25...3..........4....42.1...3..7..6.........5."
> "...8...17.6.3....5.......2....6..4..7...2....1.........4...7.....3...8......1...."
> ".9......25..3........6.....3.6...4......81...7.........8..9......2....3.......67."
> "1...2..6.7.5................8.....1....5.3.....47........4..7..2.....5...6..1...."
> "5...8.2..74..................2.5.......6....78......4..6.7.......1...5.....3.4..."


My puzzle generator worked like this: Start with an empty grid and randomly add
allowed hints until the number of solutions falls to 1.  Now try and remove
hints while keeping the number of solutions exactly 1.  The performance of this
was erratic, but occasionally produced puzzles with as few as 20 to 22 hints.
There was a few fairly evil spawn of my generator:
	
.2.|...|58.
6..|9..|..1
3..|.7.|6..
---+---+---
...|.65|...
...|...|1..
...|.32|.97
---+---+---
...|...|.38
.59|...|...
..4|...|2..

.5.|1..|...
6..|7..|...
4.8|.63|...
---+---+---
.1.|...|98.
.6.|...|...
97.|.28|...
---+---+---
...|..5|..1
...|93.|.4.
...|...|2.7

1.6|...|..5
...|.7.|.21
3..|...|.8.
---+---+---
...|8..|1.6
...|.1.|9..
...|..9|.7.
---+---+---
...|4.6|...
..2|..3|...
857|...|...


I like that they have two 3x3 sections which are without any hints.

> 
>   Jared.
> 
> P.S. Another interesting problem could be trying other number
> arrangements besides 9x9, e.g. hexadecimal puzzles... I wrote my
> solver to handle these but I never saw other than 9x9 puzzles to try
> it on (hence the idea of generating puzzles)... Is that because most
> people want puzzles to solve by hand instead of computer?

Yes

> 
> --
> http://www.updike.org/~jared/
> reverse ")-:"
>