[#P2698] Longest rotor-router cover time on the eight by eight grid
Problem. On the \(8\times8\) grid graph, fix at each vertex the clockwise order induced by north, east, south, west after deleting missing boundary neighbors. Starting from any vertex and rotor state, increment the current rotor and follow it. What is the largest number of moves before every vertex has been visited?
1Context
A seeded search gives a cover time of at least 807 moves.
2Remarks
Remark 1. A rotor index is taken in the listed local cyclic order and is incremented before the move.
Remark 2. The cover time counts moves up to the first visit to the last unvisited vertex.
3What counts as a solution
- Give an initial state attaining the maximum and a complete dynamic-programming, branch, or structural upper-bound certificate.
1Status
Current status (The worst cover time lies between 1,282 and 3,136 moves). An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state.[1]
1Records
Notes and companion material
Original intake status. OPEN in the reviewed TheoremDB packet as of 2026-08-01. An explicit rotor state gives the lower bound, while the Eulerian-graph excursion theorem gives the upper bound for every state.
- A state consists of the current vertex, visited mask, and mixed-radix rotor vector. Search should hash only states that improve the visited mask or elapsed-time bound.
- Changing increment-before-move to move-before-increment changes the numeric answer. Certificates must state the convention and local boundary orders.
- General polynomial cover-time bounds leave a large gap and do not identify the worst initial rotor state.
- Fresh exact-title, parameter, source, and corpus searches were completed on 2026-08-01.
Recorded example 1. Number vertices row-major from 0 through 63. One incumbent starts at vertex 39 with rotor-index vector listed in the computation field.
Computational notes
- Fifty thousand initial states from seed 20260724 were simulated exactly. The best took 807 moves from vertex 39 with row-major rotor indices [0,2,0,2,1,2,2,1,0,0,1,1,0,0,0,2,1,3,3,1,0,2,2,0,0,0,0,2,0,0,1,1,1,0,1,1,1,3,0,2,1,3,0,3,2,0,1,1,0,2,3,1,3,1,0,0,1,1,0,0,1,0,1,0]. A replay visited the 64th vertex on move 807.
How the 4 records connect
ProblemLongest rotor-router cover time on the eight by eight grid
- Computation 1The worst cover time lies between 1,282 and 3,136 movesin this packetReproduced
- Artifact 1Exact replay of the 1,282-move initial statesupportsReproduced
- Route 2Seeded local search raises the incumbent from 807 to 1,282producesReproduced
- Route 1General cover-time theorems settle the finite upper boundinformsSupported
2See also
- Longest four-number Ducci trajectory in the 100 boxdiscrete dynamical systems
- Collatz conjecturediscrete dynamical systems
- Merging of orbits under adding the product of nonzero digitsdiscrete dynamical systems
How to cite
TheoremDB contributors, “Longest rotor-router cover time on the eight by eight grid,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/rotor-router-eight-grid-coverThis page as plain text: rotor-router-eight-grid-cover.md
This problem includes 4 records joined by 3 typed links, sourced from doi.org[1], current as of July 25, 2026.
1References
- Packet source. Laura Florescu, Lionel Levine, and Yuval Peres, “The Range of a Rotor Walk”. The American Mathematical Monthly 123(7) (2016), 627. DOI 10.4169/amer.math.monthly.123.7.627. Source location cited by the reviewed packet record. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Supports the statement, selected result, computational method, or current boundary recorded in the reviewed packet.Also cited at Florescu, Levine, and Peres, The range of a rotor walk, Section 6, Theorem 6.1; Holroyd and Propp, Rotor walks and Markov chains, arXiv:0904.4507, pages 2-3; Friedrich and Sauerwald, The Cover Time of Deterministic Random Walks, EJC 17(1), R167 (2010).Also cited at American Mathematical Monthly 123(7), 627-642 (2016), Section 6 and Theorem 6.1.Also cited at Laura Florescu, Lionel Levine, and Yuval Peres, The range of a rotor walk, American Mathematical Monthly 123(7), 627-642 (2016), Section 6 and Theorem 6.1; lower-bound replay in this record.Also cited at Deterministic local search and exact saved-state replay, 2026-07-25.For Longest rotor-router cover time on the eight by eight grid: The sources fix the update convention and prove bounds for every Eulerian graph; the exact 8 by 8 clockwise extremum was absent from the located papers.Source named by the research packet.
- Alexander E. Holroyd and James Propp, “Rotor Walks and Markov Chains”. arXiv:0904.4507 (2009). arXiv:0904.4507, pages 2-3 for the retrospective update convention. ↗preprint · reference source · arXiv:0904.4507, checked 2026-08-01 · checked 2026-07-25Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is arXiv:0904.4507, pages 2-3 for the retrospective update convention. The packet makes no inference beyond that cited scope.
- Vladimir Yanovski, Israel A. Wagner, and Alfred M. Bruckstein, “A Distributed Ant Algorithm for\protect Efficiently Patrolling a Network”. Algorithmica 37(3) (2003), 165-186. DOI 10.1007/s00453-003-1030-9. Algorithmica 37(3), 165-186 (2003). ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is Algorithmica 37(3), 165-186 (2003). The packet makes no inference beyond that cited scope.
- Tobias Friedrich and Thomas Sauerwald, “The Cover Time of Deterministic Random Walks”. The Electronic Journal of Combinatorics 17(1) (2010), R167. DOI 10.37236/439. Electronic Journal of Combinatorics 17(1), R167 (2010). ↗scholarly publication · reference source · checked 2026-08-01Source use: citation only.For Longest rotor-router cover time on the eight by eight grid, the reviewed source scope is Electronic Journal of Combinatorics 17(1), R167 (2010). The packet makes no inference beyond that cited scope.
Original CC0 finite rotor-router extremal problem.