/** * Author: Xan * Date: 21st April 2018 * * Sudoku solver - this uses a very naive and simplistic approach, and will * therefore fail for some puzzles. I'm hoping to improve the algorithm * later, to make it better. * * TODO: * - Add Gordie's suggestion about the * display. See comment Gordie made. (DONE) * - Improve solving algorithm. * * NEXT SUDOKU PROJECT: * - Do an AI that solves sudoku, using * something fun like an evolutionary * method. */ #include #include void knock_out_horizontal_clashes(int y, int possibles[9], int sudoku[9][9]) { for (int i = 0; i < 9; i++) { int get_value = sudoku[y][i]; if (get_value != 0) { possibles[get_value - 1] = 0; } } } void knock_out_vertical_clashes(int x, int possibles[9], int sudoku[9][9]) { for (int j = 0; j < 9; j++) { int get_value = sudoku[j][x]; if (get_value != 0) { possibles[get_value - 1] = 0; } } } void knock_out_same_square(int x, int y, int possibles[9], int sudoku[9][9]) { // (i, j) is the top left of the square (x, y) is in. int i = x - (x % 3) ; int j = y - (y % 3); for (int k = 0; k < 3; k++) { for (int p = 0; p < 3; p++) { int get_value = sudoku[j + k][i + p]; if (get_value != 0) { possibles[get_value - 1] = 0; } } } } // Top left = (0, 0) void calculate_possible_values(int x, int y, int sudoku[9][9], int possibles[9]) { int value = sudoku[y][x]; for (int z = 0; z < 9; z++) { possibles[z] = 1; } if (value == 0) { knock_out_horizontal_clashes(y, possibles, sudoku); knock_out_vertical_clashes(x, possibles, sudoku); knock_out_same_square(x, y, possibles, sudoku); } } void run_once(int sudoku[9][9], int possibles[9]) { for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) { calculate_possible_values(x, y, sudoku, possibles); int possibilities = 0; int value_found = 0; for (int k = 0; k < 9; k++) { if (possibles[k] != 0) { possibilities++; value_found = k; } } if (possibilities == 1) { sudoku[y][x] = value_found + 1; } } } } // Display code inspired by Gordie's ideas // on displaying in a prettier way. // Thanks Gordie! void display_board(int sudoku[9][9]) { for (int y = 0; y < 9; y++) { if (y % 3 == 0) { if ( (y == 3 || y == 6) ) { printf(":---------+---------+---------:\n"); } else { printf(".---------.---------.---------.\n"); } } else { printf("| | | |\n"); } for (int x = 0; x < 9; x++) { if (x % 3 == 0) { printf("|"); } int value = sudoku[y][x]; if (value == 0) { printf(" . "); } else { printf(" %d ", value); } } printf("|\n"); } printf("'---------'---------'---------'\n"); } int has_won(int sudoku[9][9]) { for (int y = 0; y < 9; y++) { for (int x = 0; x < 9; x++) { if (sudoku[y][x] == 0) { return false; } } } return true; } int main() { // https://www.websudoku.com/?level=1&set_id=7924352959 int sudoku_easy[9][9] = { /********************************/ {9, 8, 3,/**/6, 0, 0,/**/0, 0, 0}, {0, 7, 4,/**/0, 0, 0,/**/9, 2, 0}, {2, 0, 0,/**/7, 0, 4,/**/0, 3, 0}, /********************************/ {4, 0, 8,/**/0, 2, 0,/**/0, 5, 7}, {0, 0, 0,/**/1, 0, 5,/**/0, 0, 0}, {1, 9, 0,/**/0, 7, 0,/**/3, 0, 2}, /********************************/ {0, 4, 0,/**/3, 0, 7,/**/0, 0, 6}, {0, 3, 2,/**/0, 0, 0,/**/7, 9, 0}, {0, 0, 0,/**/0, 0, 9,/**/5, 8, 3} /********************************/ }; // Blank board. //int sudoku_blank[9][9] = //{ // /********************************/ // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // /********************************/ // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // /********************************/ // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0}, // {0, 0, 0,/**/0, 0, 0,/**/0, 0, 0} // /********************************/ //}; // It won't work on this one: // https://www.websudoku.com/?level=4&set_id=5697322189 //int sudoku_evil[9][9] = //{ // /********************************/ // {0, 0, 0,/**/0, 9, 0,/**/1, 0, 4}, // {0, 3, 0,/**/4, 0, 0,/**/0, 0, 8}, // {0, 9, 0,/**/3, 0, 0,/**/0, 0, 0}, // /********************************/ // {0, 0, 8,/**/0, 1, 0,/**/0, 0, 0}, // {0, 7, 3,/**/0, 0, 0,/**/8, 2, 0}, // {0, 0, 0,/**/0, 5, 0,/**/7, 0, 0}, // /********************************/ // {0, 0, 0,/**/0, 0, 4,/**/0, 9, 0}, // {6, 0, 0,/**/0, 0, 2,/**/0, 1, 0}, // {9, 0, 5,/**/0, 3, 0,/**/0, 0, 0} // /********************************/ //}; int num_tries = 81; int possibles[9]; printf("S U D O K U S O L V E R\n"); printf("=========================\n"); printf("\nStarting Board:\n"); display_board(sudoku_easy); while (num_tries > 0 && !has_won(sudoku_easy)) { run_once(sudoku_easy, possibles); num_tries--; } printf("\nFinal Board:\n"); display_board(sudoku_easy); printf("\nThanks to Gordie for inspiring me on the board display code.\n"); return 0; }

Sudoku (Basic Solver)