[LRUG] Continuations

[Daniel Lucraft]

On Thu, 2007-03-15 at 14:10 +0000, Andrew Stewart wrote:
> 
> In a slightly mischievious way, I was under the impression that true  
> sudokus could always be solved by logic alone and never needed  
> guesswork.

Depends which paper you get them from. I can't remember the details but
I'm sure not all published sudoku even have unique solutions, which
implies that guesswork is necessary at some point. If you are a
'purist', however, you are correct. The Times has 'pure' sudoku, I
believe.

Until last year I was a student in a research centre with just 20 staff
and phd students, all working in a Prolog constraint environment. One
day we were chatting in the kitchen and realized that 7 of us had
*independently* written sudoku solvers.

There were some mammoth discussions on what constituted 'logic' as
opposed to guesswork that day. I'm not sure that any of the solvers were
able to solve all problems without backtracking, but that was the goal
and there was some pretty advanced constraint propagation going on.

The point is that backtracking is OK for *solving* sudoku, but what
about generating them? In order for them to be 'human friendly', they
have to be solvable through logic, or at least only minimal search. And
then you have to order the constraints by how hard they are to apply by
people, and then you can create a difficulty rating by examining which
constraints get activated during propagation.

Have fun implementing that in Ruby.

This has got rather long. I'm not a sudoku obsessive, really.

Dan