Repository navigation
Expand file tree
/
Copy pathsudokuSolver.cpp
More file actions
105 lines (87 loc) · 2.7 KB
/
Copy pathsudokuSolver.cpp
File metadata and controls
105 lines (87 loc) · 2.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
// Source : https://oj.leetcode.com/problems/sudoku-solver/
// Author : Hao Chen
// Date : 2014-09-20
/**********************************************************************************
*
* Write a program to solve a Sudoku puzzle by filling the empty cells.
*
* Empty cells are indicated by the character '.'.
*
* You may assume that there will be only one unique solution.
*
* A sudoku puzzle...
*
* ...and its solution numbers marked in red.
*
*
**********************************************************************************/
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <iostream>
#include <vector>
using namespace std;
const int SodukuSize = 9;
bool row_mask[SodukuSize][SodukuSize];
bool col_mask[SodukuSize][SodukuSize];
bool area_mask[SodukuSize][SodukuSize];
bool initSudokuMask(vector< vector<char> > &board){
//reset the memory
memset(row_mask, false, sizeof(row_mask));
memset(col_mask, false, sizeof(col_mask));
memset(area_mask, false, sizeof(area_mask));
//check each rows and cols
for(int r=0; r<board.size(); r++){
for (int c=0; c<board[r].size(); c++){
if (!isdigit(board[r][c])) {
continue;
};
int idx = board[r][c] - '0' - 1;
//check the rows/cols/areas
int area = (r/3) * 3 + (c/3);
if (row_mask[r][idx] || col_mask[c][idx] || area_mask[area][idx] ){
return false;
}
row_mask[r][idx] = col_mask[c][idx] = area_mask[area][idx] = true;
}
}
return true;
}
bool recursiveSudoKu(vector< vector<char> > &board, int row, int col){
if (row >= SodukuSize) {
return true;
}
if (col >= SodukuSize){
return recursiveSudoKu(board, row+1, 0);
}
if (board[row][col] != '.'){
return recursiveSudoKu(board, row, col+1);
}
//pick a number for empty cell
int area;
for(int i=0; i<SodukuSize; i++){
area = (row/3) * 3 + (col/3);
if (row_mask[row][i] || col_mask[col][i] || area_mask[area][i] ){
continue;
}
//set the number and sovle it recursively
board[row][col] = i + '1';
row_mask[row][i] = col_mask[col][i] = area_mask[area][i] = true;
if (recursiveSudoKu(board, row, col+1) == true){
return true;
}
//backtrace
board[row][col] = '.';
row_mask[row][i] = col_mask[col][i] = area_mask[area][i] = false;
}
return false;
}
void solveSudoku(vector<vector<char> > &board) {
if (initSudokuMask(board) == false){
return;
}
recursiveSudoKu(board, 0, 0);
}
int main(int argc, char**argv) {
return 0;
}