2017-03-23 6 views
0

バックトラックを使用してすべての可能な回答を保存したい しかし、追加された答えはスドク問題と同じです。 しかし、 "alist"に追加するときに "グリッド"を印刷すると問題ありません。どのように問題を解決できますか?コメントの代わりにスードクをバックトラッキングし、リスト内のすべての可能な回答を保存する

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) 

答えて

0

です実際に今問題が見つかりました。私はあなたの使用が奇妙であるという私の前のコメントに立つが、

これはあなたがalistgridを追加していますが、後で変更grid[x][y] = 0を呼び出すときにPythonのリストは、(私は右の用語だと思う)変更可能ですので、解決策を見つけたとき、オブジェクトでのpythonであるため、gridあなたの変数を考慮オブジェクトグリッドは、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の配列または類似のものよりも、リストにリストを使用しているので、おそらく、動作するようには思えません。

+0

ありがとうございます! –

0

「継続」のご利用が奇数である、

 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 

私の唯一の他のコメントが私ので、私は2番目の答えを追加している、あなたの関数が戻る「連想リスト」ということが、再帰では、あなたが(おそらくあなたは、APPENDに頼る?それは私には不明だ)、その値を使用することはありません

+0

私はdoes does 'がsudokuの制約を満たしているので、私はcontinueを使用します。行、列、または正方形には同じ番号を使用しないでください。 –

+0

私はそれがあなたが思っていることをしているとは思わないが、それは主要な問題ではないようだ - 私は実際に何が起こっていたのか分かったのでもう一度答えを加えた。 – Stael

関連する問題