diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | cell.h | 13 | ||||
| -rw-r--r-- | debug.h | 15 | ||||
| -rw-r--r-- | display.h | 5 | ||||
| -rw-r--r-- | solve.c | 118 | ||||
| -rw-r--r-- | update.c | 34 | ||||
| -rw-r--r-- | update.h | 8 |
7 files changed, 146 insertions, 53 deletions
@@ -2,7 +2,11 @@ CFLAGS += -Werror -Wall all: solve -solve: display.o +solve: display.o update.o cell.h + +display.o: display.c cell.h display.h + +update.o: update.c cell.h display.h clean: rm -f *.o solve @@ -1,7 +1,16 @@ +#ifndef SUDOKU_CELL_H +#define SUDOKU_CELL_H + +/* Description of a single cell on a sudoku board */ struct cell { + /* Sovled value of this cell */ char val; - char not[9]; -} cell; + /* Array used to determine which values this cell can NOT be. + * A non-zero value at index N indicates that this cell cannot have the + * value N + 1 */ + char not[9]; +}; +#endif /* SUDOKU_CELL_H */ @@ -0,0 +1,15 @@ +#ifndef SUDOKU_DEBUG_H +#define SUDOKU_DEBUG_H + +#include <stdio.h> + +#define NAME_CELL(x,y) ("ABCDEFGHI"[(x)]), ("123456789"[(y)]) + +//#define DEBUG +#ifdef DEBUG +# define DEBUG_LOG(args...) printf(args) +#else +# define DEBUG_LOG(...) +#endif + +#endif /* SUDOKU_DEBUG_H */ @@ -1 +1,6 @@ +#ifndef SUDOKU_DISPLAY_H +#define SUDOKU_DISPLAY_H + void display(struct cell board[9][9]); + +#endif /* SUDOKU_DISPLAY_H */ @@ -1,59 +1,16 @@ #include <stdio.h> #include <string.h> +#include "debug.h" +#include "update.h" #include "cell.h" #include "display.h" -static const char row_letter_lookup[] = "ABCDEFGHI"; -static const char col_letter_lookup[] = "123456789"; - -#define NAME_CELL(x,y) row_letter_lookup[x], col_letter_lookup[y] - -//#define DEBUG -#ifdef DEBUG -# define DEBUG_LOG(args...) printf(args) -#else -# define DEBUG_LOG(...) -#endif - - /* - * FIXME rename - * For each unsolved cell on the board, update its list of values that it - * cannot be based on the solved cells in the same row or the same column - * Does not attempt to solve cells - */ -void update_not_row_col(struct cell (*b)[9][9]) -{ - int x = 0; - int y = 0; - int i = 0; - int val = 0; - - for (y = 0; y < 9; y++) - { - for (x = 0; x < 9; x++) - { - val = (*b)[x][y].val; - if (val != 0) - { - DEBUG_LOG("Update: (%d,%d) has value %d\n", x, y, val); - for (i = 0; i < 9; i++) - { - (*b)[i][y].not[val - 1] = 1; - (*b)[x][i].not[val - 1] = 1; - } - } - } - } -} - -/* - * FIXME rename * For all unsolved cells on the board, solve them if they have been marked as * impossible to be 8/9 values */ -int not_to_val_row_col(struct cell (*b)[9][9]) +int solve_row_col(struct cell (*b)[9][9]) { int change_count = 0; int x = 0; @@ -242,11 +199,68 @@ int cells_fill_certainties(struct cell (*b)[9][9]) return change_count; } +/* + * Check if every cell on a board is filled. + * Returns -1 isf the board is not fully + * Returns 0 if the board is filled + */ +int board_is_filled(struct cell (*b)[9][9]) +{ + int x = 0; + int y = 0; + + for (x = 0; x < 9; x++) { + for (y = 0; y < 9; y++) { + if ((*b)[x][y].val == 0) { + return -1; + } + } + } + return 0; +} + +int board_rows_are_solved(struct cell (*b)[9][9]) +{ + return -1; +} + +int board_cols_are_solved(struct cell (*b)[9][9]) +{ + return -1; +} + +int board_3s_are_solved(struct cell (*b)[9][9]) +{ + return -1; +} + +/* + * Check if a board is solved. + * Returns -1 isf the board is unsolved + * Returns 0 if the board is solved + */ +int board_is_solved(struct cell (*b)[9][9]) +{ + int ret = 0; + ret = board_is_filled(b); + if (ret) + return ret; + + ret = board_rows_are_solved(b); + if (ret) + return ret; + + ret = board_cols_are_solved(b); + if (ret) + return ret; + + ret = board_3s_are_solved(b); + + return ret; +} int main(int argc, char **argv) { -// int x = 0; -// int y = 0; struct cell board[9][9]; memset(board, 0, sizeof(board)); @@ -351,13 +365,17 @@ int main(int argc, char **argv) change_count = 0; update_not_row_col(&board); change_count += not_to_val_cell(&board); - change_count += not_to_val_row_col(&board); + change_count += solve_row_col(&board); change_count += cells_fill_certainties(&board); total_changes += change_count; // display(board); } - printf("Solution (%d changes)\n", total_changes); + if (board_is_solved(&board) < 0) { + printf("Could not solve the board! Here is the closest (%d changes)\n", total_changes); + } else { + printf("Solution (%d changes)\n", total_changes); + } display(board); } diff --git a/update.c b/update.c new file mode 100644 index 0000000..57c5dda --- /dev/null +++ b/update.c @@ -0,0 +1,34 @@ +#include "cell.h" +#include "debug.h" + +/* + * update_not_row_col + * + * For each unsolved cell on the board, update its list of values that it + * cannot be based on the solved cells in the same row or the same column + * Does not attempt to solve cells + */ +void update_not_row_col(struct cell (*b)[9][9]) +{ + int x = 0; + int y = 0; + int i = 0; + int val = 0; + + for (y = 0; y < 9; y++) + { + for (x = 0; x < 9; x++) + { + val = (*b)[x][y].val; + if (val != 0) + { + DEBUG_LOG("Update: (%d,%d) has value %d\n", x, y, val); + for (i = 0; i < 9; i++) + { + (*b)[i][y].not[val - 1] = 1; + (*b)[x][i].not[val - 1] = 1; + } + } + } + } +} diff --git a/update.h b/update.h new file mode 100644 index 0000000..8bd67b6 --- /dev/null +++ b/update.h @@ -0,0 +1,8 @@ +#ifndef SUDOKU_UPDATE_H +#define SUDOKU_UPDATE_H + +#include "cell.h" + +void update_not_row_col(struct cell (*)[9][9]); + +#endif /* SUDOKU_UPDATE_H */ |