[LeetCode] 37. Sudoku Solver

alaege 發布于2019-08-19 11:14 / 2229人閱讀

Problem

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-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.

Solution

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) return;
        solve(board);
    }
    
    private boolean solve(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                
                if (board[i][j] == ".") {
                    for (char ch = "1"; ch <= "9"; ch++) {
                        if (isValid(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (solve(board)) return true;
                            else board[i][j] = ".";
                        }
                    }
                    return false;
                }
                
            }
        }
        return true;
    }
    
    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == ch) return false;
            if (board[row][i] == ch) return false;
            if (board[row/3*3+i/3][col/3*3+i%3] == ch) return false;
        }
        return true;
    }
}

云服務器 GPU云服務器 Solver sudoku LeetCode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/77247.html

leetcode37 Sudoku Solver

摘要：題目要求也就是給出一個解決數獨的方法，假設每個數獨只有一個解決方案。并將當前的假象結果帶入下一輪的遍歷之中。如果最終遍歷失敗，則逐級返回，恢復上一輪遍歷的狀態，并填入下一個合理的假想值后繼續遍歷。題目要求 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indi...

pepperwang 2019-08-15 10:49 評論0 收藏0
[Leetcode]36 Valid Sudoku

摘要：的可以由確定，這一點在里面的位置可以由確定所以每確定一行，每一個值都可以被轉換到一個之中。如果允許的空間復雜度，可以設置一個二維數組來用來判斷是否在里重現了重復的數字。將一個數字的每一個位上表示每一個數字。 Leetcode[36] Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - ...

zhichangterry 2019-08-14 14:54 評論0 收藏0
leetcode36 Valid Sudoku 查看數獨是否合法

摘要：如果重復則不合法，否則極為合法。在這里我們使用數組代替作為存儲行列和小正方形的值得數據結構。我存儲這所有的行列小正方形的情況，并判斷當前值是否重復。外循環則代表對下一行，下一列和下一個小正方形的遍歷。題目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...

wing324 2019-08-16 10:32 評論0 收藏0
leetcode 36 Valid Sudoku

摘要：要求我們判斷已經填入的數字是否滿足數獨的規則。即滿足每一行每一列每一個粗線宮內的數字均含，不重復。沒有數字的格子用字符表示。通過兩層循環可以方便的檢查每一行和每一列有沒有重復數字。對于每個，作為縱坐標，作為橫坐標。題目詳情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...

entner 2019-08-15 14:51 評論0 收藏0
LeetCode 攻略 - 2019 年 8 月上半月匯總（109 題攻略）

摘要：每天會折騰一道及以上題目，并將其解題思路記錄成文章，發布到和微信公眾號上。三匯總返回目錄在月日月日這半個月中，做了匯總了數組知識點?；蛘呃奖疚淖钕旅?，添加的微信等會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

tracy 2019-08-26 10:49 評論0 收藏0