解決數獨難題的難點

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將變爲負值，因爲它回退到第一位。這實際上不會導致直接的錯誤，因爲您可以使用負值爲列表或數組編制索引，但在嘗試（和失敗）再次解決難題幾次後最終會引發異常。