Solving Every Sudoku Puzzle (2006) | Hacker News Reader

Solving Every Sudoku Puzzle (2006)

norvig.com

80 pointssrathi27 comments

Another way to solve Sudoku is to understand that it is an instance of the Exact Cover problem [1]. Basically, solving a 3x3 Sudoku grid is nothing more than finding 9 "sheets" of each number which superimpose exactly on top of the grid.

For example (2x2 sudoku = 4 sheets):

is:

    1...   .2..   .3..   ...4
    .1..   ...2   3...   ..4.
    ..1. + .2.. + ...3 + 4...
    ...1   2...   ..3.   .4..

or even:

    x...   .x..   .x..   ...x
    .x..   ...x   x...   ..x.
    ..x. + .x.. + ...x + x...
    ...x   x...   ..x.   .x..
    x...   .x..   ..x.   ...x <- number row

where the last "number row" does not belong to the grid but serves to indicate the number of the sheet.

This explains how sudoku relates to the Exact Cover problem. Now, there is a good algorithm by Knuth to solve Exact Cover, which is known as Algorithm X [2].

Algorithm X is just an algorithm but Knuth has also invented a very efficient implementation of it, called Dancing Links or DLX for short [3]. DLX is described in a very good and very readable paper by Knuth himself [4]. This is one of the first serious papers I ever read and it was a real joy, mind-opener.

[1] https://en.wikipedia.org/wiki/Exact_cover

[2] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

[3] https://en.wikipedia.org/wiki/Dancing_Links

[4] http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...

There is a very succinct implementation of Algorithm X in Python that uses a variation of the Dancing Links approach.

http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt

Sudoku solver using Perl regex http://www.perlmonks.org/?node_id=471168

Sudoku solver in three lines of Perl (golf): https://web.archive.org/web/20070106133158/http://www.eccles...

      use integer;@A=split//,<>;sub R{for$i(0..80){next if$A[$i];my%t=map{$_/9
    ==$i/9||$_%9==$i%9||$_/27==$i/27&&$_%9/3==$i%9/3?$A[$_]:0=>1}0..80;R($A[
    $i]=$_)for grep{!$t{$_}}1..9;return$A[$i]=0}die@A}R

I've noticed that solving a sudoku is something of a rosetta stone for how people program. Norvig's solution is very straightforward in hindsight, but I think that code was either the result of many iterations or of a career of making progressively more readable code.

Here are some other sudoku solvers that give more insight into the coder than the problem:

Sudoku in APL: https://www.youtube.com/watch?v=DmT80OseAGs

Test driven sudoku: http://ronjeffries.com/xprog/articles/sudokumusings/

This article was my crash course for computer science (I come from another engineering field). I learned so much by studying this code, and understanding it allowed me to write a sudoku generator. The generator algorithm is much different than solving, but the basic structure was already there for me.

In any case, I'm replying to your comment because it applies to me. Norvig's code is compact and elegant, whereas mine is spaghetti code at best. I basically have lots of control statements, as there are many many processing steps that I painstakingly discovered as I went along (thousands of lines). Heck, I can barely remember them myself.

Here's my site: http://sudokuisland.com

A lot was discussed about Norvig's elegant solution compared to Ron Jeffries effort and what it said about TDD: http://ravimohan.blogspot.co.uk/2007/04/learning-from-sudoku...

To be fair, the reason Norvig was so successful was he knew exactly the sort of problem soduku was and how to solve it, whereas Ron lacked this background knowledge.

I think you're missing the point. TDD forces you to choose data representations that best fit your tests. But in most cases of complex programming you want to choose representations that reflect your current understanding of the problem and then evolve them as your understanding evolves.

In TDD your test will always predate your understanding. So it forces you to solve (part of) the problem in your head first, rather than combine the act of problem-solving and writing. And you do this over and over again. And when you change your mind about something, you have twice the code to refactor.

It's a difference between recording your thinking in code and actually thinking in code.

This reminds me of an old article that exemplifies this: http://insideofthebox.tumblr.com/post/52002125683/prime-fact...

Prime factor kata is often used as an introductory example of TDD, yet it is clearly impractical and produces garbage code. Not to mention that I've actually seen people do it, stumble, and hectically reach for their notes to see what's the next step. And it's a pretty darn simple problem.

Err, I'm missing the point of my own point? You raise an interesting point, but I don't think TDD was what stumped Ron. It's not a simple problem to solve without a lot of thought unless you have the requisite background knowledge like constraint problems. TDD did however have him going round in circles, partly for the reasons you describe.

The odd thing is that, on the evidence of those blog posts, Jeffries, doesn't appear to understand TDD. If you're using TDD to write a sudoku solver, surely the first thing you should write is a test for your "solve_sudoku" function; then your design is supposed to evolve out of the code you write to pass that test (and the further tests you write for parts of that solution, iteratively). But Jeffries starts writing a bunch of tests for a the low-level details of the representation of a sudoku board. There isn't really any "design" in those posts at all; just a guess at something you might use in a solution to the problem.

It has been shown in 2012 that you need at least 17 digits to uniquely specify a Sudoku puzzle: http://www.math.ie/McGuire_V1.pdf

Their approach was quite close to solving every sudoku puzzle, although they traversed the space by the solutions.

Small discovery: Brendan Eich implemented generators because he found them incredibly important to translate this code in JS.

In fact in the ‘Translations’ section at the end there’s a link to this Bugzilla ticket: https://bugzilla.mozilla.org/show_bug.cgi?id=380237

FWIW I've got benchmarks and ports of Norvig's sudoku solver in Python/PyPy, Dart, C#, Ruby and CoffeeScript at:

https://github.com/dartist/sudoku_solver

I love that this code is so elegant, but (and!) chooses strings and string manipulation for storage of the possible cell values.

It seems like he started with lists and switched when he got to the search method ("This is why I chose to implement the set of possible values for a square as a string: I can copy values with values.copy() which is simple and efficient.") - It's probably not an amazing insight, but I'm sure my brain would have been yelling at me "don't use strings! don't use strings!".

I implemented a solver in Common Lisp, quite a while back. The repo:https://github.com/dmsurti/sudoku and some details here: http://www.deepaksurti.com/blog/my-attempt-to-solve-sudoku.

I was learning algorithms then and a sudoku solver was both fun and a good learning exercise.

Good time to pimp my c implementation of Norvig's algorithm:

https://github.com/ssadler/ssadler-various/blob/master/sudok...

(This code is completely indulgent but very fast!)

If someone is interested in seeing Sudoku solved in other languages, here's a nice page: http://rosettacode.org/wiki/Sudoku

Not all of the code is efficient, but it's interesting nevertheless.

I feel like the 'search' function is missing the point. The sudoku puzzles are generated in such a way that there is always a next move to be deduced: there is never any need to guess. If you have to guess, then you have missed something.

Depending on what you mean here, you are misrepresenting the problem. You may not have to guess for what is a valid move that can be done on the board as it is. But you do have to guess for a valid move that will lead you to a completed board. Hence, you search among the possible moves for the one(s) that will lead to a completed board state.

I find it rather disappointing that it still takes on the order of 10^2 milliseconds to solve the hardest sudokus.

This was tested with my own algorithm and one supposedly fast found online. I will revise my code, but I doubt I will improve the speed.

This is good to know that we can win Sudoku with a computer program but not surprising. The goal of Sudoku is to make your intellect work and find logic by yourself. The article should be named: How to win every Sudoku puzzle by cheating.

Intellect's only an illusion. In this case just human interpreter of constraint propagation.

My father, approaching 70, does Sudoku with his breakfast every morning to keep his mind sharp. I think it would be at least equally beneficial for him to learn Python and write a Sudoku solver in it, and since he knows nothing of programming I imagine this would keep him busy for quite some mornings.

You might want to tell him that the better he gets at solving sudoku, the less useful it will be for keeping his mind sharp. The cognitive science research seems to show that you only benefit from the challenge, so doing something that mentally challenges other people and used to challenge you won't benefit you if you have gotten good enough at it that it has become fairly easy--for you.

Instead, as you suggest, staving off cognitive decline might be better accomplished by learning some Python, learning a new language well enough to do some traveling or reading with it, learning to play a new musical instrument, learning some simple juggling, or whatever is both safe and more cognitively taxing than polishing an existing skill by repetition.

You're being short sighted: I find the endeavor of writing a program to solve sudoku much more intellectually interesting and challenging than solving each grid manually.

I never said that writing a program wasn't intellectual. I said that by using a program to solve your Sudoku problem, you would not think anymore. It's like if I win at Chess but I actually don't play, I just ask a program to show me my next moves. The person who created the program used its intellect but not the ones using the program.

I never solved a single Sudoku. I never will. Instead, I wrote a Sudoku solver.

What's better for the brain, solving Sudokus, or writing a Sudoku solver?

>What's better for the brain, solving Sudokus, or writing a Sudoku solver?

Both can be good. Chances are that your first Sudoku solver uses some bruteforce approach, while your manual solution certainly does not. Then the intuitions that you get from many manual games can drive the design of your solver. Of course you can implement some established algorithm but I don't see that challenging.

I have mathematician friend who won't ever play Nine Men's Morris because it's a solved game, so it's not longer interesting for him. It's a shame, you can learn a lot even playing Nim variants if you don't already know the winning strategy, it's a good learning material for kids too.

Reply on news.ycombinator.com