首页 > 其他 > 详细

19.2.3 [LeetCode 36] Sudoku Solver

时间:2019-02-03 15:47:01      阅读:177      评论:0      收藏:0      [点我收藏+]

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得有点不爽

好冷啊

孤单弱小无助

 

19.2.3 [LeetCode 36] Sudoku Solver

原文:https://www.cnblogs.com/yalphait/p/10350458.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!