/* * CSE 303, Autumn 2006, Assignment 3, Problem 1 * * You must modify this program as described in the assignment. */ #include #include #include #include /* * Recursively solve the given Soduku puzzle by guessing * values for the current cell and continuing on to guess * remaining cells. Return true when the puzzle is solved. * * The first call to this function * should be for row=0 and col=0. The function will * proceed through each column in a row before moving * to the next row. If col>8, then wrap around to the * next row. If row>8 (after wraping to the next row) * the then assume that the puzzle has been solved and * return true. * * A value of zero in a cell means that a choice has not * yet been made for that cell. * */ bool solve(int puzzle[][9], int row, int col) { // Handle wrap-around of arguments if (col > 8) { col = 0; row = row + 1; } if (row > 8) return true; // If this cell has already been set, go to next if (puzzle[row][col] != 0) { return solve(puzzle,row,col+1); } // Find a number that is not present in this row/column // and attemt to solve the puzzle with that choice int guess, i; for (guess=1; guess<=9; guess++) { // Check to see if this guess is valid bool found = false; for (i=0; i<9; i++) { // Does this guess appear anywhere else in this row? if (puzzle[row][i] == guess) { found = true; break; } // Does this guess appear anywhere else in this column? if (puzzle[i][col] == guess) { found = true; break; } // Does this guess appear anywhere else in this 3x3 box? int boxRow = (row/3)*3; int boxCol = (col/3)*3; if (puzzle[boxRow+(i/3)][boxCol+(i%3)] == guess) { found = true; break; } } // Put this guess in the puzzle and attempt to solve the rest if (found) { continue; } else { puzzle[row][col] = guess; if (solve(puzzle,row,col+1)) return true; else continue; } } // If we get here, then we can't solve. Give up. puzzle[row][col] = 0; return false; } int main(int argc, char *argv[]) { int puzzle[9][9]; // The puzzle data structure int i; // Iteration variable // Read in the puzzle for (i=0; i<9; i++) { if (i%3 == 0) scanf("-------------------------\n"); int matches = scanf("| %d %d %d | %d %d %d | %d %d %d |\n", &puzzle[i][0], &puzzle[i][1], &puzzle[i][2], &puzzle[i][3], &puzzle[i][4], &puzzle[i][5], &puzzle[i][6], &puzzle[i][7], &puzzle[i][8]); if (matches != 9) { fprintf(stderr, "%s: input not in expected format\n",argv[0]); return 1; } } // Solve the puzzle solve(puzzle,0,0); // Print a message with today's time time_t today = time(NULL); char message[] = "Soduku: XXX XXX XX XX:XX:XX XXXX"; memcpy(message+8, ctime(&today), 24); puts(message); // Read in the puzzle for (i=0; i<9; i++) { if (i%3 == 0) printf("-------------------------\n"); printf("| %d %d %d | %d %d %d | %d %d %d |\n", puzzle[i][0], puzzle[i][1], puzzle[i][2], puzzle[i][3], puzzle[i][4], puzzle[i][5], puzzle[i][6], puzzle[i][7], puzzle[i][8]); } printf("-------------------------\n"); return 0; }