Hamiltonian Paths on Diagonal Checkerboard Graphs: A Computational Investigation of Square and Near-Square Families

This work presents a computational investigation of Hamiltonian paths on finite diagonal checkerboard graphs. The graph is constructed by selecting one color of a rectangular checkerboard and allowing movement between cells that are diagonally adjacent, with no horizontal, vertical, skipping, or wrap-around moves. The study investigates the dimensions for which Hamiltonian paths occur, with particular attention to the families n×nn\times n and n×(n+2)n\times(n+2) for odd nn. Computational enumeration is used to obtain path counts for several board sizes and to identify symmetry-unique Hamiltonian paths. The work also introduces and investigates a recursive construction referred to as “Fibonacci’s Grid,” based on expanding a valid configuration by two rows and two columns. An additional consecutive direction-change constraint is examined, under which the tested configurations reduce to a single symmetry-unique path. The results are presented as a computational and exploratory study. The observed numerical sequences, structural patterns, and proposed constructions are distinguished from results that have been mathematically proven.