# Share my simple c++ code with using unsorted_set

• ``````class Solution {
public:
bool dfs(vector<vector<char>>& board, int i, int j)
{
while(i<=8 && j<=8 && board[i][j] != '.')//find next empty cell
{
if(j==8)                //find empty cell in next row
{
j=0;
++i;
}
else if(j<8)            // find empty cell in next col
++j;
}

if(i==9)                // i==9 means all the cells are filled
return true;
char n;
int x = i / 3;
int y = j / 3;
for(int k=1; k<=9; ++k)
{
n = k+'0';          // enumerate all possible digit
if(row[i].find(n) == row[i].end() && col[j].find(n) == col[j].end() && cell[x][y].find(n) == cell[x][y].end())
{
row[i].insert(n);
col[j].insert(n);
cell[x][y].insert(n);
board[i][j] = n;
if(dfs(board,i,j))
return true;
else
{
row[i].erase(n);
col[j].erase(n);
cell[x][y].erase(n);
board[i][j] = '.';
}
}
}
return false;
}
void solveSudoku(vector<vector<char>>& board) {
for(int i=0; i<9; ++i)
for(int j=0; j<9; ++j)
{
if(board[i][j] != '.')
{
int x = i / 3;
int y = j / 3;
row[i].insert(board[i][j]);
col[j].insert(board[i][j]);
cell[x][y].insert(board[i][j]);
}
}
dfs(board,0,0);
return;
}
private:
unordered_set<char> row[9];
unordered_set<char> col[9];
unordered_set<char> cell[3][3];
};``````

• For an application like this, where you only have 9 items and they're numerically consecutive, a std::bitset<> is a much better choice than std::unordered_set<>. Both are O(1), but bitset doesn't require computing a hash. Also, since its size is fixed at compile time, it doesn't require dynamic memory allocation either.

http://en.cppreference.com/w/cpp/utility/bitset

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.