Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14220

Re: Autumn Challenge 2024: Numbrix Puzzle

Show all headers | View raw

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!
> 

Back to comp.lang.prolog | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web