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