Anonymous user
Solve a Numbrix puzzle: Difference between revisions
Added Prolog
m (C# added a remark.) |
(Added Prolog) |
||
Line 1,865:
41 42 45 46 49 50 81 80 79
solution found in 334 tries (0.00s)
</pre>
=={{header|Prolog}}==
<lang prolog>/*
* Solver
*/
solve([A|T]) :-
numlist(1,81,S),
select(A,S,R),
solve_([A|T],R).
solve_([_],[]).
solve_([A,B|T],R) :-
move(A,B),
select(B,R,Rt),
solve_([B|T],Rt).
move(A,B) :- lr(A,B) ; lr(B,A) ; ud(A,B) ; ud(B,A).
% create the left-right mapping rules at compile time
term_expansion(lr(0,0),LrList) :-
findall(LR,
(between(1,81,N), M is N mod 9, dif(M,0), succ(N,N1), LR = lr(N,N1)),
LrList).
lr(0,0).
% create the up-down mapping rules at compile time
term_expansion(ud(0,0),UdList) :-
findall(UD,
(between(1,72,N), N9 is N + 9, UD = ud(N,N9)),
UdList).
ud(0,0).
/*
* Grid <-> Solvable List
*/
grid_solvable([],_,_).
grid_solvable([A|T],N,S) :-
(integer(A) -> nth1(A,S,N);true),
succ(N,N1),
grid_solvable(T,N1,S).
solvable_grid([],_,_).
solvable_grid([A|T],N,G) :-
nth1(A,G,N),
succ(N,N1),
solvable_grid(T,N1,G).
/*
* Print Grid
*/
print_cell(C) :-
C >= 10 -> format(' ~d', C)
; format(' ~d', C).
print_grid([],_).
print_grid([C|T],N) :-
print_cell(C),
(0 is N mod 9 -> nl ; true),
succ(N,N1),
print_grid(T,N1).
/*
* Numbrix!
*/
numbrix(L) :-
length(S, 81),
grid_solvable(L,1,S),
solve(S),
solvable_grid(S,1,P),
print_grid(P,1),
!.
test1 :- numbrix([
_, _, _, _, _, _, _, _, _,
_, _, 46, 45, _, 55, 74, _, _,
_, 38, _, _, 43, _, _, 78, _,
_, 35, _, _, _, _, _, 71, _,
_, _, 33, _, _, _, 59, _, _,
_, 17, _, _, _, _, _, 67, _,
_, 18, _, _, 11, _, _, 64, _,
_, _, 24, 21, _, 1, 2, _, _,
_, _, _, _, _, _, _, _, _
]).
test2 :- numbrix([
_, _, _, _, _, _, _, _, _,
_, 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, _,
_, _, _, _, _, _, _, _, _
]).
test3 :- numbrix([
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
]).</lang>
{{out}}
<pre>
1 ?- test1.
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 1 2 3 4
27 26 23 22 9 8 7 6 5
true.
2 ?- test2.
9 10 13 14 19 20 63 64 65
8 11 12 15 18 21 62 61 66
7 6 5 16 17 22 59 60 67
34 33 4 3 24 23 58 57 68
35 32 31 2 25 54 55 56 69
36 37 30 1 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
true.
3 ?- test3.
17 16 13 12 11 10 9 60 59
18 15 14 5 6 7 8 61 58
19 20 3 4 65 64 63 62 57
22 21 2 1 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
true.
4 ?-
</pre>
| |||