Python數獨解算器不會返回解決方案

Question

我一直在編寫這個程序，一點一滴地測試每個部分在繼續之前工作。但是，當我完成並將所有內容放在一起時，我無法獲得解決方案。我試圖通過爲每個方塊創建一個可能的數字列表來解決數獨，並通過基於現有的方塊去除它們。我認爲，當方格中只有一個可能的數字時，這就是解決方案。它會循環，直到完成。

我一直在尋找我的代碼半小時，仍然沒有運氣。我插入了一個raw_input("")以查看是否有任何問題。我發現它在開始時取得了一些進展，但隨後停止了。

因此，我打印了可能的座標數字和過程中的某處，每一種可能性都被刪除了。

下面是代碼看起來像現在：

# Create the Sodoku grid 
grid = [[3,2,0,1,6,0,8,0,9], 
     [0,7,8,9,0,3,1,2,6], 
     [6,0,0,8,0,0,4,5,3], 
     [7,1,0,4,0,0,0,6,2], 
     [5,4,0,0,0,0,0,0,7], 
     [0,0,0,2,0,5,3,1,0], 
     [0,5,9,7,4,0,2,0,8], 
     [2,0,7,5,0,9,0,0,0], 
     [8,6,4,0,0,0,0,9,5],] 

# Create possibilities 
possible = {} 
for y in range(9): 
    for x in range(9): 
     possible[(y,x)] = [1,2,3,4,5,6,7,8,9] 

# A function that returns the row it is in. 
def check_row(y,x): 
    return grid[y] 

# A function that returns the column it is in. 
def check_column(y,x): 
    column = [] 
    for hops in range(9): 
     column.append(grid[hops][x]) 
    return column 

# A function that returns the square it is in. 
# ------------- 
# 1| 0 | 1 | 2 | 
# ------------- 
# 2| 3 | 4 | 5 | 
# ------------- 
# 3| 6 | 7 | 8 | 
# ------------- 
# 1 2 3 
def check_square(they,thex): 

    square0 = [] 
    square1 = [] 
    square2 = [] 
    square3 = [] 
    square4 = [] 
    square5 = [] 
    square6 = [] 
    square7 = [] 
    square8 = [] 

    for y in range(3): 
     for x in range(3): 
      square0.append([y,x]) 

    for y in range(3): 
     for x in range(3,6): 
      square1.append([y,x]) 

    for y in range(3): 
     for x in range(6,9): 
      square2.append([y,x]) 

    for y in range(3,6): 
     for x in range(3): 
      square3.append([y,x]) 

    for y in range(3,6): 
     for x in range(3,6): 
      square4.append([y,x]) 

    for y in range(3,6): 
     for x in range(6,9): 
      square5.append([y,x]) 

    for y in range(6,9): 
     for x in range(3): 
      square6.append([y,x]) 

    for y in range(6,9): 
     for x in range(3,6): 
      square7.append([y,x]) 

    for y in range(6,9): 
     for x in range(6,9): 
      square8.append([y,x]) 

    tests = [square0, 
      square1, 
      square2, 
      square3, 
      square4, 
      square5, 
      square6, 
      square7, 
      square8] 

    square_list = [] 

    def list_of_grid(result): 
     for cood in result: 
      [they,thex] = cood 
      square_list.append(grid[they][thex]) 


    # Check which square it of and print the list of grid 
    for test in tests: 
     if [they,thex] in test: 
      list_of_grid(test) 

    return square_list 


# Function that eliminates row possibilities 
def elim_row(y, x): 

    get_rid_of = [] 
    for element in check_row(y, x): 
     if element != 0: 
      get_rid_of.append(element) 

    for stuff in get_rid_of: 
     try: 
      if stuff in possible[(y,x)]: 
       possible[(y,x)] = [] 
      else: 
       possible[(y,x)].remove(stuff) 
     except ValueError: 
      pass 

# Funciton that eliminates column possibilites 
def elim_column(y, x): 

    get_rid_of = [] 
    for element in check_column(y, x): 
     if element != 0: 
      get_rid_of.append(element) 

    for stuff in get_rid_of: 
     try: 
      if stuff in possible[(y,x)]: 
       possible[(y,x)] = [] 
      else: 
       possible[(y,x)].remove(stuff) 
     except ValueError: 
      pass 

# Function that eliminates square possibilites 
def elim_square(y, x): 

    get_rid_of = [] 
    for element in check_square(y, x): 
     if element != 0: 
      get_rid_of.append(element) 

    for stuff in get_rid_of: 
     try: 
      if stuff in possible[(y,x)]: 
       possible[(y,x)] = [] 
      else: 
       possible[(y,x)].remove(stuff)  
     except ValueError: 
      pass 

# Check if done: 
def done(): 
    empty = 0 
    for y in range(9): 
     for x in range(9): 
      if grid[y][x] == 0: 
       empty += 1 
    if empty == 0: 
     return True 
    else: 
     return False 

# print grid 
if __name__ == "__main__": 
    # Go through each row, column and square and delete possibilites 
    while done != True: 

     raw_input("") 

     for cood in possible.keys(): 
      (y, x) = cood 

      elim_row(y,x) 
      elim_column(y,x) 
      elim_square(y,x) 

      # Check if len of possible == 1 
      if len(possible[cood]) == 1: 
       grid[y][x] = possible[cood][0] 

     print possible[(0,2)] 
     for rows in grid: 
      print rows 

Answer 1

你永遠不呼叫done()。你只有在函數對象是永遠等於True測試：

while done != True: 

函數對象永遠不會等於True。不要測試平等在這裏，只需要調用該函數：

while not done(): 

接下來，在elim_row()你明確可能的值時，你遍歷所有的值，以消除：

for stuff in get_rid_of: 
    try: 
     if stuff in possible[(y,x)]: 
      possible[(y,x)] = [] 
     else: 
      possible[(y,x)].remove(stuff) 
    except ValueError: 
     pass 

這臺possible[(y,x)]爲空值任意行中的值不爲0.您在其他2 elim_函數中執行相同的操作。

你可能想使用：

for stuff in get_rid_of: 
    if stuff in possible[(y,x)]: 
     possible[(y,x)].remove(stuff) 

這將清除您的可能性真正的快。