Solve a Holy Knight's tour: Difference between revisions
Content added Content deleted
m (→ES6: (formatting)) |
No edit summary |
||
Line 2,817:
- - - - - 27 - 29 - - - - -
solution found in 61341542 tries, 61341486 backtracks (180.56s)
</pre>
=={{header|Python}}==
<lang python>
from sys import stdout
moves = [
[-1, -2], [1, -2], [-1, 2], [1, 2],
[-2, -1], [-2, 1], [2, -1], [2, 1]
]
def solve(pz, sz, sx, sy, idx, cnt):
if idx > cnt:
return 1
for i in range(len(moves)):
x = sx + moves[i][0]
y = sy + moves[i][1]
if sz > x > -1 and sz > y > -1 and pz[x][y] == 0:
pz[x][y] = idx
if 1 == solve(pz, sz, x, y, idx + 1, cnt):
return 1
pz[x][y] = 0
return 0
def find_solution(pz, sz):
p = [[-1 for j in range(sz)] for i in range(sz)]
idx = x = y = cnt = 0
for j in range(sz):
for i in range(sz):
if pz[idx] == "x":
p[i][j] = 0
cnt += 1
elif pz[idx] == "s":
p[i][j] = 1
cnt += 1
x = i
y = j
idx += 1
if 1 == solve(p, sz, x, y, 2, cnt):
for j in range(sz):
for i in range(sz):
if p[i][j] != -1:
stdout.write(" {:0{}d}".format(p[i][j], 2))
else:
stdout.write(" ")
print()
else:
print("Cannot solve this puzzle!")
# entry point
find_solution(".xxx.....x.xx....xxxxxxxxxx..x.xx.x..xxxsxxxxxx...xx.x.....xxx..", 8)
print()
find_solution(".....s.x..........x.x.........xxxxx.........xxx.......x..x.x..x..xxxxx...xxxxx..xx.....xx..xxxxx...xxxxx..x..x.x..x.......xxx.........xxxxx.........x.x..........x.x.....", 13)
</lang>
{{out}}<pre>
17 14 29
28 18 15
13 16 27 30 19 32 07
25 02 11 06 20
12 26 31 08 33
01 24 03 10 05 34 21
36 23 09
04 35 22
01 05
10 12
02 13 04 09 06
08 11 14
36 03 07 16
35 42 33 44 37 15 20 27 22 25
38 41 17 24
39 34 43 32 45 19 28 21 26 23
40 31 29 18
46 51 56
52 55 30 47 50
48 54
53 49
</pre>
| |||