为什么此算法（Sudoku回溯求解器）不起作用？

Question

我正在尝试遵循此视频中的代码：https://www.youtube.com/watch?v=G_UYXzGuqvM&t=557s

我看到了它，它看起来确实不错，给人印象深刻且简单，但是当我尝试自己实现它时，我找不到解决方案。递归将以初始网格终止，就像没有可能的解决方案一样。我有这段代码，应该构成一个可复制的示例。

import numpy as np

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

def possible (x,y,n):
  global grid
  for i in range(0,9):
    if grid[y][i] == n:
      return False
  for i in range (0,9):
    if grid[x][i] == n:
      return False
  x0 = (x//3)*3
  y0 = (y//3)*3
  for i in range(0,3):
    for j in range(0,3):
      if grid[y0+i][x0+j] == n:
        return False
  return True

def valid (x,y):
  global grid
  n=grid[x][y]
  c=0
  for i in range(0,9):
    if grid[y][i] == n:
      c+=1
  if c>1:
    return False
  c=0
  for i in range (0,9):
    if grid[x][i] == n:
      c+=1
  if c>1:
    return False
  c=0
  x0 = (x//3)*3
  y0 = (y//3)*3
  for i in range(0,3):
    for j in range(0,3):
      if grid[y0+i][x0+j] == n:
        c+=1
  if c>1:
    return False
  return True

def valid_grid():
  global grid
  for i in range(9):
    for j in range(9):
      if grid[i][j]!=0:
        if not valid(i,j):
          return False

  return True

def solve():
  global grid
  for y in range(9):
    for x in range(9):
      if grid[y][x] == 0:
        for n in range(1,10):
          if possible(y,x,n):
            grid[y][x] = n
            solve()
            grid[y][x] = 0
        return
print(valid_grid())
solve()
print(np.array(grid))

我在哪里弄错了？如果算法是蛮力的，为什么不找到任何解决方案？

Answer 1

看看这个块：

  for i in range(0,9):
    if grid[y][i] == n:
      return False
  for i in range (0,9):
    if grid[x][i] == n:
      return False

在我看来，那里存在索引问题。您可能希望将grid[x][i]替换为grid[i][x]。看来该问题在您的代码中的其他两个地方。