我的數獨解算器總是返回無

Question

我寫了下面的數獨解算器：

# map 012 to 0, 345 to 1, 678 to 6 
dico = dict() 
for x in xrange(9) : 
     dico[ x ] = (x/3) * 3 
print dico 


def candidates(a, i, j) : 
    """"Get possible values at position (i,j) in array a""" 

    # 
    i2 = dico[ i ] 
    j2 = dico[ j ] 

    # 
    res = set(xrange(1,10)) 
    # same row 
    res -= set(a[ i ][ a[ i ] != 0 ]) 
    # same col 
    res -= set(a[ :, j ][ a[ :, j ] != 0 ]) 
    # same 3x3 square 
    res -= set(a[ i2:i2+3, j2:j2+3 ][ a[ i2:i2+3, j2:j2+3 ] != 0 ]) 
    # 
    return res 


# 
def solve(a) : 
    """Sudoku solver""" 

    # grid solved 
    if np.sum(a == 0) == 0 : 
     print "Grid solved" 
     print a 
     return a 

    else : 

     # 
     # Focus on the 1st 0 
     tmp_where = np.where(a == 0) 
     i, j = tmp_where[ 0 ][ 0 ], tmp_where[ 1 ][ 0 ] 

     # 
     for e in candidates(a, i, j) : 
      # 
      tmp = a.copy() 
      tmp[ i, j ] = e 
      # 
      solve(tmp) 

當我打電話res = solve(a)對於初始網格a，它打印正確的解決方案

# this is a 
[[2 0 0 0 8 0 3 0 0] 
[0 6 0 0 7 0 0 8 4] 
[0 3 0 5 0 0 2 0 9] 
[0 0 0 1 0 5 4 0 8] 
[0 0 0 0 0 0 0 0 0] 
[4 0 2 7 0 6 0 0 0] 
[3 0 1 0 0 7 0 4 0] 
[7 2 0 0 4 0 0 6 0] 
[0 0 4 0 1 0 0 0 3]] 

# this is the console output 
Grid solved 
[[2 4 5 9 8 1 3 7 6] 
[1 6 9 2 7 3 5 8 4] 
[8 3 7 5 6 4 2 1 9] 
[9 7 6 1 2 5 4 3 8] 
[5 1 3 4 9 8 6 2 7] 
[4 8 2 7 3 6 9 5 1] 
[3 9 1 6 5 7 8 4 2] 
[7 2 8 3 4 9 1 6 5] 
[6 5 4 8 1 2 7 9 3]] 

但是我不能用res，因爲它總是等於None！到底是怎麼回事？

res = solve(m) 
    print res == None # output is always True 

Answer 1

在遞歸調用中沒有return語句，這就是爲什麼結果是None。

def solve(a) : 
    """Sudoku solver""" 

    # grid solved 
    if np.sum(a == 0) == 0 : 
     print "Grid solved" 
     print a 
     return a 

    else : 

     # 
     # Focus on the 1st 0 
     tmp_where = np.where(a == 0) 
     i, j = tmp_where[ 0 ][ 0 ], tmp_where[ 1 ][ 0 ] 

     # 
     for e in candidates(a, i, j) : 
      # 
      tmp = a.copy() 
      tmp[ i, j ] = e 
      # 
      res = solve(tmp) 
      if res: #a failed path will return None, a success the solved matrix 
       return res