diff options
| -rw-r--r-- | TODO | 17 | ||||
| -rw-r--r-- | display.c | 5 | ||||
| -rw-r--r-- | solve.c | 287 |
3 files changed, 259 insertions, 50 deletions
@@ -0,0 +1,17 @@ +The solver can only solve when at least one cell can be solved with certainty +at each step of the process until repeating this eventually results in a solved +board. +The next step here is to allow exploration/trail of possible solutions. +Presumably, would want to keep a copy of the board just before each "guess" +that's taken to be able to easily roll back if failure. + +This would probably work really nicely as a recursive call: + + board = get_fresh_board(board) + solve_all_certainties(board) + for each possible board as cand_board: + solution = solve_all_certainties(cand_board) + if complete(solution) + success + /* we should have solution presuming board was solvable */ + @@ -7,10 +7,13 @@ void display(struct cell board[9][9]) int x; int y; int val; + printf(" A B C D E F G H I\n" + " ---------------------\n"); for (y = 0; y < 9; y++) { if (y % 3 == 0 && y != 0) - printf("------+------+------\n"); + printf(" |-------+------+------\n"); + printf("%d | ", y + 1); for (x = 0; x < 9; x++) { if (x % 3 == 0 && x != 0) @@ -4,7 +4,26 @@ #include "cell.h" #include "display.h" -void update_not_row_col(struct cell b[9][9]) +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; @@ -15,21 +34,28 @@ void update_not_row_col(struct cell b[9][9]) { for (x = 0; x < 9; x++) { - val = b[x][y].val; + 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; + (*b)[i][y].not[val - 1] = 1; + (*b)[x][i].not[val - 1] = 1; } } } } } -void not_to_val_row_col(struct cell b[9][9]) +/* + * 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 change_count = 0; int x = 0; int y = 0; int i = 0; @@ -41,27 +67,38 @@ void not_to_val_row_col(struct cell b[9][9]) total = 0; for (x = 0; x < 9; x++) { - if (b[x][y].val != 0) + if ((*b)[x][y].val != 0) continue; for (i = 0; i < 9; i++) { - if (b[x][y].not[i]) + if ((*b)[x][y].not[i]) { total++; } else { val = i + 1; } } - if (total == 8) - b[x][y].val = val; + if (total == 8) { + printf("%c%c must be %d because it is the only missing value in its row or column\n", NAME_CELL(x,y), val); + DEBUG_LOG("ROW/COL: (%d,%d) must be %d\n", x, y, val); + (*b)[x][y].val = val; + change_count++; + } } } + return change_count; } -void not_to_val_cell(struct cell b[9][9]) +/* + * FIXME rename - cell != cell + * For all unsolved cells on the board, solve them if they are the only place + * left in their local 3x3 that a value missing from that 3x3 could fit + */ +int not_to_val_cell(struct cell (*b)[9][9]) { + int change_count = 0; int cx = 0; int cy = 0; int x = 0; @@ -69,7 +106,7 @@ void not_to_val_cell(struct cell b[9][9]) int n = 0; int potentials = 0; int okx, oky; - struct cell c; + struct cell *c; /* refactor this crap */ for (cy = 0; cy < 9; cy += 3) @@ -83,17 +120,17 @@ void not_to_val_cell(struct cell b[9][9]) { for (x = 0; x < 3; x++) { - c = b[cx+x][cy+y]; - if (c.val == n) + c = &(*b)[cx+x][cy+y]; + if (c->val == n) { potentials = 0; y = 3; break; } - if (c.val) + if (c->val) continue; - if (c.not[n-1] == 0) + if (c->not[n-1] == 0) { potentials++; okx = x; @@ -103,14 +140,109 @@ void not_to_val_cell(struct cell b[9][9]) } if (potentials == 1) { - b[cx+okx][cy+oky].val = n; + DEBUG_LOG("CELL: (%d,%d) must be %d\n", cx + okx, cy + oky, n); + printf("%c%c must be %d because it can't be anything else\n", + NAME_CELL(cx+okx, cy+oky), n); + (*b)[cx+okx][cy+oky].val = n; potentials = 0; + change_count++; + } else if(potentials) { + DEBUG_LOG("CELL: (%d,%d) could be one of %d\n", cx + okx, cy + oky, potentials); + int k = 0; + for (k = 0; k < 9; k++) { + if (!(*b)[cx+okx][cy+oky].not[k]) { + DEBUG_LOG(" %d", k+1); + } + } + DEBUG_LOG("\n\n"); } } } } + return change_count; } + +/* For the numbers 1-9 not filled into a cell, fill in those which have only + * one place they can go */ +int cell_fill_certainties(struct cell (*b)[9][9], int cx, int cy) +{ + int change_count = 0; + int will_take_count = 0; + int will_take_x = 0; + int will_take_y = 0; +// struct cell *will_take = NULL; + int val = 0; + int cell_has[9] = {0}; + int x,y; + + /* Translate cell-based index to tile-based */ + cx *= 3; + cy *= 3; + + /* First: walk the cell and find which values it has */ + for (x = cx; x < cx + 3; x++) { + for (y = cy; y < cy + 3; y++) { + val = (*b)[x][y].val; + if (val) { + DEBUG_LOG("CELL_CERT: Cell (%d,%d) has %d\n", cx/3, cy/3, val); + cell_has[val - 1] = 1; + } + } + } + + /* Second: For all missing values, see if only one tile will take it. + * If only one will have it, put it in */ + for (val = 0; val < 9; val++) { + + will_take_count = 0; + + /* Does the cell lack the value? */ + if (!cell_has[val]) { + + DEBUG_LOG("Try to solve for %d\n", val + 1); + + /* Walk the cell and find which tile(s) will take it */ + for (x = cx; x < cx + 3; x++) { + for (y = cy; y < cy + 3; y++) { + if ((*b)[x][y].val) { + continue; + } + if ((*b)[x][y].not[val] == 0) { + will_take_count++; + will_take_x = x; + will_take_y = y; + } + } + } + DEBUG_LOG("will_take_count is %d\n", will_take_count); + /* Don't make indeterminate choices here*/ + if (will_take_count == 1) { + printf("%c%c must be %d because it is the only place in its 3x3 this will fit\n", + NAME_CELL(will_take_x, will_take_y), + val + 1); + (*b)[will_take_x][will_take_y].val = val + 1; + change_count++; + } + } + } + return change_count; +} + +int cells_fill_certainties(struct cell (*b)[9][9]) +{ + int change_count = 0; + int x, y; + + for (x = 0; x < 3; x++) { + for (y = 0; y < 3; y++) { + change_count += cell_fill_certainties(b, x, y); + } + } + return change_count; +} + + int main(int argc, char **argv) { // int x = 0; @@ -119,56 +251,113 @@ int main(int argc, char **argv) memset(board, 0, sizeof(board)); + board[1][0].val = 6; + board[2][0].val = 1; + board[3][0].val = 5; + board[8][0].val = 9; - board[7][0].val = 3; - board[4][1].val = 3; - board[0][7].val = 3; - board[1][4].val = 3; + board[1][1].val = 7; + board[2][1].val = 5; + board[3][1].val = 4; + board[4][1].val = 9; + board[5][1].val = 3; + board[6][1].val = 6; - /* dummy board taken from the guardian lol */ - /* FIXME: have a way to input boards, silly */ - board[0][0].val = 7; - board[0][4].val = 5; + board[0][2].val = 9; + board[3][2].val = 6; + board[7][2].val = 7; - board[1][2].val = 5; - board[1][4].val = 9; + board[0][3].val = 4; + board[3][3].val = 2; + board[5][3].val = 6; - board[2][1].val = 6; - board[2][2].val = 4; - board[2][5].val = 2; + board[0][4].val = 3; + board[2][4].val = 9; + board[6][4].val = 2; + board[8][4].val = 7; - board[3][0].val = 1; board[3][5].val = 9; - board[3][6].val = 7; + board[5][5].val = 5; + board[8][5].val = 3; + + board[1][6].val = 8; + board[5][6].val = 9; + board[8][6].val = 5; - board[4][0].val = 9; - board[4][2].val = 6; - board[4][3].val = 4; - board[4][7].val = 8; - board[4][8].val = 5; - board[5][4].val = 2; + board[2][7].val = 4; + board[3][7].val = 7; + board[4][7].val = 5; + board[5][7].val = 2; + board[6][7].val = 8; + board[7][7].val = 9; - board[6][4].val = 8; - board[6][6].val = 5; - board[6][7].val = 6; - board[7][1].val = 8; - board[7][6].val = 3; + board[0][8].val = 5; + board[5][8].val = 1; + board[6][8].val = 7; + board[7][8].val = 3; - board[8][0].val = 4; - board[8][4].val = 1; - board[8][5].val = 7; - board[8][8].val = 8; +// board[7][0].val = 3; +// board[4][1].val = 3; +// board[0][7].val = 3; +// board[1][4].val = 3; +// +// /* dummy board taken from the guardian lol */ +// /* FIXME: have a way to input boards, silly */ +// board[0][0].val = 7; +// board[0][4].val = 5; +// +// board[1][2].val = 5; +// board[1][4].val = 9; +// +// board[2][1].val = 6; +// board[2][2].val = 4; +// board[2][5].val = 2; +// +// board[3][0].val = 1; +// board[3][5].val = 9; +// board[3][6].val = 7; +// +// board[4][0].val = 9; +// board[4][2].val = 6; +// board[4][3].val = 4; +// board[4][7].val = 8; +// board[4][8].val = 5; +// +// board[5][4].val = 2; +// +// board[6][4].val = 8; +// board[6][6].val = 5; +// board[6][7].val = 6; +// +// board[7][1].val = 8; +// board[7][6].val = 3; +// +// board[8][0].val = 4; +// board[8][4].val = 1; +// board[8][5].val = 7; +// board[8][8].val = 8; display(board); - update_not_row_col(board); - not_to_val_cell(board); - not_to_val_row_col(board); + int i = 0; + int total_changes = 0; + int change_count = -1; + /* 9*9 is worst case */ + for (i = 0; i < 9*9 && change_count; i++) { + 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 += cells_fill_certainties(&board); + total_changes += change_count; +// display(board); + } + printf("Solution (%d changes)\n", total_changes); display(board); } |