I have written a Sudoku solver which can solve arbitrary NxN grids via backtracking.
Since I'm relativly new to C any feedback is welcome.
Code:
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned int uint;
typedef struct Cell {
uint candidates;
bool solved;
} Cell;
typedef struct Board {
uint block_width;
uint block_height;
uint group_size;
uint cell_count;
Cell *cells;
} Board;
typedef struct MemoryArena {
Cell *first_cell;
uint capacity;
uint size;
} MemoryArena;
#define UNDO_SIZE(board) 3 * board->group_size
#define AT(board, x, y) board->cells + y * board->group_size + x
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
#define MAX_BOARD_SIZE sizeof(uint) * 8
#define FOR_EACH_COL(ptr, board, x, y, statement) \
do { \
uint x_##ptr = x; \
Cell *ptr = AT(board, x_##ptr, 0); \
for (uint y_##ptr = 0; y_##ptr < board->group_size; y_##ptr++) { \
{ statement } \
ptr += board->group_size; \
} \
} while (0)
#define FOR_EACH_ROW(ptr, board, x, y, statement) \
do { \
uint y_##ptr = y; \
Cell *ptr = AT(board, 0, y_##ptr); \
for (uint x_##ptr = 0; x_##ptr < board->group_size; x_##ptr++) { \
{ statement } \
ptr++; \
} \
} while (0)
#define FOR_EACH_BLOCK(ptr, board, x, y, statement) \
do { \
uint xblock_##ptr = (x / board->block_width) * board->block_width; \
uint yblock_##ptr = (y / board->block_height) * board->block_height; \
Cell *ptr = AT(board, xblock_##ptr, yblock_##ptr); \
for (uint y_##ptr = 0; y_##ptr < board->block_height; y_##ptr++) { \
for (uint x_##ptr = 0; x_##ptr < board->block_width; x_##ptr++) { \
{ statement } \
ptr++; \
} \
ptr += board->group_size - board->block_width; \
} \
} while (0)
#define FOR_EACH_GROUP(ptr, board, x, y, statement) \
do { \
FOR_EACH_COL (ptr, board, x, y, statement); \
FOR_EACH_ROW (ptr, board, x, y, statement); \
FOR_EACH_BLOCK(ptr, board, x, y, statement); \
} while(0)
Cell *push_memory(MemoryArena *arena, uint size) {
assert(arena->size + size <= arena->capacity);
Cell *result = arena->first_cell + arena->size;
arena->size += size;
return result;
}
void pop_memory(MemoryArena *arena, uint size) {
assert(arena->size >= size);
arena->size -= size;
}
MemoryArena alloc_arena(Board *board) {
assert(!board->cells);
MemoryArena arena = {};
uint undo_cell_count = UNDO_SIZE(board) * board->cell_count;
arena.capacity = board->cell_count + undo_cell_count;
arena.first_cell = malloc(arena.capacity * sizeof(Cell));
board->cells = push_memory(&arena, board->cell_count);
return arena;
}
Board init_board(uint block_width, uint block_height) {
assert(block_width * block_height <= MAX_BOARD_SIZE);
Board board = {};
board.block_width = block_width;
board.block_height = block_height;
board.group_size = block_width * block_height;
board.cell_count = board.group_size * board.group_size;
return board;
}
bool place_value(Board *board, uint destx, uint desty, uint value, Cell *undo_data) {
assert(board);
assert(destx < board->group_size);
assert(desty < board->group_size);
assert(value < board->group_size);
bool success = true;
Cell *cell = AT(board, destx, desty);
assert(HAS_CANDIDATE(cell, value));
if (undo_data) {
FOR_EACH_GROUP(current_cell, board, destx, desty, {
*(undo_data++) = *current_cell;
});
}
FOR_EACH_GROUP(current_cell, board, destx, desty, {
if (HAS_CANDIDATE(current_cell, value)) {
current_cell->candidates &= ~(1 << value);
if (current_cell->candidates == 0 && current_cell != cell) {
success = false;
}
}
});
cell->candidates = 1 << value;
cell->solved = true;
return success;
}
void undo_placement(Board *board, uint destx, uint desty, Cell *undo_data) {
assert(board);
assert(destx < board->group_size);
assert(desty < board->group_size);
assert(undo_data);
FOR_EACH_GROUP(current_cell, board, destx, desty, {
*current_cell = *(undo_data++);
});
}
bool load_board(MemoryArena *arena, Board *board, char *input) {
for (uint i = 0; i < board->cell_count; i++) {
Cell cell = {};
cell.candidates = (1 << board->group_size) - 1;
board->cells[i] = cell;
}
bool success = true;
for (int y = 0; y < board->group_size; y++) {
for (int x = 0; x < board->group_size; x++) {
char input_char = *(input++);
assert(input_char != '\0');
uint value = input_char - '1';
if (value < board->group_size) {
success &= place_value(board, x, y, value, 0);
}
}
}
return success;
}
bool solve(MemoryArena *arena, Board *board, uint index) {
Cell *cell = board->cells + index;
while (index < board->cell_count && cell->solved) {
cell++;
index++;
}
if (index == board->cell_count) {
return true;
}
uint x = index % board->group_size;
uint y = index / board->group_size;
for (uint i = 0; i < board->group_size; i++) {
if (HAS_CANDIDATE(cell, i)) {
Cell *undo_data = push_memory(arena, UNDO_SIZE(board));
if (place_value(board, x, y, i, undo_data) && solve(arena, board, index + 1)) {
return true;
}
undo_placement(board, x, y, undo_data);
pop_memory(arena, UNDO_SIZE(board));
}
}
return false;
}
void print_horizontal_line(Board *board, char a, char b) {
uint length = board->block_width * (board->block_width + 1) - 1;
for (uint by = 0; by < board->block_height; by++) {
printf("%c", a);
for (uint bx = 0; bx < length; bx++) {
printf("%c", b);
}
}
printf("%c", a);
printf("\n");
}
void print_cell_candidate(Cell *cell, uint candidate_index, bool is_center_index) {
char display;
if (cell->solved && cell->candidates) {
if (is_center_index) {
display = '0';
uint i = cell->candidates;
while (i) {
i >>= 1;
display++;
}
} else {
display = ' ';
}
} else if (HAS_CANDIDATE(cell, candidate_index)) {
display = candidate_index + '1';
} else {
display = '.';
}
printf("%c", display);
}
void print_board(Board *board) {
Cell *start_of_row = board->cells;
uint center_index = board->block_width * (board->block_height / 2) + (board->block_width / 2);
for (uint y = 0; y < board->group_size; y++) {
if (y % board->block_height == 0) {
print_horizontal_line(board, '+', '-');
} else {
print_horizontal_line(board, '|', ' ');
}
for (uint by = 0; by < board->block_height; by++) {
Cell *current_cell = start_of_row;
for (uint x = 0; x < board->group_size; x++) {
if (x % board->block_width == 0) {
printf("|");
} else {
printf(" ");
}
for (uint bx = 0; bx < board->block_width; bx++) {
uint index = by * board->block_width + bx;
bool is_center_index = index == center_index;
print_cell_candidate(current_cell, index, is_center_index);
}
current_cell++;
}
printf("|\n");
}
start_of_row += board->group_size;
}
print_horizontal_line(board, '+', '-');
printf("\n");
}
bool solve_and_print_sudoku(char *input, uint block_width, uint block_height) {
Board board = init_board(block_width, block_height);
MemoryArena arena = alloc_arena(&board);
if (!load_board(&arena, &board, input)) {
fprintf(stderr, "Invalid input\n");
return false;
}
print_board(&board);
if (!solve(&arena, &board, 0)) {
fprintf(stderr, "No solution found\n");
return false;
}
print_board(&board);
free(arena.first_cell);
return true;
}
int main(int argc, char **argv) {
char *input = ".....6....59.....82....8....45........3........6..3.54...325..6..................";
uint block_width = 3;
uint block_height = 3;
if (argc == 4) {
block_width = atoi(argv[1]);
block_height = atoi(argv[2]);
input = argv[3];
} else if (argc != 1) {
fprintf(stderr,
"Usage:\n\t%s <block_width> <block_height> <board_input>\n\n"
"Example:\n\t%s %i %i \"%s\"\n\n",
argv[0], argv[0], block_width, block_height, input);
return -1;
}
uint size = block_width * block_height;
if (size > MAX_BOARD_SIZE) {
fprintf(stderr, "Invalid block size\n");
return -1;
}
uint expected_length = size * size;
if (strlen(input) != expected_length) {
fprintf(stderr, "Invalid input length\n");
return -1;
}
bool success = solve_and_print_sudoku(input, block_width, block_height);
return success ? 0 : -1;
}
Sample Input:
./sudoku.out 3 3 ".....6....59.....82....8....45........3........6..3.54...325..6.................."
Sample Output:
+-----------+-----------+-----------+
|1.3 1.3 1..|12. 1.3 |123 123 123|
|4.. ... 4..|45. 45. 6 |45. 4.. .5.|
|78. 78. 78.|7.9 7.9 |7.9 7.9 7.9|
| | | |
|1.3 |12. 1.3 12.|123 123 |
|4.6 5 9 |4.. 4.. 4..|4.6 4.6 8 |
|7.. |7.. 7.. 7..|7.. 7.. |
| | | |
| 1.3 1..|1.. 1.3 |1.3 1.3 1.3|
| 2 ..6 4..|45. 45. 8 |456 4.6 .5.|
| 7.. 7..|7.9 7.9 |7.9 7.9 7.9|
+-----------+-----------+-----------+
|1.. |12. 1.. 12.|123 123 123|
|... 4 5 |..6 ..6 ...|..6 ..6 ...|
|789 |789 789 7.9|789 789 7.9|
| | | |
|1.. 12. |12. 1.. 12.|12. 12. 12.|
|... ... 3 |456 456 4..|..6 ..6 ...|
|789 789 |789 789 7.9|789 789 7.9|
| | | |
|1.. 12. |12. 1.. |12. |
|... ... 6 |... ... 3 |... 5 4 |
|789 789 |789 789 |789 |
+-----------+-----------+-----------+
|1.. 1.. 1..| |1.. 1.. |
|4.. ... 4..| 3 2 5 |4.. 4.. 6 |
|789 789 78.| |789 789 |
| | | |
|1.3 123 12.|1.. 1.. 1..|123 123 123|
|456 ..6 4..|4.6 4.6 4..|45. 4.. .5.|
|789 789 78.|789 789 7.9|789 789 7.9|
| | | |
|1.3 123 12.|1.. 1.. 1..|123 123 123|
|456 ..6 4..|4.6 4.6 4..|45. 4.. .5.|
|789 789 78.|789 789 7.9|789 789 7.9|
+-----------+-----------+-----------+
+-----------+-----------+-----------+
| | | |
| 1 3 8 | 2 4 6 | 5 7 9 |
| | | |
| | | |
| | | |
| 6 5 9 | 1 3 7 | 2 4 8 |
| | | |
| | | |
| | | |
| 2 7 4 | 5 9 8 | 1 6 3 |
| | | |
+-----------+-----------+-----------+
| | | |
| 7 4 5 | 6 8 2 | 3 9 1 |
| | | |
| | | |
| | | |
| 8 1 3 | 4 5 9 | 6 2 7 |
| | | |
| | | |
| | | |
| 9 2 6 | 7 1 3 | 8 5 4 |
| | | |
+-----------+-----------+-----------+
| | | |
| 4 8 7 | 3 2 5 | 9 1 6 |
| | | |
| | | |
| | | |
| 3 6 2 | 9 7 1 | 4 8 5 |
| | | |
| | | |
| | | |
| 5 9 1 | 8 6 4 | 7 3 2 |
| | | |
+-----------+-----------+-----------+
