Related: Counting polystrips
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.
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.
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 code-golf rules apply. The shortest code in bytes wins.
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.