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