Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.prolog > #14207 > unrolled thread
| Started by | Mild Shock <janburse@fastmail.fm> |
|---|---|
| First post | 2024-10-02 00:14 +0200 |
| Last post | 2024-10-09 15:07 +0200 |
| Articles | 3 — 1 participant |
Back to article view | Back to comp.lang.prolog
Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-02 00:14 +0200
Re: Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-09 13:03 +0200
Re: Autumn Challenge 2024: Numbrix Puzzle Mild Shock <janburse@fastmail.fm> - 2024-10-09 15:07 +0200
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Date | 2024-10-02 00:14 +0200 |
| Subject | Autumn Challenge 2024: Numbrix Puzzle |
| Message-ID | <vdhs7n$1ivfk$1@solani.org> |
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!
[toc] | [next] | [standalone]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Date | 2024-10-09 13:03 +0200 |
| Message-ID | <ve5nui$6oa1$1@solani.org> |
| In reply to | #14207 |
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!
[toc] | [prev] | [next] | [standalone]
| From | Mild Shock <janburse@fastmail.fm> |
|---|---|
| Date | 2024-10-09 15:07 +0200 |
| Message-ID | <ve5v66$6s0r$1@solani.org> |
| In reply to | #14219 |
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! >
[toc] | [prev] | [standalone]
Back to top | Article view | comp.lang.prolog
csiph-web