InterviewBit – Sudoku

Source: InterviewBit – Sudoku

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
You may assume that there will be only one unique solution.

A sudoku puzzle,

and its solution numbers marked in red.

Example :

For the above given diagrams, the corresponding input to your program will be

[[53..7....], 
 [6..195...], 
 [.98....6.], 
 [8...6...3], 
 [4..8.3..1], 
 [7...2...6], 
 [.6....28.], 
 [...419..5], 
 [....8..79]]

and we would expect your program to modify the above array of array of characters to

[[534678912], 
 [672195348], 
 [198342567], 
 [859761423], 
 [426853791], 
 [713924856], 
 [961537284], 
 [287419635], 
 [345286179]]

---

解題：

1. 在開始解題之前，先複習一下一個合用的數獨資料需要符合哪些條件：
   1. 在同一列9個數字中沒有任何重複；
   2. 在同一行9個數字中沒有任何重複；
   3. 在以3*3劃分的九宮格9個數字中沒有任何重複。
2. 筆者最一開始是以自己實際上寫數獨題目的解題邏輯來思考怎麼拆解這題，大致上分為幾個步驟：
   1. 預設9*9每個格子均有9個數字可作為選擇填入其中；
   2. 接著先將題目提供之原始輸入值進行更新並依照 1. 的條件進行候選值之移除，舉例：

      輸入值第一行 row[0] = [53..7....]
      表示 row[0][2] 只能從 5, 3, 7 以外的6個數字中進行選擇及填入
      並以此類推

       

   3. 於上一步驟更新完成之後，檢查是否有只有一個候選數字之空格，如有則表示該格無須進行選擇及測試，可直接填入該數，完成後再次進行相關候選值之更新
3. 重複上一步驟之第二及第三項程序，直到所有待填入空格均有2個以上候選數字需另外測試。

   執行前三個步驟的程式碼如下附：

   class Solution:
       # @param A : list of list of chars
       # @return nothing
       def candidatorSettler(self, candidators, targetR, targetC,
   　　　　　　　　　　　　　　 rows, cols, matrix):
           """
           To be a valid candidator, the item must be:
           1. Not duplicated in such row
           2. Not duplicated in such column
           3. Not duplicated in such matrix
           So it must be a number not shown in its row, col, 
   　　　　　and matrix.
           """
           for i in rows[targetR]:
               try:
                   candidators.remove(i)
               except: continue
           for j in cols[targetC]:
               try:
                   candidators.remove(j)
               except: continue
           for k in matrix[targetR//3 * 3 + targetC // 3]:
               try:
                   candidators.remove(k)
               except: continue
           return candidators
   
       def candidatorsMaker(self, blanks, candLists, rows, cols,
   　　　　　　　　　　　　　 matrix): 
           """
           Find out the candidator lists which we can try fitting in
           but if the list only has one candidator, 
           we can just fill the blank without hesitation, 
   　　　　　then update the accompanied row, col, and matrix.
               
           If we cannot solve sudoku with just defined function 
   　　　　　candidatorsMaker,
           it would be necessary that we try to apply the 
            candidators and update the sudoku puzzle, 
            to find out which combination works.
           """
           puzzle_unsolved = False
           for i in range(9):
               for j in blanks[i]:
                   candLists[i][j] = self.candidatorSettler(
                                      candLists[i][j],
                                      i,j, rows, cols, matrix)
                   if len(candLists[i][j]) == 1:
                       rows[i][j] = candLists[i][j][0]
                       cols[j][i] = candLists[i][j][0]
                       matrix[i//3 * 3 + j // 3].append(
                                           candLists[i][j][0])
                       blanks[i].remove(j)
                       #print(rows[0])
                       return (True, blanks, candLists, 
                               rows, cols, matrix)
           for i in range(9):
               if len(blanks[i]) == 0: continue
               #Try combinations to fix the puzzle
               puzzle_unsolved = True
               break
           if puzzle_unsolved: 
               rows = self.candidatorsTryer(rows, candLists)
                       
           return (False, blanks, candLists, rows, cols, matrix)
   
       def solveSudoku(self, A):
           """
           remember: we only need to try updating blanks with 
           possible candidators for that specific blank.
           if found any blanks with just one candidator,
           update the sudoku, break the loops, and re-run
           """
           rows = [['0' for _ in range(9)] for _ in range(9)]
           cols = [['0' for _ in range(9)] for _ in range(9)]
           matrix = [[] for _ in range(9)]
           blanks = [[] for _ in range(9)]
           for i in range(9):
               for j in range(9):
                   if A[i][j] != ".":
                       rows[i][j] = A[i][j]
                       cols[j][i] = A[i][j]
                       matrix[i//3 * 3 + j // 3].append(A[i][j])
                   else:
                       blanks[i].append(j)
           #create candidators sets
           candLists = [[[] for _ in range(9)] for _ in range(9)]
           for i in range(9):
               for j in blanks[i]:
                   candLists[i][j] = list(map(str, range(1,10)))
           unsolved = True
           while unsolved:
               unsolved, blanks, candLists, rows, cols, matrix = 
                         self.candidatorsMaker(blanks, candLists, 
                                              rows, cols, matrix)
   
           for i in range(9):
               A[i] = "".join(rows[i])

4. 基本上前三個步驟便可以解決一些基礎的數獨問題，但在遇到需要塞數字進去進行測試的場合就完全不管用了。為了解決這個問題，需要另外設計一個backtracking機制來進行填空選擇之測試及更新，筆者原本的想法也很簡單，就是照著前幾個步驟得到的候選數字們進行更新，但在進行 list.remove(k) 的過程中會造成不可逆的結果，以致如更新後發現這個組合不可行亦無法回頭更換候選數字後重新測試。而如果候選數字不可行，則解決辦法便只剩從1-9每個數字均嘗試填入進行測試（筆者於寫這篇解析時才另外想到，針對候選數字可以不更新候選陣列，也就是不執行 list.remove(k)，即使只採用前面步驟得到的候選數字陣列仍可有效減少不必要之數值測試。）。
   而在進行填入數字並進行 backtracking 測試時，最重要的是必須讓儲存值的 9*9 矩陣保持彈性，並在確認當前組合不可行後具備數值回溯及窮盡所有可行組合之能力。
   針對執行步驟四所設計之程式碼詳如下附：

    def valChecker(self, trows, i, j, k):
        if (k in trows[i]) or (k in [trows[l][j] for l 
　　　　　　　　　　　　　　　　　in range(9)]) \
            or (k in [trows[i//3*3 + l][j//3*3] for l 
　　　　　　　　　　　　　　　　　in range(3)]) \
            or (k in [trows[i//3*3 + l][j//3*3 + 1] for l 
                               in range(3)]) \
            or (k in [trows[i//3*3 + l][j//3*3 + 2] for l 
                               in range(3)]):
                return False
        return True

    def candidatorsTryer(self, rows, candLists, i = 0, j = 0):
        """
        After finding out that the sudoku puzzle cannot be 
        finished with candidatorsMaker
        For the blanks left, we have to try each possible option 
        till one complete puzzle is done
        """
        if i == 9: return rows
        if j == 8:
            nextR = i+1
            nextC = 0
        else:
            nextR = i
            nextC = j + 1
        if rows[i][j] != "0": 
            return self.candidatorsTryer(rows, candLists, 
                                         nextR, nextC)
        for k in candLists[i][j]:
            if self.valChecker(rows, i, j, k):
                rows[i][j] = k
                if self.candidatorsTryer(rows, candLists, 
                                         nextR, nextC): 
                    return rows
                rows[i][j] = "0"
        return False

在這個架構下，如發生該空格所有候選數均無法符合數獨格式要求，便會回溯至遞迴程式的上一層並進行更新，如此便可避免更新錯誤及遺漏可能可行組合之情況。

 

GitHub: GitHub

後記：網站提供之建議解答是直接對所有待填入數值之空格直接進行步驟4之遞迴更新，程式碼相對簡潔，有興趣者亦可參考此GitHub連結。