Path: ...!eternal-september.org!feeder3.eternal-september.org!weretis.net!feeder8.news.weretis.net!reader5.news.weretis.net!news.solani.org!.POSTED!not-for-mail
From: Mild Shock <janburse@fastmail.fm>
Newsgroups: comp.lang.prolog
Subject: Re: Autumn Challenge 2024: Numbrix Puzzle
Date: Wed, 9 Oct 2024 13:03:46 +0200
Message-ID: <ve5nui$6oa1$1@solani.org>
References: <vdhs7n$1ivfk$1@solani.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 9 Oct 2024 11:03:46 -0000 (UTC)
Injection-Info: solani.org;
	logging-data="221505"; mail-complaints-to="abuse@news.solani.org"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.19
Cancel-Lock: sha1:E/HPIU2vRPIhA3uCNtb0aR+gvUk=
In-Reply-To: <vdhs7n$1ivfk$1@solani.org>
X-User-ID: eJwFwYEBwDAEBMCVCB7jpOL3H6F3YVBMOgIeDCpsa62ChNwcjqhIJmW3D32762PfzoEPTfdNmVa8LX/n/Vf/FeQ=
Bytes: 3353
Lines: 79

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!