DEV Community

Cover image for DILI #6.5(Recursive Sudoku)
DHDucky
DHDucky

Posted on

DILI #6.5(Recursive Sudoku)

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;
}

Enter fullscreen mode Exit fullscreen mode

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)