SUDOKU
It's a classic puzzle game that can be seen on your local newspaper. For those who (somehow) do not know the rules, it is as follow: Fill in the grid with digits 1-9 one each in each row, column and 3x3 box. The rules are that simple, yet sometimes, it can be mind-bogglingly hard to solve any of them. So, I came up with a plan ... just bruteforce it. If we can just try each number individually and checked if that number breaks the rule, we will reach the solution ... eventually.
But a human doing that is not quite possible. As there are 10^21 ways to arrange the digits in the Sudoku grid, that would take a very long time. So, after taking a sneak peak at Recursion, I got a "slave" to do it for me, the computer:
#include <iostream>
using namespace std;
bool checkValid(int grid[9][9], int row, int col, int val)
{
for (int i = 0; i < 9; i++){
if (grid[i][col] == val)
return false;
}
for (int i = 0; i < 9; i++){
if (grid[row][i] == val)
return false;
}
int rowBox = row - row % 3;
int colBox = col - col % 3;
int temp1 = rowBox + 3;
int temp2 = colBox + 3;
for (int i = 0; rowBox < temp1; rowBox++)
for (int j = 0; colBox < temp2; colBox++)
if (grid[rowBox][colBox] == val)
return false;
return true;
}
bool Solve(int grid[9][9], int row, int col)
{
if (row == 8 && col == 9) return true;
if (col == 9){
row++;
col = 0;
}
if (grid[row][col] != 0)
return Solve(grid, row, col + 1);
for (int i = 1; i <= 9; i++){
if (checkValid(grid,row,col,i)){
grid[row][col] = i;
if (Solve(grid,row,col+1)) return true;
}
grid[row][col] = 0;
}
return false;
}
int main()
{
int grid[9][9];
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
cin >> grid[i][j];
if (Solve(grid,0,0)){
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++)
cout << grid[i][j]<<" ";
cout << endl;
}
}
return 0;
}
Though this can only find the first solution that pops up, it's already beter than me in term of Sudoku-solving capabilities. By using a concept that uses Recursion called Backtracking, it will go through all combination and retrace its footsteps when a number it tries break the rules. Fairly straightforward, I would say!
However, it cannot guarantee that that would be the only possible solution. I have tried to reverse the order of checking from 1->9 to 9->1, but to put both of them into the same algorithm does not seem to work properly and that can only also bring the maximum amount of solutions to 2. Although, I can check for the "uniqueness" of a Sudoku, where it can only be called a Sudoku puzzle when there is only one unique solution, I would have to do that ... manually... by changing the order of number-checked by hand and see if the 2 grids are different. That is very dull as the ultimate goal of an algorithm is to do it in one go. I've got a few ideas using vectors but the bugs bugged me so here I am, asking for help.
P.S: Also, my 3x3-box-checking codes in checkValid() seemed bad so I need some advices on that.
REFERENCE:
GeeksforGeeks
Good'ol Indian Man on YT
SUDOKU YT CHANNEL THAT GOT ME TO WRITE THIS
Top comments (0)