LeetCode P37: Sudoku Solver (brute-force backtracking with pruning)

2024-04-28

The problem 37 of the LeetCode problem set asks us to write a Sudoku solver, assuming as an input a valid and uniquely solvable Sudoku board.

The approach taken below is called “brute-force backtracking with pruning”. Let's unpack this name:

• “Brute-force” means that the whole solution space is potentially evaluated. This means that this approach follows on enumerating every candidate solution, then evaluating it for correctness until a correct solution is found.
• “Backtracking” refers to a “depth-first Search” of the solution space. For each empty square, a number is temporarily filled in, then we recursively advance to the next empty square. If down the line we find no valid solutions that complete the board, we backtrack to the point we made a decision, than try the next possible decision.
• “Pruning” means that we immediately stop searching if at any moment we know that all the derived searches from that point on are not candidate solutions. This means that if we made the board illegal by filling in an invalid number, there's no point in continuing searching in that decision branch, so we backtrack to a previous point.

Solution in C

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define CHECK(p,q) do{ \
	if (board[(p)][(q)] == (c)) { return false; } \
} while(0)

bool is_valid(char** board, int i, int j, char c) {
	CHECK(i,0); CHECK(i,1); CHECK(i,2);
	CHECK(i,3); CHECK(i,4); CHECK(i,5);
	CHECK(i,6); CHECK(i,7); CHECK(i,8);

	CHECK(0,j); CHECK(1,j); CHECK(2,j);
	CHECK(3,j); CHECK(4,j); CHECK(5,j);
	CHECK(6,j); CHECK(7,j); CHECK(8,j);

	int ii = (i/3)*3; int jj = (j/3)*3;
	CHECK(ii+0,jj+0); CHECK(ii+0,jj+1); CHECK(ii+0,jj+2);
	CHECK(ii+1,jj+0); CHECK(ii+1,jj+1); CHECK(ii+1,jj+2);
	CHECK(ii+2,jj+0); CHECK(ii+2,jj+1); CHECK(ii+2,jj+2);
	return true;
}

bool find(char** board, int* out_i, int* out_j) {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == '.') {
				*out_i = i;
				*out_j = j;
				return true;
			}
		}
	}
	return false;
}

bool backtrack(char** board, int rem) {
	if (rem == 0) { return true; }

	int i; int j;
	if (!find(board, &i, &j)) {
		return true;
	}

	for (char c = '1'; c <= '9'; c++) {
		if (is_valid(board, i, j, c)) {
			board[i][j] = c;

			if (backtrack(board, rem-1)) {
				return true;
			}

			board[i][j] = '.';
		}
	}

	return false;
}

int count(char** board) {
	int n = 0;
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == '.') {
				n++;
			}
		}
	}
	return n;
}

void solveSudoku(char** board, int boardSize, int* boardColSize){
	int rem = count(board);
	backtrack(board, rem);
}

#ifdef LOCAL
int main() {
	char* init[] = {
		"53..7....",
		"6..195...",
		".98....6.",
		"8...6...3",
		"4..8.3..1",
		"7...2...6",
		".6....28.",
		"...419..5",
		"....8..79"
	};

	char** board = (char**) malloc(9 * sizeof(char*));

	for (int i = 0; i < 9; i++) {
		char* row = (char*) malloc(10 * sizeof(char));
		memcpy(row, init[i], 10);
		board[i] = row;
	}

	solveSudoku((char**)board, 9, NULL);

	assert(strcmp(board[0], "534678912") == 0);
	assert(strcmp(board[1], "672195348") == 0);
	assert(strcmp(board[2], "198342567") == 0);
	assert(strcmp(board[3], "859761423") == 0);
	assert(strcmp(board[4], "426853791") == 0);
	assert(strcmp(board[5], "713924856") == 0);
	assert(strcmp(board[6], "961537284") == 0);
	assert(strcmp(board[7], "287419635") == 0);
	assert(strcmp(board[8], "345286179") == 0);

	for (int i = 0; i < 9; i++) {
		printf("%s\n", board[i]);
		free(board[i]);
	}
	free(board);
}
#endif

Build Command

gcc -o p37 -Wall -O3 -g -DLOCAL -fsanitize=address -fsanitize=undefined p37.c