cellularmitosis/Makefile

## README.md

      
    Raw
  

              README.md
            
          
    Blog 2020/5/27
<- previous |
index |
next ->
A trivial sudoku solver, in C

Update: it should be noted there are many boards which this program cannot solve, such as this one.
After writing a sudoku solver in Python yesterday,
I decided to throw together a quick-n-dirty C implementation, to see how much faster it would be.
The answer is way faster!
Whereas my fastest Python solution ran in 1.9 seconds on my slowest machine (a 266MHz NSLU2), the C implementation runs in 31 milliseconds on the same machine!
cell@nslu2:/tmp$ time ./a.out wikipedia.txt
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

real    0m0.033s
user    0m0.000s
sys     0m0.010s
cell@nslu2:/tmp$ time ./a.out wikipedia.txt
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

real    0m0.031s
user    0m0.010s
sys     0m0.010s

For perspective, a 'Hello, world!' C program runs in 21 milliseconds on the same machine!
cell@nslu2:/tmp/hello$  gcc -std=c89 -Wall -Werror -O3 hello.c
cell@nslu2:/tmp/hello$ time ./a.out
Hello, world!

real    0m0.021s
user    0m0.000s
sys     0m0.010s
cell@nslu2:/tmp/hello$ time ./a.out
Hello, world!

real    0m0.022s
user    0m0.010s
sys     0m0.000s

On my i3-2350M, the sudoku solver runs in 3 milliseconds!
Aside from the fact that it is implemented in C, one aspect which makes this implementation fast
is that the set of possible solutions in each grid location is represented as a bit vector,
rather than a full-blow set implementation
(a trick I picked up from... was it The Pragmatic Programmer, or perhaps it was Programming Pearls?).
Hilariously, it takes over a minute to compile sudoku.c on this machine (266 lines of code as measured by cloc)!
cell@nslu2:/tmp$ time make
gcc -std=c89 -Wall -Werror -O3 sudoku.c

real    1m6.525s
user    0m43.300s
sys     0m5.610s


## Makefile
a.out: sudoku.c
	gcc -std=c89 -Wall -Werror -O3 sudoku.c

clean:
	rm -f a.out

.PHONY: clean

## sudoku.c
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>

/* A sudoku solver. */

/*
Copyright (c) 2020 Jason Pepas
Released under the terms of the MIT license.
See https://opensource.org/licenses/MIT
*/

/*
Board file format: plain text, 9 lines of 9 numbers (zero for empty box).
Example:
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
*/

/*
Data structures:
- A 'box' is a set of the remaining possible solutions for a spot in the grid.
  This set is represented as a uint16_t bitvector, with the sudoke numbers 1-9
  represented as the first 9 bits in the bitvector.
- A solved box has only one bit set.
- A 'board' is a 2-dimensional array (9x9) of boxes (bitvectors).
- A solved board is a 9x9 grid of bitvectors which each have only one item.
*/

/*
The general approach is to iterate over the board and use logic to reduce
the number of possible solutions in each box until the board is solved.

Algorithm:
- For each row, build a set of the solved numbers in that row, then
  remove those solutions from the remaining possibilities in each of the
  unsolved boxes in that row.
- Do the same for each column.
- Do the same for each 3x3 grid.
- Repeat the above process until either the board is solved, or until
  deadlock is detected (i.e. the board state remains unchanged after an
  iteration).
*/

/* the board. */
uint16_t g_board[9][9];

/* set all 9 bits in this box. */
void board_set_all(int row, int col) {
    uint16_t all_nums = /* 0b0000000111111111 */ 0x1FF;
    g_board[row][col] = all_nums;
}

/* convert a number to a bitvector. */
uint16_t num_to_bitvec(int num) {
    return 1 << (num-1);
}

/* add num to the box's bitvector. */
void board_set_num(int row, int col, int num) {
    g_board[row][col] |= num_to_bitvec(num);
}

/* count the number of bits which are set in the bitvector. */
int count_set_bits(uint16_t box) {
    int set_bits_count = 0;
    int i = 0;
    while (i < 16) {
        if (box & /* 0b1 */ 0x1) {
            set_bits_count++;
        }
        box = (box >> 1);
        i++;
        continue;
    }
    return set_bits_count;
}

/* is the box solved? */
bool box_is_solved(int row, int col) {
    uint16_t box = g_board[row][col];
    int bitcount = count_set_bits(box);
    return bitcount == 1;
}

/* is the board solved? */
bool board_is_solved() {
    int row = 0;
    int col = 0;
    while (row < 9) {
        while (col < 9) {
            if (!box_is_solved(row, col)) {
                return false;
            }
            col++;
            continue;
        }
        row++;
        continue;
    }
    return true;
}

/* return the character representation of the box. */
char board_get_ch(int row, int col) {
    if (!box_is_solved(row, col)) {
        return '0';
    }
    uint16_t box = g_board[row][col];
    uint8_t num = 1;
    while (num < 10) {
        if (box & /* 0b1 */ 0x1) {
            return (char)(num + '0');
        }
        box = (box >> 1);
        num++;
        continue;
    }
    assert(false);
    exit(2);
}

/* print the board state.  prints '0' for unsolved boxes. */
void print_board() {
    int row = 0;
    while (row < 9) {
        int col = 0;
        while (col < 9) {
            char ch = board_get_ch(row, col);
            putchar(ch);
            col++;
            continue;
        }
        putchar('\n');
        row++;
        continue;
    }
}

/* return the total count of all remaining possibliities in every box.
a solved board has a possibilities count of 81. */
int possibilities_count() {
    int pcount = 0;
    int row = 0;
    while (row < 9) {
        int col = 0;
        while (col < 9) {
            uint16_t box = g_board[row][col];
            int bitcount = count_set_bits(box);
            pcount += bitcount;
            col++;
            continue;
        }
        row++;
        continue;
    }
    return pcount;
}

/* read the board in from a file. */
void load_board(char* fname) {
    FILE* f = fopen(fname, "r");
    assert(f != NULL);
    const int bufsize = 110;  /* 9+2 per line * 9 lines + 1 null */
    char buf[bufsize];
    size_t count = fread(buf, 1, bufsize, f);
    assert(count >= 90);
    fclose(f);
    int i = 0;
    int row = 0;
    while (row < 9) {
        int col = 0;
        while (col < 9) {
            assert (i < bufsize);
            char ch = buf[i];
            if (ch == '0') {
                board_set_all(row, col);
            } else {
                int num = ch - '0';
                board_set_num(row, col, num);
            }
            i++;
            col++;
            continue;
        }
        /* skip over the newline. */
        char ch = buf[i];
        while (ch == '\n' || ch == '\r') {
            i++;
            ch = buf[i];
            continue;
        }
        row++;
        continue;
    }
}

/* return the combined bitmask of all solved boxes in the row. */
uint16_t get_row_solved_bitmask(int row) {
    uint16_t bitmask = 0;
    int col = 0;
    while (col < 9) {
        if (box_is_solved(row, col)) {
            bitmask |= g_board[row][col];
        }
        col++;
        continue;
    }
    return bitmask;
}

/* iterate over the rows, reducing possibilities. */
void iterate_rows() {
    int row = 0;
    while (row < 9) {
        uint16_t solved = get_row_solved_bitmask(row);
        int col = 0;
        while (col < 9) {
            if (!box_is_solved(row, col)) {
                /* subtract the solved bits from this box. */
                uint16_t box = g_board[row][col];
                box &= ~(solved);
                g_board[row][col] = box;
            }
            col++;
            continue;
        }
        row++;
        continue;
    }
}

/* return the combined bitmask of all solved boxes in the column. */
uint16_t get_col_solved_bitmask(int col) {
    uint16_t bitmask = 0;
    int row = 0;
    while (row < 9) {
        if (box_is_solved(row, col)) {
            bitmask |= g_board[row][col];
        }
        row++;
        continue;
    }
    return bitmask;
}

/* iterate over the columns, reducing possibilities. */
void iterate_columns() {
    int col = 0;
    while (col < 9) {
        uint16_t solved = get_col_solved_bitmask(col);
        int row = 0;
        while (row < 9) {
            if (!box_is_solved(row, col)) {
                /* subtract the solved bits from this box. */
                uint16_t box = g_board[row][col];
                box &= ~(solved);
                g_board[row][col] = box;
            }
            row++;
            continue;
        }
        col++;
        continue;
    }
}

/* return the combined bitmask of all solved boxes in the grid. */
uint16_t get_grid_solved_bitmask(int grid) {
    uint16_t bitmask = 0;
    int first_row = (grid / 3) * 3;
    int first_col = (grid % 3) * 3;
    int row = first_row;
    while (row < (first_row + 3)) {
        int col = first_col;
        while (col < (first_col + 3)) {
            if (box_is_solved(row, col)) {
                bitmask |= g_board[row][col];
            }
            col++;
            continue;
        }
        row++;
        continue;
    }
    return bitmask;
}

/* iterate over the grids, reducing possibilities. */
void iterate_grids() {
    int grid = 0;
    while (grid < 9) {
        uint16_t solved = get_grid_solved_bitmask(grid);
        int first_row = (grid / 3) * 3;
        int first_col = (grid % 3) * 3;
        int row = first_row;
        while (row < (first_row + 3)) {
            int col = first_col;
            while (col < (first_col + 3)) {
                if (!box_is_solved(row, col)) {
                    /* subtract the solved bits from this box. */
                    uint16_t box = g_board[row][col];
                    box &= ~(solved);
                    g_board[row][col] = box;
                }
                col++;
                continue;
            }
            row++;
            continue;
        }
        grid++;
        continue;
    }
}

/* iterate over the board, reducing possibilities. */
void iterate_board() {
    iterate_rows();
    iterate_columns();
    iterate_grids();
}

int main(int argc, char* argv[]) {
    load_board(argv[1]);
    int before_pcount = possibilities_count();
    while (!board_is_solved()) {
        iterate_board();
        int after_pcount = possibilities_count();
        if (after_pcount == before_pcount) {
            fprintf(stderr, "Error: don't know how to solve this board.\n");
            exit(3);
        } else {
            before_pcount = after_pcount;
            continue;
        }
    }
    print_board();
    return EXIT_SUCCESS;
}

## wikipedia-board.txt
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
	a.out: sudoku.c
	gcc -std=c89 -Wall -Werror -O3 sudoku.c

	clean:
	rm -f a.out

	.PHONY: clean
	#include <stdlib.h>
	#include <stdint.h>
	#include <stdio.h>
	#include <assert.h>
	#include <stdbool.h>

	/* A sudoku solver. */

	/*
	Copyright (c) 2020 Jason Pepas
	Released under the terms of the MIT license.
	See https://opensource.org/licenses/MIT
	*/

	/*
	Board file format: plain text, 9 lines of 9 numbers (zero for empty box).
	Example:
	530070000
	600195000
	098000060
	800060003
	400803001
	700020006
	060000280
	000419005
	000080079
	*/

	/*
	Data structures:
	- A 'box' is a set of the remaining possible solutions for a spot in the grid.
	This set is represented as a uint16_t bitvector, with the sudoke numbers 1-9
	represented as the first 9 bits in the bitvector.
	- A solved box has only one bit set.
	- A 'board' is a 2-dimensional array (9x9) of boxes (bitvectors).
	- A solved board is a 9x9 grid of bitvectors which each have only one item.
	*/

	/*
	The general approach is to iterate over the board and use logic to reduce
	the number of possible solutions in each box until the board is solved.

	Algorithm:
	- For each row, build a set of the solved numbers in that row, then
	remove those solutions from the remaining possibilities in each of the
	unsolved boxes in that row.
	- Do the same for each column.
	- Do the same for each 3x3 grid.
	- Repeat the above process until either the board is solved, or until
	deadlock is detected (i.e. the board state remains unchanged after an
	iteration).
	*/

	/* the board. */
	uint16_t g_board[9][9];

	/* set all 9 bits in this box. */
	void board_set_all(int row, int col) {
	uint16_t all_nums = /* 0b0000000111111111 */ 0x1FF;
	g_board[row][col] = all_nums;
	}

	/* convert a number to a bitvector. */
	uint16_t num_to_bitvec(int num) {
	return 1 << (num-1);
	}

	/* add num to the box's bitvector. */
	void board_set_num(int row, int col, int num) {
	g_board[row][col] \|= num_to_bitvec(num);
	}

	/* count the number of bits which are set in the bitvector. */
	int count_set_bits(uint16_t box) {
	int set_bits_count = 0;
	int i = 0;
	while (i < 16) {
	if (box & /* 0b1 */ 0x1) {
	set_bits_count++;
	}
	box = (box >> 1);
	i++;
	continue;
	}
	return set_bits_count;
	}

	/* is the box solved? */
	bool box_is_solved(int row, int col) {
	uint16_t box = g_board[row][col];
	int bitcount = count_set_bits(box);
	return bitcount == 1;
	}

	/* is the board solved? */
	bool board_is_solved() {
	int row = 0;
	int col = 0;
	while (row < 9) {
	while (col < 9) {
	if (!box_is_solved(row, col)) {
	return false;
	}
	col++;
	continue;
	}
	row++;
	continue;
	}
	return true;
	}

	/* return the character representation of the box. */
	char board_get_ch(int row, int col) {
	if (!box_is_solved(row, col)) {
	return '0';
	}
	uint16_t box = g_board[row][col];
	uint8_t num = 1;
	while (num < 10) {
	if (box & /* 0b1 */ 0x1) {
	return (char)(num + '0');
	}
	box = (box >> 1);
	num++;
	continue;
	}
	assert(false);
	exit(2);
	}

	/* print the board state. prints '0' for unsolved boxes. */
	void print_board() {
	int row = 0;
	while (row < 9) {
	int col = 0;
	while (col < 9) {
	char ch = board_get_ch(row, col);
	putchar(ch);
	col++;
	continue;
	}
	putchar('\n');
	row++;
	continue;
	}
	}

	/* return the total count of all remaining possibliities in every box.
	a solved board has a possibilities count of 81. */
	int possibilities_count() {
	int pcount = 0;
	int row = 0;
	while (row < 9) {
	int col = 0;
	while (col < 9) {
	uint16_t box = g_board[row][col];
	int bitcount = count_set_bits(box);
	pcount += bitcount;
	col++;
	continue;
	}
	row++;
	continue;
	}
	return pcount;
	}

	/* read the board in from a file. */
	void load_board(char* fname) {
	FILE* f = fopen(fname, "r");
	assert(f != NULL);
	const int bufsize = 110; /* 9+2 per line * 9 lines + 1 null */
	char buf[bufsize];
	size_t count = fread(buf, 1, bufsize, f);
	assert(count >= 90);
	fclose(f);
	int i = 0;
	int row = 0;
	while (row < 9) {
	int col = 0;
	while (col < 9) {
	assert (i < bufsize);
	char ch = buf[i];
	if (ch == '0') {
	board_set_all(row, col);
	} else {
	int num = ch - '0';
	board_set_num(row, col, num);
	}
	i++;
	col++;
	continue;
	}
	/* skip over the newline. */
	char ch = buf[i];
	while (ch == '\n' \|\| ch == '\r') {
	i++;
	ch = buf[i];
	continue;
	}
	row++;
	continue;
	}
	}

	/* return the combined bitmask of all solved boxes in the row. */
	uint16_t get_row_solved_bitmask(int row) {
	uint16_t bitmask = 0;
	int col = 0;
	while (col < 9) {
	if (box_is_solved(row, col)) {
	bitmask \|= g_board[row][col];
	}
	col++;
	continue;
	}
	return bitmask;
	}

	/* iterate over the rows, reducing possibilities. */
	void iterate_rows() {
	int row = 0;
	while (row < 9) {
	uint16_t solved = get_row_solved_bitmask(row);
	int col = 0;
	while (col < 9) {
	if (!box_is_solved(row, col)) {
	/* subtract the solved bits from this box. */
	uint16_t box = g_board[row][col];
	box &= ~(solved);
	g_board[row][col] = box;
	}
	col++;
	continue;
	}
	row++;
	continue;
	}
	}

	/* return the combined bitmask of all solved boxes in the column. */
	uint16_t get_col_solved_bitmask(int col) {
	uint16_t bitmask = 0;
	int row = 0;
	while (row < 9) {
	if (box_is_solved(row, col)) {
	bitmask \|= g_board[row][col];
	}
	row++;
	continue;
	}
	return bitmask;
	}

	/* iterate over the columns, reducing possibilities. */
	void iterate_columns() {
	int col = 0;
	while (col < 9) {
	uint16_t solved = get_col_solved_bitmask(col);
	int row = 0;
	while (row < 9) {
	if (!box_is_solved(row, col)) {
	/* subtract the solved bits from this box. */
	uint16_t box = g_board[row][col];
	box &= ~(solved);
	g_board[row][col] = box;
	}
	row++;
	continue;
	}
	col++;
	continue;
	}
	}

	/* return the combined bitmask of all solved boxes in the grid. */
	uint16_t get_grid_solved_bitmask(int grid) {
	uint16_t bitmask = 0;
	int first_row = (grid / 3) * 3;
	int first_col = (grid % 3) * 3;
	int row = first_row;
	while (row < (first_row + 3)) {
	int col = first_col;
	while (col < (first_col + 3)) {
	if (box_is_solved(row, col)) {
	bitmask \|= g_board[row][col];
	}
	col++;
	continue;
	}
	row++;
	continue;
	}
	return bitmask;
	}

	/* iterate over the grids, reducing possibilities. */
	void iterate_grids() {
	int grid = 0;
	while (grid < 9) {
	uint16_t solved = get_grid_solved_bitmask(grid);
	int first_row = (grid / 3) * 3;
	int first_col = (grid % 3) * 3;
	int row = first_row;
	while (row < (first_row + 3)) {
	int col = first_col;
	while (col < (first_col + 3)) {
	if (!box_is_solved(row, col)) {
	/* subtract the solved bits from this box. */
	uint16_t box = g_board[row][col];
	box &= ~(solved);
	g_board[row][col] = box;
	}
	col++;
	continue;
	}
	row++;
	continue;
	}
	grid++;
	continue;
	}
	}

	/* iterate over the board, reducing possibilities. */
	void iterate_board() {
	iterate_rows();
	iterate_columns();
	iterate_grids();
	}

	int main(int argc, char* argv[]) {
	load_board(argv[1]);
	int before_pcount = possibilities_count();
	while (!board_is_solved()) {
	iterate_board();
	int after_pcount = possibilities_count();
	if (after_pcount == before_pcount) {
	fprintf(stderr, "Error: don't know how to solve this board.\n");
	exit(3);
	} else {
	before_pcount = after_pcount;
	continue;
	}
	}
	print_board();
	return EXIT_SUCCESS;
	}