題目描述

判斷一個 9x9 的數獨是否有效。只需要根據以下規則，驗證已經填入的數字是否有效即可。數字 1-9 在每一行只能出現一次。 數字 1-9 在每一列只能出現一次。 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

上圖是一個部分填充的有效的數獨。

數獨部分空格內已填入了數字，空白格用 ‘.’ 表示。

示例 1:

輸入: [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ] 輸出: true

示例 2:

輸入: [["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"] ] 輸出: false 解釋: 除了第一行的第一個數字從 5 改為 8 以外，空格內其他數字均與 示例1 相同。但由于位于左上角的 3x3 宮內有兩個 8 存在, 因此這個數獨是無效的。

說明:

一個有效的數獨（部分已被填充）不一定是可解的。 只需要根據以上規則，驗證已經填入的數字是否有效即可。 給定數獨序列只包含數字 1-9 和字符 '.' 。 給定數獨永遠是 9x9 形式的。

解題
遍歷二維數組，判斷每一行、每一列、每個3x3方塊是否包含重復項即可。代碼如下：

public boolean isValidSudoku(char[][] board) {boolean[][] row = new boolean[9][10];boolean[][] column = new boolean[9][10];boolean[][] box = new boolean[9][10];for(int i=0;i<9;i++) {for(int j=0;j<9;j++) {if(board[i][j] != '.') {int num = board[i][j]-'0';int boxIndex = i/3+(j/3)*3;if(row[i][num] || column[j][num] || box[boxIndex][num]) {return false;}row[i][num]=true;column[j][num]=true;box[boxIndex][num]=true;}}}return true;}

總結

以上是生活随笔為你收集整理的2019-03-15-算法-进化（有效的数独）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。