Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 22, 2018 02:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/1e6419e4dc3cbcd8236652f77042b680 to your computer and use it in GitHub Desktop.
Save jianminchen/1e6419e4dc3cbcd8236652f77042b680 to your computer and use it in GitHub Desktop.
Sudoku solver - being an interviewer
#include <iostream>
#include <vector>
using namespace std;
bool fill(int k, int row, int col, bool cols[9][9], bool grids[3][3][9], bool rows[9][9]) {
if(cols[col][k-1] == 1)
return false;
if(rows[row][k-1] == 1)
return false;
if(grids[row/3][col/3][k-1] == 1)
return false;
cols[col][k-1] = 1;
rows[row][k-1] = 1;
grids[row/3][col/3][k-1] = 1;
return true;
}
void unfill(int k, int row, int col, bool cols[9][9], bool grids[3][3][9], bool rows[9][9]) {
cols[col][k-1] = 0;
rows[row][k-1] = 0;
grids[row/3][col/3][k-1] = 0;
}
bool recursion(int row, int col, bool cols[9][9], bool grids[3][3][9], bool rows[9][9], const vector<vector<char>>&board) {
if(row >= 9 ){
return true;
}
if(col >= 9) {
return recursion(row + 1, 0, cols, grids, rows, board);
}
if(board[row][col] != '.') {
return recursion(row, col + 1, cols, grids, rows, board);
}
for(int i = 1; i <= 9; i++) {
if (fill(i, row, col, cols, grids, rows)) {
if(recursion(row, col+1, cols, grids, rows, board))
return true;
else unfill(i, row, col, cols, grids, rows);
}
}
return false;
}
bool sudokuSolve(const vector<vector<char>>& board )
{
bool rows[9][9] = {0}, cols[9][9] = {0}, grids[3][3][9] = {0};
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(board[i][j] != '.') {
if(!fill(board[i][j]-'0', i, j, cols, grids, rows)) return false;
}
}
}
return recursion(0, 0, cols, grids, rows, board);
// your code goes here
}
/*
bool columns[9][9];
bool grids[9][9];
bool rows[9][9];
53..7....
6..195...
.98....6.
8...6...3
7...2...6
.6....28.
...419..5
....8..79
[".","8","9",".","4",".","6",".","5"]
[".","7",".",".",".","8",".","4","1"]
["5","6",".","9",".",".",".",".","8"]
[".",".",".","7",".","5",".","9","."]
[".","9",".","4",".","1",".","5","."]
[".","3",".","9",".","6",".","1","."]
["8",".",".",".",".",".",".",".","7"]
[".","2",".","8",".",".",".","6","."]
[".",".","6",".","7",".",".","8","."]]
*/
int main() {
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment