From Newsgroup: comp.lang.prolog
Woa! I am always struggling to beat SWI-Prolog,
since I am always 2-3 times slower. But this
time not, possibly to do that the problem
is highly non-deterministic, so SWI-Prologs
clever tail recursion cannot kick in. Plus
my neck optimization possibly shows in predicates
such as next/2, since it also applies if there is
no cut (!)/0 and for predicates such as arithmetic
comparison and arithmetic evaluation as well,
and next optimization is ultra fast, since it
uses the native stack for these cases as well.
Here a bitwise based search:
/* SWI-Prolog 9.3.11 */
?- between(4,6,N), K is N^2-1,
time(aggregate_all(count, (between(0,K,P),
Q is 1<<P, path3(P, Q, N)), C)), write(C), nl, fail; true.
% 471,690 inferences, 0.031 CPU in 0.042 seconds
(74% CPU, 15094080 Lips)
552
% 53,076,891 inferences, 4.422 CPU in 4.428 seconds
(100% CPU, 12003255 Lips)
8648
% 15,537,147,614 inferences, 1421.922 CPU in 1438.575 seconds
(99% CPU, 10926864 Lips)
458696
/* Dogelog Player 1.2.4, JDK 22 */
?- between(4,6,N), K is N^2-1,
time(aggregate_all(count, (between(0,K,P),
Q is 1<<P, path3(P, Q, N)), C)), write(C), nl, fail; true.
% Zeit 76 ms, GC 0 ms, Lips 6258960, Uhr 09.10.2024 12:31
552
% Zeit 3507 ms, GC 1 ms, Lips 15151859, Uhr 09.10.2024 12:31
8648
% Zeit 1256978 ms, GC 76 ms, Lips 12363270, Uhr 09.10.2024 12:52
458696
But the difference of being faster is only small...
Mild Shock schrieb:
Hi,
A path inside a rectangular grid can be
encoded by numbering the cells so that
successive integers are in adjacent cells.
Example:
3---2---1 20--21
| | |
4 17--18--19 22
| | |
5 16--15--14 23
| | |
6 9--10 13 24
| | | | |
7---8 11--12 25
Turn it into a so called Numbrix puzzle,
created by Marilyn vos Savant, in that
you reveal a few numbers, and
the solitaire player has find and fill
the remaining numbers. Similar approach
as in Sudoku, except the constaints are
different. Implement the following in Prolog:
a) A solver for Numbrix
b) A riddle generator for Numbrix
c) Some game play for Numbrix
Have Fun!
--- Synchronet 3.20a-Linux NewsLink 1.114