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