# Why my solution take such lot of time？489ms

• I try to fill ‘.’ one by one, before filling, I will use validNum() to get valid numbers.
Then， check those numbers， if not suitable， use tryFill(i - 1) backtracking.

``````class Solution {
public:
vector<int> validNum(int u, vector<vector<char>> board)
{
vector<int> ans;
vector<bool> used(9, false);
int x = u / 9, y = u % 9;
for (int i = 0; i < 9; i++)
{
if (board[x][i] != '.'){

used[board[x][i] - '0' - 1] = true;
}
if (board[i][y] != '.'){

used[board[i][y] - '0' - 1] = true;
}
int bx = (x / 3) * 3 + i / 3, by = (y / 3) * 3 + i % 3;
if (board[bx][by] != '.'){

used[board[bx][by] - '0' - 1] = true;
}

}

if (board[x][y] != '.') used[board[x][y] - '0' - 1] = false;
for (int i = 0; i < 9; i++)
{
if (!used[i]) ans.push_back(i + 1);// 不要忘记+1
}
return ans;

}

void tryFill(int start, vector<int> unknown, vector<vector<char>>& board)
{if(start > 50)
cout<<start<<" ";
if (start < 0) return;
int i = start;
for (; i < unknown.size(); i++)
{
int u = unknown[i];
int x = u / 9, y = u % 9;

vector<int> validN = validNum(u, board);
int validLen = validN.size();

int index;
if (board[x][y] == '.')
index = 0;
else
for (int i = 0; i < 9; i++)
if (validN[i] == board[x][y] - '0')
{
index = i + 1;
break;
}
for (; index < validLen; index++)
{
board[x][y] = validN[index] + '0';
if (i != unknown.size() - 1){
vector<int> NextValidN = validNum(unknown[i + 1], board);
if (NextValidN.size() != 0)
break;
}
}
if (index == validLen && i != unknown.size() - 1 )//这里一定要有i != unknown.size() - 1， 因为当填入最后一个空格，这个一定是有效的
{
board[x][y] = '.';
tryFill(i - 1, unknown, board);
break;//太重要了 这个break
}

}

}

void solveSudoku(vector<vector<char>>& board) {
//先用hash 去看每个cell可能的数字
//再回溯法

//bool hrow[9][9] = {false}, hcol[9][9] = {false}, hblock[9][9] = {false};
vector<int> unknown;//x = u / 9 , y = u % 9 u->[0, 80];
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++)
if (board[i][j] == '.')

unknown.push_back(i * 9 + j);
}
tryFill(0, unknown, board);
cout << "";
}

};
``````

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