Solve a Numbrix puzzle: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,125: | Line 1,125: | ||
41 42 45 46 49 50 81 80 79 |
41 42 45 46 49 50 81 80 79 |
||
solution found in 334 tries (0.00s) |
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> |
</pre> |
||