#include #include #include #include #include void write_sudoku(const char* path, int grid[]) { int fd = open(path, O_RDWR | O_CREAT, 0700); if(fd == -1) { perror("open"); exit(1); } write(fd, grid, 81*sizeof(int)); close(fd); } void read_sudoku(const char* path, int grid[]) { int fd = open(path, O_RDONLY); if(fd == -1) { perror("open"); exit(1); } read(fd, grid, 81*sizeof(int)); close(fd); } void print_sudoku(int grid[]) { for(int i=0; i<9; i++) { if(i % 3 == 0) printf("-------------------------\n"); for(int j=0; j<9; j++) { if(j % 3 == 0) printf("| "); if(grid[i*9 + j] == 0) printf(". "); else printf("%d ", grid[i*9 + j]); } printf("|\n"); } printf("-------------------------\n"); } bool is_line_valid(int grid[], int cur) { int line = cur / 9; int col = cur % 9; for(int i=0; i<9; i++) if(i != col && grid[line * 9 + i] == grid[cur]) return false; return true; } bool is_col_valid(int grid[], int cur) { int line = cur / 9; int col = cur % 9; for(int i=0; i<9; i++) if(i != line && grid[i * 9 + col] == grid[cur]) return false; return true; } bool is_square_valid(int grid[], int cur) { int line = cur / 9; int col = cur % 9; for(int i=0; i<3; i++) for(int j=0; j<3; j++) { int target = 9 * (((line / 3) * 3) + i) + (col / 3) * 3 + j; if(target != cur && grid[target] == grid[cur]) return false; } return true; } bool is_valid(int grid[], int cur) { return is_line_valid(grid, cur) && is_col_valid(grid, cur) && is_square_valid(grid, cur); } bool solve_sudoku(int grid[]) { bool fixed[81]; // memorize which cell contains a fixed value for(int i=0; i<81; i++) fixed[i] = grid[i] != 0; // start from the beginning int cur = 0; while(cur >= 0 && cur < 81) { if(fixed[cur]) // don't try to modify a fixed point cur++; else { grid[cur]++; //printf("# grid[%d][%d] <- %d\n", cur / 9, cur % 9, grid[cur]); if(grid[cur] == 10) { // we made a bad choice earlier grid[cur] = 0; // so we reinitialize this cell for(--cur; cur>=0 && fixed[cur]; cur--) {} // and we backtrack //printf("# backtrack to grid[%d][%d] (%d)\n", cur / 9, cur % 9, grid[cur]); } else if(is_valid(grid, cur)) cur++; } } return cur == 81; // we were able to solve the sudoku, yipeah! } int main(int argc, char* argv[]) { if(argc != 2) { fprintf(stderr, "Usage: %s file-name\n", argv[0]); return 1; } int grid[81]; read_sudoku(argv[1], grid); print_sudoku(grid); print_sudoku(grid); return 0; if(solve_sudoku(grid)) print_sudoku(grid); else printf("No solution\n"); return 0; }