我必须设计一个程序来使用回溯来解决NxN数独，N可以是1,4,9,16 .
我已经设法 Build 了一个解决4x4板的程序，但对于9x9板及以上，我对如何搜索网格感到困惑 .
到目前为止，我的代码如下 .
如何搜索square（n）x square（n）网格？
def is_solved(board, n):
# If board is not solved, return False.
for x in range(n): # vertical coordinate
for y in range(n): # horizontal coordinate
if board[x][y] == 0: # zero representing an empty cell
return False
return True # else, the board is filled and solved, return True
def find_possibilities(board, i, j, n):
# Finds all possible numbers of an entry
possible_entries = {}
# initialize a dictionary with possible numbers to fill board
for num in range(1, n+1):
possible_entries[num] = 0
# horizontal
for y in range(0, n):
if not board[i][y] == 0: # current position is not 0, not empty
possible_entries[board[i][y]] = 1
# vertical
for x in range(0, n):
if not board[x][j] == 0:
possible_entries[board[x][j]] = 1
for num in range(1, n+1):
if possible_entries[num] == 0:
possible_entries[num] = num
else:
possible_entries[num] = 0
return possible_entries
def sudoku_solver(board):
n = len(board)
i = 0
j = 0
if is_solved(board, n):
print(board)
return True
else:
# find the first empty cell
for x in range(0, n):
for y in range(0, n):
if board[x][y] == 0:
i = x
j = y
break
# find all possibilities to fill board[i][j]
possibilities = find_possibilities(board, i, j, n)
for x in range(1, n + 1):
if not possibilities[x] == 0:
board[i][j] = possibilities[x]
return sudoku_solver(board)
# backtracking step
board[i][j] = 0 # resets the cell to an empty cell
def solve_sudoku(board):
if sudoku_solver(board):
return True
else:
return False
1 回答
在我看来，你想要添加第三个检查，覆盖当前单元格所在的网格 . 对于任何板尺寸，我们可以假设网格将是板尺寸的平方根 .
然后每个单元格将位于一个网格中，该网格的最小列数为
int(i / math.sqrt(n))，最大值为int(column_minimum + i % math.sqrt(n))，最小行数为int(j / math.sqrt(n))，最大行数为int(row_minimum + j % math.sqrt(n)).迭代行和列并以与行和列检查相同的方式处理应该允许进行最终检查 .
该解决方案有效：