Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Implement the shortest Sudoku solver using guessing. Since I have received a few request I have added this as an alternative question for those wishing to implement a brute force sudoku solver.

Sudoku Puzzle:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A|   3   |     1 |
B|     6 |       |   5
C| 5     |       | 9 8 3
-+-----------------------
D|   8   |     6 | 3   2
E|       |   5   |
F| 9   3 | 8     |   6
-+-----------------------
G| 7 1 4 |       |     9
H|   2   |       | 8
I|       | 4     |   3

Answer:

 | 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7

Rules:

  1. Assume all mazes are solvable by logic only.
  2. All input will be 81 characters long. Missing characters will be 0.
  3. Output the solution as a single string.
  4. The "grid" may be stored internally however you wish.
  5. The solution must using a brute force guessing solution.
  6. Solutions should solve within a reasonable time limit.

Example I/O:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
share|improve this question
    
How can the input be 27 characters long? It needs to be 81 characters long - 9 rows x 9 columns. That's what your example does too. Also, I assume that "missing characters will be 0" means that if the number of characters is less than 81, then the zeroes go on the end? –  Jonathan M Davis Feb 3 '11 at 5:15
    
Oh, wait. I get the missing characters will be 0 bit. Duh. Those are the ones that need to be guessed. In any case, the number of characters does need to be 81, not 27. –  Jonathan M Davis Feb 3 '11 at 5:22
add comment

9 Answers

k (72 bytes)

Credit for this goes to Arthur Whitney, creator of the k language.

p,:3/:_(p:9\:!81)%3
s:{*(,x)(,/{@[x;y;:;]'&21=x[&|/p[;y]=p]?!10}')/&~x}
share|improve this answer
    
classic! I was going to post this too! –  nightTrevors Feb 13 at 13:41
add comment

Python, 197 characters

def S(s):
 i=s.find('0')
 if i<0:print s;return
 for v in'123456789':
  if sum(v==s[j]and(i/9==j/9or i%9==j%9or(i%9/3==j%9/3and i/27==j/27))for j in range(81))==0:S(s[:i]+v+s[i+1:])
S(raw_input())
share|improve this answer
add comment

Answer in D:

import std.algorithm;
import std.conv;
import std.ascii;
import std.exception;
import std.stdio;

void main(string[] args)
{
    enforce(args.length == 2, new Exception("Missing argument."));
    enforce(args[1].length == 81, new Exception("Invalid argument."));
    enforce(!canFind!((a){return !isDigit(to!dchar(a));})
                     (args[1]),
                      new Exception("Entire argument must be digits."));

    auto sudoku = new Sudoku(args[1]);
    sudoku.fillIn();

    writeln(sudoku);
}

class Sudoku
{
public:

    this(string str) nothrow
    {
        normal = new int[][](9, 9);

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                normal[i][j] = to!int(str[k++]) - '0';
        }

        reversed = new int*[][](9, 9);

        for(size_t i = 0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                reversed[j][i] = &normal[i][j];
        }

        boxes = new int*[][](9, 9);
        indexedBoxes = new int*[][][](9, 9);

        for(size_t boxRow = 0, boxNum = 0; boxRow < 3; ++boxRow)
        {
            for(size_t boxCol = 0; boxCol < 3; ++boxCol, ++boxNum)
            {
                for(size_t i = 3 * boxRow, square = 0; i < 3 * (boxRow + 1); ++i)
                {
                    for(size_t j = 3 * boxCol; j < 3 * (boxCol + 1); ++j)
                    {
                        boxes[boxNum][square++] = &normal[i][j];
                        indexedBoxes[i][j] = boxes[boxNum];
                    }
                }
            }
        }
    }

    void fillIn()
    {
        fillIn(0, 0);
    }

    @property bool valid()
    {
        assert(full);

        for(size_t i = 0; i < 9; ++i)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(!canFind(normal[i], n) ||
                   !canFind!"*a == b"(reversed[i], n) ||
                   !canFind!"*a == b"(boxes[i], n))
                {
                    return false;
                }
            }
        }

        return true;
    }

    override string toString() const
    {
        char[81] retval;

        for(size_t i = 0, k =0; i < 9; ++i)
        {
            for(size_t j = 0; j < 9; ++j)
                retval[k++] = to!char(normal[i][j] + '0');
        }

        return to!string(retval);
    }

private:

    @property bool full()
    {
        for(size_t i = 0; i < 9; ++i)
        {
            if(canFind(normal[i], 0))
                return false;
        }

        return true;
    }

    bool fillIn(size_t row, size_t col)
    {
        if(row == 9)
            return valid;

        size_t nextRow = row;
        size_t nextCol = col + 1;

        if(nextCol == 9)
        {
            nextRow = row + 1;
            nextCol = 0;
        }

        if(normal[row][col] == 0)
        {
            for(int n = 1; n < 10; ++n)
            {
                if(canFind(normal[row], n) ||
                   canFind!"*a == b"(reversed[col], n) ||
                   canFind!"*a == b"(indexedBoxes[row][col], n))
                {
                    continue;
                }

                normal[row][col] = n;

                if(fillIn(nextRow, nextCol))
                    return true;
            }

            normal[row][col] = 0;

            return false;
        }
        else
            return fillIn(nextRow, nextCol);
    }

    int[][] normal;
    int*[][] reversed;
    int*[][] boxes;
    int*[][][] indexedBoxes;
}

With the sample input, it takes .033s on my Phenom II X6 1090T when compiled with dmd -w (i.e. without optimizations), and it takes .011s when compiled with dmd -w -O -inline -release (i.e. with optimizations).

share|improve this answer
add comment

Try this: in C++

The main loop is here:

    void Puzzle::doBrute(int start)
    {
        for(; start < 81; ++start)
        {
            if (puzzle[start] == '0')
            {   break;
            }
        }

        if (start == 81)
        {
            std::cout << puzzle << "\n";
            throw int(0);
        }
        else
        {
            int x   = start % 9;
            int y   = start / 9;

            for(int t = 1; t <= 9; ++t)
            {
                if (use(x, y, t))
                {
                    puzzle[start] = '0' + t;
                    doBrute(start+1);
                    unuse(x,y,t);
                }
            }
            puzzle[start] = '0';
        }
    }

The rest of the support code is:

#include <vector>
#include <string>
#include <iostream>
#include <stdlib.h>

class ValidTest
{
    std::vector<int>    set;
    public:
        ValidTest() : set(10, 0) {}
        void   use(int val)  { set[val] = 1;}
        void unuse(int val)  { set[val] = 0;}
        bool    ok(int val)  { return (set[val] == 0);}
};

class Puzzle
{
    ValidTest   row[9];
    ValidTest   col[9];
    ValidTest   box[9];
    std::string puzzle;

    public:

    Puzzle(std::string const& data)
        : puzzle(data)
    {
        if (puzzle.size() != 81)
        {
            std::cout << "Puzzle failed\n";
            exit(1);
        }

        for(int loop =0;loop < 81;++loop)
        {
            int v   = puzzle[loop] - '0';
            if (v == 0)
            {   continue;
            }

            int x   = (loop % 9) ;
            int y   = (loop / 9) ;

            if (!use(x, y, v))
            {
                std::cout << "Bad Input\n";
                exit(1);
            }
        }
    }
    void brute()
    {
        try
        {
            doBrute(0);
            std::cout << "No Solution\n";
        }
        catch(...)
        {
            std::cout << "Solved\n";
        }
    }
    private:

    bool use(int x, int y, int v)
    {
        int  b = (x / 3) + (y/3*3);

        bool result = row[y].ok(v) && col[x].ok(v) && box[b].ok(v);
        if (result)
        {
            row[y].use(v);
            col[x].use(v);
            box[b].use(v);
        }
        return result;
    }
    void unuse(int x,int y, int v)
    {
        int  b = (x / 3) + (y/3*3);

        row[y].unuse(v);
        col[x].unuse(v);
        box[b].unuse(v);
    }
    void doBrute(int start);
};

int main(int argc, char* argv[])
{
    Puzzle  puzzle(argv[1]);

    puzzle.brute();
}
share|improve this answer
add comment

Python, 188 bytes

This is a further shortened version of my winning submission for CodeSprint Sudoku, modified for command line input instead of stdin (as per the OP):

def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
import sys
f(sys.argv[1])

If you're using Python 2, '%d'%5**18 can be replaced with `5**18` to save 3 bytes.

To make it run faster, you can replace '%d'%5**18 with any permutation of '123456789' at a cost of 1 byte.

If you want it to accept the input on stdin instead, you can replace import sys;f(sys.argv[1]) with f(raw_input()), bringing it down to 177 bytes.

def f(s):
 x=s.find('0')
 if x<0:print s;exit()
 [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18]
f(raw_input())

EDIT: Here's a link to a more detailed walkthrough.

share|improve this answer
    
Very nice solution. –  primo Dec 15 '12 at 15:49
add comment

J, 103

'p n'=:(;#)I.0=a=:("."0)Y
((a p}~3 :'>:?n#9')^:([:(27~:[:+/[:(9=#@~.)"1[:,/(2 2$3),;.3],|:,])9 9$])^:_)a

expected run time: O(gazillion billion years)

share|improve this answer
    
And why is the expected run time "O(gazillion billion years)"? (shouldn't that be just "gazillion billion years" without the O? –  Quincunx Feb 13 at 5:21
    
When I saw this question I immediatly knew that J is going to crush this one. There has to be a way to make this shorter than K. –  koko Feb 13 at 10:18
    
@Quincunx, strictly speaking, it's a wrong use of big-O; the "joke" was supposed to read "constant run time, asymptotically gazillion billion years". –  Eelvex Feb 13 at 14:51
    
@koko, I couldn't find something better but I'm still working on it. –  Eelvex Feb 13 at 14:52
add comment

Perl, 235 chars

$_=$s=<>;$r=join$/,map{$n=$_;'.*(?!'.(join'|',map+($_%9==$n%9||int($_/9)==int($n/9)||int($_/27)==int($n/27)&&int($_/3%3)==int($n/3%3)and$_<$n?'\\'.($_+1):$_>$n&&substr$s,$_,1)||X,@a).')(.).*'}@a=0..80;s!.!($&||123456789).$/!eg;say/^$r/

This is a golfed version of something I posted many years ago to the Fun With Perl mailing list: a sudoku-solving regexp.

Basically, it mangles the input into 81 lines, each containing all the numbers that could occur in the corresponding square. It then constructs a regexp to match one number from each line, using backreferences and negative lookahead assertions to reject solutions that violate the row, column or region constraints. Then it matches the string against the regexp, letting Perl's regexp engine do the hard work of trial and backtracking.

Astonishingly, it's possible to create a single regexp that works for any input, like my original program does. Unfortunately, it's quite slow, so I based the golfed code here on the hardcoded-givens version (found later in the FWP thread), which tweaks the regexp to reject early any solutions that it knows will later violate a constraint. This makes it reasonably fast for easy to moderate level sudokus, although particularly hard ones can still take a rather long time to solve.

Run the code with perl -M5.010 to enable the Perl 5.10+ say feature. The input should be given on standard input, and the solution will be printed to standard output; example:

$ perl -M5.010 golf/sudoku.pl
030001000006000050500000983080006302000050000903800060714000009020000800000400030
832591674496387251571264983185746392267953418943812765714638529329175846658429137
share|improve this answer
add comment

1-liner coffee-script

solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0

Here is the bigger version with sample usage:

solve = (sudoku, cell = 0) ->
  if cell is 9*9 then return sudoku

  x = cell%9
  y = (cell - x)/9

  if sudoku[x][y] isnt 0 then return solve sudoku, cell+1

  row = (i) -> sudoku[x][i]
  col = (i) -> sudoku[i][y]
  box = (i) -> sudoku[x - x%3 + (i - i%3)/3][y - y%3 + i%3]

  good = (guess) -> [0...9].every (i) -> guess not in [row(i), col(i), box(i)]

  guesses = [1..9].filter good

  solves = (guess) -> sudoku[x][y] = guess; solve sudoku, cell+1

  (guesses.some solves) or sudoku[x][y] = 0

sudoku = [
  [1,0,0,0,0,7,0,9,0],
  [0,3,0,0,2,0,0,0,8],
  [0,0,9,6,0,0,5,0,0],
  [0,0,5,3,0,0,9,0,0],
  [0,1,0,0,8,0,0,0,2],
  [6,0,0,0,0,4,0,0,0],
  [3,0,0,0,0,0,0,1,0],
  [0,4,0,0,0,0,0,0,7],
  [0,0,7,0,0,0,3,0,0]
]
console.log if solve sudoku then sudoku else 'could not solve'
share|improve this answer
    
Could be shortened by shortening solve, removing lots of whitespace (I know it's significant, but in many places it could be removed), using symbols instead of words (like != instead of isnt), using indentation instead of then keyword, replacing [0...9] with [0..8]. –  xfix Jan 4 '13 at 11:56
add comment

D (322 chars)

For each unsolved square it builds an array of available options and then loops over it.

import std.algorithm,std.range,std.stdio;void main(char[][]args){T s(T)(T p){foreach(i,ref c;p)if(c<49){foreach(o;"123456789".setDifference(chain(p[i/9*9..i/9*9+9],p[i%9..$].stride(9),p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner).array.sort)){c=o&63;if(s(p))return p;}c=48;return[];}return p;}s(args[1]).write;}

with whitespace:

import std.algorithm, std.range, std.stdio;

void main(char[][] args) {
    T s(T)(T p) {
        foreach (i, ref c; p) if (c < 49) {
            foreach (o; "123456789".setDifference(chain(
                    p[i/9*9..i/9*9+9],
                    p[i%9..$].stride(9),
                    p[i/27*27+i%9/3*3..$][0..21].chunks(3).stride(3).joiner
                ).array.sort))
            {
                c = o&63;
                if (s(p)) return p;
            }
            c=48;
            return [];
        }
        return p;
    }
    s(args[1]).write;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.