7 ms·

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 s

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/ http://www2.research.att.com/~gsf/sudoku/

crux_ 15y ago
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.
- pieceofpeace 15y ago
  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.
  - crux_ 15y ago
    The constraint-finding is for generating puzzles that are easy, hence the comment about puzzle manners.

crux_ 15y ago

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.

pieceofpeace 15y ago
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.
- crux_ 15y ago
  The constraint-finding is for generating puzzles that are easy, hence the comment about puzzle manners.