一、問題描述

數獨(Sudoku)是一款大眾喜愛的數字邏輯游戲。玩家需要根據9X9盤面上的已知數字,推算出所有剩余空格的數字,并且滿足每一行、每一列、每一個粗線宮內的數字均含1-9,并且不重復。
輸入:
包含已知數字的9X9盤面數組[空缺位以數字0表示]
輸出:
完整的9X9盤面數組

輸入示例:

0 9 2 4 8 1 7 6 34 1 3 7 6 2 9 8 58 6 7 3 5 9 4 1 26 2 4 1 9 5 3 7 87 5 9 8 4 3 1 2 61 3 8 6 2 7 5 9 42 7 1 5 3 8 6 4 93 8 6 9 1 4 2 5 70 4 5 2 7 6 8 3 1

輸出示例:

5 9 2 4 8 1 7 6 34 1 3 7 6 2 9 8 58 6 7 3 5 9 4 1 26 2 4 1 9 5 3 7 87 5 9 8 4 3 1 2 61 3 8 6 2 7 5 9 42 7 1 5 3 8 6 4 93 8 6 9 1 4 2 5 79 4 5 2 7 6 8 3 1

二、思路

對于這個題我們的第一思路當然是用深度遍歷加回溯法來完成。

首先將數字存在9*9的二維數組數據結構內,其次尋找值為0的元素,將其換成1到9任一個數字。

　　若能滿足稱為數獨的三個條件,則繼續往下搜索值為0的元素。

　　　　同樣將其換成0到9之間的任意數字,若發現所有的數字都不滿足條件的話,則回溯到上一個點,并把該點的值繼續換成其他數字。

　　直到所有的81個點都遍歷完,若遍歷完發現沒有滿足條件的值可以填滿值為0的位子,則返回False。

三、代碼實現

首先我們先寫一個函數來判斷數字num是否可以放到9*9矩陣的(row,col)位置上。

def check(matrix,row,col,value):    """    檢測在(row,col)放value是否合適    1.每行含1-9,不含重復值value    2.每列含1-9,不含重復值value    3.3*3區塊含1-9,不含重復值value    """    #檢測每行    for j in range(9):        if matrix[row][j]==value:            return False    #檢測每列    for i in range(9):        if matrix[i][col]==value:            return False    # 檢測元素所在3*3區域    area_row=row//3*3    area_col=col//3*3    for i in range(area_row,area_row+3):        for j in range(area_col,area_col+3):            if matrix[i][j]==value:                return False    return True

然后我們就可以用回溯法來完成數獨游戲了:

def solveSudoku(matrix,count=0):    """    遍歷每一個未填元素,遍歷1-9替換為合適的數字    """    if count==81:#遞歸出口        return True    row=count//9#行標    col=count%9#列標    if matrix[row][col]!=0:#已填充        return solveSudoku(matrix,count=count+1)    else:#未填充        for i in range(1,10):            if check(matrix,row,col,i):#找到可能的填充數                matrix[row][col]=i                if solveSudoku(matrix,count=count+1):#是否可完成                    return True#可完成                #不可完成                matrix[row][col]=0#回溯, i換個數繼續走        return False#不可完成matrix=[]for i in range(9):    matrix.append(list(map(int,input().split())))# print(matrix)solveSudoku(matrix,0)# print(solveSudoku(matrix,0))# for i in range(9):#     print (' '.join(map(str,matrix[i])))# print(matrix)for li in matrix:    print(' '.join(list(map(str,li))))

這里值得注意的一點是,我們可以用遞歸函數來判斷,若我們將當前點的值設為 i 時,其余點是否可以完成數獨游戲,即:

for i in range(1,10):            if check(matrix,row,col,i):#找到可能的填充數                matrix[row][col]=i                if solveSudoku(matrix,count=count+1):#是否可完成                    return True#可完成

如果不能完成的話,則回溯,我們這里只需要將matrix[row][col]設為0,然后讓他接著遍歷0-9中的其余數即可。