Sudoku Solver using Depth-first search and Backtracking.

Makefile

CC     = clang 
#CC    = gcc 
CFLAGS  = -g -O4 -std=c99
CFLAGS += -Wall -Wextra -Wconversion -Wstrict-overflow=5 -Wno-div-by-zero
CFLAGS += -Wpointer-arith -Wtype-limits -Wsign-compare 

all: sudoku

sudoku.c

/* 
 * Copyright (c) 2012, Mason Larobina <[email protected]>
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met: 
 * 
 * 1. Redistributions of source code must retain the above copyright notice, 
 *    this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdio.h>
#include <err.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>
#include <inttypes.h>

#define FULL (1022) /* 1<<1 | 1<<2 | 1<<3 ... 1<<9 */

typedef uint8_t u8;
typedef uint16_t u16;

typedef struct { 
    u8 x, y;
} point;

typedef struct sudoku {
    u8 grid[9][9],
        unsolved;
    u16 row[9],    /* row constraints */
        col[9],    /* column constraints */
        sec[3][3]; /* sub-grid constraints */
    point blank[81];
} sudoku;

static void dump(sudoku *s) {
    for (u8 y = 0; y < 9; y++) {
        u8 *p = s->grid[y];
        if (y % 3 == 0) putchar('\n');
        printf("  %d %d %d  %d %d %d  %d %d %d\n",
            p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7], p[8]);
    }
}


static void fill_square(sudoku *s, point *p, u8 digit) { 
    s->grid[p->y][p->x] = digit;
    s->unsolved--;
    u16 mask = (u16)(1u << digit);
    s->row[p->y] |= mask;
    s->col[p->x] |= mask;
    s->sec[p->y/3][p->x/3] |= mask;
}

static void unfill_square(sudoku *s, point *p, u8 digit) { 
    s->grid[p->y][p->x] = 0;
    s->unsolved++;
    u16 mask = (u16)(1u << digit);
    s->row[p->y] ^= mask;
    s->col[p->x] ^= mask;
    s->sec[p->y/3][p->x/3] ^= mask;
}

static int most_constrained_point(sudoku *s, point *ret) { 
    u8 min = 10, midx, count = 0;
    point *p = s->blank;
    for (u8 i = 0; i < s->unsolved; i++, p++) { 

        u16 mask = (s->row[p->y] | s->col[p->x] | 
                s->sec[p->y/3][p->x/3]) ^ FULL;

        if (!mask) 
            return 0; /* unsolvable grid */

        else if ((count = (u8)__builtin_popcount(mask)) < min) { 
            min = count;
            midx = i;
            if (count == 1) 
                break;
        }
    }

    if (min == 10) 
        return 0;

    memcpy(ret, &s->blank[midx], sizeof(point)); /* copy point */

    /* fill in hole from end of the array */
    if (s->unsolved > 1) /* prevent memory overlap */
        memcpy(&s->blank[midx], &s->blank[s->unsolved-1], sizeof(point)); 

    return 1;
}

static int solve_sudoku(sudoku *s) { 
    point p; 
    if (!most_constrained_point(s, &p))
        return 0;

    u16 mask = (s->row[p.y] | s->col[p.x] | s->sec[p.y/3][p.x/3]) ^ FULL;

    for (u8 i = 1; i < 10; i++) { 
        if ((mask & (1U<<i)) == 0)
            continue;

        fill_square(s, &p, i); 

        if (s->unsolved == 0 || solve_sudoku(s))
            return 1; /* we've found the solution! */
        
        unfill_square(s, &p, i); /* backtrack, try next candidate */
    }

    if (s->unsolved > 1) 
        memcpy(&s->blank[s->unsolved-1], &p, sizeof(point)); /* append */
    return 0;
}

void read_sudoku(sudoku *s, char buf[81]) {
    memset(s, 0, sizeof(sudoku)); 
    s->unsolved = 81;

    u8 *g = &(s->grid[0][0]); /* pointer to head of grid memory area */
    memcpy(g, buf, 81); 
    for (u8 i = 0; i < 81; i++)
        *g++ -= '0'; 
    
    u16 digit, mask;
    point *p = s->blank;
    for (u8 y = 0; y < 9; y++) {
        for (u8 x = 0; x < 9; x++) { 
            if ((digit = s->grid[y][x])) {
                s->unsolved--;
                mask = (u16)(1u << digit);
                s->row[y] |= mask;
                s->col[x] |= mask;
                s->sec[y/3][x/3] |= mask;
            } else { 
                p->y = y; 
                p->x = x; 
                p++;
            }
        }
    }
}

int main(int argc, char **argv) {
    assert(argc > 1);
    FILE *f = fopen(argv[1], "r");
    if (f == NULL) 
        err(1, "Unable to open \"%s\"", argv[1]);

    char buf[81]; 
    sudoku s;

    while (fscanf(f, "%81c\n", buf) == 1) {
        read_sudoku(&s, buf);
        assert(solve_sudoku(&s) == 1);
        //dump(&s);
    }

    fclose(f);
    return 0;
}

sudoku17

$ wget http://people.csse.uwa.edu.au/gordon/sudoku17
$ wc -l sudoku17
49151 sudoku17
$ head -n 10 sudoku17
000000010400000000020000000000050407008000300001090000300400200050100000000806000
000000010400000000020000000000050604008000300001090000300400200050100000000807000
000000012000035000000600070700000300000400800100000000000120000080000040050000600
...