Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Solving Every Sudoku Puzzle (2006)

norvig.com

Post reply on HN
Print view View original

1–10 of 28 posts

Re: Solving Every Sudoku Puzzle (2006)

#2

Post by JohnyLy »

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.

Re: Solving Every Sudoku Puzzle (2006)

#3

Post by hackerway »

JohnyLy wrote: post #2

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.

Re: Solving Every Sudoku Puzzle (2006)

#4

Post by justinator »

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

Re: Solving Every Sudoku Puzzle (2006)

#5

Post by bshimmin »

JohnyLy wrote: post #2

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.

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.

Re: Solving Every Sudoku Puzzle (2006)

#6

Post by incepted »

JohnyLy wrote: post #2

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.

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.

Re: Solving Every Sudoku Puzzle (2006)

#7

Post by wickawic »

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/

Re: Solving Every Sudoku Puzzle (2006)

#8

Post by mdup »

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):

    1324
    3142 
    4213
    2431
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
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...

Re: Solving Every Sudoku Puzzle (2006)

#10

Post by nicholas73 »

wickawic wrote: post #7

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

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

Post reply on HN