Solving Every Sudoku Puzzle (2006)

80 点作者 srathi将近 10 年前

13 条评论

mdup将近 10 年前

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):<pre><code> 1324 3142 4213 2431 </code></pre> is:<pre><code> 1... .2.. .3.. ...4 .1.. ...2 3... ..4. ..1. + .2.. + ...3 + 4... ...1 2... ..3. .4.. </code></pre> or even:<pre><code> x... .x.. .x.. ...x .x.. ...x x... ..x. ..x. + .x.. + ...x + x... ...x x... ..x. .x.. x... .x.. ..x. ...x <- number row </code></pre> 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] <a href="https://en.wikipedia.org/wiki/Exact_cover" rel="nofollow">https://en.wikipedia.org/wiki/Exact_cover</a>[2] <a href="https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X" rel="nofollow">https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X</a>[3] <a href="https://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow">https://en.wikipedia.org/wiki/Dancing_Links</a>[4] <a href="http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz" rel="nofollow">http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color...</a>

评论 #9901813 未加载

justinator将近 10 年前

Sudoku solver using Perl regex <a href="http://www.perlmonks.org/?node_id=471168" rel="nofollow">http://www.perlmonks.org/?node_id=471168</a>Sudoku solver in three lines of Perl (golf): <a href="https://web.archive.org/web/20070106133158/http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html" rel="nofollow">https://web.archive.org/web/20070106133158/http://www.eccles...</a><pre><code> 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</code></pre>

wickawic将近 10 年前

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: <a href="https://www.youtube.com/watch?v=DmT80OseAGs" rel="nofollow">https://www.youtube.com/watch?v=DmT80OseAGs</a>Test driven sudoku: <a href="http://ronjeffries.com/xprog/articles/sudokumusings/" rel="nofollow">http://ronjeffries.com/xprog/articles/sudokumusings/</a>

评论 #9901422 未加载

评论 #9902540 未加载

asgard1024将近 10 年前

It has been shown in 2012 that you need at least 17 digits to uniquely specify a Sudoku puzzle: <a href="http://www.math.ie/McGuire_V1.pdf" rel="nofollow">http://www.math.ie/McGuire_V1.pdf</a>Their approach was quite close to solving every sudoku puzzle, although they traversed the space by the solutions.

yuchi将近 10 年前

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: <a href="https://bugzilla.mozilla.org/show_bug.cgi?id=380237" rel="nofollow">https://bugzilla.mozilla.org/show_bug.cgi?id=380237</a>

mythz将近 10 年前

FWIW I've got benchmarks and ports of Norvig's sudoku solver in Python/PyPy, Dart, C#, Ruby and CoffeeScript at:<a href="https://github.com/dartist/sudoku_solver" rel="nofollow">https://github.com/dartist/sudoku_solver</a>

mrspeaker将近 10 年前

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

deepaksurti将近 10 年前

I implemented a solver in Common Lisp, quite a while back. The repo:<a href="https://github.com/dmsurti/sudoku" rel="nofollow">https://github.com/dmsurti/sudoku</a> and some details here: <a href="http://www.deepaksurti.com/blog/my-attempt-to-solve-sudoku" rel="nofollow">http://www.deepaksurti.com/blog/my-attempt-to-solve-sudoku</a>.I was learning algorithms then and a sudoku solver was both fun and a good learning exercise.

sadgit将近 10 年前

Good time to pimp my c implementation of Norvig's algorithm:<a href="https://github.com/ssadler/ssadler-various/blob/master/sudoku-hammer/sudoku.c" rel="nofollow">https://github.com/ssadler/ssadler-various/blob/master/sudok...</a>(This code is completely indulgent but very fast!)

discardorama将近 10 年前

If someone is interested in seeing Sudoku solved in other languages, here's a nice page: <a href="http://rosettacode.org/wiki/Sudoku" rel="nofollow">http://rosettacode.org/wiki/Sudoku</a>Not all of the code is efficient, but it's interesting nevertheless.

thret将近 10 年前

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.

评论 #9903300 未加载

vtsrh将近 10 年前

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.

JohnyLy将近 10 年前

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.