Re: Autumn Challenge 2024: Numbrix Puzzle

Another test with memoization was not yet
that successful. Maybe its time to introduce
multi-argument indexing? Have to investigate...
Mild Shock schrieb:

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!