14
\$\begingroup\$

Related: Counting polystrips

Background

Link-a-Pix is a puzzle on a rectangular grid, where the objective is to reveal the hidden pixel art by the following rules:

  • Connect two cells with number N with a line spanning N cells, so that the two cells are at the two ends of the line.
  • The number 1 is considered connected to itself (which makes it an exception to the rule of "connect two cells").
  • Two different lines are not allowed to overlap.
  • The puzzle is solved when all the given numbers on the grid are connected by the above rules. There may be some unused cells after the puzzle is solved.

The following is an example puzzle and its unique solution.

(Source: The NP completeness of some lesser known logic puzzles, 2019)

A polylink is defined as a single line on a Link-a-Pix puzzle. It is identified by the collection of cells (i.e. a polyomino) the line passes through, the endpoints, and the path (i.e. a Hamiltonian path) defined by the line. It is somewhat similar to a polystrip, except that the strip can touch itself side-by-side, and the two endpoints of the strip are marked.

The following are pairwise distinct polylinks (X's are the endpoint cells and O's are the other cells on the strip). A rotation or reflection of a polylink is different from the original unless they perfectly coincide.

X-O   X X   X-O   O-O
  |   | |     |   | |
X O   O O   O-O   O O
| |   | |   |     | |
O-O   O-O   O-X   X X

Some distinct polylinks have the same underlying polyomino and endpoints, as follows. When such a link is used in a Link-a-Pix puzzle, it makes the entire puzzle have multiple solutions, which is not desirable.

O-O-O   O-O-O
|   |   |   |
O-X O   O X O
    |   | | |
X-O-O   X O-O

Therefore, let's define a uniquely solvable polylink as one which does not have another different polylink with the same polyomino and endpoints.

Challenge

Given the number \$n\$, count the number \$a(n)\$ of distinct uniquely solvable polylinks with \$n\$ cells. Due to the definition of a polylink, \$a(1) = 1\$ (the single cell with only one endpoint is a valid "line" on a Link-a-Pix puzzle).

Standard rules apply. The shortest code in bytes wins.

Test cases

The "uniquely solvable" makes the sequence deviate from A002900 from n = 9. There are exactly 10 "ambiguous" polylinks of 9 cells, all of which happen to have the shape of a 3x3 square:

O O O      O O O      X O O
O X O x4;  O O O x4;  O O O x2
X O O      X O X      O O X

Main test cases:

a(1) = 1
a(2) = 2 (horizontal and vertical)
a(3) = 6 (2 orientations of I, 4 for L)
a(4) = 18 (L*8, I*2, S*4, O*4, T is not a link)
a(5) = 50 (I*2, L*8, N*8, P*8*2, U*4, V*4, W*4, Z*4)
a(6) = 142
a(7) = 390
a(8) = 1086
a(9) = 2938
a(10) = 8070
a(11) = 21690
a(12) = 59022
a(13) = 158106

a(6) through a(13) were generated using a reference program in Python.

\$\endgroup\$
5
\$\begingroup\$

J, 99 bytes

1#.3>[:#/.~[:(2({.,&(/:~)}.)_1(-"1<./)@|.+/\)"2(#~([:*/@~:+/\)"2)@([:,/,~"1 2/)~&((,-)=0 1)&(,:,.0)

Try it online!

Builds up paths starting with 0 0, filtering the ones that cross themselves. Then it normalizes each path so that every coordinate is non-negative. To check if the path is a unique solvable polylink, the end tiles and the path tiles get sorted and the results are compared to each other. If the count is 1 (for n=1) or 2 (both directions are created), it's a hit.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 292 268 265 bytes

A slow golf of the reference program. \$a(10)=8070\$ took close to 8 minutes locally.

n=input()-1
G=[]
for x in-1j,1,1j,-1:
 for q in range(3**n):v=[0];w=x;exec'v+=w,;w=w+(w-v[-2])*(-1j)**(q%3+3);q/=3;'*n;G+=[{n-min(n.real for n in v)-min(n.imag for n in v)*1j:0<j<len(v)-1for j,n in enumerate(v)}][len(v)-len(set(v)):]
print map(G.count,G).count(6)/6

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 40 bytes

0ị+ⱮØ.,U;N$¤ḟṭ€)Ẏ
Ø0WWÇ⁸’¤¡ṪṭṢƊ€ċⱮ`ỊSH»1

Try it online!

A pair of links that takes an integer and returns the value of \$a(n)\$. The last two bytes handle the special case of \$n=1\$ since that’s the the only situation where there aren’t pairs of poly links swapping start and end. Handles up to \$n=10\$ in the time limit on TIO but times out for higher values.

Explanation

Helper link

Takes a list of lists of coordinates and extends it by moving each final coordinate up, down, left and right, filtering out any intersections with the existing list

               )  | For each list of coordinates:
0ị                | - Last member (i.e. most recently visited coordinate)
  +Ɱ       ¤      | - Add each of the results of the following:
    Ø.            |   - [0, 1]
      ,U          |   - Paired with its reverse [0,1],[1,0]
        ;N$       |   - Concatenated to its negative [0,1],[1,0],[0,-1],[-1,0]
            ḟ     | - Filter out those already in the list
             ṭ€   | - Tag each onto the end of a new copy of the list
                Ẏ | Join all outer lists together

Main link

Takes an integer argument n and returns the value of a(n)

Ø0                      | [0,0]
  W                     | Wrapped in a list [[0,0]]
   W                    | Wrapped in a list [[[0,0]]]
    Ç⁸’¤¡               | Call the helper link n-1 times
            Ɗ€          | For each of the lists of coordinates:
         Ṫ              | - Tail
          ṭṢ            | - Tagged onto sorted list of the rest
              ċⱮ`       | Count the number of times each list appears
                 Ị      | <= 1
                  S     | Sum
                   H    | Half
                    »1  | Max of this and 1
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.