Project 2 || Wong Edition || C++ Project || B.Tech Diaries

Project #2 - Sudoku (in conjunction with Algorithm project)

Implement the Sudoku game and the backtracking algorithm using functions from the STL's: <stack>, <pair>.

Solution:

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

const int N = 9, EMPTY = 0;

class Sudoku
{
private:
    std::vector<std::vector<int>> table;

public:
    Sudoku(std::string filename)
    {
        table.resize(N);
        for (int i = 0; i < N; i++)
        {
            table[i].resize(N);
        }
        get_pattern(filename);
    }

    ~Sudoku() {}

    void get_pattern(std::string filename)
    {
        std::ifstream infile;
        char n;
        int c = 0;
        infile.open(filename);
        while (infile >> n)
        {
            table[c / N][c % N] = n - '0';
            c++;
        }
        infile.close();
    }

    bool is_safe(int row, int col, int num)
    {
        int i, j;

        // Check if the number is already present in the row
        for (i = 0; i < N; i++)
            if (table[row][i] == num || table[i][col] == num)
                return false;

        // Check if the number is already present in the box
        int boxRow = row - row % 3;
        int boxCol = col - col % 3;
        for (i = boxRow; i < boxRow + 3; i++)
            for (j = boxCol; j < boxCol + 3; j++)
                if (table[i][j] == num)
                    return false;

        // If we reach here, it is safe to place the number in the given cell
        return true;
    }

    bool solve()
    {
        std::stack<std::pair<int, int>> st;

        // Find the first empty cell in the grid
        int row = -1, col = -1, r, c, num;
        for (r = 0; r < N; r++)
        {
            for (c = 0; c < N; c++)
            {
                if (table[r][c] == EMPTY)
                {
                    row = r, col = c;
                    break;
                }
            }
            if (row != -1)
                break;
        }

        // If there are no more empty cells, we have solved the puzzle
        if (row == -1)
        {
            return true;
        }

        // Push the first empty cell onto the stack
        st.push({row, col});

        while (!st.empty())
        {
            // Get next empty cell
            std::pair<int, int> p = st.top();
            st.pop();
            row = p.first, col = p.second;

            // Try each number from 1 to 9
            for (num = 1; num <= 9; num++)
            {
                if (is_safe(row, col, num))
                {
                    // Fill cell with number and continue solving
                    table[row][col] = num;
                    if (solve())
                        return true;

                    // Backtrack
                    table[row][col] = EMPTY;
                }
            }
            // No number worked, backtrack
            st.push(p);
            return false;
        }
        return true;
    }
    void print()
    {
        int r, c;
        for (r = 0; r < N; r++)
        {
            for (c = 0; c < N; c++)
            {
                std::cout << table[r][c] << " ";
            }
            std::cout << std::endl;
        }
    }
};

int main(int argc, char const *argv[])
{
    Sudoku s("sudoku_pattern/pattern01.txt");
    std::cout<<"Problem: "<<std::endl;
    s.print();

    std::cout<<"Solution: "<<std::endl;
    if (s.solve())
        s.print();
    else
        std::cout << "No solution" << std::endl;

    return 0;
}

Input (sudoku_pattern/pattern01.txt):

0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0

Output:

Problem: 
0 0 3 0 2 0 6 0 0
9 0 0 3 0 5 0 0 1
0 0 1 8 0 6 4 0 0
0 0 8 1 0 2 9 0 0
7 0 0 0 0 0 0 0 8
0 0 6 7 0 8 2 0 0
0 0 2 6 0 9 5 0 0
8 0 0 2 0 3 0 0 9
0 0 5 0 1 0 3 0 0
Solution:
4 8 3 9 2 1 6 5 7
9 6 7 3 4 5 8 2 1
2 5 1 8 7 6 4 9 3
5 4 8 1 3 2 9 7 6
7 2 9 5 6 4 1 3 8
1 3 6 7 9 8 2 4 5
3 7 2 6 8 9 5 1 4
8 1 4 2 5 3 7 6 9
6 9 5 4 1 7 3 8 2