Python whileループが早く終了する

Question

解決済みのsudokuパズルを解き放つPythonプログラムを作ろうとしています。これは、タイルの座標をランダムに生成し、そのタイルに既に数値が入っている場合は、再度試みます。それはそこに置くために1と9の間の数を生成し、その行、列、またはセクションにその数がまだなければ、値を割り当てて占有タイルのリストにその座標を追加します。すべてのタイルが塗りつぶされたら、ループを終了して完成したグリッドを返すことになっています。

問題は、約70回のループの後にいつも停止するため、プログラムがフリーズすることです。ここで

は私が話している関数のコードです：

def populate(grid): 
    usedCoords = [] 
    populated = False 
    while not populated: 
     x = random.randrange(len(grid)) 
     y = random.randrange(len(grid)) 
     while [x,y] in usedCoords: 
      x = random.randrange(len(grid)) 
      y = random.randrange(len(grid)) 
     value = random.randrange(1, len(grid) + 1) 
     if not rowCheck(grid, x, y, value) and not columnCheck(grid, x, y, value) and not squareCheck(grid, x, y, value): 
      grid[x][y] = value 
      usedCoords.append([x,y]) 
      print(len(usedCoords)) 
     if len(usedCoords) == len(grid) ** 2: 
      populated = True 
    return grid 

そして、ここではそれを参照する関数のコードです：

def rowCheck(grid, x, y, value): 
    for i in range(len(grid)): 
     if not i == x: 
      if grid[i][y] == value: 
       return True 
    return False 

def columnCheck(grid, x, y, value): 
    for i in range(len(grid)): 
     if not i==y: 
      if grid[x][i] == value: 
       return True 
    return False 

def squareCheck(grid, x, y, value): 
    grid2 = [0] * (sectionSide) #new grid for the specific section 
    for i in range(len(grid2)): 
     grid2[i] = [0] * sectionSide 
    for i in range(x - (sectionSide - 1), x + sectionSide): #scanning only nearby coordinates 
     for j in range(y - (sectionSide - 1), y + sectionSide): 
      try: 
       if i // sectionSide == x // sectionSide and j // sectionSide == y // sectionSide: 
        grid2[i][j] = grid[x][y] 
      except IndexError: 
       pass 
    for i in range(len(grid2)): 
     for j in range(len(grid2[i])): 
      if grid2[i][j] == value and not (i == x and j == y): 
       return True 
    return False 

Answer 1

がある他の問題かもしれませんが、あなたのコードに大きな問題があるのは、解決できないボード状態が作成されていれば、それを取り戻す方法がないということです。あなたのコードは、ボードの最初の2行で、次の値を入れたらどうなるか考えてみましょう：

1 2 3 4 5 6 7 8 9 
4 5 6 7 8 1 2 3 

これまでに配置されている数字はすべての法的ですが、あなたが置くことができる何の数がありません2行目の最後のスペース。私はあなたのコードが最終的にこのようなボードの位置の束を作成するときに固執していると思うだろう、これは任意の価値を取ることができません。法的手続きが残っていなければ、それは永遠に繰り返されます。

この問題を回避するには、より洗練されたアルゴリズムが必要です。