Tag Archives: Sudoku

Sudoku using backtracking in C

The title says it all. Here is the code:

#include <stdlib.h>
#include <stdio.h>

static void get_row_column(unsigned int cell, unsigned int *row, unsigned int *column)
{
    *row = cell / 9;
    *column =  cell % 9;
}

static unsigned int get_value(const unsigned int *grid, unsigned int row, unsigned int column)
{
    return grid[row * 9 + column];
}

static unsigned int unique_in_column(const unsigned int *grid, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column);
    unsigned int r;
    unsigned int unique = 1;
    for (r = 0; r < 9 && unique; r++) {
        unique = r == row || get_value(grid, r, column) != grid[cell];
    } 
    return unique;
}

static unsigned int unique_in_row(const unsigned int *grid, unsigned int cell)
{
    unsigned int row;
    unsigned int column;
    get_row_column(cell, &row, &column);
    unsigned int c;
    unsigned int unique = 1;
    for (c = 0; c < 9 && unique; c++) {
        unique = c == column || get_value(grid, row, c) != grid[cell];
    } 
    return unique;
}

static void get_box(unsigned int cell, unsigned int *row, unsigned int *column)
{
    get_row_column(cell, row, column);
    *row = (*row / 3) * 3;
    *column = (*column / 3) * 3;
}

static unsigned int unique_in_box(const unsigned int *grid, unsigned int cell)
{
    unsigned int row, column;
    unsigned int top, left;
    unsigned int r, c;
    unsigned int unique = 1;
    get_row_column(cell, &row, &column);
    get_box(cell, &top, &left);
    for (r = top; r < top + 3 && unique; r++) {
        for (c = left; c < left + 3 && unique; c++) {
            if (r != row && c != column) {
                unique = get_value(grid, r, c) != grid[cell];
            }
        }
    }
    return unique;
}

static unsigned int promising(const unsigned int *grid, unsigned int cell)
{
    return grid[cell] == 0 
        || (unique_in_row(grid, cell)
        && unique_in_column(grid, cell)
        && unique_in_box(grid, cell)); 
}

static unsigned int get_next_cell(const unsigned int *grid, unsigned int *cell)
{
    unsigned int found = 0;
    unsigned int i;
    for (i = *cell; i < 81 && !found; i++) {
        if (grid[i] == 0) {
            found = 1;
            *cell = i;
        }
    }
    return found;
}

static void print_grid(const unsigned int *grid)
{
    unsigned int i;
    for (i = 0; i < 81; i++) {
        printf("%d ", grid[i]);
        if (i % 9 == 8) {
            printf("\n");
        }
    }
    printf("\n");
}

static void sudoku_recursive(unsigned int *grid, unsigned int cell,
        unsigned int *succeeded)
{
    if (!get_next_cell(grid, &cell)) {
        *succeeded = 1;
        print_grid(grid);
    }
    else {
        unsigned int i;
        for (i = 1; i <= 9 && !*succeeded; i++) {
            unsigned int temp = grid[cell];
            grid[cell] = i;
            if (promising(grid, cell)) {
                sudoku_recursive(grid, cell + 1, succeeded);
            }
            grid[cell] = temp;
        }
    }
}

void sudoku(unsigned int *grid)
{
    unsigned int cell = 0;
    unsigned int succeeded = 0;
    sudoku_recursive(grid, cell, &succeeded);
}

An example program with the “World’s hardest sudoku“:

#include <stdio.h>

int main(void)
{
    unsigned int grid[] = {
        8, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 3, 6, 0, 0, 0, 0, 0,
        0, 7, 0, 0, 9, 0, 2, 0, 0,
        0, 5, 0, 0, 0, 7, 0, 0, 0,
        0, 0, 0, 0, 4, 5, 7, 0, 0,
        0, 0, 0, 1, 0, 0, 0, 3, 0,
        0, 0, 1, 0, 0, 0, 0, 6, 8,
        0, 0, 8, 5, 0, 0, 0, 1, 0,
        0, 9, 0, 0, 0, 0, 4, 0, 0
    };
    sudoku(grid);
    return 0;
}

The output:

8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2