sudoku.c

sudoku.c

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

#define SUDOKU_SZ 9
#define SUDOKU_BLK_SZ 3

typedef struct {
	uint8_t cells[SUDOKU_SZ * SUDOKU_SZ];
	uint16_t rows[SUDOKU_SZ];
	uint16_t cols[SUDOKU_SZ];
	uint16_t blocks[SUDOKU_SZ];
} sudoku;

sudoku BOARD_1 = {
	.cells = {
    	0, 0, 0,  2, 6, 0,  7, 0, 1,  // 0
    	6, 8, 0,  0, 7, 0,  0, 9, 0,  // 0
    	1, 9, 0,  0, 0, 4,  5, 0, 0,  // 0
    
    	8, 2, 0,  1, 0, 0,  0, 4, 0,  // 3
    	0, 0, 4,  6, 0, 2,  9, 0, 0,  // 3
    	0, 5, 0,  0, 0, 3,  0, 2, 8,  // 3
    
    	0, 0, 9,  3, 0, 0,  0, 7, 4,  // 6
    	0, 4, 0,  0, 5, 0,  0, 3, 6,  // 6
    	7, 0, 3,  0, 1, 8,  0, 0, 0,  // 6
    },
    .rows = { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    .cols = { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    .blocks = { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};

#define INDEX(row, col) (col + SUDOKU_SZ * row)
#define BLOCK(row, col) \
	(col / SUDOKU_BLK_SZ + \
		SUDOKU_BLK_SZ * (row / SUDOKU_BLK_SZ))  // integer division
#define FILLED(map, symbol) (1 & (map >> (symbol - 1)))
#define VALID_MOVE(board, row, col, symbol) \
	(	!FILLED((board)->rows[row], symbol) && \
		!FILLED((board)->cols[col], symbol) && \
		!FILLED((board)->blocks[BLOCK(row, col)], symbol))

void print_mask(uint16_t mask) {
	for (uint8_t sym = 1; sym <= SUDOKU_SZ; ++sym) {
		if (FILLED(mask, sym)) {
			printf("%u, ", sym);
		}
	}
}

void print_masks(uint16_t type[]) {
	for (size_t i = 0; i != SUDOKU_SZ; ++i) {
		uint16_t mask = type[i];
		print_mask(mask);
		printf("\n");
	}
	printf("\n");
}

void sudoku_print(sudoku *board) {
	for (size_t row = 0; row != SUDOKU_SZ; ++row) {
		for (size_t col = 0; col != SUDOKU_SZ; ++col) {
			uint8_t sym = board->cells[INDEX(row, col)];
			if (sym) {
				printf("%d ", board->cells[INDEX(row, col)]);
			} else {
				printf("- ");
			}
		}
		printf("\n");
	}
	/*printf("rows: "); print_masks(board->rows);
	printf("cols: "); print_masks(board->cols);
	printf("blocks: "); print_masks(board->blocks);*/
}

/* doesn't check validity */
void sudoku_set(sudoku *board, size_t row, size_t col, uint8_t symbol) {
	board->cells[INDEX(row, col)] = symbol;
	uint16_t mask = 1 << (symbol - 1);
	// printf("row:%zu col:%zu sym:%u mask:%u\n", row, col, symbol, mask);
	board->rows[row] |= mask;
	board->cols[col] |= mask;
	board->blocks[BLOCK(row, col)] |= mask;
}

void sudoku_clear(sudoku *board, size_t row, size_t col) {
	uint8_t symbol = board->cells[INDEX(row, col)];
	board->cells[INDEX(row, col)] = 0;
	uint16_t mask = ~(1 << (symbol - 1));
	board->rows[row] &= mask;
	board->cols[col] &= mask;
	board->blocks[BLOCK(row, col)] &= mask;
}

void sudoku_init(sudoku *board) {
	for (size_t row = 0; row != SUDOKU_SZ; ++row) {
		for (size_t col = 0; col != SUDOKU_SZ; ++col) {
			uint8_t sym = board->cells[INDEX(row, col)];
			if (sym != 0) {
				if (!VALID_MOVE(board, row, col, sym)) {
					printf("failed at: row:%zu, col:%zu, sym:%u\n",
						row, col, sym);
					sudoku_print(board);
				}
				assert(VALID_MOVE(board, row, col, sym));
				sudoku_set(board, row, col, sym);
			}
		}
	}
}

size_t sudoku_solve(sudoku board, size_t depth) {
	for (size_t row = 0; row != SUDOKU_SZ; ++row) {
		for (size_t col = 0; col != SUDOKU_SZ; ++col) {			
			uint8_t sym = board.cells[INDEX(row, col)];
			if (!sym) {
				//printf("%zu row:%zu col:%zu\n", depth, row, col);
				//sudoku_print(&board);
				size_t solutions = 0;
				uint16_t taken = board.rows[row] |
				  board.cols[col] |
				  board.blocks[BLOCK(row, col)];
				for (uint8_t try = 1; try <= SUDOKU_SZ; ++try) {
					if (!FILLED(taken, try)) {
						sudoku_set(&board, row, col, try);
						solutions += sudoku_solve(board, depth + 1);
						sudoku_clear(&board, row, col);
					}
				}
				return solutions;
			}
		}
	}
	sudoku_print(&board);
	printf("\n\n");
	return 1;
}

int sudoku_read(sudoku *board) {
	memset(board, 0, sizeof(sudoku));
	for (size_t i = 0; i != SUDOKU_SZ * SUDOKU_SZ; ++i) {
		int c = getchar();
		do {
			if (c == '-') {
				board->cells[i] = 0;
				break;
			} else {
				uint8_t sym = c - '0';
				if (sym > 0 && sym <= SUDOKU_SZ) {
					board->cells[i] = sym;
					break;
				}
			}
		} while ((c = getchar()) >= 0);
		if (c < 0) {
			return 0;
		}
	}
	sudoku_init(board);
	return 1;
}

int main(int argc,  char **argv) {
	int puzzle = 1;
	sudoku board;
	while (sudoku_read(&board)) {
		printf("===== Puzzle %d: =====\n", puzzle++);
		sudoku_print(&board);
		printf("*** Solutions:\n");
		size_t solutions = sudoku_solve(board, 0);
		printf("%zu solutions.\n", solutions);
	}
	return 0;
}