Constructing circuit codes by permuting initial sequences

I. INTRODUCTION

• Long d-coils are sought in the snake-in-the-box problem.The paper notes that d-coils have also been called snakes.Source: §I · p. 1
• A circuit code is represented by a cyclic transition sequence, with each entry specifying the coordinate changed at that step.The sequence wraps around modulo its length.Source: §I · p. 1
• The paper presents two new constructions of circuit codes and reports results from them.Source: §I · p. 1

II. PERMUTED CIRCUIT CODES

• Duplicate skeletons from the same permutation are rejected by comparing them up to isomorphism.Source: §II · p. 2
• The algorithm combines a permutation and initial leap to form a returning skeleton, then backtracks over an initial sequence while testing the spread condition.Proposed transitions induce changes in each permuted sequence.Source: §II · pp. 2–3
• Permuted copies of proposed transitions impose extra constraints, allowing a short initial sequence to produce a long coil.Source: §II · p. 3
• A six-dimensional example forms a permuted coil of length 24 from an initial sequence and its compatible permuted copies.The example uses permutation (345201) and initial leap (0,1,1,0,0,0).Source: §II · p. 3

III. EXAMPLES OF PERMUTED CIRCUIT CODES

• The previous section’s construction produced d-coils of lengths 348 and 640, longer than the previously known longest lengths of 344 and 630.Source: §III · p. 3
• For spread-3 circuit codes in dimensions 10 and 11, the construction produced lengths 100 and 160, exceeding previous lengths 86 and 154.Source: §III · p. 3
• The reported search for 8-coils of this type, starting at x0, produced longest results of length 94, compared with 96 for the longest known general 8-coil.Source: §III · p. 4
• Special cases with a truncated final permuted sequence generally yielded shorter results than full permuted repetitions with similar parameters.Source: §III · p. 4

• Large leap periods can require only a short initial sequence for a long coil, while new vertices must avoid occupied vertices under the required spread condition.Source: §IV · p. 4
• Length 320 was found for a 10-coil with leap period P = 16; searching periods P > 12 took 80 minutes.Source: §IV · p. 4
• Length 576 was the longest reported 11-coil for leap period P = 24; searching periods P > 22 took 1320 minutes.Source: §IV · p. 4
• A 6.9-week search found its first length-638 result after about 2 days, while a restricted search at P = 20 found a length-640 11-coil.Source: §IV · p. 4
• An exhaustive search for a length-48 7-coil took 3480 minutes, and the longest 8-coil exhaustive search was described as prohibitive with current methods.The paper notes that like-for-like comparison with an earlier exhaustive search is difficult.Source: §IV · p. 4
• For d > 12, large leap periods are quickly unsuccessful and short periods take prohibitively long to search exhaustively; the construction is not expected to have a broad useful range without modification.Source: §IV · p. 4

• The extended graph encodes hypercube vertices through coordinate nodes and represents sequences by links between original vertices, preserving hypercube automorphisms.Sequences equivalent up to hypercube symmetries are isomorphic in the extended graph; canonical forms can be compared using NAUTY.Source: §V · p. 5
• Although generally slower than brute-force methods for simple paths and circuits, the extended-graph method also handles chains or skeletons of disconnected vertices.Source: §V · p. 5
• A d-coil is invertible when its two oriented circuits are isomorphic; in an isomorphism, one pair of vertices or changes must remain fixed, distinguishing vertex-fixed from change-fixed inversions.Source: §V · p. 6
• Of the 4 maximal 6-coils (N = 26), only 1 is invertible, and d-coils appear to be rare.Source: §V · p. 6
• All but one of the referenced invertible sequences have vertex-fixed inversions.Source: §V · p. 6

• Given two d-snakes, the method generally permutes one change sequence and appends its changes one by one to seek a valid combination.Source: §VI · p. 6
• When assigning permutations, the search backtracks if the new snake violates the required spread condition, trying another permutation or an earlier assignment.Source: §VI · p. 7
• The construction produced a length-188 coil and a length-190 snake, exceeding the previously known lengths of 180 and 188, respectively.Source: §VI · p. 7
• The authors do not expect this construction to be widely useful for large d.Source: §VI · p. 7

VII. RESULTS FROM DIRECT SEARCHES

• Backtracking rejected partial circuit-code sequences when a forward or backward subsequence could be renumbered below the starting subsequence.Every subsequence was tested at every step.Source: §VII · p. 7
• The snake search was not exhaustive, and more efficient search strategies may be available.The approach avoids repeatedly finding circuits from multiple starting points.Source: §VII · p. 7
• Lengths 58, 58, and 50 were found for d = 9, spread 3; d = 12, spread 5; and d = 13, spread 6, exceeding the respective previous records of 56, 56, and 48.The earlier records are cited as,, and, respectively.Source: §VII · p. 7

VIII. CONCLUSIONS

• Both search methods constrain the search to reduce its combinatorial explosion.One assembles a sequence from permuted copies of a shorter sequence; the other combines two lower-order sequences using only one pair of changes in the highest coordinate.Source: §VIII · p. 7
• The constrained searches can be competitive with general searches and have produced new records in several cases.The paper presents those cases among its results.Source: §VIII · p. 7
• A graph-based method detects circuit-code symmetries by adding vertices that represent nodes related to, but not initially linked with, hypercube nodes.The method brings about symmetries equivalent to hypercube symmetries through additional vertices.Source: §VIII · p. 7

DETAILS OF CIRCUIT CODES

• One listed sequence has fewer than one quarter of its changes in a single coordinate.The passage then introduces the full sequence.Source: DETAILS OF CIRCUIT CODES · p. 8
• The listed transition sequences include N = 94 and N = 188.The entries are preceded by transition-sequence strings.Source: DETAILS OF CIRCUIT CODES · p. 8
• The cited transition-sequence entry gives the string 4501430540 and reports N = 190, preserving that supported count without extending it to other entries.Source: DETAILS OF CIRCUIT CODES · p. 9