Sudoku solver with two scans

• class Solution {
public:
void solveSudoku(vector<vector<char>>& board) {

``````    vector<pair<int,int>> positions;
for(int i=0; i<board.size(); i++)
{
for(int j=0; j<board[0].size(); j++)
{
if(board[i][j]=='.')
{
positions.push_back(make_pair(i, j));
}
}
}
int num = positions.size();
vector<bool>visited(num, false);

bool flag = recursive(board, positions, visited, 0);
}

bool recursive(vector<vector<char> > &board, vector<pair<int, int> > &positions, vector<bool> &visited, int idx)
{

int num = positions.size();
if(idx==num) return true; //exceed the number

int i = positions[idx].first;
int j = positions[idx].second;

for(int k=1; k<=9; k++)
{

board[i][j] = k+'0';
if(valid(board, i, j) && recursive(board, positions, visited, idx+1))
return true;
board[i][j] = '.';   //backtrack
}
return false;
}

bool valid(vector<vector<char> > &board, int irow, int icol)
{
int val = board[irow][icol];
for(int i=0; i<9; i++)
{
if(board[i][icol]==val&& i!=irow) return false;
}
for(int j=0; j<9; j++)
{
if(board[irow][j]==val&& j!=icol) return false;
}

int rs = (irow/3)*3;
int cs = (icol/3)*3;
for(int i=rs; i<rs+3; i++)
{
for(int j=cs; j<cs+3; j++)
{
if(board[i][j]==val&&i!=irow&&j!=icol)
return false;
}
}
return true;
}
``````

};

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