本文實例講述了Python判斷有效的數(shù)獨算法。分享給大家供大家參考，具體如下：

一、題目

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

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

數(shù)獨部分空格內(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

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

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

二、解法

• 先創(chuàng)建三個空數(shù)組 row、col、cell，以 cell 為例，里面的每個空字典都代表一個 3×3單元格，然后我們需要把數(shù)據(jù)一個個填進(jìn)去
• 遍歷整個二維數(shù)組，然后邊遍歷邊把數(shù)組分別存入到 行 row , 列 col , 3×3單元格 cell 內(nèi)的字典，存為key ，而不是 value 。
• 然后我們就可以判斷,行、列、3×3單元格 對應(yīng)的字典內(nèi)是否已經(jīng)存在board[x][y]這個鍵名，如果存在，那么說明重復(fù)了，返回 False
• 注意，字典中的值這里都為1，但是沒有任何意義，你可以隨意更改
• 把數(shù)組存入 3×3的單元格是一個難點，num = 3*(x//3)+y//3，這個式子是關(guān)鍵，可以找個數(shù)獨，然后代入進(jìn)去好好理解下
• 當(dāng)然你也可以不用這個式子，用if/else語句來判斷也行，那樣比較好理解，但是不如這個式子簡潔
• 類似于: if y<3 : ... elif 3<=y<6 : ... elif 6<=y : ...,

代碼如下：

#row，col，cell分別代表行，列，3x3單元格
row, col, cell =
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}],
[{}, {}, {}, {}, {}, {}, {}, {}, {}]
for x in range(9):
  for y in range(9):
    #取得單元格
    num = 3*(x//3)+y//3
    temp = board[x][y]
    #不需要存入 '.'
    if temp != '.':
      if (temp not in row[x]
      and temp not in col[y]
      and temp not in cell[num]):
        row[x][temp] = '1'
        col[y][temp] = '1'
        cell[num][temp] = '1'
      else:
        return False
return True

時間 64ms，擊敗了 99.3%

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)組操作技巧總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python列表(list)操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計有所幫助。

最新評論