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

21–30 of 55 posts

Re: Sudoku Solving

#21

Post by crux_ »

ondrasej wrote: post #16
nazgulnarsil wrote: post #13

Earlier quoted context omitted.

solving without trial and error at all.

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

Re: Sudoku Solving

#22

Post by crux_ »

thret wrote: post #18
crux_ wrote: post #14

Earlier quoted context omitted.

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)

Sudoku are designed so that there is always a correct move that does not require guesswork.

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

#23

Post by pieceofpeace »

crux_ wrote: post #14
nazgulnarsil wrote: post #13

Earlier quoted context omitted.

solving without trial and error at all.

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)

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

#24

Post by crux_ »

pieceofpeace wrote: post #23
crux_ wrote: post #14

Earlier quoted context omitted.

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)

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.

Re: Sudoku Solving

#26

Post by bobfunk »

nazgulnarsil wrote: post #13
crux_ wrote: post #8

Earlier quoted context omitted.

I'm curious... what would be the 'proper' technique?

solving without trial and error at all.

It really depends on why you want to solve them.

In some cases you might want the algorithm that solves them to also give you some kinda hint on how hard it would be for a human to solve it.

The most efficient algorithm I know of to solve these kind of problems is Knuth's Dancing Links X algorithm. It's beautiful and very fun to implement.

I have a simple ruby implementation of it geared to solve sudokus online on github: https://github.com/biilmann/Ruby-DLX-Sudoku-Solver

Re: Sudoku Solving

#27

Post by roryokane »

Norvig tries to test his program against the hardest puzzle he can find, but only tries to find this hard puzzle by generating random ones. The program Sudoku Susser (http://www.madoverlord.com/projects/sudoku.t) actually comes with “the hardest sudoku in the world”, which I think the author of that program has proven somehow, so Norvig should try his program on that.

Sudoku Susser can solve sudoku puzzles not only the brute-force way shown in the article, but also using “human” reasoning, and show you all the steps.

Re: Sudoku Solving

#28

Post by jules »

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!

Re: Sudoku Solving

#30

Post by jules »

ondrasej wrote: post #16
nazgulnarsil wrote: post #13

Earlier quoted context omitted.

solving without trial and error at all.

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.

Post reply on HN