pith. sign in

arxiv: 2605.20243 · v1 · pith:J33FMPRYnew · submitted 2026-05-18 · 🧮 math.HO · cs.GT

God numbers for Graphs, Games and Groups

Z. Adams , M.Z. Cassim , C. Hou , O. Knill , V. Seco Roopnaraine , M.H. Saleem This is my paper

Pith reviewed 2026-05-21 08:52 UTC · model grok-4.3

classification 🧮 math.HO cs.GT
keywords god numbergraph theorysolitaire puzzleszero-sum gamesZermelo theoremsliding puzzlesgame graphscombinatorial games
0
0 comments X

The pith

Finite solitaire puzzles and zero-sum games can be axiomatized as directed graphs from which Zermelo's theorem follows directly.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models finite solitaire puzzles and two-player zero-sum sequential games as directed graphs, with states as vertices and moves as edges. In this representation the god number measures the shortest distance from a starting state to the solved states for solitaire puzzles, or the minimax length over strategies for games. A sympathetic reader might care because this turns puzzle difficulty and winning strategies into concrete graph quantities like distances and critical values, while making classic results such as Zermelo's theorem immediate consequences of the setup rather than separate theorems.

Core claim

By representing states of a puzzle or game as vertices in a directed graph and moves as edges, the god number for solitaire puzzles is the shortest path distance from the starting vertex to the set of solved states, or the diameter if unspecified. For two-player games, it is the minimax value that minimizes the longest possible game length over all strategies, where a strategy is a subgraph containing the initial vertex. This framework makes Zermelo's theorem that one player has a winning strategy or the game draws follow directly from the graph definitions.

What carries the argument

The god number, defined as the minimal distance to the solution space A in solitaire cases or as a minimax critical value over strategy subgraphs in two-player cases.

If this is right

  • God number computation is NP-complete in general and for concrete sliding puzzles like the 15-puzzle.
  • Group games such as Rubik-type problems, the Tower of Hanoi, and transposition sorting all reduce to the same graph distance measure.
  • A chess problem labeled 'mate in k' receives god number exactly k under the minimax definition.
  • Strategies in two-player games are uniformly modeled as subgraphs containing the initial vertex.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The single graph model might let researchers compare solution complexities across unrelated puzzles like sliding blocks and cube twists using the same computational tools.
  • Extending the definitions beyond finite cases could show where graph-theoretic distance measures stop capturing real game outcomes.
  • Treating all examples through one axiomatization could surface shared hardness patterns between sorting problems and board games that are not obvious from isolated studies.

Load-bearing premise

Every finite solitaire puzzle and zero-sum sequential game can be faithfully represented as a directed graph where distances and minimax values capture the intended notions of solving or winning without needing extra structure.

What would settle it

A concrete finite solitaire puzzle or game whose actual solution lengths or winning conditions cannot be matched by shortest paths or minimax values in any directed graph model of its states and moves.

Figures

Figures reproduced from arXiv: 2605.20243 by C. Hou, M.H. Saleem, M.Z. Cassim, O. Knill, V. Seco Roopnaraine, Z. Adams.

Figure 1
Figure 1. Figure 1: Both solitaires and two-player games are defined graph theoretically. In the solitaire case, the puzzle is either solvable or not. In the two-player case, there is a Zermelo trichotomy: a game is either a win for V (V can remove edges leaving V so that every game event lands in A ∩ W), a win for W (W can remove edges leaving W so that every game event lands in A ∩ V , or a draw. If both players can remove … view at source ↗
Figure 2
Figure 2. Figure 2: For a multi-player game with more than 2 players, the Zermelo analog of coalitions is already more complicated. Coalitions can form. v t2 p1 p2 t1 q V0 V1 V2 V0 terminal terminal [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A simple 3 player game, where only coalitions of 2 players can win. This example (as well as the graph) were machine generated. The machine was only fed the above simple axiom system, without giving any additional help. We wanted a simple example. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An exhibit of a few toys and games, we have played with when working on this project. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Infinite connect 5 (Gomoko) can also be played on finite boards like on a 19×19 go game board. “Go” itself has been played for more than 4000 years. Go type games or hex type games are examples of topological games, where the winning positions are geometrically defined. 5 × 5 go was determined to be a win for the first player (Black) [22], like for “microgo” on 2 × 2 board which requires only to look at 34… view at source ↗
Figure 6
Figure 6. Figure 6: Tic Tac Toe is infamous due to its simplicity and its multi-cultural value, appearing in blockbuster Hollywood movies like “WarGames”. It is a 2-player game that is well known to lead to a draw. We can easily map out the entire game graph. 2 4 6 8 500 1000 1500 [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The game graph of the standard Tic Tac Toe game has 5478 vertices. This the number of eligible the 39 possible 3 × 3 matrices with entries in {0, 1, 2} (we need to look a subset because the number of white stones is always one larger or equal than the number of black stones). The graph ball sizes Br(0) starting from the initial v = 0 position are 1, 10, 82, 334, 1090, 2350, 3870, 5010, 5400, 5478. The diff… view at source ↗
Figure 8
Figure 8. Figure 8: We see the ball B1(0) of play radius 1 centered at 0. It consists of 82 possible Tic Tac Toe games in which both players have played one stone. We count the number of plays of the first player, as in chess [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: We see the ball B1(0) of play radius 1 centered at a winning position for the first player [PITH_FULL_IMAGE:figures/full_fig_p012_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: We see the graph after an other move by the first player. 12 [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: We see the Cayley graph of an Abelian group in which 6 generators a, b, c, a−1 , b−1 , c−1 are given. Its diameter is 10. The BFS layer profile has a concave up segment. Most Cayley graphs show a unimodal BFS layer profile. 7This example was found AI assisted. 13 [PITH_FULL_IMAGE:figures/full_fig_p013_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The 3-puzzle game G is an example of a sliding game. It is the 2 × 2 analog of the 15 game which is played on a 4x4 board. The graph has two connected components; each is a cyclic graph of order 12. The god number in the winnable component is God(G) = 6. For the 8-puzzle, the god number is 31. For the 15 game, the god number is 80. For the n × n generalization, its computation is NP complete. 14 [PITH_FU… view at source ↗
Figure 13
Figure 13. Figure 13: The 5 puzzle game is the 2 × 3 analog of the 15 game. The graph has two connected components. The god number is 21. 3.3. In the code section we have included the code which generated the following picture. We show here only the first connected component, which represent the solvable cases: the position  4 5 x 1 2 3  has distance 21 from  1 2 3 4 5 x  [PITH_FULL_IMAGE:figures/full_fig_p015_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: The solvable connected component of the previous picture is here seen embedded in 3D. The game graph has 360 = 6!/2 vertices and 420 edges. All vertex degrees are equal to 2 or 3. 3.4. Whether a solitaire has a win strategy depends on whether v is in the same connected component than one of the points A. If v is disconnected from A, there is no solution. There are various mechanisms which can render G dis… view at source ↗
Figure 15
Figure 15. Figure 15: Rubik puzzles of size 2 × 2 × 1, 2 × 3 × 1, 2 × 2 × 2 (pocket cube), 2 × 2 × 3, 2 × 3 × 3, 3 × 3 × 1, 3 × 3 × 3, 4 × 4 × 4 and 5 × 5 × 5 (professor’s cube). 16 [PITH_FULL_IMAGE:figures/full_fig_p016_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: we see the simple 2×2 tic-tac-toe game has no draw. The initial player V always wins. The god number is 2. The initial player always wins in 2 moves. The empty board is the initial position v. The vertex set V is the set of boards with an even number of stones. The vertex set W is the set of boards with an odd number of stones. S is the set of boards where all squares are occupied or where a row, a column… view at source ↗
Figure 17
Figure 17. Figure 17: In the left case, we have a draw. The god number is 1 because after both parties have moved, we only have kings left, which is part of S. In the middle case, there 8 possible legal moves initially, one of them (catch the queen) leads to a white win, two to black wins and the rest to draws. A game engine tells that the god number is 11 to get to a mate. In the right case, there is an obvious mate in 1. The… view at source ↗
Figure 18
Figure 18. Figure 18: The Moebius strip and Cylinder both generate game graphs G1, G2. These two graphs are both Cayley graphs of S8 and both have the same constant vertex degree 16, and so the same number of edges. But they have different diameter 10 rsp. 11. 6. Sliding puzzles 6.1. Sliding puzzles generalize the classic 15-puzzle (Γ = C4 × C4) or the magic ball Γ is the icosahedron graph) to arbitrary connected graphs. Slidi… view at source ↗
Figure 19
Figure 19. Figure 19: Magic Rainbow puzzle ball. 6.13. Given a graph G and a vertex v, one can look at the neighborhood graph Br(v) which consists of all vertices in distance r or less from v. This defines a layer partition or spheres Sr = Br\Br−1 of G of positions which can be reached with r moves but not with r−1 moves. It is in some sense a “wave front” in the graph game. It defines the BFS layer profile {|Sr(x)|}God(G,v) r… view at source ↗
Figure 20
Figure 20. Figure 20: The middle two cases cases are “draw in one”. The strategy for V is to eliminate all but the capturing move. In the right, W wins. 7.9. The exponential growth in graph complexity from configurations I/II to III demonstrates the combinatorial explosion inherent in chess variants as piece density increases. The maximum shortest-path distance max d(x) reflects the diameter of the reachable graph and indicate… view at source ↗
Figure 21
Figure 21. Figure 21: A 4 × 4 board [PITH_FULL_IMAGE:figures/full_fig_p029_21.png] view at source ↗
Figure 22
Figure 22. Figure 22: The game graph for the king side pawn. 29 [PITH_FULL_IMAGE:figures/full_fig_p029_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: The game graph for the queen side pawn. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: The game graph for both pawns 31 [PITH_FULL_IMAGE:figures/full_fig_p031_24.png] view at source ↗
Figure 25
Figure 25. Figure 25: The game graph for opposite pawns 32 [PITH_FULL_IMAGE:figures/full_fig_p032_25.png] view at source ↗
Figure 26
Figure 26. Figure 26: The ball B1(v) of chess on a 2 × 4 board without paws. This game is ”mate in 1”. The queen can move in front of the king and force a chess mate. Lets call this position w. The winning strategy H of V is the subgraph H generated by the edge v → w. All other edges are cut away. Player W would like to maximize the length of a game play in H but the edge degree of w is zero because it is a mate. 33 [PITH_FUL… view at source ↗
Figure 27
Figure 27. Figure 27: A 4 card game. 8.3. Is there a simple Black Jack 21 type game for which one has a chance to write down the full game graph? We experimented with an 11 version, where the highest card is 6 and only two suits. So there are 5 cards A2,A3,A4,A5,A6 and B2,B3,B4,B5,B6. What happens with any game with random shuffle is that we need to look at all the possible permutation cases in which the card deck can be dealt… view at source ↗
Figure 28
Figure 28. Figure 28: The graph of the card game with 90 positions. 34 [PITH_FULL_IMAGE:figures/full_fig_p034_28.png] view at source ↗
Figure 29
Figure 29. Figure 29: The floppy was designed by Katsuhiko Okamoto. 9.4. For the 2 × 2 × 2 cube case, the god number is 11 respectively 14 is known. There are 3 ′674′160 positions for the 2 × 2 × 2 (pocket) cube in the half turn metric the god number is 11 (analog to 20 in the standard Rubik 3 × 3 × 3 cube). If one of the cubes is fixed, the number of positions reduces to 8!37 which is 1/24 of 3′674′160. In the quarter turn me… view at source ↗
Figure 30
Figure 30. Figure 30: Hungarian rings 9.6. For the Rubik’s clock, the god number is known to be 12. There are 214 positions. The Rubik’s clock has lots of generators: there are 24 flag positions and in each case 4 generators. So that there are 26 = 64 generators. 38 [PITH_FULL_IMAGE:figures/full_fig_p038_30.png] view at source ↗
Figure 31
Figure 31. Figure 31: Rubik’s clock has many generators. 10. Tic Tac Toe games 10.1. The standard 32 Tic-Tac-Toe is famously known to be a draw [28]. The n d -game looks for a line of length n in a d-dimensional hypercube of side n. The two-dimensional m, n, k-game (k in a row on an m × n board) formalise positional tic-tac-toe [10]. Hales and Jewett [30] used strategy-stealing to show no second player wins an n d -game, and t… view at source ↗
Figure 32
Figure 32. Figure 32: Connect 4 game. Board k = 2 k = 3 k = 4 k = 5 k = 6 3 × 3 Win (2) Draw — — — 4 × 4 Win (2) Win (3) Draw — — 5 × 5 Win (2) Win (3) Draw Draw — 6 × 5 Win (2) Win (3) Win Draw — 7 × 7 Win (2) Win (3) Win Draw Draw 9 × 6 Win (2) Win (3) Win Draw Draw 15 × 15 Win (2) Win (3) Win Win (Gomoku) Draw 10.4. From [7]: k = 1, 2 are trivial wins except for (1, 1, 2) and (2, 1, 2); (m, n, 3) is a win if and only if (m … view at source ↗
Figure 33
Figure 33. Figure 33: The tower of Hanoi with n pieces has god number 2n − 1 42 [PITH_FULL_IMAGE:figures/full_fig_p042_33.png] view at source ↗
Figure 34
Figure 34. Figure 34: The Hanoi graph in the case n = 2 has 9 vertices, 12 edges and diameter 3. We see also the graph for n = 6, where we have |V | = 729 and |E| = 1092. The positions where all disks are on one peg are on the boundary. {{1, 2, 3}, {}, {}} {{2, 3}, {1{{}2, 3 , {}}}, {}, {1}} 3 2 1 3 1 2 {{1, 3}, {}, {2}} {{3}, {}, {1, 2}} {{1, 3}, {2}, {}} {{3}, {1, 2}, {}} {{}, {1, 2}, {3}} 1 2 3 {{}, {2}, {1, 3}} {{1}, {}, {… view at source ↗
Figure 35
Figure 35. Figure 35: The Hanoi graph for n=3. Going along the boundary is the optimal path. It recursively first uses the solution for n=2, then moves the entire pile and then again uses the solution for n=2. 11.4. The Hanoi problem with p = 4 pegs is not explored for large n. The 4 peg problem is a more interesting transport problem as one can now work more effectively using two ”storage pegs”. The game graph obviously has a… view at source ↗
Figure 36
Figure 36. Figure 36: The graphs of the Reeves puzzle, (p = 4-peg Hanoi puzzle) have smaller diameter as we have more transport possibilities. We measure the graph diameters God(2) = 3, God(3) = 5, God(4) = 9, God(5) = 13, God(6) = 17. We see here the case n = 4. 12. Other games 12.1. Hex [31] is a two-player game that has relations to theorems in topology. It can be played on any rectangle [50]. It was invented in 1942 by Pie… view at source ↗
Figure 37
Figure 37. Figure 37: In hex, there is no draw. player can decide whether to take over the position of the first. Also for Torus Hex there is no tie because of topology. Also here, The first player always wins because if the second had a strategy, it could be used by the first without the first stone. The topology is related to Brower fixed point theorem and Sperner lemma. God number is larger or equal to n. The 3 × 3 Hex boar… view at source ↗
Figure 38
Figure 38. Figure 38: A peg solitaire where we play on a triangular grid with 6 holes. The 9 holes to the right are considered off grid. In this case the game has no solution with this initial condition v, where A is the set of configurations with one peg. 45 [PITH_FULL_IMAGE:figures/full_fig_p045_38.png] view at source ↗
Figure 39
Figure 39. Figure 39: To the left we see the full game graph on a 3 × 3 lattice Peg solitaire. It has 29 = 512 vertices. To the right we see the connected component of an initial condition with one peg missing (upper right vertex). The game can not be solved. The code producing this graph is below. 12.6. The 80ies were already in a frenzy about Rubik type games. There were Hungarian ring type games like the Nintendo drum in wh… view at source ↗
Figure 40
Figure 40. Figure 40: The masterball puzzle is a Cayley graph in the group S16 × S16. The puzzle is still sold on ebay (picture). 12.11. There are 3,6 or 9 Men’s Morris versions. It is known M¨uhle=mill in German. In 9 Men’s morris, the players place and move nine men to form ”mills” which are three in a row, allowing to remove an opponents piece. The game ends when a player is reduced to two pieces. The Nine Men’s morris goes… view at source ↗
Figure 41
Figure 41. Figure 41: Nine Men’s Morris is known to be a draw case in the Zermelo theorem. 12.12. Mankala is a 2-player game that is also known as Serrata. Its transport nature makes it resemble the more popular dice game Backgammon but it is completely deterministic. The 47 [PITH_FULL_IMAGE:figures/full_fig_p047_41.png] view at source ↗
Figure 42
Figure 42. Figure 42: Mankala is also known as Serrata. Unlike Backgammon, it is determin￾istic. Each player has pits and a bank to the right. The goal is to cash in as many stones as possible. To play,a player takes a pile from its own side and distributes the stones anti-clockwise, one by one. When ending in the bank, the player can play again. Play until no stones are any more in the pits. The game produces a complex game t… view at source ↗
Figure 43
Figure 43. Figure 43: Tetrominoes 48 [PITH_FULL_IMAGE:figures/full_fig_p048_43.png] view at source ↗
Figure 44
Figure 44. Figure 44: Cross parking game. An example of a sliding game with more holes. (was bought at the MoMath Museum in New York). 12.15. New games are also developed in modern times. An example alpha-zero described in [8]. In one of the games there, one has a stack Z = {1, . . . , n}. The bank starts with a total 0. Player V picks a number from Z and either adds or multiplies it to the total. The number is removed from th… view at source ↗
Figure 45
Figure 45. Figure 45: Two puzzles that are isomorphic. to a solution path with a decent length. In the Rubik cube, the value system could be the number of correct cubes. In the chess case, it can be the sum of the values of each captured piece. In the 15 game it can be a distance between permutations. In a transposition puzzle, we have seen the graph distance dH(x, y) on G which uses the distance matrix from the host graph Γ t… view at source ↗
Figure 46
Figure 46. Figure 46: The game graph of K3 is the utility graph K3,3. The game graph of the path graph P4 of length 3 is the dual of a 2-sphere (a Catalan solid in this case) The game graph of the star graph S4 is the dual of of a 2-manifold. The pictures were generated with the program given above. 15.7. Below is GAP code for the Rubik cube. It has been used in the 80ies. (It was used in student projects for a mathematical so… view at source ↗
Figure 47
Figure 47. Figure 47: A page of [53] listing the axioms. 65 [PITH_FULL_IMAGE:figures/full_fig_p065_47.png] view at source ↗
Figure 48
Figure 48. Figure 48: A page of [79] defining ”strategy” 66 [PITH_FULL_IMAGE:figures/full_fig_p066_48.png] view at source ↗
read the original abstract

We describe and axiomatize finite solitaire puzzles and zero sum sequential games graph theoretically. Zermelo's theorem telling that there is a win for one of the players or a draw follows from the definitions. The god number is a geometric quantity that quantifies the number of moves necessary to solve the puzzle. In the solitaire case, the god number is the minimal distance from the initial state $v$ to the solution space $A$. If $v$ and $A$ are not specified, the god number is the graph diameter. God number computations are related to combinatorial sorting problems and is a NP-complete problem in general even when restricted to concrete sliding problems. In the two-player case, the god number is a minimax critical value: it minimizes the maximal game event length over the set of all strategies. A strategy is a sub-graph of the game graph that contains the initial vertex. The definition is done so that a ``mate in k" chess problem has god number k. As for examples: in the solitaire case, we look at group games like Rubik type problems, transposition games related to sorting, at sliding puzzles like the 15 puzzle or rainbow ball, or the tower of Hanoi. For two-player games, we illustrate the story using examples of small chess games, a small card game or tic-tac-toe type problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 3 minor

Summary. The manuscript axiomatizes finite solitaire puzzles and zero-sum sequential games as directed graphs with a distinguished solution set A (or terminal positions). It asserts that Zermelo's theorem on the existence of a win for one player or a draw follows directly from the definitions. The god number is introduced as the minimal graph distance from initial vertex v to A in the solitaire case (or the diameter if unspecified), and as a minimax critical value over strategy subgraphs in the two-player case. Examples are provided from group-theoretic puzzles (Rubik-type), sliding puzzles (15-puzzle, rainbow ball, Tower of Hanoi), transposition/sorting problems, and small two-player games (chess variants, card games, tic-tac-toe). The paper notes that god-number computation relates to combinatorial sorting and is NP-complete in general, even for concrete sliding puzzles.

Significance. If the framework holds, it supplies a unified graph-theoretic language for puzzles and games that directly encodes standard notions of distance and minimax, with the god number serving as a geometric measure of solution length. This perspective links to known results in combinatorial game theory and complexity, and the explicit tie to 'mate in k' problems is a clear illustration. However, the manuscript largely restates existing concepts from graph theory and Zermelo's theorem without new theorems, original computations, or machine-checked proofs, so its significance is primarily expository rather than advancing the research frontier.

major comments (3)
  1. [Axiomatization of games and puzzles] The assertion that Zermelo's theorem follows from the definitions is correct by backward induction on finite directed graphs with terminals, but the paper should specify in the axiomatization section whether graphs are required to be acyclic or how cycles (if present) are handled to avoid infinite play; this is load-bearing for the claim that the result is immediate from the graph model alone.
  2. [Two-player case and god number definition] The definition of a strategy as a subgraph containing the initial vertex (and the god number as the minimax length over such subgraphs) requires explicit conditions ensuring the subgraph is functional (out-degree exactly 1 at non-terminal positions) to guarantee it corresponds to a valid strategy; without this, the reduction to 'mate in k' is not fully rigorous.
  3. [Complexity and sorting problems] The claim that god-number computation is NP-complete in general, even restricted to sliding problems, is a strong computational statement; the manuscript should either cite the specific reduction (e.g., from a known sorting or puzzle problem) or provide a brief sketch, as this underpins the complexity discussion.
minor comments (3)
  1. [Abstract] The abstract and introduction would benefit from a clearer statement of what is novel in the axiomatization versus standard graph-distance and minimax constructions.
  2. [Examples] Explicit small-scale computations of the god number (e.g., for the 3-disk Tower of Hanoi or a 2x2 sliding puzzle) would strengthen the illustrative examples.
  3. [Definitions] Notation for the solution set A and initial vertex v should be introduced once and used consistently; avoid shifting between 'solution space' and 'terminal positions' without cross-reference.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the thoughtful and detailed report. The comments highlight areas where the axiomatization and definitions can be made more precise, and we will incorporate revisions to address them while preserving the expository nature of the manuscript. We respond to each major comment below.

read point-by-point responses

  1. Referee: The assertion that Zermelo's theorem follows from the definitions is correct by backward induction on finite directed graphs with terminals, but the paper should specify in the axiomatization section whether graphs are required to be acyclic or how cycles (if present) are handled to avoid infinite play; this is load-bearing for the claim that the result is immediate from the graph model alone.

    Authors: We agree that explicit handling of potential cycles strengthens the claim. The manuscript already emphasizes finite graphs for both solitaire puzzles and games. We will revise the axiomatization section to state that the directed graphs are finite and that any play continuing indefinitely (via cycles) is classified as a draw. This ensures termination or draw in all cases, allowing Zermelo's theorem to follow directly from the finite graph model and the definitions of terminal positions without requiring acyclicity. revision: yes

  2. Referee: The definition of a strategy as a subgraph containing the initial vertex (and the god number as the minimax length over such subgraphs) requires explicit conditions ensuring the subgraph is functional (out-degree exactly 1 at non-terminal positions) to guarantee it corresponds to a valid strategy; without this, the reduction to 'mate in k' is not fully rigorous.

    Authors: This is a valid point for rigor in the two-player setting. We will update the definition of a strategy to require that the subgraph has out-degree exactly one at every non-terminal position for the player whose turn it is, while preserving the out-degree of the opponent as in the original game graph. This functional condition ensures the subgraph encodes a deterministic strategy, making the minimax characterization of the god number and its equivalence to 'mate in k' fully rigorous. revision: yes

  3. Referee: The claim that god-number computation is NP-complete in general, even restricted to sliding problems, is a strong computational statement; the manuscript should either cite the specific reduction (e.g., from a known sorting or puzzle problem) or provide a brief sketch, as this underpins the complexity discussion.

    Authors: We will strengthen this section by adding a reference to established results on the complexity of optimal solutions in sliding-block puzzles (such as generalizations of the 15-puzzle, where shortest-path computation in the configuration graph is known to be NP-hard via reductions from problems like vertex cover on implicit graphs). A brief sketch of the reduction idea will also be included to connect it to combinatorial sorting problems as mentioned in the text. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper models finite solitaire puzzles and zero-sum sequential games as directed graphs with a distinguished solution set A, from which Zermelo's theorem follows immediately by backward induction on the finite structure. The god number is explicitly defined as the graph distance from initial vertex v to A, the graph diameter when unspecified, or a minimax value over strategy subgraphs; these are direct applications of standard graph distance and game-theoretic minimax without any fitted parameters, self-referential predictions, or load-bearing self-citations. The construction is stipulated as the representation itself, rendering the framework self-contained rather than deriving results from unverified prior claims or reducing equations to their inputs by definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The paper introduces the 'god number' as a new named quantity defined from existing graph distance and strategy subgraphs. No numerical free parameters are fitted. The main axioms are standard finite-graph assumptions and the existence of a solution set A.

axioms (2)
  • domain assumption Every finite solitaire puzzle and zero-sum sequential game can be represented as a finite directed graph with a designated solution set A.
    Invoked in the opening definitions of solitaire and game graphs.
  • standard math Zermelo's theorem holds for finite two-player zero-sum games of perfect information.
    Stated as following directly from the graph definitions.
invented entities (1)
  • God number no independent evidence
    purpose: A single geometric quantity that measures minimal moves to solution in solitaire or minimax length in two-player games.
    Defined as minimal distance to A or as minimax critical value over strategy subgraphs.

pith-pipeline@v0.9.0 · 5792 in / 1470 out tokens · 31761 ms · 2026-05-21T08:52:57.637215+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

81 extracted references · 81 canonical work pages

  1. [1]

    Akers and B

    S.B. Akers and B. Krishnamurthy. A group-theoretic model for symmetric interconnection networks.IEEE Trans.Comput., 38:555–566, 1989

    work page 1989

  2. [2]

    Albert, R.J

    M.H. Albert, R.J. Nowakowski, and D. Wolfe.Lessons in Play, An introduction to combinatorial game theory. A.K. Peters, 2007

    work page 2007

  3. [3]

    L.V. Allis. A knowledge-based approach of connect-four. 1988. M.Sc Thesis, VU Amsterdam

    work page 1988

  4. [4]

    L.V. Allis. Searching for solutions in games and artificial intelligence. 1994. Ph.D. Limburg

    work page 1994

  5. [5]

    A.F. Archer. A modern treatment of the 15 puzzle.American Mathematical Monthly, 106:793–799, 1999

    work page 1999

  6. [6]

    The cyclic towers of hanoi.Information Processing Letters, 13:118–119, 1981

    Atkinson. The cyclic towers of hanoi.Information Processing Letters, 13:118–119, 1981

    work page 1981

  7. [7]

    Beck.Combinatorial Games, Tic-Tac-Toe Theory, volume 114 ofEncyclopedia of Mathematics and its Applications

    J. Beck.Combinatorial Games, Tic-Tac-Toe Theory, volume 114 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press

    work page

  8. [8]

    Benesh and R

    B. Benesh and R. Cambbell. Element building games onZ n.Arnold Mathematical Journal, 7:599–608, 2021

    work page 2021

  9. [9]

    Berend and A

    D. Berend and A. Sapir. The diameter of hanoi graphs.Information Processing Letters, 98:79–85, 2006

    work page 2006

  10. [10]

    Berlekamp, J

    E. Berlekamp, J. Conway, and R. Guy.Winning Ways, for your mathematical plays. A.K. Peters, second edition, 2001

    work page 2001

  11. [11]

    Beyer, S

    M. Beyer, S. Mereta, A. Rolda, and P Voran. Higher-dimensional cubical sliding puzzles, 2023

    work page 2023

  12. [12]

    T. Bousch. La quatri` eme tour de hano¨ ı.Bulletin of the Belgian Mathematical Society, 21:895–912, 2014

    work page 2014

  13. [13]

    Br¨ ungger, A

    A. Br¨ ungger, A. Marzetta, K. Fukuda, and J. Nievergelt. The parallel search bench zram and its applications. Annals of Operations Research, 90:45–63, 1999

    work page 1999

  14. [14]

    Cameron.Permutation Groups, volume 45 ofStudent Texts

    P.J. Cameron.Permutation Groups, volume 45 ofStudent Texts. London Mathematical Society, 1999

    work page 1999

  15. [15]

    Cashman, S.J

    C. Cashman, S.J. Miller, J. Shuffelton, and D. Son. Black hole zeckendorf games.Hardy-Ramanujan Journal, 48:102–107, 2025

    work page 2025

  16. [16]

    A. Cayley. On the theory of groups, as depending on the symbolic equationθ n = 1.Philosophical Magazine, 7, 1854

    work page

  17. [17]

    Chen and J

    X. Chen and J. Shen. On the frame-stewart conjecture about the towers of hanoi.SIAM Journal on Computing, 33(3):584–589, 2004

    work page 2004

  18. [18]

    Conway.On Numbers and Games

    J.H. Conway.On Numbers and Games. A K Peters, Ltd, 2001

    work page 2001

  19. [19]

    The lean theorem prover (system description)

    Leonardo de Moura, Soonho Kong, Floris van Doorn, and Jakob von Raumer. The lean theorem prover (system description). volume 9195, pages 378–388, 08 2015

    work page 2015

  20. [20]

    Dimand and R.W

    M.A. Dimand and R.W. Dimand (eds). The foundations of game theory, vol 1-3. An Elgar Reference Collection, 1997

    work page 1997

  21. [21]

    Dudeney.The Canterbury Puzzles

    H.E. Dudeney.The Canterbury Puzzles. Dutton and Company, 1908

    work page 1908

  22. [22]

    van den Herik E.C.D van der Werf and J.W.H.M

    H.J. van den Herik E.C.D van der Werf and J.W.H.M. Uiterwijk. Solving go on small boards.ICGA Journal, 26:92–107, 2003

    work page 2003

  23. [23]

    Fijalkow.Games on Graphs

    N. Fijalkow.Games on Graphs. Cambridge University Press, 2026

    work page 2026

  24. [24]

    J.S. Frame. Solution to advanced problem 3918.American Mathematical Monthly, 48:216–217, 1941

    work page 1941

  25. [25]

    D. Gale. The game of Hex and the Brouwer fixed point theorem.Amer. Math. Monthly, 86:818–827, 1979

    work page 1979

  26. [26]

    A. Ganesan. Automorphism groups of cayley graphs generated by connected transposition sets.Discrete Math- ematics, 313:2482–2485, 2013

    work page 2013

  27. [27]

    The GAP Group.GAP – Groups, Algorithms, and Programming, Version 4.15.1, 2025

    work page 2025

  28. [28]

    M. Gardner. Mathematical carnival: Ticktacktoe games.Sci. Amer., 1975

    work page 1975

  29. [29]

    S.W. Golomb. Rubik’s cube and quarks: Twists on the eight corner cells of rubik’s cube provide a model for many aspects of quark behavior.American Scientist, 70:257–259, 1982

    work page 1982

  30. [30]

    Hales and R.I

    A.W. Hales and R.I. Jewett. Regularity and positional games.Trans. AMS, 106:222–229, 1963

    work page 1963

  31. [31]

    R. B. Hayward.Hex, a playful introduction, volume 54 ofAnneli Lax New Mathematical Library. AMS, 2022

    work page 2022

  32. [32]

    A.M. Hinz. Pascal’s triangle and the tower of hanoi.American Mathematical Monthly, 99:538–544, 1992

    work page 1992

  33. [33]

    Hinz, Klavˇ zar, Milutinovi´ c, and Petr.The Tower of Hanoi — Myths and Maths

    A.M. Hinz, Klavˇ zar, Milutinovi´ c, and Petr.The Tower of Hanoi — Myths and Maths. Birkh¨ auser, 2013

    work page 2013

  34. [34]

    Hinz and Parisse

    A.M. Hinz and Parisse. On the planarity of hanoi graphs.Expositiones Mathematicae, 20:263–268, 2002

    work page 2002

  35. [35]

    Solving 7,7,5-game and 8,8,5 game.The Journal of the Computer Games Community, 40, 2018

    W-Y Hsu, C-L Ko, and I-C Wu. Solving 7,7,5-game and 8,8,5 game.The Journal of the Computer Games Community, 40, 2018

    work page 2018

  36. [36]

    Johnson and W.E

    W.W. Johnson and W.E. Story. Notes on the “15” puzzle.American Journal of Mathematics, 2:397–404, 1879

    work page

  37. [37]

    Joyner.Adventures in Group Theory, Rubik’s Cube, Merlin’s Machine and Other Mathematical Toys

    D. Joyner.Adventures in Group Theory, Rubik’s Cube, Merlin’s Machine and Other Mathematical Toys. Johns Hopkins University Press, second edition, 2008

    work page 2008

  38. [38]

    L. Kalmar. Zur Theorie der abstrakten Spiele. 1928

    work page 1928

  39. [39]

    R.M. Karp. Reducibility among combinatorial problems. In In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85–103. Plenum, 1972. 72 MATH/CS 91r, Harvard, Spring 2026

    work page 1972

  40. [40]

    Kearns.Graphical Games

    M. Kearns.Graphical Games. Cambridge University Press, 2007

    work page 2007

  41. [41]

    Kiyomi and T

    M. Kiyomi and T. Matsui. Integer programming based algorithms for peg solitaire problems. InLecture Notes in Computer Science, volume 2063, pages 229–240, 2001

    work page 2063

  42. [42]

    D. E. Knuth.Surreal numbers. Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1974

    work page 1974

  43. [43]

    Kompelmakher and V.A

    V.L. Kompelmakher and V.A. Liskovets. Sequential generation of arrangements by means of a basis of trans- positions.Kybernetica, 3:17–21, 1975

    work page 1975

  44. [44]

    R.E. Korf. Depth-first iterative-deepening.Artificial Intelligence, 27:97–110, 1985

    work page 1985

  45. [45]

    Korf and L.A

    R.E. Korf and L.A. Taylor. Finding optimal solutions to the twenty-four puzzle. InProceedings of the AAAI Conference on Artificial Intelligence (AAAI-93), pages 756–761, 1993

    work page 1993

  46. [46]

    Richard E. Korf. Linear-time disk-based implicit graph search.Journal of the ACM, 55(6):1–26, 2008

    work page 2008

  47. [47]

    Kornhauser, G

    D. Kornhauser, G. Miller, and P. Spirakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. InProceedings of the 25th Annual Symposium, pages 241–250, 1984

    work page 1984

  48. [48]

    Lucas.R´ ecr´ eations math´ ematiques, volume III

    E. Lucas.R´ ecr´ eations math´ ematiques, volume III. Paris, 1883

    work page

  49. [49]

    Maschler, E

    M. Maschler, E. Solan, and S. Zamir.Game Theory. Cambridge University Text, 2013

    work page 2013

  50. [50]

    Nowakowski M.H

    R.J. Nowakowski M.H. Albert and D. Wolfe.Lessons in Play, An introduction to Combinatorial Game theory. A.K. Peters, Wellesley Massachusetts, 2007

    work page 2007

  51. [51]

    Miller, M.T

    S.J. Miller, M.T. Phaovibul, and M. Shen. God’s number of bi-colored cubes. 2024

    work page 2024

  52. [52]

    Moscovich.The Puzzle Universe, A History of Mathematics in 315 puzzles

    I. Moscovich.The Puzzle Universe, A History of Mathematics in 315 puzzles. Firefly Books, 2019

    work page 2019

  53. [53]

    Von Neumann and O

    J. Von Neumann and O. Morgenstern.Theory of Games and Economic Behavior. Princeton University Press, 1953

    work page 1953

  54. [54]

    Knill, R.M¨ ader, R.Sanders, J.Simon

    O. Knill, R.M¨ ader, R.Sanders, J.Simon. The rotation group of Rubik’s cube.Sigsam Bulletin, 21, 1987

    work page 1987

  55. [55]

    A151944: Maximal number of moves required for the m x n generalization of the sliding block 15-puzzle

    OEIS. A151944: Maximal number of moves required for the m x n generalization of the sliding block 15-puzzle. Anton Kulchitsky, referring Richard E. Korf (2008) and corrections Tomas Rokicki

    work page 2008

  56. [56]

    Sequence a007664 (Reve’s puzzle)

    OEIS Foundation. Sequence a007664 (Reve’s puzzle). Accessed: 2026-04-22

    work page 2026

  57. [57]

    Orlin.Math Games with Bad Drawings

    B. Orlin.Math Games with Bad Drawings. Black Dog and Leventhal Publishers, 2022

    work page 2022

  58. [58]

    Osborne and A

    M.J. Osborne and A. Rubinstein.A Course in Game Theory. MIT Press, 1994

    work page 1994

  59. [59]

    Parberry

    I. Parberry. A real-time algorithm for the (n 2 −1)-puzzle.Information Processing Letters, 56:23–28, 1995

    work page 1995

  60. [60]

    Patashnik

    O. Patashnik. Qubic: 4x4x4 tic-tac-toe.Math. Mag., 53:202–216, 1980

    work page 1980

  61. [61]

    Pritchard.The Classified Encyclopedia of Chess Variants

    D.B. Pritchard.The Classified Encyclopedia of Chess Variants. John Beasley, 2007. originally printed Biddles Ltd, Kings’s Lynn

    work page 2007

  62. [62]

    Ratner and M

    D. Ratner and M. Warmuth. Finding a shortest solution for the nxn extension of the 15-puzzle is intractable. AAAI-86 Proceedings, 1986

    work page 1986

  63. [63]

    Ratner and M

    D. Ratner and M. Warmuth. Finding a shortest solution for the (n×n)-extension of the 15-puzzle is intractable. Journal of Symbolic Computation, 10:111–137, 1990

    work page 1990

  64. [64]

    Reinefeld

    A. Reinefeld. Complete solution of the eight-puzzle. InProceedings of the International Joint Conference on Artificial Intelligence (IJCAI-93), pages 248–253, 1993

    work page 1993

  65. [65]

    Alon R.M

    N. Alon R.M. Adin and Y. Roichman. Circular sorting, 2025

    work page 2025

  66. [66]

    Roberts.Thinking recursively with Java

    E. Roberts.Thinking recursively with Java. Wiley, 2006

    work page 2006

  67. [67]

    Rokicki, H

    T. Rokicki, H. Kociemba, M. Davidson, and J. Dethridge. The diameter of the Rubik’s cube group is twenty. SIAM Journal on Discrete Mathematics, 27:1082–1105, 2013

    work page 2013

  68. [68]

    A. E. Roth. Intoduction to the Shapley value. InThe Shapley value. Cambridge University Press, 1988

    work page 1988

  69. [69]

    Rubik.Cubed, The puzzle of us all

    E. Rubik.Cubed, The puzzle of us all. Flatiron Books, New York, 2020

    work page 2020

  70. [70]

    Schwalbe and P

    U. Schwalbe and P. Walker. Zermelo and the early history of game theory.Games and Economic Behavior, 34:123–137, 2001

    work page 2001

  71. [71]

    Scorer, P.M

    R.S. Scorer, P.M. Grundy, and C.A.B. Smith. Some binary games.Mathematical Gazette, 28:96–103, 1944

    work page 1944

  72. [72]

    C. E. Shannon. Programming a computer for playing chess.Philosophical Magazine, 41(314), 1950. National IRE Convention on March 9, 1949

    work page 1950

  73. [73]

    Shapley.A value for n-person games

    L.S. Shapley.A value for n-person games. Rand Coorporation, 1952

    work page 1952

  74. [74]

    Singmaster.Rubik’s magic cube

    D. Singmaster.Rubik’s magic cube. Enslow Publishers, 1981

    work page 1981

  75. [75]

    Steinerberger

    S. Steinerberger. On the number of positions in chess without promotion.International Journal of Game Theory, 44:761–767, 2015

    work page 2015

  76. [76]

    B.M. Stewart. Solution to advanced problem 3918.American Mathematical Monthly, 48:217–219, 1941

    work page 1941

  77. [77]

    Uehara and S

    R. Uehara and S. Iweta. Generalized hi-q is np-complete.Trans IEICE 73, pages 270–273, 1990

    work page 1990

  78. [78]

    van Zuylen, J

    A. van Zuylen, J. Bieron, F. Schalekamp, and G. Yu. An upper bound on the number of circular transpositions to sort a permutation, 2014

    work page 2014

  79. [79]

    von Neumann

    J. von Neumann. Zur theorie der gesellschaftsspiele.Mathematische Annalen, pages 295–320, 1928. Translated by S. Bargmann to English. 73 GRAPHS,GAMES,GROUPS

    work page 1928

  80. [80]

    R. M. Wilson. Graph puzzles, homotopy, and the alternating group.Journal of Combinatorial Theory, Series B, 16:86–96, 1974

    work page 1974

Showing first 80 references.