Peter Norvig on Solving Every Sudoku Puzzle

http://www.norvig.com/sudoku.html

by panaggio • 15 years ago

55 22 15 years ago

norvig.com

spacemanaki• 15 years ago

Submitted yesterday, and now dead, I would guess because it's been discussed a few times before:

http://news.ycombinator.com/item?id=3092025

http://www.google.com/search?gcx=c&sourceid=chrome&i...

astrodust• 15 years ago

I can't be the only one disappointed that this didn't literally solve all possible puzzles, but rather is a universal solver.

alttag2• 15 years ago

I'm wondering why the grid notation doesn't account for the irregular variation, and why the grid size values are hard coded, so mini and large-size sudoku is out too.

The second is easy to correct in a live (i.e., not pedagogical) version. The first is a bit more difficult.

pankaj_k_net• 15 years ago

Inspired by Peter Norvig's article I once implemented a similar algorithm in JavaScript with a web interface that solves any Sudoku puzzle and made it available at my personal website: http://pankaj-k.net/sudoku/sudoku.html. You can either enter the Sudoku puzzle values in the 9x9 grid or just pick one randomly from the input set linked to by Peter. Clicking on Solve button show the solution.

yourcelf• 15 years ago

I did one too, a few years ago: http://tirl.org/software/sudoku/ I hadn't seen Norvig's article yet then, but I had just taken a course taught out of Russel & Norvig's book -- and I arrived at a similar solution (depth-first search).

Argorak2• 15 years ago

I had to solve Sudoku and similar puzzles at university using Prolog (and fell in love with it in the process). What really saddens me is that every Prolog system ships with a constraint solver (some better, some not), yet many other languages don't have good bindings or libraries for constraint solving.

rndmcnlly02• 15 years ago

You might enjoy answer set programming (ASP). It's a different take on logic programming based on the idea of automatically transforming your problem into a SAT-like representation and then running fancy conflict-driven constraint learning solvers on it. In many solvers, you give up Turing completeness in exchange for being really productive with solving NP-complete problems (similar to regex engines turning you into a bad-ass string matching programmer).

Here's a tutorial application of ASP to map generation: http://eis-blog.ucsc.edu/2011/10/map-generation-speedrun/

Argorak2• 15 years ago

Thank you for the pointer. I wasn't aware of ASP and will definitely spend some time with it.

rndmcnlly02• 15 years ago

Oh, and here's a sudoku solver in 15 source lines with ASP: http://asparagus.cs.uni-potsdam.de/encoding/show/id/3540

Also, a sudoku puzzle generator directly incorporating the unique solution constraint: http://asparagus.cs.uni-potsdam.de/encoding/show/id/12739

abp• 15 years ago

Here is one that has:

https://github.com/clojure/core.logic

Flenser2• 15 years ago

As computer security expert Ben Laurie has stated, Sudoku is "a denial of service attack on human intellect". Several people I know (including my wife) were infected by the virus, and I thought maybe this would demonstrate that they didn't need to spend any more time on Sudoku. It didn't work for my friends (although my wife has since independently kicked the habit without my help), but at least one stranger wrote and said this page worked for him, so I've made the world more productive.

This has probably worked on me too. Watching a computer play tetris had the same effect on me for that game.

epo2• 15 years ago

What a [deleted] comment by Laurie.

Does he really imagine people solve Sudoku puzzles just to get the answer and because they are too stupid to look at the solved answer?

Do we have any other insights from these people [edited]? Perhaps why go for a walk when you did the same walk last week? Or why eat food when you're only going to go to the toilet?

And people wonder why geeks don't have friends.

EDIT for tone.

imurray• 15 years ago

http://ycombinator.com/newsguidelines.html

Please: "Be civil.... When disagreeing, please reply to the argument instead of calling names."

There is something in Laurie's comment. You could have focussed on why people enjoy Sudoku anyway without being rude and sarcastic.

esrauch2• 15 years ago

Except that this isn't just showing that there is an alternate way to find an answer, it's showing that a pretty braindead algorithm can solve it. Comparing the difficulty in solving sudoku to something even as simple as Checkers (which took years of research and supercomputer time to solve) will show just how braindead and simple it is.

I've never understood why people do Sudoku puzzles, you seem to know though. It actually seems like one of the least interesting hobbies someone can have; meaningless, rote and without any possibility of cleverness or intelligence or self improvement or improving your health or literally any other dimension that I can think of a hobby being evaluated on.

Walks at least provide fresh air, a change in environment, and a great opportunity to reflect. What exactly is the attraction of sudoku? How is it different than doing long division for fun?

dwhitney• 15 years ago

I had to write a sudoku solver in a job interview on a white board. I felt and still feel that it was a bit non-trivial for a job interview question, but nonetheless I arrived at the same answer Peter Norvig did.

maurycy2• 15 years ago

I wonder, what if I don't know Sudoku rules at all?

darklajid• 15 years ago

Not being sarcastic: The interviewer would explain it to you in 2 minutes (like the article does, including very common strategies), offer you a simple one to sovle and maybe grant you a little more time to come up with an algorithm.

If you don't understand sudoku rules afterwards or cannot implement something according to a set of rules and without previous exposure, than this might be a result the interviewer is interested in as well?

alttag2• 15 years ago

> A2 has 4 possibilities (1679) and A3 has 5 possibilities (12679); together that's 20, and if we keep multiplying, we get 4.62838344192 × 1038 possibilities for the whole puzzle

I realize this is the start of his search section, and he uses it as a springboard to present constrained search, but this struck me as either incorrect or an intentional straw man.

Applying even the simplest constraint (that a value cannot appear more than once in a cell) means that standard combinatorial formulas don't product accurate counts: by selecting a value, each peer has at least one cell that decrements its count of possible values (otherwise the value would have been detected by the naive algorithm). Applying constraints is the subtext of his eventual point, but I'm not seeing the value in presenting the flawed math the way he did.

The math on this really bugged me (my mind went directly to his eventual solution), and I had to go back and read the introduction to the "Search" section a couple of times to even wrap my head around what he was proposing for the "brute force" solution. Maybe its because I arrived at a solution similar to his eventual one years ago when I tackled a sudoku solver.

The other line that bothered me was: "The second choice is to somehow process much more than one possibility per machine instruction." After reading through, I understand what he means, but it's not equivalent to what he said.

esrauch2• 15 years ago

I don't think it's a disingenuous idea; the a naive search solution is to fill in all of the boxes and then check if its a valid board. In fact, that is the only possible way you could do it if your evaluation function returned either "solved" or "not".

Peter Norvig on Solving Every Sudoku Puzzle

Related Stories