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);
}
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);
}
