# 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.

![](http://i.imgur.com/czECoDH.png)

![](http://i.imgur.com/qCACuD2.png)

* 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.

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/37_sudoku_solver.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.