37 Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.
  • The Algorithm:
    • For every row and column element, check for the possibility of a solution
    • A solution exist if there is single existing solution
      • We check this by using a hash set; set it up to contain elements 1 through 9. For every matrix element, remove all the elements in the hash set that are in said row, column, and 3x3 square of the matrix element
      • If the hash set contains 1 element, return said element.
      • Otherwise, move on to the next matrix element.
    • Continue looping through the board matrix using the solutions of previous solutions until the entirity of the matrix is filled.
  • Flaws:
    • This algorithm doesnt not work with all sudoku boards! It only works when the algorithm itself eliminates all possible elements on the board with 100% certainty. I need to modify it to handle the cases when there are 2 or 3 elements remaining in the hash set, and pick a route to see if it works. Or something like that.
pair<int, int> find_quad(int row, int col) {
pair<int, int> p;
for (int i = 0; i <= 6; i += 3) {
for (int j = 0; j <= 6; j += 3) {
if (row >= i && row <= i + 2) {
if (col >= j && col <= j + 2) {
return p = make_pair(i, j);
}
}
}
}
}
void getSolution(vector<vector<char>> &board, int row, int col) {
unordered_set<char> hash_set = { '1','2','3','4','5','6','7','8','9' };
// remove row elements - row element stays constant
for (int i = 0; i < 9; i++) {
if (board.at(row).at(i) == '.') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(row).at(i) << " ";
//pause();
auto &found = hash_set.find(board.at(row).at(i));
if (found != hash_set.end()) {
// found
hash_set.erase(found);
}
}
// remove column elements - column elements stay constant
for (int i = 0; i < 9; i++) {
if (board.at(i).at(col) == '.') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(i).at(col) << " ";
//pause();
auto &found = hash_set.find(board.at(i).at(col));
if (found != hash_set.end()) {
// found
hash_set.erase(found);
}
}
// remove 3x3 elements
pair<int, int> quad = find_quad(row, col);
for (int i = quad.first; i < quad.first + 3; i++) {
for (int j = quad.second; j < quad.second + 3; j++) {
if (board.at(i).at(j) == '.') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(i).at(j) << " ";
//pause();
auto &found = hash_set.find(board.at(i).at(j));
if (found != hash_set.end()) {
// found
hash_set.erase(found);
}
}
}
//cout << endl;
//for (auto i : hash_set) {
// cout << i << " ";
//}
}
void solveSudoku(vector<vector<char>>& board) {
bool finished = false;
while (!finished) {
finished = true;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.at(i).size(); j++) {
if (board.at(i).at(j) == '.') {
getSolution(board, i, j);
finished = false;
//print2d(board);
}
}
}
}
}
int main() {
// fails
vector<vector<char>> board = {
{ '.', '.','9', '7','4','8', '.','.','.', },
{ '7', '.','.', '.','.','.', '.','.','.', },
{ '.', '2','.', '1','.','9', '.','.','.', },
{ '.', '.','7', '.','.','.', '2','4','.', },
{ '.', '6','4', '.','1','.', '5','9','.', },
{ '.', '9','8', '.','.','.', '3','.','.', },
{ '.', '.','.', '8','.','3', '2','.','.', },
{ '.', '.','.', '.','.','.', '.','.','6', },
{ '.', '.','.', '2','7','5', '9','.','.', },
};
print2d(board);
solveSudoku(board);
print2d(board);
// works
board = {
{ '5', '3','.', '.', '7', '.', '.', '.', '.', },
{ '6', '.','.', '1', '9', '5', '.', '.', '.', },
{ '.', '9','8', '.', '.', '.', '.', '6', '.', },
{ '8', '.','.', '.', '6', '.', '.', '.', '3', },
{ '4', '.','6', '8', '.', '3', '.', '.', '1', },
{ '7', '.','.', '.', '2', '.', '.', '.', '6', },
{ '.', '6','.', '.', '.', '.', '2', '8', '.', },
{ '.', '.','.', '4', '1', '9', '.', '.', '5', },
{ '.', '.','.', '.', '8', '.', '.', '7', '9', },
};
print2d(board);
solveSudoku(board);
print2d(board);
}
Via Command Line
input.txt
5 3 x x 7 x x x x
6 x x 1 9 5 x x x
x 9 8 x x x x 6 x
8 x x x 6 x x x 3
4 x x 8 x 3 x x 1
7 x x x 2 x x x 6
x 6 x x x x 2 8 x
x x x 4 1 9 x x 5
x x x x 8 x x 7 9
inline void pause()
{
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
template<typename T>
inline void print2d(vector<vector<T>> &stuffs) {
cout << endl;
for (auto i : stuffs) {
for (auto j : i)
cout << setw(2) << j << " ";
cout << endl;
}
cout << endl;
pause();
}
pair<int, int> find_quad(int row, int col) {
pair<int, int> p;
for (int i = 0; i <= 6; i += 3) {
for (int j = 0; j <= 6; j += 3) {
if (row >= i && row <= i + 2) {
if (col >= j && col <= j + 2) {
return p = make_pair(i, j);
}
}
}
}
}
void getSolution(vector<vector<char>> &board, int row, int col) {
unordered_set<char> hash_set = { '1','2','3','4','5','6','7','8','9' };
// remove row elements - row element stays constant
for (int i = 0; i < 9; i++) {
if (board.at(row).at(i) == 'x') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(row).at(i) << " ";
//pause();
//auto &found = hash_set.find(board.at(row).at(i));
if (hash_set.find(board.at(row).at(i)) != hash_set.end()) {
// found
hash_set.erase(hash_set.find(board.at(row).at(i)));
}
}
// remove column elements - column elements stay constant
for (int i = 0; i < 9; i++) {
if (board.at(i).at(col) == 'x') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(i).at(col) << " ";
//pause();
//auto &found = hash_set.find(board.at(i).at(col));
if (hash_set.find(board.at(i).at(col)) != hash_set.end()) {
// found
hash_set.erase(hash_set.find(board.at(i).at(col)));
}
}
// remove 3x3 elements
pair<int, int> quad = find_quad(row, col);
for (int i = quad.first; i < quad.first + 3; i++) {
for (int j = quad.second; j < quad.second + 3; j++) {
if (board.at(i).at(j) == 'x') continue;
// check if hash set has one element
if (hash_set.size() == 1) {
board.at(row).at(col) = *hash_set.begin();
return;
}
//cout << board.at(i).at(j) << " ";
//pause();
//auto &found = hash_set.find(board.at(i).at(j));
if (hash_set.find(board.at(i).at(j)) != hash_set.end()) {
// found
hash_set.erase(hash_set.find(board.at(i).at(j)));
}
}
}
//cout << endl;
//for (auto i : hash_set) {
// cout << i << " ";
//}
}
void solveSudoku(vector<vector<char>>& board) {
bool finished = false;
while (!finished) {
finished = true;
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board.at(i).size(); j++) {
if (board.at(i).at(j) == 'x') {
getSolution(board, i, j);
finished = false;
//print2d(board);
}
}
}
}
}
vector<vector<char>> processFile(char *myfile) {
vector<vector<char>> board;
vector<char> temp;
ifstream file(myfile);
string str;
while (std::getline(file, str)) {
for (int i = 0; i < str.length(); i++) {
if (str.at(i) == ' ') continue;
else {
temp.push_back(str.at(i));
}
}
board.push_back(temp);
temp.clear();
}
return board;
}
int main(int argc, char** argv) {
vector<vector<char>> board = processFile(argv[1]);
print2d(board);
solveSudoku(board);
print2d(board);
}