Simple Sudoku Solver

Question

i have made a simple sudoku solver which is a puzzle game where the player has to figure out the empty cell and checks which numbers are absent from the corresponding row, column.

how can I improve it further?

#include <iostream>

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    for (int i = 0; i<9; ++i)
    {
        if (puzzle[row][i] == num) return 0;
        if (puzzle[i][col] == num) return 0;
    }
    return 1;
}

int solveSudoku(int puzzle[][9], int row, int col)
{
    if (row<9 && col<9)
    {
        if (puzzle[row][col] != 0)
        {
            if ((col + 1)<9) return solveSudoku(puzzle, row, col + 1);
            else if ((row + 1)<9) return solveSudoku(puzzle, row + 1, 0);
            else return 1;
        }
        else
        {
            for (int i = 0; i<9; ++i)
            {
                if (isAvailable(puzzle, row, col, i + 1))
                {
                    puzzle[row][col] = i + 1;
                    if ((col + 1)<9)
                    {
                        if (solveSudoku(puzzle, row, col + 1)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else if ((row + 1)<9)
                    {
                        if (solveSudoku(puzzle, row + 1, 0)) return 1;
                        else puzzle[row][col] = 0;
                    }
                    else return 1;
                }
            }
        }
        return 0;
    }
    else return 1;
}

void printSudoku(int puzzle[9][9])
{
    for (int i = 0; i<9; ++i)
    {
        for (int j = 0; j<9; ++j) {
            std::cout << puzzle[i][j] << " ";
        }
        std::cout << "\n";
    }
}

int main()
{
    int puzzle[9][9] = { 
    { 3, 0, 6, 5, 0, 8, 4, 0, 0 },
    { 5, 2, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 8, 7, 0, 0, 0, 0, 3, 1 },
    { 0, 0, 3, 0, 1, 0, 0, 8, 0 },
    { 9, 0, 0, 8, 6, 3, 0, 0, 5 },
    { 0, 5, 0, 0, 9, 0, 6, 0, 0 },
    { 1, 3, 0, 0, 0, 0, 2, 5, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 7, 4 },
    { 0, 0, 5, 2, 0, 6, 3, 0, 0 } };

    solveSudoku(puzzle, 0, 0);
    printSudoku(puzzle);
}

Answer 1

Your isAvailable() is wrong.

You check if a number is within the row or col. But you also need to check if it is within the same (3*3) square.

int isAvailable(int puzzle[][9], int row, int col, int num)
{
    int sqCol = col % 3 * 3;
    int sqRow = row % 3 * 3;
    for (int i = 0; i<9; ++i)
    {
        if (puzzle[row][i] == num) return 0;
        if (puzzle[i][col] == num) return 0;

        // You need to add this test.
        if (puzzle[sqRow + (i % 3)][sqCol + (i / 3)] == num) return 0;
    }
    return 1;
}

Rather than having you loop from 0 and then using i+1 why not loop from 1?

for (int i = 0; i<9; ++i)

// I would just do 
for (int i = 1; i<=9; ++i)
     Now intuitively use i

Your test for reaching the end of line and end of col is in several places. Rather than test on the call. Just increment the col and handle overflow at the top of the function (in one place). This will greately simplify the whole thing.

int solveSudoku(int puzzle[][9], int row, int col)
{
    if (col == 9) {
        col = 0;
        row++;
    }
    if (row == 9) {
        return 1;
    }

    if (puzzle[row][col] != 0) {
        return solveSudoku(puzzle, row, col + 1);
    }

    for (int i = 1; i <= 9; ++i)
    {
        if (isAvailable(puzzle, row, col, i))
        {
            puzzle[row][col] = i;
            if (solveSudoku(puzzle, row, col + 1))
                return 1;
            }
        }
    }
    puzzle[row][col] = 0;
    return 0;
}

Answer 2

int isAvailable(int puzzle[][9], int row, int col, int num)
int solveSudoku(int puzzle[][9], int row, int col)
void printSudoku(int puzzle[9][9])

Passing built in arrays as parameters actually just pass a pointer. Declaring functions like this, even if you understand how it works, is poor practice.

If you declare

using puzzle_grid = std::array<std::array<int,3>,3>;

then you an declare:

void foo (const puzzle_grid& puzzle)

It also lets you use a range-for loop for the kind of access used in the printSudoku function.

However, your code to access each position in a systematic mannner (rows, cols, diag, box) is inefficient. As I pointed out in the tic-tac-toe answer recently, you can declare a linear array and multiply the rows and columns out yourself for single position access, but use single additions of a stride to navigate your pattern.

(actually, the stride probably works even if you declare the array as 2D as you have it. I’m not sure that’s completely proper though)

Then you can have a single predicate which takes a starting point and a stride and does the loop of nine comparisons; this one function will cover rows, columns, and diagonals, efficiently.

---

It appears as though the return type for solveSudoku wants to be bool, not int. But you’re never checking the result anyway.