2014.2.28 21:30
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.
Solution:
My solution to this problem is by DFS and backtracking. The difference is that I added some optimization strategies to the program:
1. [7][6] can be represented as [7 * 9 + 6], you don't have to calculate it every time, store the coordinates in an array instead.
2. [69] can be represented as [69 / 9][69 % 9], you don't have to calculate it every time, becasue '/' and '%' are expensive operators.
3. When you've filled in a blank, where is the next blank to fill? You can find the next blank in O(1) time, instead of scanning the whole board.
4. When one attempt failed, how do you backtrack efficiently? With a <vector>, pop_back() and push_back() is a good choice.
The Dancing Links Algorithm seems to be a very exquisite way to solve Sudoku, but here it might be way too complicated for an interview question. Perhaps I'm just too lazy to learn it, spare me~(>_<)
Total time complexity is O((n^2)!), but it would never appear that large. Space complexity is O(n^2).
Accepted code:
1 // 1AC, very well, avoiding too much '/' and '%' will speed up the program. 2 #include <cmath> 3 #include <vector> 4 using namespace std; 5 6 class Solution { 7 public: 8 void solveSudoku(vector<vector<char> > &board) { 9 n2 = (int)board.size(); 10 if (n2 == 0) { 11 return; 12 } else if (n2 == 1) { 13 board[0][0] = '1'; 14 return; 15 } 16 17 n = (int)sqrt(1.0 * n2); 18 n4 = n2 * n2; 19 20 int i, j; 21 row.resize(n2); 22 for (i = 0; i < n2; ++i) { 23 row[i].resize(n2); 24 } 25 col.resize(n2); 26 for (i = 0; i < n2; ++i) { 27 col[i].resize(n2); 28 } 29 block.resize(n2); 30 for (i = 0; i < n2; ++i) { 31 block[i].resize(n2); 32 } 33 bc.resize(n2); 34 for (i = 0; i < n2; ++i) { 35 bc[i].resize(n2); 36 } 37 row_coordinate.resize(n4); 38 col_coordinate.resize(n4); 39 for (i = 0; i < n4; ++i) { 40 row_coordinate[i] = i / n2; 41 col_coordinate[i] = i % n2; 42 } 43 44 for (i = 0; i < n2; ++i) { 45 for (j = 0; j < n2; ++j) { 46 row[i][j] = col[i][j] = block[i][j] = 0; 47 } 48 } 49 50 for (i = 0; i < n2; ++i) { 51 for (j = 0; j < n2; ++j) { 52 bc[i][j] = i / n * n + j / n; 53 } 54 } 55 56 cc = 0; 57 for (i = 0; i < n2; ++i) { 58 for (j = 0; j < n2; ++j) { 59 if (board[i][j] != '.') { 60 // it is a digit 61 row[i][board[i][j] - '1'] = 1; 62 col[j][board[i][j] - '1'] = 1; 63 block[bc[i][j]][board[i][j] - '1'] = 1; 64 } else { 65 empty_slots.push_back(i * n2 + j); 66 ++cc; 67 } 68 } 69 } 70 71 suc = false; 72 dfs(board); 73 74 // perform cleanup operations 75 for (i = 0; i < n2; ++i) { 76 row[i].clear(); 77 col[i].clear(); 78 block[i].clear(); 79 bc[i].clear(); 80 } 81 row.clear(); 82 col.clear(); 83 block.clear(); 84 bc.clear(); 85 empty_slots.clear(); 86 row_coordinate.clear(); 87 col_coordinate.clear(); 88 } 89 private: 90 bool suc; 91 int n, n2, n4; 92 int cc; 93 vector<vector<int> > row, col, block; 94 vector<vector<int> > bc; 95 vector<int> empty_slots; 96 vector<int> row_coordinate, col_coordinate; 97 98 void dfs(vector<vector<char> > &board) { 99 if (suc) { 100 return; 101 } 102 if (cc == 0) { 103 suc = true; 104 return; 105 } 106 107 int r, c; 108 int i; 109 110 r = row_coordinate[empty_slots[cc - 1]]; 111 c = col_coordinate[empty_slots[cc - 1]]; 112 for (i = 0; i < n2; ++i) { 113 if (row[r][i] || col[c][i] || block[bc[r][c]][i]) { 114 continue; 115 } 116 row[r][i] = 1; 117 col[c][i] = 1; 118 block[bc[r][c]][i] = 1; 119 empty_slots.pop_back(); 120 --cc; 121 board[r][c] = (i + '1'); 122 123 dfs(board); 124 if (suc) { 125 return; 126 } 127 128 row[r][i] = 0; 129 col[c][i] = 0; 130 block[bc[r][c]][i] = 0; 131 empty_slots.push_back(r * n2 + c); 132 ++cc; 133 board[r][c] = '.'; 134 } 135 } 136 };