143-144/300

有效的數(shù)獨(dú)

判斷一個(gè) 9x9 的數(shù)獨(dú)是否有效。只需要根據(jù)以下規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。

數(shù)字 1-9 在每一列只能出現(xiàn)一次。

數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

上圖是一個(gè)部分填充的有效的數(shù)獨(dú)。

數(shù)獨(dú)部分空格內(nèi)已填入了數(shù)字，空白格用 ‘.’ 表示。

示例 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

解釋: 除了第一行的第一個(gè)數(shù)字從 5 改為 8 以外，空格內(nèi)其他數(shù)字均與 示例1 相同。

但由于位于左上角的 3x3 宮內(nèi)有兩個(gè) 8 存在, 因此這個(gè)數(shù)獨(dú)是無(wú)效的。

說(shuō)明:

一個(gè)有效的數(shù)獨(dú)(部分已被填充)不一定是可解的。

只需要根據(jù)以上規(guī)則，驗(yàn)證已經(jīng)填入的數(shù)字是否有效即可。

給定數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 ‘.’ 。

給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。

來(lái)源：力扣(LeetCode)

鏈接：https://leetcode-cn.com/problems/valid-sudoku

思路：記錄

根據(jù)題目要求，對(duì)于每一個(gè)數(shù)，都有三個(gè)點(diǎn)位：某行，某列，某個(gè)3x3 subgrid

只要保證不重復(fù)就ok。 譬如下圖：左邊圖是個(gè)美好的數(shù)獨(dú)，右邊圖改了一下。

對(duì)于[0][0]的’8’有三個(gè)點(diǎn)位：0行，0列，(0,0)的subgrid

對(duì)于[2][2]的’8’有三個(gè)點(diǎn)位：2行，2列，(0,0)的subgrid

對(duì)于[3][0]的’8’有三個(gè)點(diǎn)位：3行，0列，(1,1)的subgrid

這就說(shuō)明(0,0)subgrid有倆’8’，0列也有倆’8’，不行啊。

所以見(jiàn)過(guò)的用(行，此數(shù)字)，(此數(shù)字，列)【倒個(gè)個(gè)兒，防止行列不分】，(subgrid的坐標(biāo)，此數(shù)字) 來(lái)記錄。

然后判斷集合==set(此集合)，同則T，不同就F。

class Solution:

def isValidSudoku(self, board: List[List[str]]) -> bool:

res = []

for i, row in enumerate(board):

for j, n in enumerate(row):

if n != '.':

res += (i,n),(n,j),(i//3,j//3,n)

return len(res) == len(set(res))1

2

3

4

5

6

7

8

9

10

解數(shù)獨(dú)

編寫(xiě)一個(gè)程序，通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。

一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則：

數(shù)字 1-9 在每一行只能出現(xiàn)一次。

數(shù)字 1-9 在每一列只能出現(xiàn)一次。

數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

空白格用 ‘.’ 表示。

一個(gè)數(shù)獨(dú)。

答案被標(biāo)成紅色。

Note:

給定的數(shù)獨(dú)序列只包含數(shù)字 1-9 和字符 ‘.’ 。

你可以假設(shè)給定的數(shù)獨(dú)只有唯一解。

給定數(shù)獨(dú)永遠(yuǎn)是 9x9 形式的。

來(lái)源：力扣(LeetCode)

鏈接：https://leetcode-cn.com/problems/sudoku-solver

思路：有選擇的嘗試

譬如走到[0][2]要填個(gè)數(shù)：

最初選擇：{‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}

減去行出現(xiàn)過(guò)的{’.’, ‘3’, ‘5’, ‘7’}

減去列出現(xiàn)過(guò)的 {’.’, ‘8’}

減去subgrid中出現(xiàn)過(guò)的：{’.’, ‘3’, ‘5’, ‘6’, ‘8’, ‘9’}

最后的結(jié)果是：{‘1’, ‘2’, ‘4’}

然后當(dāng)[0][2]=1時(shí)，走向[0][3]，開(kāi)始新的一輪嘗試。

譬如，前面都嘗試沒(méi)問(wèn)題，然后嘗試[0][7] =2的下一步[0][8] = 9

但列出現(xiàn)過(guò)9，這時(shí)候{‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’} - {‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’}-{‘1’, ‘3’, ‘5’, ‘6’, ‘9’} - {‘1’, ‘2’, ‘6’} = set()， 屁也沒(méi)有， 退回上一步[0][7] =2， 把[0][7]恢復(fù)為’.’

然后嘗試[0][7] =9，那么下一步[0][8] = 2

行列subgrid都不重復(fù)，進(jìn)入下一行的嘗試，[1][1] = …

當(dāng)進(jìn)行到[8][2] =1時(shí)，一切完美，沒(méi)有’.'的存在，我們就可以一層層返回之前的嘗試收尾。

class Solution:

def solveSudoku(self, board):

def dfs():

for i, row in enumerate(board):

for j, num in enumerate(row):

if num == '.':

for x in {'1', '2', '3', '4', '5', '6', '7', '8', '9'} - {row[k] for k in range(9)} - {board[k][j] for k in range(9)} - {board[i // 3 * 3 + m][j // 3 * 3 + n] for m in range(3) for n in range(3)}:

board[i][j] = x

if dfs(): return True

board[i][j] = '.'

return False

return True

dfs()1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

總結(jié)

以上是生活随笔為你收集整理的python37降到36原来的包还可以用吗_【lc刷题】36/37 有效的数独/解数独(143-144/300)...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。