快捷導(dǎo)航

用Python解數(shù)獨(dú)的方法示例

更新時(shí)間：2019年10月24日 10:52:56 作者：東方鶚

這篇文章主要介紹了用Python解數(shù)獨(dú)的方法示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

芬蘭數(shù)學(xué)家因卡拉花費(fèi)3個(gè)月時(shí)間設(shè)計(jì)出的世界上迄今難度最大的數(shù)獨(dú)。數(shù)獨(dú)是 9 橫 9 豎共有 81 個(gè)格子，同時(shí)又分為 9 個(gè)九宮格。規(guī)則很簡(jiǎn)單：每個(gè)空格填入 1~9 任意一個(gè)數(shù)字，需要保證每個(gè)橫排和豎排以及九宮格內(nèi)無(wú)相同數(shù)字。

解數(shù)獨(dú)是一個(gè)可有可無(wú)的愛(ài)好，知道這個(gè)益智游戲，但是不很上心。但是前兩天，由于自己的學(xué)生裝了一個(gè) ubuntu 18.04 的系統(tǒng)，上面有一些數(shù)獨(dú)游戲，偶然間，讓我看見(jiàn)了，為了更好的顯擺自己的 Python 知識(shí)，決定用 Python 寫一個(gè)程序，所以就有了下面的文字。

1、將待解的數(shù)獨(dú)轉(zhuǎn)換成 Python 矩陣

m = [
 [6, 0, 0, 1, 0, 0, 7, 0, 8],
 [0, 0, 0, 8, 0, 0, 2, 0, 0],
 [2, 3, 8, 0, 5, 0, 1, 0, 0],
 [0, 0, 0, 0, 4, 0, 0, 9, 2],
 [0, 0, 4, 3, 0, 8, 6, 0, 0],
 [3, 7, 0, 0, 1, 0, 0, 0, 0],
 [0, 0, 3, 0, 7, 0, 5, 2, 6],
 [0, 0, 2, 0, 0, 4, 0, 0, 0],
 [9, 0, 7, 0, 0, 6, 0, 0, 4]
]

就是這么簡(jiǎn)單，將待填寫的空白格用 0 來(lái)代替。

2、尋找第一個(gè)空格位置

def start_pos(m:"數(shù)獨(dú)矩陣"):
 """ 功能：返回第一個(gè)空白格的位置坐標(biāo)"""
 for x in range(9):
  for y in range(9):
   if m[x][y] == 0:
    return x, y
 return False, False # 若數(shù)獨(dú)已完成，則返回 False, False

找到 Python 矩陣中第一個(gè)是 0 的元素的位置坐標(biāo)。

3、尋找下一個(gè)空格位置

def get_next(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：獲得下一個(gè)空白格在數(shù)獨(dú)中的坐標(biāo)。  
 """
 for next_y in range(y+1, 9): # 下一個(gè)空白格和當(dāng)前格在一行的情況
  if m[x][next_y] == 0:
   return x, next_y
 for next_x in range(x+1, 9): # 下一個(gè)空白格和當(dāng)前格不在一行的情況
  for next_y in range(0, 9):
   if m[next_x][next_y] == 0:
    return next_x, next_y
 return -1, -1    # 若不存在下一個(gè)空白格，則返回 -1，-1

找到 Python 矩陣中下一個(gè)是 0 的元素的位置坐標(biāo)。詳細(xì)內(nèi)容看注釋。

4、尋找適合當(dāng)前空格的數(shù)字的集合

def value(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：返回符合"每個(gè)橫排和豎排以及
    九宮格內(nèi)無(wú)相同數(shù)字"這個(gè)條件的有效值。
 """ 
 i, j = x//3, y//3
 grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
 v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
  set(list(zip(*m))[y])
 return list(v)

每個(gè)空格可以填入 1~9 中的任意一個(gè)數(shù)字，但要符合規(guī)則：每個(gè)空格填入 1~9 任意一個(gè)數(shù)字，需要保證每個(gè)橫排和豎排以及九宮格內(nèi)無(wú)相同數(shù)字。下面的代碼中的 grid 變量，保存的是當(dāng)前位置所處的九宮格。v 變量是通過(guò)集合運(yùn)算，將 1~9 這個(gè)數(shù)字集合中，與行的數(shù)字集合、列的數(shù)字集合以及九宮格的數(shù)字集合重疊的部分去除掉。剩余的部分就是符合條件的數(shù)字的集合。

5、使用遞歸嘗試解數(shù)獨(dú)（Sudoku）

def try_sudoku(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：試著填寫數(shù)獨(dú) """
 for v in value(m, x, y):
  m[x][y] = v
  next_x, next_y = get_next(m, x, y)
  if next_y == -1: # 如果無(wú)下一個(gè)空白格
   return True
  else:
   end = try_sudoku(m, next_x, next_y) # 遞歸
   if end: # 數(shù)獨(dú)解完之后，此處的 end 會(huì)是 True
    return True
   m[x][y] = 0 # 在遞歸的過(guò)程中，如果數(shù)獨(dú)沒(méi)有解開(kāi)，
      # 則回溯到上一個(gè)空白格

詳細(xì)內(nèi)容看注釋。

6、代碼展示

import random 
import sys 
sys.setrecursionlimit(100000) # 發(fā)現(xiàn)python默認(rèn)的遞歸深度是很有限的
        #（默認(rèn)是1000），因此當(dāng)遞歸深度超過(guò)999的
        # 樣子，就會(huì)引發(fā)這樣的一個(gè)異常。


def get_next(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：獲得下一個(gè)空白格在數(shù)獨(dú)中的坐標(biāo)。  
 """
 for next_y in range(y+1, 9): # 下一個(gè)空白格和當(dāng)前格在一行的情況
  if m[x][next_y] == 0:
   return x, next_y
 for next_x in range(x+1, 9): # 下一個(gè)空白格和當(dāng)前格不在一行的情況
  for next_y in range(0, 9):
   if m[next_x][next_y] == 0:
    return next_x, next_y
 return -1, -1    # 若不存在下一個(gè)空白格，則返回 -1，-1
  
def value(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：返回符合"每個(gè)橫排和豎排以及
    九宮格內(nèi)無(wú)相同數(shù)字"這個(gè)條件的有效值。
 """ 
 i, j = x//3, y//3
 grid = [m[i*3+r][j*3+c] for r in range(3) for c in range(3)]
 v = set([x for x in range(1,10)]) - set(grid) - set(m[x]) - \
  set(list(zip(*m))[y]) 
 return list(v)

def start_pos(m:"數(shù)獨(dú)矩陣"):
 """ 功能：返回第一個(gè)空白格的位置坐標(biāo)"""
 for x in range(9):
  for y in range(9):
   if m[x][y] == 0:
    return x, y
 return False, False # 若數(shù)獨(dú)已完成，則返回 False, False

def try_sudoku(m:"數(shù)獨(dú)矩陣", x:"空白格行數(shù)", y:"空白格列數(shù)"):
 """ 功能：試著填寫數(shù)獨(dú) """
 for v in value(m, x, y):
  m[x][y] = v
  next_x, next_y = get_next(m, x, y)
  if next_y == -1: # 如果無(wú)下一個(gè)空白格
   return True
  else:
   end = try_sudoku(m, next_x, next_y) # 遞歸
   if end:
    return True
   m[x][y] = 0 # 在遞歸的過(guò)程中，如果數(shù)獨(dú)沒(méi)有解開(kāi)，
      # 則回溯到上一個(gè)空白格

def sudoku(m):  
 x, y = start_pos(m)
 try_sudoku(m, x, y)
 print(m)  
 
  

     
if __name__ == "__main__":
 m = [
  [6, 0, 0, 1, 0, 0, 7, 0, 8],
  [0, 0, 0, 8, 0, 0, 2, 0, 0],
  [2, 3, 8, 0, 5, 0, 1, 0, 0],
  [0, 0, 0, 0, 4, 0, 0, 9, 2],
  [0, 0, 4, 3, 0, 8, 6, 0, 0],
  [3, 7, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 3, 0, 7, 0, 5, 2, 6],
  [0, 0, 2, 0, 0, 4, 0, 0, 0],
  [9, 0, 7, 0, 0, 6, 0, 0, 4]
 ]

 sudoku(m)
 
""" 數(shù)獨(dú)結(jié)果如下：
[
 [6, 9, 5, 1, 2, 3, 7, 4, 8], 
 [7, 4, 1, 8, 6, 9, 2, 5, 3], 
 [2, 3, 8, 4, 5, 7, 1, 6, 9], 
 [8, 1, 6, 7, 4, 5, 3, 9, 2], 
 [5, 2, 4, 3, 9, 8, 6, 7, 1], 
 [3, 7, 9, 6, 1, 2, 4, 8, 5], 
 [4, 8, 3, 9, 7, 1, 5, 2, 6], 
 [1, 6, 2, 5, 8, 4, 9, 3, 7], 
 [9, 5, 7, 2, 3, 6, 8, 1, 4]
]
"""

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: