稍微回顾一下历史: 从我小时候起，我就一直在玩一个非常简单的单人纸牌游戏，但我一直没有找到解决方案，老实说，我不知道是否有一个解决方案，但我想在我的电脑的帮助下找到答案.首先，让我解释一下规则:
- 首先，你必须拿一张网格表，画一个10x10正方形的面积.
- 接下来，你必须把第一个数字放在你的正方形上(我通常用0，0的正方形)
- 现在，您必须开始按照特定的跳转规则从1到100进行计数(我将立即开始)，并在您要跳转到的方块内注释相应的数字.
- skip 规则是:水平或垂直方向留2个空格，对角方向只留一个空格.
问题是: 我用Python语言编写了以下(非常慢的)代码.考虑到我的解释是计算机必须探测的可能性是100！，我认为"暴力"方法将需要相当长的时间.我运行的是第11代i7，但我的Python代码只在一个内核上执行.
我如何加速我的代码和/或我如何改进算法？
以下是代码:
class Gametable:
def __init__( self ):
#This value contains the maximum number reched by the algorithm
self.max_reached = 1
def start_at( self, coordX, coordY ):
tmpTable = [
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ]
]
#We do not need to check the first jump, since the table should be empty.
if self.is_valid_move( coordX, coordY, 1, tmpTable ):
print("Found a solution!")
else:
print("Found no solution :(")
def print_table( self, table ):
print(52*"-")
for X in range(10):
for Y in range(10):
if table[ X ][ Y ] == 0:
print("| ", end="")
else:
print("| {:02d} ".format( table[ X ][ Y ]), end='')
print(" |")
print(52*"-")
print()
def is_valid_move( self, X, Y, counter, table):
# Check bounds
if X < 0:
return False
elif X > 9:
return False
elif Y < 0:
return False
elif Y > 9:
return False
# Now check next steps
if table[ X ][ Y ]==0:
table[ X ][ Y ] = counter
if self.is_valid_move( X + 3, Y, counter+1, table ) or self.is_valid_move( X - 3, Y, counter+1, table ) or self.is_valid_move( X , Y + 3, counter+1, table ) or self.is_valid_move( X, Y - 3, counter+1, table ) or self.is_valid_move( X + 2, Y + 2, counter+1, table ) or self.is_valid_move( X + 2, Y - 2, counter+1, table ) or self.is_valid_move( X - 2, Y + 2, counter+1, table ) or self.is_valid_move( X - 2, Y - 2, counter+1, table ):
return True
else:
if counter > self.max_reached:
print("Max reached "+str(self.max_reached))
self.print_table(table)
self.max_reached = counter
table[X][Y] = 0 # We'll have to delete the last step if there is no further possibility
return False
mytable = Gametable()
mytable.start_at( 0, 0 )
这是一个游戏的例子:
