News for hackers. Stuff that matters.
Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @03:43AM (#2371597)
That strikes me as extremely unlikely.

I think the complexity class of Sudoko is NP-Complete (a quick google confirms it's not exactly NP but very close: http://11011110.livejournal.com/23221.html?thread=19381 -- complexity is the same as solving SAT problems which have only one unique solution)

Re:Sudoku Solving by pieceofpeace on Saturday March 26, 2011 @05:32AM (#2371730)
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/

Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @05:49AM (#2371745)
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.

Re:Sudoku Solving by pieceofpeace on Saturday March 26, 2011 @11:18AM (#2372250)
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.
Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @02:53PM (#2372841)
The constraint-finding is for generating puzzles that are easy, hence the comment about puzzle manners.
Re:Sudoku Solving by Natsu on Saturday March 26, 2011 @04:39AM (#2371663)
I usually solve them by hand without guess and check, though occasionally, you get down to where there are pairs of values where you have no choice but to try one and see what works (or maybe I just need to figure out more constraints to use).
Re:Sudoku Solving by thret on Saturday March 26, 2011 @04:46AM (#2371669)
Sudoku are designed so that there is always a correct move that does not require guesswork.
Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @05:12AM (#2371706)
That is not true.

They're typically designed to be unambiguous (only one correct solution), so in that sense there is always a 'correct' move.

However, finding that correct move is exactly as hard, in the computational sense, as finding the solution to the entire puzzle.

> . . . | . . . | . 1 2

> . . . | . . . | . . 3

> . . 2 | 3 . . | 4 . .

> ------+-------+------

> . . 1 | 8 . . | . . 5

> . 6 . | . 7 . | 8 . .

> . . . | . . 9 | . . .

> ------+-------+------

> . . 8 | 5 . . | . . .

> 9 . . | . 4 . | 5 . .

> 4 7 . | . . 6 | . . .

There should only be one solution. Enjoy yourself, and remember: No guessing! (Source: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptio...)

Re:Sudoku Solving by thret on Saturday March 26, 2011 @08:58AM (#2371968)
Well, an ambiguous Sudoku is like a 12 line sonnet...

It isn't computationally relevant but even if trial and error were a simpler approach I feel like that is not in the spirit of the game. Sudoku is a number maze, the goal is to backtrack.

Also I refuse to attempt something that is supposedly too difficult for humans to solve, I'm incapable of quitting puzzles and don't relish spending the next X hours proving it can be done :)

Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @02:49PM (#2372827)
I believe the above puzzle has only one valid solution.
Re:Sudoku Solving by jws on Saturday March 26, 2011 @09:21AM (#2372001)
9x9 grid of digits with an ambiguous solution is not a Sudoku. It is part of the definition.

Within the set of initial grids that have unambiguous solutions there are ones which require guessing or backtracking, these are generally not considered proper Sudokus and are not presented to humans to solve.

A Sudoku is not a destination, it is a journey.

Re:Sudoku Solving by T-hawk on Saturday March 26, 2011 @11:36AM (#2372309)
If a Sudoku has one and only one solution, then it is always solvable without guessing or backtracking. It just might not be within the scope of the human brain. There exist (many) configurations where every cell is influenced by every other, so to solve any one cell essentially requires a simultaneous solve of the entire puzzle. There's no theoretical reason a human couldn't do that too; it's a problem simply of computational capacity not fundamental approach.
Re:Sudoku Solving by crux_ on Saturday March 26, 2011 @02:58PM (#2372862)
How would you structure a program to solve such a puzzle without having it generate and test potential solutions along the way?