/* Copyright (c) 2005 Peter O'Gorman * sudoku.c - a program to solve sudoku puzzles, see * http://www.sudoku.com * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ #include #include #include #include #include #include #include #ifdef NDEBUG #define debug(x) #define debug1(x,y) #define debug2(x,y,z) #define debug3(a,x,y,z) #else #define debug(x) fprintf(stderr,x) #define debug1(x,y) fprintf(stderr,x,y) #define debug2(x,y,z) fprintf(stderr,x,y,z) #define debug3(a,x,y,z) fprintf(stderr,a,x,y,z) #endif /* The sudoku puzzle is a 9x9 grid, some of the cells in the grid have * values 1-9 at the beginning, the idea is to then fill in the blanks * so that all digits 1 to 9 are used in all columns and all rows and * in each of the 9 mini-grids. an example is probably best : * +---+---+---+---+---+---+---+---+---+ * | | 6 | # 1 | | 4 # | 5 | | * +---+---+---+---+---+---+---+---+---+ * | | | 8 # 3 | | 5 # 6 | | | * +---+---+---+---+---+---+---+---+---+ * | 2 | | # | | # | | 1 | * +###################################+ * | 8 | | # 4 | | 7 # | | 6 | * +---+---+---+---+---+---+---+---+---+ * | | | 6 # | | # 3 | | | * +---+---+---+---+---+---+---+---+---+ * | 7 | | # 9 | | 1 # | | 4 | * +###################################+ * | 5 | | # | | # | | 2 | * +---+---+---+---+---+---+---+---+---+ * | | | 7 # 2 | | 6 # 9 | | | * +---+---+---+---+---+---+---+---+---+ * | | 4 | # 5 | | 8 # | 7 | | * +---+---+---+---+---+---+---+---+---+ * * Okay? * * So we have s struct of cells which cotains value, flags and remains * fields. The value holds the current value, the flags, we use the lower * 9 bits, if a bit is set then the cell can not contain the corresponding * number. * */ /* This program takes a grid on standard input and puts the solution on * standard output. e.g. * % ./sudoku * 060104050 * 008305600 * 200000001 * 800407006 * 006000300 * 700901004 * 500000002 * 007206900 * 040508070 * * Although it may be easier to put the grid in a file and do * % ./sudoku < puzzle * * To compile this program: * % cc -DNDEBUG -o sudoku sudoku.c * * */ struct cell { char value; unsigned int flags; unsigned char remain; } cell; struct grid { struct cell cells[9][9]; } grid; struct grid start_grid; static int solve_grid(struct grid * io_grid); static int readgrid(void); static int update_cells(struct grid * io_grid, int row, int col); static void read_input(void * imp, ssize_t * size); static int is_solved(const struct grid * in_grid); /* Return "true" if the grid is full of numbers. */ static int is_solved(const struct grid * in_grid) { int i,j; int solved = 1; for (j = 0; j < 9; j++) { for (i = 0; i< 9; i++) { if (in_grid->cells[j][i].value == 0) { solved = 0; break; } } if (!solved) break; } return solved; } /* Solve the grid, return "true" if success */ static int solve_grid(struct grid * io_grid) { int solved = 0; int i,j; int changed = 0; int y = 0; int z = 0; int value; int not_val; int x; int errors = 0; /* If a row/column/mini-grid contains 8 cells that either have a value, * or have been marked as being not N, then the remaining cell must * be N */ do { for (value = 1; value < 10; value++) { not_val = 0x0001 << (value -1); for (j =0; j < 9; j++) { x = 0; for (i = 0; i < 9; i++) { if ((io_grid->cells[j][i].value != 0) || (io_grid->cells[j][i].flags & not_val)) { x++; } } if (x == 8) { for (i = 0; i < 9; i++) { if ((io_grid->cells[j][i].value != 0) || (io_grid->cells[j][i].flags & not_val)) { continue; } io_grid->cells[j][i].value = value; errors += update_cells(io_grid, j,i); } } } for (i =0; i < 9; i++) { x = 0; for (j = 0; j < 9; j++) { if ((io_grid->cells[j][i].value != 0) || (io_grid->cells[j][i].flags & not_val)) { x++; } } if (x == 8) { for (j = 0; j < 9; j++) { if ((io_grid->cells[j][i].value != 0) || (io_grid->cells[j][i].flags & not_val)) { continue; } io_grid->cells[j][i].value = value; errors += update_cells(io_grid, j,i); debug3("B -%d,%d - %d\n",j,i, value); } } } x = 0; for (j = (0 + y); j < (3+y); j++) { for (i = (0 + z); i < (3+z); i++) { if (io_grid->cells[j][i].value != 0) { x++; } else if (io_grid->cells[j][i].flags & not_val) x++; } } if (x == 8) { for (j = (0+y); j < (3+y); j++) { for (i = (0+z); i < (3+z); i++) { if (io_grid->cells[j][i].value != 0) continue; if (io_grid->cells[j][i].flags & not_val) continue; io_grid->cells[j][i].value = value; errors += update_cells(io_grid, j,i); debug3("X -%d,%d - %d\n",j,i, value); } } } } y = y +3; if ( y >= 9) { y =0; z = z +3;} } while (z < 9); if (errors) return 0; /* If a cell has only one value it could be, then set it */ do { changed = 0; for (j = 0; j < 9; j++) { for (i = 0; i < 9; i++) { if (io_grid->cells[j][i].remain == 1) { int flags = io_grid->cells[j][i].flags; int value = 1; while (flags & 0x001) { value++; flags = flags >> 1; } debug3("j-%d, i-%d,value %d\n",j,i, value); io_grid->cells[j][i].value = value; io_grid->cells[j][i].remain = 0; update_cells(io_grid,j,i); changed = 1; } } } } while (changed); if (is_solved(io_grid)) return 1; /* We could not find a soltion with pure logic, * we must guess and recurse. We only guess for cells where * there are 2 possible options, otherwise it begins to get too hard * for normal people to possibly solve */ for (j = 0; j < 9; j++) { for (i = 0; i < 9; i++) { if (io_grid->cells[j][i].remain == 2) { struct grid mygrid[2]; int value = 1; int flags = io_grid->cells[j][i].flags; memcpy(&mygrid[0],io_grid,sizeof(struct grid)); memcpy(&mygrid[1],io_grid,sizeof(struct grid)); while (flags & 0x001) { value++; flags >>= 1; } mygrid[0].cells[j][i].value = value; mygrid[0].cells[j][i].remain = 0; do { value++; flags >>= 1; } while (flags & 0x001); mygrid[1].cells[j][i].value = value; mygrid[1].cells[j][i].remain = 0; changed = 0; if (!update_cells(&mygrid[0],j,i)) { changed = solve_grid(&mygrid[0]); } debug("Guessing\n"); if (changed) { memcpy(io_grid,&mygrid[0],sizeof(struct grid)); break; } if (!update_cells(&mygrid[1],j,i)) { changed = solve_grid(&mygrid[1]); } if (changed) { memcpy(io_grid,&mygrid[1],sizeof(struct grid)); break; } } } if (changed) break; } #ifndef NDEBUG for (j = 0; j < 9; j++) { for (i = 0; i < 9; i++) { putchar(io_grid->cells[j][i].value + '0'); } putchar('\n'); } #endif return is_solved(io_grid); } /* read at least size bytes of input */ static void read_input(void * imp, ssize_t * size) { ssize_t read_count = 0; assert(imp != NULL); assert(size != NULL); while (read_count < *size) { read_count += read(STDIN_FILENO,imp,*size - read_count); } *size = read_count; } /* If a cell gets a number then we need to call update_cells * it modifies other cells flags */ static int update_cells(struct grid * io_grid, int row, int col) { int i,j,x,y,z; char value = io_grid->cells[row][col].value; int not_val = 1 << (value-1); int errors = 0; int remain; assert(io_grid != NULL); assert(value); i=col; io_grid->cells[row][col].flags = 0x01FF; io_grid->cells[row][col].remain = 0; /* First of set the other cells in this row an column as being * NOT value */ for (j=0;j<9;j++) { if (row == j) continue; if (value == io_grid->cells[j][i].value) { errors++; break; } if (io_grid->cells[j][i].value) continue; if ((io_grid->cells[j][i].flags & not_val) == 0) { io_grid->cells[j][i].flags |= not_val; io_grid->cells[j][i].remain--; assert(io_grid->cells[j][i].remain); } } if (0 == errors) { j = row; for (i=0; i< 9; i++) { if (col == i) continue; if (value == io_grid->cells[j][i].value) { errors++; break; } if (io_grid->cells[j][i].value) continue; if ((io_grid->cells[j][i].flags & not_val) == 0) { io_grid->cells[j][i].flags |= not_val; io_grid->cells[j][i].remain--; assert(io_grid->cells[j][i].remain); } } } /* Now do the same for the mini-grid */ if (0 == errors) { x = row / 3; y = col / 3; x = x * 3; y = y * 3; for (j = x; j < (x+3); j++) { for (i = y; i < (y+3); i++) { if ((j == row) && (i == col)) continue; if (value == io_grid->cells[j][i].value) { errors++; break; } if (io_grid->cells[j][i].value) continue; if ((io_grid->cells[j][i].flags & not_val) == 0) { io_grid->cells[j][i].flags |= not_val; io_grid->cells[j][i].remain--; assert(io_grid->cells[j][i].remain); } } } } if (errors) return errors; return errors; } /* int readgrid(void) puts the initial grid into start_grid, returns error */ static int readgrid() { char input[99]; ssize_t red_size = 0; /* read, red, red :-p */ int errors = 0; int crlf = 0; int i,j,x; do { red_size = 90; read_input(&input, &red_size); if (red_size != 90) { debug1("red_size != 90 - %d\n",red_size); errors++; break; } if ((input[9] != '\r') && (input[9] != '\n')) { debug("((input[9] != '\r') && (input[9] != '\n')) \n"); errors++; break; } if ((input[9] == '\r') && (input[10] == '\n')) { /* CRLF endings, need to read more chars */ red_size = 9; read_input(&input[90],&red_size); if (red_size != 9) { debug("red_size != 9\n"); errors++; break; } crlf = 1; } x = 0; for (j=0;j<9;j++) { for (i=0;i<9;i++) { start_grid.cells[j][i].remain = 9; start_grid.cells[j][i].flags = 0; start_grid.cells[j][i].value = input[x] -'0'; if ((start_grid.cells[j][i].value < 0) || (start_grid.cells[j][i].value > 9)) { debug("input[(j*9)+i] > 9\n"); errors++; break; } if (start_grid.cells[j][i].value > 0) { start_grid.cells[j][i].remain = 0; } x++; } if (errors) break; if ((input[x] != '\n') && ((input[x] != '\r') || ((input[x] =='\r' && crlf == 1 && input[x+1] !='\n')))) { debug1("crs in wrong place %d\n",x); errors++; break; } x++; x += crlf; if (errors) break; } for (j=0;j<9;j++) { for (i=0;i<9;i++) { if (start_grid.cells[j][i].value > 0) { if (update_cells(&start_grid,j,i)) { errors++; break; } } } } } while (0); return errors; } int main(int argc, const char *argv[]) { int errors=0; int solved=0; int i,j; if (argc > 1) { fprintf(stderr,"This program does not accept arguments.\n"); fprintf(stderr,"Usage - %s\n",argv[0]); fprintf(stderr,"And then enter the grid. 0 for blanks.\n"); return 1; } errors=readgrid(); if (errors) { fprintf(stderr,"Invalid Input\n"); return 1; } solved = solve_grid(&start_grid); if (!solved) { fprintf(stderr,"Can not solve this puzzle. Sorry.\n"); return 1; } for (j = 0; j < 9; j++) { for (i = 0; i < 9; i++) { putchar(start_grid.cells[j][i].value + '0'); } putchar('\n'); } return 0; }