[python]连线不过黑点问题尝试

在贴吧看到这样一个问题(简化一下)
0 -1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
要求不过“-1”这个点,把“0”连起来,不能重复,不能斜着连。
感觉挺有意思的就遍了这么个东西

import numpy as np

Found = False
# zx:=row number;zy:=col number
zx = 6
zy = 5
# black point(bx,by)
bx = 1
by = 0
times = 0

def generatePoints():
global zx
global zy
global bx
global by
points = np.zeros((zx,zy))
for row in range(zx):
for cal in range(zy):
p = 0
if row == by and cal == bx:
p = -1
points[row,cal] = p
return points

def walk(curPoint,keepWalking,pathMap,step):
global Found
global zx
global zy
global times
if keepWalking and not Found:
# (1,0)
nextPoint = [curPoint[0] + 1, curPoint[1]] if (nextPoint[0]) = 0 and not Found:
if pathMap[nextPoint[0],nextPoint[1]] == 0:
nestStep = step + 1
newMap = pathMap.copy()
newMap[nextPoint[0], nextPoint[1]] = nestStep
walk(nextPoint, True, newMap,nestStep)
else:
if 0 not in pathMap:
print("solution")
Found = True
print(pathMap)
else:
times += 1

# (0,1)
nextPoint = [curPoint[0], curPoint[1] + 1] if (nextPoint[1]) = 0 and not Found:
if pathMap[nextPoint[0],nextPoint[1]] == 0:
nestStep = step + 1
newMap = pathMap.copy()
newMap[nextPoint[0],nextPoint[1]] = nestStep
walk(nextPoint, True, newMap,nestStep)
else:
if 0 not in pathMap:
Found = True
print("solution")
print(pathMap)
else:
times += 1

def pathing(sp,points):
step = 1
pathMap = points.copy()
pathMap[sp[0],sp[1]] = step
walk(sp,True,pathMap,step)

points = generatePoints()
print("initial points map")
print(points)
for row in range(zx):
if not Found:
for cal in range(zy):
if not Found:
p = points[row,cal] if p == 0:
# start
sp = [row,cal] pathing(sp,points)
else:
continue

if not Found:
print("no solution found")
print(times,"tried")

因为没有仔细测过,不知道有没有逻辑问题。
跑出来最后是无解
initial points map
[[ 0. -1. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.]] no solution found
1899691 tried
但是稍微改改,比如矩阵大小或者-1的位置,还是能跑出东西的。
initial points map
[[-1. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.] [ 0. 0. 0. 0. 0.]] solution
[[-1. 1. 18. 19. 20.] [ 3. 2. 17. 16. 21.] [ 4. 9. 10. 15. 22.] [ 5. 8. 11. 14. 23.] [ 6. 7. 12. 13. 24.]] 47524 tried
++++++++++++++++++++++++++++++
initial points map
[[ 0. -1. 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.]] solution
[[ 1. -1. 29. 28. 27.] [ 2. 11. 12. 25. 26.] [ 3. 10. 13. 24. 23.] [ 4. 9. 14. 21. 22.] [ 5. 8. 15. 20. 19.] [ 6. 7. 16. 17. 18.]] 443 tried

作者:Iyon_

相关推荐

在这里插入图片描述

表白小程序:python代码–樱花树(Turtle库)

python获取抖音无水印地址demo

python基础教程:浅谈python for循环的巧妙运用(迭代、列表生成式)

规则

智慧魔珠金字塔(类似俄罗斯方块)的所有情况 python