# NxN Sudoku Solver

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);

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 |
|           |           |           |
+-----------+-----------+-----------+


compiling using:

gcc -ggdb -Wall -Wextra -Wconversion -pedantic -std=gnu11 -c "untitled.c"


results in the following list of problems:

untitled.c: In function ‘alloc_arena’:
untitled.c:107:25: warning: ISO C forbids empty initializer braces [-Wpedantic]
MemoryArena arena = {};
^

untitled.c: In function ‘init_board’:
untitled.c:122:19: warning: ISO C forbids empty initializer braces [-Wpedantic]
Board board = {};
^

In file included from untitled.c:1:0:
untitled.c: In function ‘place_value’:
untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:140:12: note: in expansion of macro ‘HAS_CANDIDATE’
assert(HAS_CANDIDATE(cell, value));
^~~~~~~~~~~~~

untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:47:15: note: in definition of macro ‘FOR_EACH_COL’
{ statement }                                                             \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:152:13: note: in expansion of macro ‘HAS_CANDIDATE’
if (HAS_CANDIDATE(current_cell, value))
^~~~~~~~~~~~~

untitled.c:154:38: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
current_cell->candidates &= ~(1 << value);
^

untitled.c:47:15: note: in definition of macro ‘FOR_EACH_COL’
{ statement }                                                             \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:58:15: note: in definition of macro ‘FOR_EACH_ROW’
{ statement }                                                             \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:152:13: note: in expansion of macro ‘HAS_CANDIDATE’
if (HAS_CANDIDATE(current_cell, value))
^~~~~~~~~~~~~

untitled.c:154:38: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
current_cell->candidates &= ~(1 << value);
^

untitled.c:58:15: note: in definition of macro ‘FOR_EACH_ROW’
{ statement }                                                             \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:71:19: note: in definition of macro ‘FOR_EACH_BLOCK’
{ statement }                                                         \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:152:13: note: in expansion of macro ‘HAS_CANDIDATE’
if (HAS_CANDIDATE(current_cell, value))
^~~~~~~~~~~~~

untitled.c:154:38: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
current_cell->candidates &= ~(1 << value);
^

untitled.c:71:19: note: in definition of macro ‘FOR_EACH_BLOCK’
{ statement }                                                         \
^~~~~~~~~

untitled.c:150:5: note: in expansion of macro ‘FOR_EACH_GROUP’
FOR_EACH_GROUP(current_cell, board, destx, desty,
^~~~~~~~~~~~~~

untitled.c:163:24: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
cell->candidates = 1 << value;
^

untitled.c:187:21: warning: ISO C forbids empty initializer braces [-Wpedantic]
Cell cell = {};
^

untitled.c:188:27: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
cell.candidates = (1 << board->group_size) - 1;
^

untitled.c:194:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int y = 0; y < board->group_size; y++)
^

untitled.c:196:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int x = 0; x < board->group_size; x++)
^

untitled.c:200:26: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
uint value = input_char - '1';
^~~~~~~~~~

untitled.c:204:47: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
success &= place_value(board, x, y, value, 0);
^

untitled.c:204:50: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
success &= place_value(board, x, y, value, 0);
^

untitled.c:183:30: warning: unused parameter ‘arena’ [-Wunused-parameter]
bool load_board(MemoryArena *arena, Board *board, char *input)
^~~~~

untitled.c: In function ‘solve’:
untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:233:13: note: in expansion of macro ‘HAS_CANDIDATE’
if (HAS_CANDIDATE(cell, i))
^~~~~~~~~~~~~

untitled.c: In function ‘print_cell_candidate’:
untitled.c:38:57: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
#define HAS_CANDIDATE(cell, candidate) cell->candidates & (1 << candidate)
^

untitled.c:294:14: note: in expansion of macro ‘HAS_CANDIDATE’
else if (HAS_CANDIDATE(cell, candidate_index))
^~~~~~~~~~~~~

untitled.c:296:23: warning: conversion to ‘char’ from ‘uint {aka unsigned int}’ may alter its value [-Wconversion]
display = candidate_index + '1';
^~~~~~~~~~~~~~~

untitled.c: In function ‘main’:
untitled.c:396:24: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
block_width  = atoi(argv[1]);
^~~~

untitled.c:397:24: warning: conversion to ‘uint {aka unsigned int}’ from ‘int’ may change the sign of the result [-Wsign-conversion]
block_height = atoi(argv[2]);                ^~~~

• Thanks. Two questions: 1. Regarding the conversion issues. Is it OK to just cast explicitly to uint. 2. How do you recommend I should initialize my structs to zero without specifying all members? If I compile Board board = {0}; with clang (with the same compiler flags) it warns warning: missing field 'block_height' initializer. Aug 19, 2018 at 17:44
• to add explicit casts over the implicit conversions is telling the compiler that you know the risks and are sure that non of the problems will occur. To me, it seems to be much easier to just use the right variable types to begin with, Aug 20, 2018 at 4:45

It would be better to prefer functions over macroes.

For example this:

#define AT(board, x, y) board->cells + y * board->group_size + x


It won't work correctly, if you 'call' it by the following way:

c = AT(board, x, y + 1);


Precompiler will turn it to:

c = board->cells + y + 1 * board->group_size + x;


Which is not probably the wanted result.

With functions you won't get that kind of problems. Good compiler can inline most of static functions, so you don't get performance penalty.

If you use macroes, use parenthesis when necessary

If a macro contains a counting expression, like this one:

#define MAX_BOARD_SIZE sizeof(uint) * 8


you should add parenthesis around it. This way:

#define MAX_BOARD_SIZE (sizeof(uint) * 8)


Or else you may face problems with this kind of code:

max_board_count = sizeof(board_buffer) / MAX_BOARD_SIZE;


Without parenthesis it would generate unwanted result:

max_board_count = sizeof(board_buffer) / sizeof(uint) * 8;