# C++ using back track, 4ms

• ``````class Solution {
public:
int N = 81;
void solveSudoku(vector<vector<char>>& board) {
solve(board);
}

bool solve(vector<vector<char> >& sudo) {
int board[N];							// board
int spaces[N];							// space have to be fill
int nspaces = 0;						// the num of space at begin
int available[N];						// which num is available in one square

// initial
memset(board, 0, N * sizeof(int));
memset(spaces, 0, N * sizeof(int));
memset(available, 255, N * sizeof(int));

for (int i = 0;i < N;++i)
{
if (sudo[i/9][i%9] == '.')
{
board[i] = 0;
spaces[nspaces++] = i;
}
else
{
board[i] = sudo[i/9][i%9] - '0';
}
}
if (nspaces == 0)
return true;
int node = 0, min = 9; // node: which square's possible choices is least, min is the num of choices
// artites: every square's possilbe choices, init 9, neighbors: every square which neigbhor has been fill
for (int i = 0, neighbors = 0, artites = 9;i < N;++i, neighbors = 0, artites = 9)
{
if (board[i] == 0)
{
// at the same row
for (int j = i/9*9;j < (i/9 + 1)*9;++j)
{
if (board[j] && !(neighbors >> board[j] & 1))
{
neighbors |= 1 << board[j];
--artites;
available[i] &= ~(1 << board[j]);
}
}
// at the same column
for (int j = i%9;j < N;j += 9)
{
if (board[j] && !(neighbors >> board[j] & 1))
{
neighbors |= 1 << board[j];
--artites;
available[i] &= ~(1 << board[j]);
}
}
// at the same 3*3 square
for (int j = 0, m = i/27*27 + i%9/3*3;j < 3;++j)
{
for (int n = 0;n < 3;++n)
{
if (board[j*9 + m + n] && !(neighbors >> board[j*9 + m + n] & 1))
{
neighbors |= 1 << board[j*9 + m + n];
--artites;
available[i] &= ~(1 << board[j*9 + m + n]);
}
}
}
if (artites < min)
{
min = artites;
node = i;
}
}
}
// illegal
if (min == 0)
return false;
// select every possible choice fill in the square
for (int i = 1;i < 10;++i)
{
if ((available[node] >> i) & 1)
{
sudo[node/9][node%9] = i + '0';
if (solve(sudo))
return true;
else
sudo[node/9][node%9] = '.';
}
}
return false;
}
``````

};

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