Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Sudoku Solving

norvig.com

Post reply on HN
Print view View original

41–50 of 55 posts

Re: Sudoku Solving

#41

Post by pieceofpeace »

crux_ wrote: post #24
pieceofpeace wrote: post #23

Earlier quoted context omitted.

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.

Re: Sudoku Solving

#42

Post by T-hawk »

jws wrote: post #33
crux_ wrote: post #22

Earlier quoted context omitted.

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 . . > .…

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.

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

#43

Post by adrianN »

iki23 wrote: post #38
mberning wrote: post #6

I remember doing something very similar in college. My first cut used a hideous object model, but my second go at it used a 3 dimensional matrix to track all of the data and was much faster and space efficient. The "Why?" at the end of the article pretty much sums up why I can't play most board games and puzzles. Once you 'solve' sudoku, chess, connect 6, ect. it really takes the fun out of it, even if your brain doe…

Doesn't apply to chess imho. I still keep discovering different views of the game on occasional plays. The standard algorithm takes too much time, so you have to find out how to see what's important.

I played chess for a while in a chess club. But to become any good you need to memorize a lot of positions to be able to efficiently recognize good moves. Playing creatively to have fun almost always leads to defeat.

Re: Sudoku Solving

#44

Post by adrianN »

jules wrote: post #28
muhuk wrote: post #5

Why did I do this? As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". My wife was infected by the virus, and I wanted to convince her that the problem had been solved and didn't need any more of her time. Very true.

Now lets go back to watching TV!

Nah, that's a solved problem. I let my VCR watch TV for me. Now if I had an electric monk, I could stop believing in things.

Re: Sudoku Solving

#46

Post by ondrasej »

crux_ wrote: post #21
ondrasej wrote: post #16

Earlier quoted context omitted.

If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones). I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).

That would be a big database. (10^21 entries,roughly.) http://en.wikipedia.org/wiki/Mathematics_of_Sudoku#Enumerati...

That's why I called it pathologic... ;)

Edit: using the symmetries described in the same Wikipedia article, the size of the database could be reduced significantly to roughly 5*10^9, which is quite manageable.

Re: Sudoku Solving

#47

Post by ondrasej »

jules wrote: post #30
ondrasej wrote: post #16

Earlier quoted context omitted.

If you do the constraint propagation right, the number of trials and errors will be very small (and it will be only one trial and no errors for the easy ones). I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. (apart from pathologic solutions like querying a database of all valid 9x9 sudoku combinations).

> I'd be very interested to see what an algorithm that solves any valid sudoku puzzle looks like. You might be interested in the article linked to by this post.

The code in the post is based on depth-first search, which basically is a trial and error approach. A well implemented and effective one thanks to constraint propagation, but it is still trial and error. And there are cases, in which backtracking (trial and error) is necessary - at least one of them is documented in the post (the puzzle "hard1" that took 188 seconds).

Re: Sudoku Solving

#48

Post by crux_ »

thret wrote: post #31
crux_ wrote: post #22

Earlier quoted context omitted.

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 . . > .…

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 c…

I believe the above puzzle has only one valid solution.

Re: Sudoku Solving

#49

Post by crux_ »

pieceofpeace wrote: post #41
crux_ wrote: post #24

Earlier quoted context omitted.

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…

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

Re: Sudoku Solving

#50

Post by crux_ »

T-hawk wrote: post #42
jws wrote: post #33

Earlier quoted context omitted.

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.

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 com…

How would you structure a program to solve such a puzzle without having it generate and test potential solutions along the way?
Post reply on HN