相關介紹

什么是數獨？

數獨是源自18世紀瑞士的一種數學游戲，是一種運用紙、筆進行演算的邏輯游戲，玩家需要根據9×9盤面上的已知數字，推理出所有剩余空格的數字，并滿足每一行、每一列、每一個粗線宮（3*3）內的數字均含1-9，不重復 ，
數獨盤面是個九宮，每一宮又分為九個小格，在這八十一格中給出一定的已知數字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數字，使1-9每個數字在每一行、每一列和每一宮中都只出現一次，所以又稱“九宮格”，

什么是回溯法？

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標，但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”，使用回溯法的核心是記錄每一步操作的位置，并在當前位置的數字均不符合條件時退回至上一位置，由此，可以使用堆疊來實作，

思路及實作

演算法思路

首先，從第一行開始尋找第一個待填寫的元素位置，并壓入用于記錄每次操作位置的堆疊中；然后，判斷此時該位置元素是否合法（合法：即該數字位于0-9之間，并且與該數字所在行、所在列、所在宮內的數字均不重復），當該數字合法時，則繼續尋找下一個待填寫的位置，并壓入堆疊中；當該數字不合法時，若該數字還沒有大于9則自增，若該數字已大于9則退回至上一位置（當前位置歸零并彈出）；最后，當最后一個待填寫的元素合法且不等于0之前，重復執行上述步驟，

代碼撰寫

設定記錄空位置的堆疊

• 首先，宣告串列，

#全域變數記錄空位置（使用回溯法）
indexList = []

• 然后，實作入堆疊和出堆疊的方法，

# --- 入堆疊 --- #
def myPush(coordinate):
	indexList.append(coordinate)

# --- 出堆疊 --- #
def myPop():
	indexList.pop()

尋找第一個空元素位置

# --- 尋找第一個空元素位置 --- #
def firstEmpty():
    for i in range(0,9):
        for j in range(0,9):
            if sudoku[i][j] == 0:
                myPush([i,j])
                return

尋找最后一個空元素位置

# --- 尋找最后一個空元素位置 --- #
def lastEmpty():
    for i in range(8,-1,-1):
        for j in range(8,-1,-1):
            if sudoku[i][j] == 0: #'0'
                return [i,j]

位置判空加入堆疊中

# --- 位置判空加入堆疊中 --- #
def isEmpty():
    #獲取堆疊頂元素
    a,b = indexList[-1]
    #從下一元素開始找起
    b += 1 
    for i in range(a,9):
        if i != a:
            b = 0
        for j in range(b,9):
            if sudoku[i][j] == 0:
                myPush([i,j])
                return

當前位置自增

# --- 當前位置自增 ---#
def myAdd():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    sudoku[x][y] += 1

判斷當前位置是否合法

# --- 判斷當前位置是否合法 --- #
def isLegal():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    temp = sudoku[x][y]

    #判斷該行是否重復
    for i in range(9):
        if sudoku[x][i] == temp and i != y:
            return False; #當前位置不合法

    #判斷該列是否重復
    for i in range(9): 
        if sudoku[i][y] == temp and i != x:
            return False; #當前位置不合法

    #判斷該宮是否重復
    xx = int(x / 3)
    yy = int(y / 3)
    for i in range(3):
        for j in range(3):
            if sudoku[xx * 3 + i][yy * 3 + j] == temp and (xx * 3 + i) != x and (yy * 3 + j) != y:
                return False; #當前位置不合法
    return True #當前位置合法

判斷某一位置是否合法 (用于判斷末尾元素)

# --- 判斷某一位置是否合法 --- #
def oneIsLegal(x,y):
    temp = sudoku[x][y]
    #判斷該行是否重復
    for i in range(9):
        if sudoku[x][i] == temp and i != y:
            return False; #當前位置不合法

    #判斷該列是否重復
    for i in range(9): 
        if sudoku[i][y] == temp and i != x:
            return False; #當前位置不合法

    #判斷該宮是否重復
    xx = int(x / 3)
    yy = int(y / 3)
    for i in range(3):
        for j in range(3):
            if sudoku[xx * 3 + i][yy * 3 + j] == temp and (xx * 3 + i) != x and (yy * 3 + j) != y:
                return False; #當前位置不合法
    return True #當前位置合法

回退函式

# --- 回退函式 --- #
def myReturn():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    sudoku[x][y] = 0
    myPop()

輸出數獨

# --- 輸出數獨 --- #
def myOutput():
    print("答案為：")
    for i in range(9):
        print(sudoku[i])

主程式

# --- 程式入口 --- #
def main():
    #尋找首個空元素
    firstEmpty()

    #尋找末尾空元素
    last = lastEmpty()
    m,n = last

    #當末尾空元素合法且不等于0時停止回圈
    while oneIsLegal(m,n) != True or sudoku[m][n] == 0:
        #獲取堆疊頂元素
        x,y = indexList[-1]

        #判斷當前位置是否合法
        if isLegal() == True and sudoku[x][y] <= 9 and 0 < sudoku[x][y]:
            #尋找下一個空元素
            isEmpty()
        else:
            #不合法 - 回退
            if sudoku[x][y] >= 9:
                myReturn()
                myAdd()
            else: #不合法 - 自增
                myAdd()
    myOutput()

if __name__ == "__main__":
    main()

測驗數獨

#儲存數獨元素
sudoku = [[8,0,0,0,0,0,0,0,0],
          [0,0,3,6,0,0,0,0,0],
          [0,7,0,0,9,0,2,0,0],
          [0,5,0,0,0,7,0,0,0],
          [0,0,0,0,4,5,7,0,0],
          [0,0,0,1,0,0,0,3,0],
          [0,0,1,0,0,0,0,6,8],
          [0,0,8,5,0,0,0,1,0],
          [0,9,0,0,0,0,4,0,0],
]

運行結果

完整代碼

#全域變數記錄空位置（使用回溯法）
indexList = []

#儲存數獨元素
sudoku = [[8,0,0,0,0,0,0,0,0],
          [0,0,3,6,0,0,0,0,0],
          [0,7,0,0,9,0,2,0,0],
          [0,5,0,0,0,7,0,0,0],
          [0,0,0,0,4,5,7,0,0],
          [0,0,0,1,0,0,0,3,0],
          [0,0,1,0,0,0,0,6,8],
          [0,0,8,5,0,0,0,1,0],
          [0,9,0,0,0,0,4,0,0],
]

# --- 程式入口 --- #
def main():
    #尋找首個空元素
    firstEmpty()
    #尋找末尾空元素
    last = lastEmpty()
    m,n = last
    #當末尾空元素合法且不等于0時停止回圈
    while oneIsLegal(m,n) != True or sudoku[m][n] == 0:
        #獲取堆疊頂元素
        x,y = indexList[-1]
        #判斷當前位置是否合法
        if isLegal() == True and sudoku[x][y] <= 9 and 0 < sudoku[x][y]:
            #尋找下一個空元素
            isEmpty()
        else:
            #不合法 - 回退
            if sudoku[x][y] >= 9:
                myReturn()
                myAdd()
            else: #不合法 - 自增
                myAdd()
    myOutput()

# --- 尋找第一個空元素位置 --- #
def firstEmpty():
    for i in range(0,9):
        for j in range(0,9):
            if sudoku[i][j] == 0: #'0'
                myPush([i,j])
                return

# --- 尋找最后一個空元素位置 --- #
def lastEmpty():
    for i in range(8,-1,-1):
        for j in range(8,-1,-1):
            if sudoku[i][j] == 0: #'0'
                return [i,j]

# --- 位置判空加入堆疊中 --- #
def isEmpty():
    #獲取堆疊頂元素
    a,b = indexList[-1]
    #從下一元素開始找起
    b += 1
    for i in range(a,9):
        if i != a:
            b = 0
        for j in range(b,9):
            if sudoku[i][j] == 0: #'0'
                myPush([i,j])
                return

# --- 入堆疊 --- #
def myPush(coordinate):
    indexList.append(coordinate)

# --- 出堆疊 --- #
def myPop():
    indexList.pop()

# --- 當前位置自增 ---#
def myAdd():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    sudoku[x][y] += 1

# --- 判斷當前位置是否合法 --- #
def isLegal():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    temp = sudoku[x][y]
    #判斷該行是否重復
    for i in range(9):
        if sudoku[x][i] == temp and i != y:
            return False; #當前位置不合法
    #判斷該列是否重復
    for i in range(9): 
        if sudoku[i][y] == temp and i != x:
            return False; #當前位置不合法
    #判斷該宮是否重復
    xx = int(x / 3)
    yy = int(y / 3)
    for i in range(3):
        for j in range(3):
            if sudoku[xx * 3 + i][yy * 3 + j] == temp and (xx * 3 + i) != x and (yy * 3 + j) != y:
                return False; #當前位置不合法
    return True #當前位置合法
    
# --- 判斷某一位置是否合法 --- #
def oneIsLegal(x,y):
    temp = sudoku[x][y]
    #判斷該行是否重復
    for i in range(9):
        if sudoku[x][i] == temp and i != y:
            return False; #當前位置不合法
    #判斷該列是否重復
    for i in range(9): 
        if sudoku[i][y] == temp and i != x:
            return False; #當前位置不合法
    #判斷該宮是否重復
    xx = int(x / 3)
    yy = int(y / 3)
    for i in range(3):
        for j in range(3):
            if sudoku[xx * 3 + i][yy * 3 + j] == temp and (xx * 3 + i) != x and (yy * 3 + j) != y:
                return False; #當前位置不合法
    return True #當前位置合法

# --- 回退函式 --- #
def myReturn():
    #獲取堆疊頂元素
    x,y = indexList[-1]
    sudoku[x][y] = 0
    myPop()

# --- 輸出數獨 --- #
def myOutput():
    print("答案為：")
    for i in range(9):
        print(sudoku[i])

if __name__ == "__main__":
    main()