Autumn Challenge 2024: Numbrix Puzzle

General
22

You are right giving up point/1 makes it again faster

next(X-Y, X2-Y) :-
  between(0, 2, X),
  X2 is X+1,
  between(0, 3, Y).
next(X-Y, X2-Y) :-
  between(1, 3, X),
  X2 is X-1,
  between(0, 3, Y).
next(X-Y, X-Y2) :-
  between(0, 3, X),
  between(0, 2, Y),
  Y2 is Y+1.
next(X-Y, X-Y2) :-
  between(0, 3, X),
  between(1, 3, Y),
  Y2 is Y-1.
line([P1, P2]) :-
  next(P1, P2).
line([P1, P2 | Rs]) :-
  line([P2 | Rs]),
  next(P1, P2),
  \+ member(P1, Rs).
""") 

Query: time(aggregate_all(count, (length(_L, 16), line(_L)), C))
% 1,400,301 inferences, 0.078 CPU in 0.078 seconds (100% CPU, 18003404 Lips)
{'truth': True, 'C': 552}
23

You can also give up most of the between/3. You only
need a point/1 for the last element of your list _L.
Like this, also swapping the two next/2 call argument order:

next(X-Y, X2-Y) :- X < 3, X2 is X+1.
next(X-Y, X2-Y) :- X > 0, X2 is X-1.
next(X-Y, X-Y2) :- Y < 3, Y2 is Y+1.
next(X-Y, X-Y2) :- Y > 0, Y2 is Y-1.
point(X-Y) :- 
  between(0, 3, X),
  between(0, 3, Y).
line([P1, P2]) :-
  point(P2),
  next(P2, P1).
line([P1 | Rs]) :-
  line(Rs),
  Rs = [P2 | _],
  next(P2, P1),
  \+ member(P1, Rs).

Swpping argument order of next/2 preserves validity
since next/2 is symmetric, no re-programming of next/2
was needed. But it helps to establish ground input

to ground output dataflow in each next/2 call:

?- time(aggregate_all(count, (length(_L, 16), line(_L)), C)).
% 893,214 inferences, 0.047 CPU in 0.058 seconds (81% CPU, 19055232 Lips)
C = 552.

The number of inferences went down from 1,400,301
to 893,214, because next/2 is only called with mode (+,-)
and not anymore with mode (-,-).

Edit 06.10.2024
I don’t know how to make next/2 fully declarative.
Maybe something with succ/2. But then there is still
the problem of bounds checking. The above solution

is highly optimized to mode (+,-) and also some invariants
of the search. So you don’t find between(0,2,X) in the
first clause of next/2, rather the more efficient X < 3,

and the test X >= 0 is omitted, since the invariant is that
next/2 never walks out of the square. You could of course
go back to CLP(FD), to implement next/2.

24

Ah, good hint! I got this.

25

What I did not understand:
I now have the very same prolog program (I even copied it over again),
but my result is different:

Query: time(aggregate_all(count, (length(_L, 16), line(_L)), C))
% 908,134 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 19180497 Lips)
{'truth': True, 'C': 552}

How do I read this performance output?

26

Now my current best implementation is:

next(X-Y, X2-Y) :- X < 3, X2 is X+1.
next(X-Y, X2-Y) :- X > 0, X2 is X-1.
next(X-Y, X-Y2) :- Y < 3, Y2 is Y+1.
next(X-Y, X-Y2) :- Y > 0, Y2 is Y-1.
line([P1, X-Y]) :-
  between(0, 3, X),
  between(0, 3, Y),
  next(X-Y, P1).
line([P1, P2 | Rs]) :-
  line([P2 | Rs]),
  next(P2, P1),
  \+ member(P1, Rs).

Query: time(aggregate_all(count, (length(_L, 16), line(_L)), C))
% 826,436 inferences, 0.043 CPU in 0.043 seconds (100% CPU, 19185039 Lips)
{'truth': True, 'C': 552}
28

Its not that bad actually, I can count a 6x6 board in ca. 23 minutes:

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

But I am somehow running out of ideas, how to do some speed-up.
I tried a couple of things the last days, but they only made it slower.
How could we count N=7, 8, etc.. The following paper about the

related problem of Hamilton Cycles isn’t very encouraging: :frowning:

Enumerating Hamiltonian Cycles
Ville H. Pettersson - 2014
https://www.combinatorics.org/ojs/index.php/eljc/article/download/v21i4p7/pdf/

I guess he was using a computing farm and parallelizing the problem:

image
image840×125 13.7 KB

29

using symmetry:
For 4x4 you have to evaluate only 3 starting points:

4 8 . .
. 4 . .
. . . .
. . . .

Number indicates multiplication factor.
result = 4 * (start=0,0) + 8 * (start=1,0) + 4 * (start=1,1)

But this brings you only a factor of about 5.
This is way not sufficient for higher numbers.

30

Just discovered the following fact:
If fields are colored like chess and field=0,0 is black:
For all odd sizes (3x3, 5x5, …) the start field can only be a black one.
So for 5x5:

4 . 4 . .
. 4 . . .
. . 4 . .
. . . . .
. . . . .

result = 4 * (start=0,0) + 4 * (start=2,0) + 4 * (start=1,1) + 1 * (start=2,2)

31

I guess the checker board pattern is result from lemma:

image
image981×72 14.6 KB

Taken from this paper here. Not sure how to utilize it.

Did you mean this kind of heat map:

A . B . A         A = 824, B = 496
. C . C .         C = 728
B . D . B         D = 456
. C . C .
A . B . A

And then 4*A + 4*B + 4*C + D = 8648.

The query was:

?- between(0, 24, P), aggregate_all(count, 
    (Q is 1<<P, path3(P, Q, 5)), C), write(C), 
    write(' '), flush_output, fail; true.
824 0 496 0 824 0 728 0 728 0 496 0 456 0 496 0 728 0 728 0 824 0 496 0 824 
true.

The code is a generalization of the bitwise solution
with a parameter N for the square side size:

next(P, Q, N) :- P mod N+1 < N, Q is P+1.
next(P, Q, N) :- P mod N > 0, Q is P-1.
next(P, Q, N) :- P div N+1 < N, Q is P+N.
next(P, Q, N) :- P div N > 0, Q is P-N.

path3(_, L, N) :- N^2 =:= popcount(L), !.
path3(P, L, N) :-
   next(P, H, N), J is 1<<H,
   L /\ J =:= 0,
   R is L \/ J,
   path3(H, R, N).

Despite using bitset, still brute force, not extremly fast,
as already mentioned takes ca. 20 minutes for 6x6 rect.

33

yes.
I have a typo, correct:

4 . 4 . .
. 4 . . .
. . 1 . .
. . . . .
. . . . .
34

Even in danger of being kicked off this forum :grinning:
I have changed to plain C and can now do 7x7:

> time ./num
27070560

real    4m28,789s
user    4m28,440s
sys     0m0,001s

I evaluate the following start points:

4 . 8 . . . .
. 4 . 4 . . .
. . 4 . . . .
. . . 1 . . .
. . . . . . .
. . . . . . .
. . . . . . .

But still no chance for 8x8.

35

I wonder why there are 160 GB used.
I have an idea, but I will have to test this to find out if this reduces the exponential grow.