我正在用Python编写一个数独求解器,它接受一个部分填充的板,并使用回溯和前向检查来填充其余部分并解决难题。前向检查是指每次为空白单元格赋值时,检查其行、列和框中未赋值的“邻居”在赋值后是否仍有非空域。
为了表示我的board(dimensitions:N x N board with P x Q box),我使用了一个2D列表,其中每个条目的形式为[value,[domain]],其中value是为单元格分配的编号(如果未分配则为0),domain是使数独游戏保持一致的单元格的可能值。
我相信我的递归做错了什么,但不知道是什么。函数总是失败并返回false。下面是我的递归求解函数的一部分,预处理代码被删除了。如果有必要,我可以发布整个函数及其助手函数。
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
###some preprocessing here to check if puzzle is solved and find next empty cell if not
vals = board[row][col][1] #domain/possible values for the empty cell
for num in vals:
#if num doesn't violate the row, col, and box sudoku constraints
if constraintCheck(row, col, num, P, N, Q, board):
#make copy of cell's domain for backtracking
tempDomain = copy.deepcopy(board[row][col][1])
board[row][col][0] = num #assign num to the cell
#remove num from domains of neighbors,
#if an empty domain results after removing num,
#return False and the original board,
#else return True and the updated board
noEmptyDomains, board = propagate_fc(board, N, P, Q, row, col, num)
if noEmptyDomains:
board[row][col][1] = [num] #update domain to be num and then recurse
if fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
return True
#backtrack -- reset value and domain of assigned cell
board[row][col][1] = tempDomain
board[row][col][0] = 0
else:
board[row][col][0] = 0
return False
编辑:更多代码和试用Blckknght的解决方案
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return True
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
board[row][col][0] = num
noEmptyDomains, new_board = propagate_fc(board, N, P, Q, row, col, num) # new var
if noEmptyDomains:
new_board[row][col][1] = [num] # this doesn't modify board, only new_board
if fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout):
return True
board[row][col][0] = 0 # the only thing that's required to backtrack
return False
def propagate_fc(board, N, P, Q, row, col, num):
origBoard = copy.deepcopy(board)
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False, origBoard #domain is empty; return original board
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False, origBoard #domain is empty
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False, origBoard #domain is empty
return True, board #success; return board with updated domains
如果您正在进行回溯,您需要能够将您的板的状态返回到以前的状态。您当前的代码不能这样做。propagate_fc
函数以不容易撤消的方式修改board
。
由于我认为没有一种简单的方法可以逆转propagate_fc
的逻辑,所以我建议更改求解器的设计,使其复制板,并且在将其传递到进一步的递归步骤之前只修改副本。如果副本没有导致解决方案,可以扔掉它,而不是试图编写回溯代码来修复它。
(我肯定可以追溯,只是不清楚跟踪变化的好方法是什么,而且对这个答案来说,弄清楚它是太多的工作了。)
无论如何,以下是我对求解器修改版本的建议:
def fc_recursive_solve(board, N, P, Q, row, col, outputFile, timeout):
if time.clock() >= timeout:
return "timeout"
while row < N and board[row][col][0] != 0: #find next blank
if col == N-1:
row = row + 1
col = 0
else:
col = col + 1
if row == N: #solved
return board
for num in vals:
if constraintCheck(row, col, num, P, N, Q, board):
new_board = copy.deepcopy(board)
new_board[row][col][0] = num
if propagate_fc(new_board, N, P, Q, row, col, num):
new_board[row][col][1] = [num]
result = fc_recursive_solve(new_board, N, P, Q, row, col, outputFile, timeout)
if result is not None and result != "timeout":
return result
return None
以下是propagate_fc
的更改版本:
def propagate_fc(board, N, P, Q, row, col, num):
# no copying any more here
#row propagate
for x in range(N):
if board[x][col][0] == 0:
if num in board[x][col][1]:
board[x][col][1].remove(num)
if len(board[x][col][1]) == 0:
return False
#col propagate
for y in range(N):
if board[row][y][0] == 0:
if num in board[row][y][1]:
board[row][y][1].remove(num)
if len(board[row][y][1]) == 0:
return False
#box propagate
rDiv = row/P
cDiv = col/P
for i in range((rDiv * P), ((rDiv + 1) * P)):
for j in range((cDiv * Q), ((cDiv + 1) * Q)):
if board[i][j][0] == 0:
if num in board[i][j][1]:
board[i][j][1].remove(num)
if len(board[i][j][1]) == 0:
return False
return board #success; return new board
这里唯一真正的变化是,我不需要返回板
,因为我们总是在原地修改它。只需要bool结果(来说明board是否有效)。
(我最初认为还有另一个问题,If len(...)==0
检查每个块,但最终证明这并不是问题。只有当从当前
d a值(通过将这些块缩进两个级别)时,执行这些检查的性能可能会稍好一些,但这不太可能是性能上的巨大提升。)board[x][y][1]
列表中删除
问题内容: 如何回滚失败的Rails迁移?我希望这会撤消失败的迁移,但是不,它会回滚以前的迁移(失败的迁移减去一个)。而且也不起作用。我已经遇到过几次了,这非常令人沮丧。这是我做的一个简单测试,可以重复该问题: 结果: 好的,让我们回滚一下: 嗯?那是我在SimpleTest之前的最后一次迁移,而不是失败的迁移。(哦,如果迁移输出中包含版本号,那就太好了。) 因此,让我们尝试为失败的迁移Simpl
问题内容: 我试图在Windows 2008 R2中使用Kibana运行ElasticSearch。 我关注了这篇文章:在带有木瓜的Windows服务器上安装logstash 一步一步,但我得到的是: 当我去 我得到: 因此,似乎ElasticSearch正在运行,但是由于某些原因,Kibana无法连接到它。 ElasticSearch日志包含错误: 知道我在做什么错吗? 问题答案: 我也遇到过类
问题内容: 考虑以下脚本: 关键是,在所有这些步骤之后,此python进程在我的机器上的内存使用率约为30%(Python 2.6.5,是否可应要求提供更多详细信息?)。这是top输出的摘录: 分别 : 根据该文档为: 由于特定的实现,尤其是和,并非某些空闲列表中的所有项目都可能无法释放。 这是否意味着,如果我(暂时)需要大量的不同或数字,我需要这个导出到C / C ++,因为Python的GC没
我列出了一个问题“Spring事务失败回滚”。我有一个服务类,它调用2 DAO将数据插入到数据库表中。 我的事务配置: 我的服务和dao定义如下:
问题内容: 嗯,我有一个金钱对象,可以将其他金钱对象添加到其中。我在Java中尝试测试我的代码是否还可以,但是随后失败了。 我非常肯定自己的代码是正确的(返回正确的答案),我认为我使用的是错误的方式。T_T 如果要查找是否要进行测试,该怎么使用? 问题答案: 您没有在Money类中重写Object类中的方法。如果是这样,则通过它们的引用比较对象,在这种情况下,引用是不同的。 在这里您可以找到实施规
所以我正在尝试在我的新Windows7盒子上安装XAMPP。它将失败,出现以下错误消息。我启用了debug以供参考。 我检查了netstat,没有端口冲突。此外,我还确保安装了VS2008 redist(x64,这对我的系统是正确的)。我不确定从这里到哪里去。 正在尝试启动Apache应用程序...正在执行“C:\XAMPP\Apache\bin\httpd.exe”返回代码:0检测到状态更改:检