스도쿠를 되돌리고 목록에 가능한 모든 답변을 저장하십시오.

Question

역 추적 을 사용하여 스도쿠의 가능한 모든 답변을 저장하고 싶지만 추가 답변은 스도쿠 문제와 같습니다. 그러나 "알리 스트"에 추가 할 때 "그리드"를 인쇄해도 문제가 없습니다. 문제를 어떻게 해결할 수 있습니까? 주석 대신에

def backtrack(grid,x,y,alist): 
    if x == 9: 

     alist.append(grid) 
     print(grid) 
     return alist 

    v = grid[x][y] 

    if v == 0: 
     for i in range(1,10): 

      check = True 
      if i in grid[x]: 
       check = False 
       continue 
      for row in range(0,9): 
       if i == grid[row][y]: 
        check = False 
        continue 

      for row in range(3*(x//3),3*(x//3)+3): 
       for col in range(3*(y//3),3*(y//3)+3): 
        if i == grid[row][col]: 
         check = False 
         continue 
      if check == True: 
       grid[x][y]= i 
       if y < 8: 
        backtrack(grid,x,y+1,alist) 

       else: 
        backtrack(grid,x+1,0,alist) 
     grid[x][y] = 0 
     return alist 
    else: 
     if y< 8: 
      backtrack(grid,x,y+1,alist) 
     else: 
      backtrack(grid,x+1,0,alist) 

     return alist 


problem = [[4, 0, 3, 0, 2, 0, 6, 0, 0], 
          [9, 6, 0, 3, 0, 0, 0, 0, 0], 
          [2, 0, 1, 8, 0, 6, 0, 9, 0], 
          [0, 0, 8, 1, 0, 2, 9, 0, 0], 
          [7, 2, 0, 0, 6, 0, 0, 0, 8], 
          [0, 0, 6, 7, 0, 8, 2, 0, 0], 
          [0, 0, 2, 6, 0, 9, 5, 0, 0], 
          [8, 0, 0, 2, 0, 3, 0, 0, 9], 
          [0, 0, 5, 0, 1, 0, 3, 0, 0]] 
alist = [] 
for a in backtrack(problem,0,0,alist): 
    print(a) 

Answer 1

실제로 문제를 발견했습니다. 비록 내가 당신의 사용이 이상하다는 나의 이전 논평을지지하지만.

고려하여 변수 grid이 객체는 파이썬이기 때문에 당신이 alist에 grid를 추가 해결책을 찾을 때 파이썬 목록을 변경할 수 있기 때문에,하지만 나중에 변경 grid[x][y] = 0를 호출 할 때 (그 오른쪽 용어 생각)을 alist의 첫 번째 위치에서 참조되는 object 그리드. alist에서 각 격자가 수정되었습니다

grid = [[4, 0, 3, 0, 2, 0, 6, 0, 0], 
         [9, 6, 0, 3, 0, 0, 0, 0, 0], 
         [2, 0, 1, 8, 0, 6, 0, 9, 0], 
         [0, 0, 8, 1, 0, 2, 9, 0, 0], 
         [7, 2, 0, 0, 6, 0, 0, 0, 8], 
         [0, 0, 6, 7, 0, 8, 2, 0, 0], 
         [0, 0, 2, 6, 0, 9, 5, 0, 0], 
         [8, 0, 0, 2, 0, 3, 0, 0, 9], 
         [0, 0, 5, 0, 1, 0, 3, 0, 0]] 

alist = [grid, grid, grid] 

grid[0][0] = "hello" 
print alist 

:

이 코드를 사용해보십시오.

대신 그리드 개체의 복사본을 만들어 알리미에 추가하면 How to clone or copy a list? 옵션을 볼 수 있습니다. 예 :

import copy 

... 

...alist.append(copy.deepcopy(grid)) 

copy.copy

는 오히려 NumPy와 배열 또는 이와 유사한 것보다, 목록과 목록을 사용하고 있기 때문에 가능성이 작동하지 않습니다.

Answer 2

:

 if i in grid[x]: 
      check = False 
      continue # here we break out to the next value of i 
     for row in range(0,9): 
      if i == grid[row][y]: 
       check = False 
       continue # here we move to the next value of 'row' 
          # which we would do anyway 

는 나는 당신이

로 이동 것이라고 많은 경우에 의미 생각 '계속'의 사용이 홀수

,

return alist 

.

내 유일한 코멘트는 재귀에 해당 값을 사용하지 않습니다 함수 반환 'alist'고하지만입니다 (아마도 당신은 APPEND에 의존? 그것은 나에게 불분명) 내가 있기 때문에 두 번째 대답을 추가 해요