當前位置:網站首頁>再戰leetcode (解數獨)

再戰leetcode (解數獨)

2022-01-28 00:11:20 學逗b

37. 解數獨

題目描述

在這裏插入圖片描述
在這裏插入圖片描述
在這裏插入圖片描述

回溯法

leetcode題解

在這裏插入圖片描述
代碼

public class Test {
    
    public static void main(String[] args) {
    
        char[][] board = {
    
                {
    '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'}
        };
        new Solution().solveSudoku(board);
        printBroad(board);
    }

    public static void printBroad(char[][] board) {
    
        for (int i = 0; i < board.length; i++) {
    
            System.out.printf("[");
            for (int j = 0; j < board[i].length; j++) {
    
                System.out.printf(String.valueOf(board[i][j]) + ",");
            }
            System.out.printf("],");
            System.out.println();
        }
    }
}

class Solution {
    
    public void solveSudoku(char[][] board) {
    
        solveSudokuHelper(board);
    }

    /** * @param board 棋盤 * @return 是否是正確的棋盤 */
    private boolean solveSudokuHelper(char[][] board) {
    
        // 一個for循環遍曆棋盤的行,一個for循環遍曆棋盤的列
        // 一行一列確定下來之後,遞歸遍曆這個比特置放9個數字的可能性
        for (int i = 0; i < 9; i++) {
    
            for (int j = 0; j < 9; j++) {
    
                // 不修改原始數字,直接跳過
                if (board[i][j] != '.') {
    
                    continue;
                }
                // 依次遍曆9個字符 '1' 到 '9'
                for (char k = '1'; k <= '9'; k++) {
    
                    // 如果將這個字符放入棋盤是合法的就將這個字符放入棋盤內
                    if (isValidSudoku(i, j, k, board)) {
    
                        // 將這個字符放入進入棋盤
                        board[i][j] = k;
                        if (solveSudokuHelper(board)) {
    
                            return true;
                        }
                        // 說明後面的路走不通,所以前面放這個旗子會導致後面的路走不通
                        // 需要移除這個旗子
                        board[i][j] = '.';
                    }
                }
                // 9個數字都用完了,直接返回false
                // 因為一行一列確定下來了,這裏嘗試了9個數字都不行,說明這個棋盤找不到解决數獨問題的解决方法
                // 那麼直接返回 (這也是為什麼沒有終止條件也不會永遠填不滿棋盤而無限遞歸下去!)
                return false;
            }
        }
        // 說明棋盤沒有問題
        return true;
    }

    /** * 判斷棋盤是否合法有如下三個維度 * 1.同行是否重複 * 2.同列是否重複 * 3.9宮格裏是否重複 * * @param row 需要判斷的旗子在棋盤上的行號 * @param col 需要判斷的旗子在棋盤上的列號 * @param val 需要判斷的旗子在棋盤上的值 * @param board 棋盤 * @return 該旗子放下後在這個棋盤上是否合法 */
    private boolean isValidSudoku(int row, int col, char val, char[][] board) {
    
        for (int i = 0; i < 9; i++) {
    
            // 出現重複數字違反第二條直接返回false
            if (board[row][i] == val) {
    
                return false;
            }
        }
        // 出現重複數字違反第一條直接返回false
        for (int j = 0; j < 9; j++) {
    
            if (board[j][col] == val) {
    
                return false;
            }
        }
        // 判斷第三個,九宮格內是否重複
        // 其中的 (row/3)代錶的是第幾個九宮格,而 (row/3)*3的目的是為了獲得第幾個九宮格一開始的索引
        int startRow = (row / 3) * 3;
        // 同上可得
        int startCol = (col / 3) * 3;
        // 判斷現在9宮格內有重複的字母嗎
        for (int i = startRow; i < startRow + 3; i++) {
    
            for (int j = startCol; j < startCol + 3; j++) {
    
                if (board[i][j] == val) {
    
                    return false;
                }
            }
        }
        return true;
    }
}

debug一下應該就了解了為啥

版權聲明
本文為[學逗b]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201280011195087.html

隨機推薦