Anonymous user
Solve a Numbrix puzzle: Difference between revisions
no edit summary
No edit summary |
|||
Line 1,125:
41 42 45 46 49 50 81 80 79
solution found in 334 tries (0.00s)
</pre>
=={{header|Python}}==
<lang python>
from sys import stdout
neighbours = [[-1, 0], [0, -1], [1, 0], [0, 1]]
exists = []
lastNumber = 0
wid = 0
hei = 0
def find_next(pa, x, y, z):
for i in range(4):
a = x + neighbours[i][0]
b = y + neighbours[i][1]
if wid > a > -1 and hei > b > -1:
if pa[a][b] == z:
return a, b
return -1, -1
def find_solution(pa, x, y, z):
if z > lastNumber:
return 1
if exists[z] == 1:
s = find_next(pa, x, y, z)
if s[0] < 0:
return 0
return find_solution(pa, s[0], s[1], z + 1)
for i in range(4):
a = x + neighbours[i][0]
b = y + neighbours[i][1]
if wid > a > -1 and hei > b > -1:
if pa[a][b] == 0:
pa[a][b] = z
r = find_solution(pa, a, b, z + 1)
if r == 1:
return 1
pa[a][b] = 0
return 0
def solve(pz, w, h):
global lastNumber, wid, hei, exists
lastNumber = w * h
wid = w
hei = h
exists = [0 for j in range(lastNumber + 1)]
pa = [[0 for j in range(h)] for i in range(w)]
st = pz.split()
idx = 0
for j in range(h):
for i in range(w):
if st[idx] == ".":
idx += 1
else:
pa[i][j] = int(st[idx])
exists[pa[i][j]] = 1
idx += 1
x = 0
y = 0
t = w * h + 1
for j in range(h):
for i in range(w):
if pa[i][j] != 0 and pa[i][j] < t:
t = pa[i][j]
x = i
y = j
return find_solution(pa, x, y, t + 1), pa
def show_result(r):
if r[0] == 1:
for j in range(hei):
for i in range(wid):
stdout.write(" {:0{}d}".format(r[1][i][j], 2))
print()
else:
stdout.write("No Solution!\n")
print()
r = solve(". . . . . . . . . . . 46 45 . 55 74 . . . 38 . . 43 . . 78 . . 35 . . . . . 71 . . . 33 . . . 59 . . . 17"
" . . . . . 67 . . 18 . . 11 . . 64 . . . 24 21 . 1 2 . . . . . . . . . . .", 9, 9)
show_result(r)
r = solve(". . . . . . . . . . 11 12 15 18 21 62 61 . . 6 . . . . . 60 . . 33 . . . . . 57 . . 32 . . . . . 56 . . 37"
" . 1 . . . 73 . . 38 . . . . . 72 . . 43 44 47 48 51 76 77 . . . . . . . . . .", 9, 9)
show_result(r)
r = solve("17 . . . 11 . . . 59 . 15 . . 6 . . 61 . . . 3 . . . 63 . . . . . . 66 . . . . 23 24 . 68 67 78 . 54 55"
" . . . . 72 . . . . . . 35 . . . 49 . . . 29 . . 40 . . 47 . 31 . . . 39 . . . 45", 9, 9)
show_result(r)
</lang>{{out}}<pre>
49 50 51 52 53 54 75 76 81
48 47 46 45 44 55 74 77 80
37 38 39 40 43 56 73 78 79
36 35 34 41 42 57 72 71 70
31 32 33 14 13 58 59 68 69
30 17 16 15 12 61 60 67 66
29 18 19 20 11 62 63 64 65
28 25 24 21 10 01 02 03 04
27 26 23 22 09 08 07 06 05
09 10 13 14 19 20 63 64 65
08 11 12 15 18 21 62 61 66
07 06 05 16 17 22 59 60 67
34 33 04 03 24 23 58 57 68
35 32 31 02 25 54 55 56 69
36 37 30 01 26 53 74 73 70
39 38 29 28 27 52 75 72 71
40 43 44 47 48 51 76 77 78
41 42 45 46 49 50 81 80 79
17 16 13 12 11 10 09 60 59
18 15 14 05 06 07 08 61 58
19 20 03 04 65 64 63 62 57
22 21 00 00 66 79 80 81 56
23 24 69 68 67 78 77 54 55
26 25 70 71 72 75 76 53 52
27 28 35 36 73 74 49 50 51
30 29 34 37 40 41 48 47 46
31 32 33 38 39 42 43 44 45
</pre>
| |||