I am working on an optimized Sudoku solver. The basic idea of backtracking remains, though I have added forward checking. The domain (what numbers can be set into a cell) is stored for every cell. Before I try to set a number into a cell and backtrack if it doesn't work, I check all the related cells to see if the number is the only one that could be set there. If a conflict occurs, I try the next number, and so on. Optimally, this reduces the amount of backtracking necessary.
However, my code is unfortunately not working properly. I would greatly appreciate your help.
Best regards
Eric
Code:
#include <iostream>
#include <bitset>
#include <array>
using namespace std;
#define n 9
void print_board(int board[n][n]);
bool solve(array<bitset<n>, n * n> &domains, int board[n][n], int i = 0, int j = 0);
void initialize_domains(array<bitset<n>, n * n> &domains, int board[n][n]);
bool update_domains(array<bitset<n>, n * n> &domains, int board[n][n], int i, int j, int k);
std::bitset<n> reverse_bits(const std::bitset<n> &bitset)
{
std::bitset<n> reversed;
for (int i = 0; i < n; ++i)
{
reversed[i] = bitset[n - 1 - i]; // Sets the i-th bit in reversed to the (N-1-i)-th bit in bitset
}
return reversed;
}
void printDomains(const std::array<std::bitset<n>, n * n> &domains)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
std::cout << "Domain for cell (" << i << ", " << j << "): " << reverse_bits(domains[i * n + j]) << std::endl;
}
}
}
int main() // main function handles the flow of the program
{
int board[n][n] = {// definition of the initial board
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}};
std::array<std::bitset<n>, n * n> domains;
initialize_domains(domains, board);
print_board(board);
solve(domains, board);
cout << "\n";
print_board(board);
}
void print_board(int board[n][n]) // displays the Sudoku board
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cout << board[i][j] << " ";
}
cout << "\n";
}
}
// starting from the cell of a cell, update the domains of the influenced cells
bool update_domains(std::array<std::bitset<n>, n * n> &domains, int board[n][n], int i, int j, int k)
{
for (int a = 0; a < n; ++a)
{
domains[i * n + a].set(k - 1); // row
domains[j + n * a].set(k - 1); // column
// If it's no longer possible to place a number in the cell
if (domains[i * n + a].all() && board[i][a] == 0)
return false;
if (domains[j + n * a].all() && board[a][j] == 0)
return false;
}
for (int row = (i / 3) * 3; row < ((i / 3) * 3) + 3; ++row)
{
for (int col = (j / 3) * 3; col < ((j / 3) * 3) + 3; ++col)
{
domains[row * n + col].set(k - 1); // subgrid
if (domains[row * n + col].all() && board[row][col] == 0)
return false;
}
}
return true;
}
// 0 = possible to place the number
// 1 = not possible to place the number
void initialize_domains(array<bitset<n>, n * n> &domains, int board[n][n])
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] != 0)
update_domains(domains, board, i, j, board[i][j]);
}
}
}
// i specifies the row
// j specifies the column
bool solve(array<bitset<n>, n * n> &domains, int board[n][n], int i, int j) // responsible for solving the Sudoku using brute-force backtracking
{
if (i == n) // if all rows and thus all columns are successfully filled, the Sudoku is solved
return true;
if (j == n) // if the column index exceeds the dimension, the first cell of the next row must be considered
return solve(domains, board, i + 1, 0);
if (board[i][j] != 0) // if there is no empty cell at the current position, move to the next position
return solve(domains, board, i, j + 1);
for (int k = 1; k <= n; ++k) // all valid numbers from 1-9 are tried linearly
{
if (domains[i * n + j].test(k - 1)) // if the number is not in the domain of the current cell, it can be skipped
continue;
array<bitset<n>, n * n> pre_updated_domain = domains;
if (update_domains(domains, board, i, j, k)) // no conflict
{
board[i][j] = k; // the supposedly valid number is tried
if (solve(domains, board, i, j + 1)) // if no further conflicts arise, this is the correct solution
return true;
board[i][j] = 0;
}
// if the number leads to a conflict (in an influenced cell, no number can be placed anymore), it will not be used
domains = pre_updated_domain;
}
return false; // if none of the n numbers is valid, a conflict has occurred
}
My current is outcome i the following:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9
I have expected:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9
What I see as the blocking point is that the update_domains(...) function blocks exploring the possibilities because
Because of that, your code currently never can end filling even the first line : it supposes that the board is updated but it's not the case in when you call it in solve()
So, move the board[i][j] = k; before if(update_domains... and move the board[i][j] = 0; accordingly
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9