Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Glenn Flower has written an (open source) program that solves using constraint propagation only. It does solve some of the hardest Sudoku's.

He discusses the strategies used here: http://www2.research.att.com/~gsf/sudoku/



From the first paragraph of your link:

> The solver uses depth first and/or breadth first with constraint propagation to prune the search

That would be backtracking.

Further, the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them. The article itself states that for solving, backtracking with fewer constraints performs better.


You are right that "the purpose of many the constraint techniques seem to be aimed at creating puzzles that are amenable to humans, not solving them"

I shared the link because I found his sudoku generator and the constraint methods interesting.

> That would be backtracking.

Let me quote the first para in full:

  The solver uses depth first and/or breadth first tree search
  with constraint propagation to prune the search for the next
  best move (forms of forward checking.) There are space/time
  tradeoffs between depth/breadth first search and the constraints
  used; sudoku(1) has options to control the combinations.
  The common characteristic for all constraints, here and elsewhere,
  is that they avoid trial and error. Its fine for a computer
  to guess and backtrack but a definite breach of puzzle manners
  to require a human to do so.
I could be wrong but, yes, it does use backtracking to find the constraint that can give a number for an empty cell but it never has to change a number it has put in a cell. That differs from the trial and error approach that moves forward by guessing values and checking if it leads to a valid solution.


The constraint-finding is for generating puzzles that are easy, hence the comment about puzzle manners.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: