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

31–40 of 55 posts

Re: Sudoku Solving

#31

Post by thret »

crux_ wrote: post #22
thret wrote: post #18

Earlier quoted context omitted.

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

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

#33

Post by jws »

crux_ wrote: post #22
thret wrote: post #18

Earlier quoted context omitted.

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

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

#34

Post by silentbicycle »

roryokane wrote: post #27

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…

I wouldn't call constraint propagation "brute-force". It isn't enumerating every combination of values and backtracking (as either a non-contstraint Prolog program or a C program with up to 81 nested for-loops would). Rather, it's removing every possibility that has already been canceled out (constraint propagation), then saving undo information, making one guess, and seeing if that sets off another chain reaction or reaches a solution.

He acknowledges the possibility of using more "reasoning" in the article, but dismisses it:

"We could try to code more sophisticated strategies. For example, the naked twins strategy looks for two squares in the same unit that both have the same two possible digits. [...] Coding up strategies like this is a possible route, but would require hundreds of lines of code (there are dozens of these strategies), and we'd never be sure if we could solve every puzzle."

If you want to read more about constraint programming, there is an excellent overview chapter in CTM (http://www.info.ucl.ac.be/~pvr/book.html). "The Art of the Propagator" (http://dspace.mit.edu/handle/1721.1/44215) is also good, though it focuses more on arithmetic value propagation than set propagation problems like sudoku. For more advanced material, look at the clp(FD) papers by Danial Diaz (http://cri-dist.univ-paris1.fr/diaz/publications/cv-short.ht...); familiarity with Prolog terminology will be helpful.

Re: Sudoku Solving

#35

Post by ozataman »

Would be interesting to see how this fares performance-wise in comparison:

http://corp.galois.com/blog/2009/3/18/solving-sudoku-using-c...

It's a sudoku solver based on Cryptol, which is "... a language tailored for cryptographic algorithms." built on top of Haskell. The amazing this is that all you need to define is a function that checks whether a given board is solved. Cryptol does the searching for you!

Re: Sudoku Solving

#36

Post by gumbo »

isak2 wrote: post #11

I wrote one in C# a while ago: http://isaksky.wordpress.com/2010/10/30/objected-oriented-so...

I did the same, need to dig into my back up hard drive to find it. Maybe i'm going to expose a REST api for generating sudokus. Do you think this might be interesting?

"Did you know that in order to generate a sudoku you need first to solve it?"

Re: Sudoku Solving

#37

Post by jws »

I find that calculating the sequence of stereo pairs for an MP3 file is much simpler and more accurate if I dispense with the human listener.

For instance, I just rendered "In the Year 2525" 593 times faster than a human can listen to it on a single thread of a core i3.

Re: Sudoku Solving

#38

Post by iki23 »

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.

Re: Sudoku Solving

#39

Post by spacemanaki »

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…

I think you're being a bit unfair to chess, but anyway you can still play Go. I think it's far from "solved" as amateurs beat computer programs very often, as I understand.

Re: Sudoku Solving

#40

Post by xtacy »

If you really want speed, then I would recommend using a good implementation of Dancing Links for solving constraint satisfaction problems. Don Knuth proposes a doubly linked list structure to speed up recursive state space exploration: www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz.
Post reply on HN