Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3sub-boxes of the grid.

Empty cells are indicated by the character '.'.

A sudoku puzzle...

...and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character '.'.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

 

 1 class Solution {
 2 public:
 3     bool solvefromone(int x, int y, vector<vector<char>>&board) {
 4         bool used[10] = { false };
 5         for (int i = 0; i < 9; i++) {
 6             if (board[x][i] != '.')
 7                 used[board[x][i] - '0'] = true;
 8             if (board[i][y] != '.')
 9                 used[board[i][y] - '0'] = true;
10         }
11         int xs = x / 3 * 3, xe = xs + 2, ys = y / 3 * 3, ye = ys + 2;
12         for (int i = xs; i <= xe; i++)
13             for (int j = ys; j <= ye; j++)
14                 if (board[i][j] != '.')
15                     used[board[i][j] - '0'] = true;
16         int nextx=x, nexty=y;
17         for(int i=y+1;i<9;i++)
18             if (board[x][i] == '.') {
19                 nextx = x; nexty = i;
20                 break;
21             }
22         if (nexty == y) {
23             for (int i = x + 1; i < 9; i++) {
24                 for (int j = 0; j < 9; j++) {
25                     if (board[i][j] == '.') {
26                         nextx = i; nexty = j;
27                         break;
28                     }
29                 }
30                 if (nextx != x)break;
31             }
32         }
33         for(int i=1;i<=9;i++)
34             if (!used[i]) {
35                 board[x][y] = i + '0';
36                 if (nextx == x && nexty == y)
37                     return true;
38                 if (solvefromone(nextx, nexty, board))
39                     return true;
40             }
41         board[x][y] = '.';
42         return false;
43     }
44     void solveSudoku(vector<vector<char>>& board) {
45         for (int i = 0; i < 9; i++)
46             for (int j = 0; j < 9; j++)
47                 if (board[i][j] == '.')
48                     solvefromone(i, j, board);
49     }
50 };

View Code

 

暴力深搜，手误WA得有点不爽

好冷啊

孤单弱小无助