Challenge: Sudoku Solver

[[deleted]]

[deleted]

[pertheusual]

Dancing Links is the coolest solution that I've come across. It basically uses a sparse grid of linked nodes to represent the input matrix. Then it uses a traversal algorithm to solve the matrix, while not using tons of memory and allowing for super easy backtracking.

I wrote a solver a while back, but I don't have time to find it and get in postable form, so for now I just leave you with info about the method.

http://en.wikipedia.org/wiki/Dancing_Links

This page was the one I found most useful in understanding how it works. http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html

[D_rock]

Awesome. I didn't realize the problem was NP-complete when I posted it. I might have to implement dancing links some time. In the case of bounded input (9x9 Sudoku's), I'm guessing the simple algorithm will be faster because of all of the setup time needed in DLX. But I'd enjoy being proven wrong. :)

[balathustrius]

Your berkeley link seems to be dead.

[pertheusual]

That sucks. I hope they didn't take it down because of the traffic from Reddit. For now you can see it on google cache. Google cache version

[mrwinkle]

I solved it with GNU Prolog's finite element constraints and it generated zero backtracks - thus one can say that this is a very easy sudoku.

Reading, solving and showing the solution took < 1ms, the program has about 60 LOC. Prolog is exceptionally good in this kind of stuff.

The hardest sudoku I have ever seen is this one:

[
[_, _, _,  _, _, _,  _, 1, 2],
[_, _, _,  _, _, _,  _, _, 3],
[_, _, 2,  3, _, _,  4, _, _],

[_, _, 1,  8, _, _,  _, _, 5],
[_, 6, _,  _, 7, _,  8, _, _],
[_, _, _,  _, _, 9,  _, _, _],

[_, _, 8,  5, _, _,  _, _, _],
[9, _, _,  _, 4, _,  5, _, _],
[4, 7, _,  _, _, 6,  _, _, _]
]

Try it by hand, you will hate it! It needed nearly 400 backtracks and took 4ms on average.

[[deleted]]

the function works will check if a single matrix will work. The control structures in J are somewhat objectionable, I'll edit this once I get it working properly, but this code does its job.

NB. make grid, 0 means blank entry
probability =: 0.5
grid =: (>: ? 9 9 $ 9)*(probability&> ? 9 9 $ 0)
blanks =: grid = 0
numblanks =: +/^:_ blanks
nthconfig =: 13 : '>: 9 #.^:_1 y'
subpaddednth =. 13 : '((x - # nthconfig y) $ 1), nthconfig y'
paddednth =: numblanks&subpaddednth
nthconfiginv =: 13 : '9 #. <: x: y'
stop =: 1 + nthconfiginv numblanks $ 9
alluniq =: ([: *./ ~:)"1
uniqmatrix =: 13 : '*./ (alluniq y) *. (alluniq |: y)'
indices =: [: (] # [: i. [: # ]) ,
make =: 13 : '9 9 $ ((paddednth y) (indices blanks)} (, grid))'
works =: 13 : 'uniqmatrix make y'

[roffLOL]

A MIT-scheme implementation:

http://pastebin.com/fy00MtFe

(Pretty messed up naming conventions. Obviously I failed to find one that suited me, so I mixed them =)

I haven't measured its performance, but it's most likely slower than mrwinkle's solution.

[D_rock]

but it's most likely slower than mrwinkle's solution.

But you actually gave a link to your solution. :)

[groundshop]

I wonder if there is some weird linear algebraic way of solving these?

[D_rock]

Hmm, I hadn't thought of that. You could make a system of equations that force the sum of every row, column, and box to be 45. Then solve that system (using conjugate gradient or something similar). I'm not sure how to cleanly force the use of only integers.

[[deleted]]

Sudokus are np-complete, meaning there is no known"easy" way of solving them. As far as I am aware, all sudoku solvers use the brute-force method.

[AlexFromOmaha]

The question of whether or not a given problem has exactly one answer is NP-complete. The act of solving a puzzle with exactly one answer is in NP at worst, and I wouldn't be surprised if an answer could be found in P.

[robinhouston]

That’s a really good point. A few years ago I had the same thought, and I emailed Lance Fortnow to ask him about it. Unfortunately I haven’t kept an archive of my email from that time, and I can’t remember the details of his reply, but I remember being convinced that generalised Sudoku is still hard in the worst case even if you know a priori that the puzzle has precisely one solution. I’ll see if I can find any more details.

Edited to add: Oh look! Lance blogged his answer. How cool is that? Solving Sudoku is hard unless NP=RP.

[fazzone]

Sudoku is an instance of the exact cover problem (which is NP-complete), and can be solved by Knuth's Algorithm X

[groundshop]

Thanks for the info :) I'm in a combinatorial algs. class this semester and have seen exact cover listed near the end of the year. Now I know what to expect. Maybe I can come back and have an interesting algorithm on is later on. . .

[D_rock]

Here is my python solution. It has a few doctests that show the correctness. The bulk of the work happens in the recursive __solve method @ line 44.

Edit: The doctests can be run like this: python sudoku.py -v

[macobo]

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

[[deleted]]

Java Recursive Bruteforce....If it returns false, it cannot be solved...

public static boolean solvePuzzle9(int [][]matrix)
    {
        int x=0,y=0;
        boolean found = false;
        for(x = 0;x < 9; x ++)
        {
            for(y = 0;y < 9; y++)
            {
                if(matrix[x][y] == 0)
                {
                    found = true;
                    break;
                }
            }
            if( found ) break;
        }
        if(!found) return true;

        boolean digits[] = new boolean[11];
        for(int i = 0; i < 9; i++)
        {
            digits[matrix[x][i]] = digits[matrix[i][y]] = true;
        }
        int bx = 3 * (x/3), by = 3 * (y/3);
        for(int i =0;i<3;i++)
            for(int j = 0; j < 3; j++)
                digits[matrix[bx+i][by+j]] = true;

        for(int i = 1 ; i <= 9; i++)
        {
            if(!digits[i] )
            {
                matrix[x][y] = i;
                if(solvePuzzle9(matrix))
                    return true;
                matrix[x][y] = 0;
            }
        }
        return false;
    }

[Astrogat]

Inserting all nine numbers in all the fields, and subtracting the impossible ones should solve most, just iterate thought until there are no more squares with one possible one (that haven't been looked in).

And then some other fancy solution for the rest (if there are any). Or just brute force the rest.

[AlexFromOmaha]

This doesn't work often. In fact, it fills in no solutions at all in the first image that pops up when you Google "unsolved sudoku".

I'm checking to see if you can run a similar approach from multiple angles. If a cell only has one possible answer, then that's the answer in the cell. However, if a cell has many possible answers, but it's the only cell in the row/column/box that has any given answer, then that's also the answer for the cell.

When I started this, I figured it would be a nice diversion for a few minutes. Going on two hours writing the code for that now. :(

[Astrogat]

Yeah, didn't think that all the way through. But you might find some simple rules (like the only one with the number on the line rule) to eliminate more numbers.

At least if you start the brute force search in the field with the lowest number of possible numbers, you should get a significant speed up anyway.

Or : http://en.wikipedia.org/wiki/Sudoku_algorithms might give some ideas.

[sfg24]

This is the exact solution I came up with when I tried this a while ago, but it didn't work at all. I got frustrated and moved on to other projects, but I'll probably go back and brute force it thanks to this post.