1. 题目链接

    传送门

  2. 题意

    数独游戏大家都有玩过, 本题给出一个9*9数独棋盘, 你需要给出一个合法的终局棋盘

  3. 解题思路

    对每一个位置dfs搜索可行解, 81层dfs不会爆栈, 安心dfs就好, 搜索方式见代码

  4. AC代码

     class Solution {

     public void solveSudoku(char[][] board) {
         solve(board, 0);
     }

     public boolean solve(char[][] board, int num) {
         if(num == 81) return true;

         int row = num / 9, col = num % 9;
         if(board[row][col] == '.') {
             for(char ch = '1'; ch <= '9'; ++ch) {
                 if(isVaild(board, row, col, ch)) {
                     board[row][col] = ch;
                     if(solve(board, num + 1))
                         return true;
                     else
                         board[row][col] = '.';
                 }
             }
             return false;
         }
         return (solve(board, num + 1));
     }

     public boolean isVaild(char[][] board, int r, int c, char ch) {
         for(int i = 0; i < 9; i++) {
             if(board[i][c] == ch) return false;
             if(board[r][i] == ch) return false;
             if(board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == ch) return false;
         }
         return true;
     }
 }

  5. PS

    第一次使用markdown写博客, 生疏且僵硬, 555~~

版权声明：本文为fan-jiaming原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/fan-jiaming/p/12121388.html