解决数独难题的难点

Question

我被卡在解决数独谜题与python.I解决它使用回溯error.My方法CodeGo.net，正确地实现这个方法正确地达到了一些元素。但后一些元素它不移动到下一个空单元来实现这一点，但它正在着眼于那个特定的单元格。我认为我的函数来检查某个位置上的值是否有效是正确的。我无法弄清楚我正在做的错误。有人可以帮我解决这个问题。

代码：

from numpy import * 
def isValid(matrix,row,col): 
    element = matrix[row][col] 
    #print element 
    #print where(matrix[row,:] == element) 
    if len(where(matrix[row,:] == element)[0]) == 1 and len(where(matrix[:,col] == element)[0]) == 1: 
     #print 'entered' 
     row_type = row%3;col_type =col%3 
     row_index = row-row_type;col_index = col-col_type 
     if len(where(matrix[row_index:row_index+3,col_index:col_index+3])[0] == 1): 
      return 1 
     else: 
      return 0 
    else : 
     return 0 


sudoku = loadtxt('1') 
sudoku = array(sudoku,dtype = int) 

blankRow,blankCol = where(sudoku == 0) 
i=0 
while i< len(blankRow): 
    print 'i:',i 
    #print 'entered' 
    while sudoku[blankRow[i],blankCol[i]] < 9: 
     #print 'entered',sudoku[blankRow[i],blankCol[i]] 
     sudoku[blankRow[i],blankCol[i]] += 1 
     #j = sudoku[blankRow[i],blankCol[i]] 
     valid = isValid(sudoku,blankRow[i],blankCol[i]) 
     if valid == 1: 
      break   
    if sudoku[blankRow[i],blankCol[i]] == 9 and valid != 1: 
     print 'entered' #invalid,i:',i,'j',j,'row:',blankRow[i],'col:',blankCol[i] 
     sudoku[blankRow[i],blankCol[i]] = 0 
     i-= 1 
    i+=1 

Answer 1

你回溯永远不会奏效，因为你无条件地为外循环的末尾添加1〜i。我认为，要放在一个else块增量，附着在if它上面：

if sudoku[blankRow[i],blankCol[i]] == 9 and valid != 1: 
    print 'entered' #invalid,i:',i,'j',j,'row:',blankRow[i],'col:',blankCol[i] 
    sudoku[blankRow[i],blankCol[i]] = 0 
    i-= 1 
else:   # add this! 
    i+=1  # indent this! 

请注意，您可能需要添加一些额外的检查，以使你的代码的行为是否正确，将给出一个无解难题。在这种情况下，i将变为负值，因为它回退到第一位。这实际上不会导致直接的错误，因为您可以使用负值为列表或数组编制索引，但在尝试（和失败）再次解决难题几次后最终会引发异常。