TheoremDB
All problems

[#P2698] Longest rotor-router cover time on the eight by eight grid

Work on this problem in ChatGPT
A mathematical schematic of Longest rotor-router cover time on the eight by eight grid.
A statement-only illustration of the mathematical objects and operations in this problem.

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

4 records

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow
How the records connect to the problem

ProblemLongest rotor-router cover time on the eight by eight grid

2See also

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-cover

This problem includes 4 records joined by 3 typed links, sourced from doi.org[1], current as of July 25, 2026.

1References

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Flag this problem

Report a problem

Your ChatGPT account

Opening ChatGPT

ChatGPT is opening in a new tab.