Smatchcube's website 🌍


Sudoku solver

/* sudoku_solver.c
 *
 * This is a simple sudoku solver using backtracking.
 * A valid file for input consist of nine lines of nine digits,
 * without space or delimiters between digits. (see the file `board`
 * for an example of a valid input file).
 * The program works only if the grid admits at least one solution.
 * Empty boxes are represented by the digit zero.
 *
 * Notation: i for column, j for row, both zero indexed
 * and starting from the upper left corner of the grid.
 *
 * */

#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint_fast8_t digit;
typedef uint_fast8_t pos;

bool load_grid(FILE*, digit board[9][9]);
void solve(digit board[9][9]);
void set_first_pos(pos* i, pos* j, bool grid[9][9]);
void next_cell(pos* i, pos* j, bool grid[9][9]);
void previous_cell(pos* i, pos* j, bool grid[9][9]);
bool is_legit(pos i, pos j, digit board[9][9]);
void print_board(digit board[9][9]);

int main(int argc, char* argv[])
{
	FILE* fp;
	digit board[9][9] = {0};

	if (argc != 2) {
		fprintf(stderr, "Usage: %s [FILE]\n", argv[0]);
		return EXIT_FAILURE;
	}
	if ((fp = fopen(argv[1], "r")) == NULL) {
		fprintf(stderr, "Can't open %s for read: %s\n", argv[1],
			strerror(errno));
		return EXIT_FAILURE;
	}
	if (load_grid(fp, board) == false) {
		fprintf(stderr,
			"Error while loading the grid: invalid input format\n");
		fclose(fp);
		return EXIT_FAILURE;
	}
	fclose(fp);

	solve(board);
	print_board(board);

	return EXIT_SUCCESS;
}

bool load_grid(FILE* fp, digit board[9][9])
/* set up the initial grid */
{
	digit board_tmp[9][9];
	for (pos i = 0; i < 9; ++i) {
		for (pos j = 0; j < 9; ++j) {
			board_tmp[i][j] = fgetc(fp) - '0';
			if (board_tmp[i][j] > 9)
				return false;
		}
		// discard end of line
		char ch;
		while ((ch = fgetc(fp)) != '\n' && ch != EOF)
			continue;
	}
	for (pos i = 0; i < 9; ++i) {
		for (pos j = 0; j < 9; ++j)
			board[i][j] = board_tmp[i][j];
	}
	return true;
}

void solve(digit board[9][9])
/* solve the grid using backtracking */
{
	bool grid[9][9];  // indication of numbers that can be changed
	for (pos i = 0; i < 9; ++i) {
		for (pos j = 0; j < 9; ++j)
			grid[i][j] = board[i][j] != 0;
	}
	pos i;
	pos j;
	set_first_pos(&i, &j, grid);
	board[i][j] = 1;
	while (i != 8 || j != 8 || !is_legit(8, 8, board)) {
		if (is_legit(i, j, board)) {  // forward to the next box
			next_cell(&i, &j, grid);
			board[i][j] = 1;
		}
		else {	// try next digit
			++board[i][j];
			while (board[i][j] > 9) {
				previous_cell(&i, &j, grid);
				++board[i][j];
			}
		}
	}
}

void set_first_pos(pos* i, pos* j, bool grid[9][9])
/* Set the position to the first valid position */
{
	for (*i = 0; *i < 9; ++*i) {
		for (*j = 0; *j < 9; ++*j) {
			if (!grid[*i][*j])
				return;	 // current case is empty
		}
	}

	// grid already completed, set position to the last one
	*i = 8;
	*j = 8;
}

void next_cell(pos* i, pos* j, bool grid[9][9])
/* set the position to the next empty cell
 * or last cell if everything is filled */
{
	do {
		if (*j == 8) {
			(*j) = 0;
			++(*i);
		}
		else
			++(*j);
	} while (grid[*i][*j] && (*i != 8 && *j != 8));
}

void previous_cell(pos* i, pos* j, bool grid[9][9])
/* set the position to the previous valid cell */
{
	do {
		if (*j == 0) {
			(*j) = 8;
			--(*i);
		}
		else
			--(*j);
	} while (grid[*i][*j]);
}

bool is_legit(pos i, pos j, digit board[9][9])
/* check whether the digit at the position is legit */
{
	const digit d = board[i][j];
	// check for duplicate in the row j
	for (pos n = 0; n < 9; ++n) {
		if (board[i][n] == d && n != j)
			return false;
	}
	// check for duplicate in the column i
	for (pos n = 0; n < 9; ++n) {
		if (board[n][j] == d && n != i)
			return false;
	}
	// check for duplicate in the 3x3 block
	const pos u = i - i % 3 + 3;
	const pos v = j - j % 3;
	const pos w = j - j % 3 + 3;
	for (pos n = i - i % 3; n < u; ++n) {
		for (pos m = v; m < w; ++m) {
			if (board[n][m] == d && n != i && m != j)
				return false;
		}
	}
	return true;
}

void print_board(digit board[9][9])
{
	for (pos i = 0; i < 9; ++i) {
		for (pos j = 0; j < 9; ++j) {
			if (board[i][j] == 0)
				printf("  ");
			else
				printf("%c ", '0' + board[i][j]);
		}
		putchar('\n');
	}
}