ClassicLogic: A K NOWLEDGE -D RIVEN B ENCHMARK OF C LASSIC P UZZLE G AMES FOR E VALUATING C OMPOSITIONAL G ENERALIZATION
arXiv:2607.05185v1 [cs.AI] 6 Jul 2026
A P REPRINT Mahnoor Shahid Universität Duisburg-Essen Germany [email protected]
Hannes Rothe Universität Duisburg-Essen Germany [email protected]
A BSTRACT Compositional generalization, the ability to understand and produce novel combinations of known components, remains a fundamental challenge for modern artificial intelligence. While few benchmarks exist, many focus on linguistic tasks and lack complex, explicit compositional structures. We introduce ClassicLogic, a new benchmark suite designed to evaluate an agent’s ability to learn and compose problem-solving strategies. The benchmark consists of four classic logic puzzles: Sudoku, KenKen, Kakuro, and Futoshiki. Its core innovation is a hierarchical, explicit knowledge base for each game, where complex solving strategies are formally defined as compositions of simpler, foundational strategies. This structure allows for fine-grained evaluation of an agent’s reasoning capabilities, from learning basic rules to applying multi-step compositional strategies to solve puzzles of increasing, mathematically validated difficulty. The open-source benchmark provides a challenging new testbed for advancing neuro-symbolic and other advanced AI reasoning systems. The benchmark is open-source and available at: https: //github.com/Place-Beyond-Bytes/classic_games_benchmark.git. Keywords Compositional Generalization, Benchmark, Neuro-Symbolic AI, Logic Puzzles, Multi-Step Reasoning
1
Introduction
The ability to flexibly combine existing knowledge to solve new problems is a hallmark of human intelligence (Sternberg, 1984; Cosmides and Tooby, 1997). This capacity, termed as compositional generalization Keysers et al. (2019); Wiedemer et al. (2023), enables us to generate a potentially infinite range of complex ideas and behaviors from a finite set of known components (Fodor and Pylyshyn, 1988). Modern artificial intelligence, particularly large-scale models, has demonstrated remarkable capabilities in processing and generating human-like data(Zhao et al., 2023). Yet, a critical gap persists between their pattern-matching prowess and the robust, systematic reasoning characteristic of human intelligence(Marcus, 2018). These models often fail at tasks requiring logical deduction and multi-step planning, revealing a fundamental weakness in their ability to generalize systematically (Patil and Jadon, 2025; Cao et al., 2025). To address this, the community has developed benchmarks such as SCAN (Lake and Baroni, 2018) and COGS (Kim and Linzen, 2020) to test for compositional generalization, primarily in the domain of natural language processing. However, a gap exists for benchmarks that test compositional reasoning in more structured, symbolic problem-solving domains (Wang et al., 2024). Such domains require not only recognizing patterns but also building and executing explicit, multi-step strategies. In this paper, we introduce ClassicLogic, a novel benchmark designed to provide a transparent and challenging testbed for compositional reasoning. Our contribution is a suite of four classic logic puzzles—Sudoku, KenKen, Kakuro, and Futoshiki—that are procedurally generated and comes with a hierarchical knowledge base (KB) of solving strategies, where complex solving strategies are explicitly defined as compositions of simpler, atomic rules. For instance, advanced strategies are explicitly defined as compositions of more fundamental ones (e.g., identifying a ‘naked_pair’ in Sudoku
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
is a composition of the ‘naked_single’ and ‘constraint_propagation’ strategies). This structure allows us to dissect the reasoning process and evaluate three distinct and crucial forms of compositional generalization: (1) Entity Composition, such as identifying handwritten digits as numerical entities within the puzzle grid; (2) Relational Composition, such as integrating cell-value states with arithmetic or inequality constraints; and (3) Procedural Composition, such as chaining simple solving rules into complex, multi-step strategies. By providing a framework to test these multi-facets of reasoning, ClassicLogic offers a more nuanced evaluation than simple accuracy metrics. In summary, our main contributions are: • A novel, open-source benchmark (ClassicLogic) featuring four challenging logic puzzles with procedurally generated instances and guaranteed unique solutions. • A hierarchical knowledge base (KB) for each game base, where complex strategies are explicitly composed of simpler ones, allowing for fine-grained control over task difficulty and required reasoning depth. • To our knowledge, the first unified framework to explicitly disentangle and evaluate three distinct forms of compositional generalization: Entity Composition (perception), Relational Composition (rule-following), and Procedural Composition (strategic planning). It enables researchers to diagnose why a model fails—whether it is unable to learn base rules, combine them, or transfer them. As such, ClassicLogic provides a crucial new tool to guide the development of more robust, interpretable, and systematically intelligent AI systems.
2
Related Work
The evaluation of compositional generalization has been a central theme in cognitive science and AI. Early work highlighted the systematicity of human thought as a core property of intelligence (Fodor and Pylyshyn, 1988), a concept that modern benchmarks aim to quantify. 2.1
Benchmarks for Compositional Generalization
Existing benchmarks have largely focused on linguistic and visual domains. In linguistics, datasets like SCAN (Lake and Baroni, 2018) and COGS (Kim and Linzen, 2020) evaluate whether models can generalize to novel combinations of familiar words and commands. Similarly, alongside them, others have emerged to test more complex facets. For instance, gSCAN (Ruis et al., 2020) tests generalization in visually-grounded instruction following , while CFQ provides a more realistic testbed based on querying a large knowledge base (Keysers et al., 2020). In vision, the CLEVR dataset (Johnson et al., 2017) evaluates for compositional reasoning about objects and their spatial and semantic relationships. Subsequent work like CLEVRER added a temporal dimension to probe causal reasoning (Yi et al., 2020), and GQA introduced a more naturalistic and compositionally complex question-answering dataset (Hudson and Manning, 2019). While these benchmarks are foundational for assessing generalization on perceptual and sequential data, they primarily test for an implicit understanding of composition. They are not designed to evaluate an agent’s ability to learn and execute an explicit, multi-step procedural strategy from a symbolic knowledge base. However, ClassicLogic provides a ground-truth and symbolic hierarchy of strategies. This allows for direct evaluation of an agent’s ability to build and execute complex plans in a discrete, symbolic environment. 2.2
AI in Games and Automated Reasoning
The use of games as a crucible for artificial intelligence is a long and storied tradition. Landmark achievements, such as DeepMind’s AlphaGo for GO (Silver et al., 2016) and Pluribus for poker (Brown and Sandholm, 2019), have demonstrated superhuman performance in complex strategy games. Such immensely powerful systems often rely on reinforcement learning, trained over massive volumes of self-play and functioning as opaque, “black-box" agents. The strategies they learn are emergent and subsymbolic, not explicitly represented in a human-interpretable format (Liang et al., 2025). In contrast to opaque deep RL agents, ClassicLogic provides a transparent evaluation environment where the goal is not to create an optimal player, but to diagnose if an agent can learn and deploy human-cognizable strategies. Moreover, there is extensive research on automated puzzle solvers, particularly for logic puzzles (Mitra and Baral, 2015; Piette et al., 2019; Giadikiaroglou et al., 2024). These problems are often formally framed as Constraint Satisfaction Problems (CSPs) (Russell and Norvig, 2010; Berthier, 2013), for which highly efficient and specialized solvers exist. However, the goal of these systems is to find a valid solution as quickly as possible because they are optimized for the final product. They do not evaluate whether an agent can learn the human-like reasoning process required to get 2
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
there (Qefalija et al., 2024). Whereas, ClassicLogic is uniquely focused on evaluating the reasoning process itself. It provides a framework to test how an agent learns, not just whether it can produce a correct answer. It is not designed to compete with bespoke CSP solvers, but rather to serve as a benchmark that tests whether a learning agent can build an understanding of the puzzle’s underlying principles by learning and composing strategies from our hierarchical knowledge base. 2.3
Neuro-Symbolic Approaches
A rising field that directly intersects with our work is Neuro-Symbolic (NeSy) AI. The goal of NeSy is to integrate the pattern-recognition strengths of neural networks with the reasoning capabilities of symbolic systems (Hitzler and Sarker, 2022; Garcez and Lamb, 2023; Sakr et al., 2022). Systems like DeepProblog (Manhaeve et al., 2018) and Neural Logic Machines (Dong et al., 2019) attempt to build models that can perform explicit logical reasoning on top of neural perception. ClassicLogic provides an ideal testbed for such systems, as it contains both perceptual components (e.g., recognizing MNIST digits) and a complex, symbolic reasoning structure (the strategy KB). Currently, a major challenge for the NeSy field is the lack of comprehensive benchmarks that require deep, compositional, and symbolic reasoning; we aim to fill this gap (Wang et al., 2024). In regards to that, our benchmark serves as a testbed for NeSy systems as it provides a challenging new environment that requires the tight integration of perception and multi-step symbolic reasoning.
3
The ClassicLogic Benchmark Suite
The ClassicLogic benchmark is a suite of four procedurally generated logic puzzle environments designed to facilitate the diagnostic evaluation of compositional reasoning in artificial agents. In this section, we formalize its architecture, the structure of its game environments, and its core innovation: the hierarchical knowledge base of solution strategies. 3.1
Design Principles
The development of ClassicLogic is guided by four core principles to ensure a rigorous and fair evaluation platform for end-to-end reasoning systems: • Perceptual Grounding: All initial puzzle states are presented to the agent not as symbolic matrices, but as visual grids rendered with MNIST digit images. This design choice necessitates an initial perceptual function, Φ : I → G, to map the visual input from the image space I to a symbolic grid state G, creating a unified testbed for integrated perception and reasoning. • Strategy-Driven Generation: A puzzle instance P is not generated randomly, but is constructed to require a specific, minimal set of strategies Σreq for its solution. This allows for targeted testing of an agent’s ability to deploy specific reasoning patterns. • Validated Difficulty Scaling: The difficulty of a puzzle P , denoted by a function D(P ), is directly correlated with the compositional depth of the strategies in Σreq . We define compositional depth, δ(s), of a strategy s recursively, providing a formal measure of puzzle complexity. • Guaranteed Uniqueness: For every puzzle instance P generated by the benchmark, there exists a unique solution state Ssol . This eliminates ambiguity in evaluation and ensures that success is based on valid logical deduction. 3.2
Game Environments
The suite comprises four classic logic puzzles, each formalized as a distinct environment, as mentioned in Table 1. Let a grid state be a matrix G of size N × N . The state of any puzzle, P , can be represented as a tensor T ∈ RN ×N ×K , where N is the grid dimension and K represents the features of each cell (e.g., a one-hot vector for candidate digits). The action space A is typically discrete, allowing an agent to set a value v in a cell (i, j), i.e., A ⊆ {(i, j, v)}N i,j,v=1 . Sudoku The environment is a partially filled 9 × 9 grid G. The objective is to fill the empty cells with digits d ∈ {1, ..., 9} subject to the constraint that for any cell Gij , its value must be unique in its row, column, and designated 3 × 3 subgrid. Formally, ∀i, j, k ∈ {1, ..., 9} where i ̸= k, Gij ̸= Gkj ; where j ̸= k, Gij ̸= Gik ; and for all cells (i′ , j ′ ) in the same 3 × 3 block as (i, j), Gij ̸= Gi′ j ′ . 3
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
Table 1: Overview of the Game Environments in the ClassicLogic Benchmark Suite. Game
Grid Size
Core Constraint Type
Sudoku KenKen Kakuro Futoshiki
9×9 N ×N Irregular N ×N
Latin Square + Block Latin Square + Arithmetic Cages Cross-Sum Logic Latin Square + Inequality
KenKen An N × N grid is partitioned into a set of non-overlapping cages C = {c1 , c2 , ..., cm }. Each cage ck ∈ C is defined by a tuple (Zk , Vk , Ok ), where Zk is the set of cell coordinates in the cage, Vk ∈ N+ is a target value, and Ok ∈ {+, −, ×, ÷} is a binary arithmetic operator. The constraint for each cage is that the application of operator Ok to the values in the cells of Zk must result in Vk . Kakuro The grid consists of “clue cells" and “entry cells." A clue cell contains one or two clue values, (cdown , cright ), where c ∈ N+ . The constraint is that the sum of the digits in the contiguous block of entry cells below the clue must equal cdown , and the sum of the digits in the block to its right must equal cright . Furthermore, all digits within any given block must be unique. Futoshiki An N × N grid must be filled with digits {1, ..., N } adhering to Latin square rules (uniqueness in rows and columns). Additionally, the environment contains a set of relational constraints R of the form Gij ≺ Gi′ j ′ , where (i, j) and (i′ , j ′ ) are adjacent cell coordinates and ≺∈ {<, >}. To provide a concrete visualization of these environments, Figure 1 presents sample instances for Sudoku, KenKen, and Futoshiki. Each example displays both the initial puzzle state, as it would be presented to an agent, and its corresponding unique solution. These samples illustrate the diversity of constraints and logical structures that agents must handle within the ClassicLogic benchmark. 3.3
The Hierarchical Knowledge Base (KB)
The central innovation of ClassicLogic is its explicit, hierarchical knowledge base. Formally, the KB for each game is a tuple K = (S, C), where S is a set of strategies and C is a composition relation defined on S. The set of strategies S is partitioned into a set of atomic base strategies Sbase and a set of composed strategies Scomp . A strategy s ∈ S is a function that maps a puzzle state Pt to a new, more constrained state Pt+1 by making a valid logical deduction, i.e., s : Pt 7→ Pt+1 . The composition relation C defines how strategies in Scomp are constructed. For any composed strategy sc ∈ Scomp , there exists an ordered set of constituent strategies {s1 , s2 , ..., sk } ⊆ S such that sc represents the sequential application or Lk logical combination of these constituents. We can denote this composition as sc := i=1 si . For example, consider the state of a Sudoku puzzle P as a grid of candidate sets, where Pij ⊆ {1, ..., 9} is the set of possible values for cell (i, j). A base strategy, Constraint Propagation (scp ), takes a confirmed cell value and removes it from the candidate sets of all peer cells. This simple action is a foundational component for more complex strategies. A moderate strategy like Naked Pair (snp ) is composed of a pattern-recognition step followed by this action, which we can denote as snp := sfind_pair ⊕ scp . The sub-procedure, sfind_pair , identifies when two cells in a unit share the exact same two candidates (e.g., Pij = Pik = {a, b}). This finding then enables the application of scp to eliminate candidates a and b from all other cells in that unit. This compositional principle extends to more advanced, multi-unit strategies as visualized in Figure 2. An X-Wing (sxw ) is a more complex moderate strategy that is similarly composed of a sophisticated pattern-recognition procedure followed by the same base action: sxw := sfind_xwing ⊕ scp . Here, sfind_xwing is itself a composition of a more basic procedure, let’s call it Unit Scan (sscan ), which finds the positions of a candidate in a unit. An X-Wing pattern is identified for a digit d when there exist two rows r1 , r2 and two columns c1 , c2 such that the repeated application of sscan confirms that Positions(d, r1 ) = {c1 , c2 } and Positions(d, r2 ) = {c1 , c2 }. The hierarchy deepens further with hard strategies like Swordfish (ssf ), which is a direct extension of the X-Wing logic. It is composed as ssf := sfind_swordfish ⊕ scp , where sfind_swordfish is a scaled-up version of the X-Wing’s pattern recognition. It applies the same foundational sscan procedure but seeks a 3x3 pattern across three rows and three columns. This demonstrates a deep compositional structure where advanced strategies are formed not just by combining different simple rules, but by scaling and reapplying the same underlying logical patterns in a more complex configuration. 4
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
(a) Sudoku Puzzle
(b) KenKen Puzzle
(c) Futoshiki Puzzle
(d) Sudoku Solution
(e) KenKen Solution
(f) Futoshiki Solution
Figure 1: Visual examples from the ClassicLogic benchmark, showcasing the diversity of reasoning challenges. The top row (a-c) displays the initial puzzle states for Sudoku, KenKen, and Futoshiki, presented with perceptual MNIST digits. The bottom row (d-f) shows their corresponding, unique logical solutions.
3.4
Procedural Generation and Difficulty Calibration
A central requirement for a robust benchmark is the ability to generate a vast and diverse set of puzzles with precisely controlled properties. Standard reverse-solving algorithms, which iteratively remove clues from a solved grid, are often computationally intractable. To address this, we employ a sophisticated two-stage hybrid generation process. This methodology separates the computationally expensive task of logical structure generation from the lightweight task of producing playable instances, providing both rigor and real-time performance. 3.4.1
Stage 1: Strategy-Driven Template Generation
The goal of this stage is to produce a library, TPL, of minimal, abstract puzzle structures, or templates. Each template represents the logical essence of a puzzle class with a specific difficulty. We formally define a puzzle instance as a tuple P = (G, CP ), where G is a grid structure and CP is a set of concrete clues (e.g., pre-filled cell values, arithmetic cage definitions). A solution S is a complete assignment of values to G that satisfies all game rules and the clues in CP . A template is an abstracted puzzle, T pl = (L, Cabs , Σreq ), where L is a logical layout (e.g., a graph representation of the grid), Cabs is a set of abstract placeholder constraints, and Σreq is the pre-analyzed, minimal set of strategies required to solve any valid instantiation of this template. Template generation (Algorithm 1) begins with a canonical solution grid, Ssol . It then performs an iterative clue ablation process. For each clue c ∈ CSsol , it creates a candidate puzzle P ′ = (G, CP \ {c}). This candidate is validated against two criteria using two distinct solvers: 5
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
Figure 2: An example illustration of the strategy hierarchy in the ClassicLogic Knowledge Base of Sudoku. Complex strategies are explicitly constructed from simpler, foundational ones, allowing for precise control over the compositional reasoning required by a puzzle.
1. Uniqueness Check: A complete, optimal solver, FullSolver(P ′ ), which returns the set of all valid solutions. The removal is valid only if |FullSolver(P ′ )| = 1. 2. Difficulty Check: A constrained solver, LimitedSolver(P ′ , K≤Dtarget ), equipped only with strategies from the Knowledge Base whose compositional depth δ(s) is less than or equal to the target difficulty Dtarget . The removal is valid only if this solver finds the solution, ensuring the puzzle does not require harder strategies. The final, minimal puzzle Pfinal is then abstracted into a canonical template T pl by a function fabs : P → T pl. This intensive process is run to populate the template library TPL. To validate our formal difficulty metric, we conducted an empirical study correlating D(P ) with the performance of our baseline heuristic solver (see Section 4.1). Algorithm 1 Strategy-Driven Template Generation 1: Input: Target difficulty Dtarget 2: Initialize: Ssol ← GenerateCanonicalSolution() 3: P ← (G, CSsol ) 4: Cremovable ← GetClues(P ) 5: for each clue c ∈ Shuffled(Cremovable ) do 6: P ′ ← (G, CP \ {c}) 7: if |FullSolver(P ′ )| = 1 then 8: Let Klimit ← {s ∈ K | δ(s) ≤ Dtarget } 9: if LimitedSolver(P ′ , Klimit ) is successful then 10: P ← P′ 11: end if 12: end if 13: end for 14: T pl ← fabs (P ) 15: Output: Template T pl
3.4.2
▷ Initial puzzle is the full solution
▷ Accept clue ablation
▷ Abstract final puzzle to a template
Stage 2: Real-time Puzzle Instantiation
With a rich library TPL of pre-generated and validated templates, creating a playable puzzle instance is computationally trivial. This process (Algorithm 2) involves template selection followed by instantiation and transformation. 6
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
The instantiation function, finst : T pl → Pbase , maps the template’s abstract structure L and constraints Cabs to a concrete puzzle instance Pbase . This is achieved via a randomized backtracking search that assigns concrete values while satisfying the template’s constraints. To generate a wide variety of structurally equivalent but superficially distinct puzzles from a single template, we apply a transformation τ from a set of symmetry-preserving transformations T (e.g., rotation, reflection, and value permutations). The final puzzle is Pfinal = τ (Pbase ). This two-stage architecture ensures both logical rigor and real-time performance. Algorithm 2 Real-time Puzzle Instantiation 1: Input: Target difficulty Dtarget , Template library TPL 2: Initialize: TPLfiltered ← {T pl ∈ TPL|D(T pl) = Dtarget } 3: if TPLfiltered is empty then 4: return Error("No templates for difficulty") 5: end if 6: T plselected ← RandomlySelect(TPLfiltered ) 7: Pbase ← finst (T plselected ) 8: τ ← RandomlySelect(T ) 9: Pfinal ← τ (Pbase ) 10: Output: Final puzzle instance Pfinal
3.5
▷ Select a transformation ▷ Apply transformation
A Framework for Evaluating Compositional Generalization
The ClassicLogic benchmark provides a structured framework to evaluate three distinct and critical forms of compositional generalization. We formalize these as follows, from basic perception to multi-step strategic planning. 1. Entity Composition is the foundational ability to learn a mapping function, Φ : I → E, from the raw perceptual input space I (pixel grids) to a set of symbolic entities E. An entity e ∈ E is a tuple representing a fundamental object, such as (digit, 7) or (operator, >). An agent demonstrates successful entity composition if, for every initial clue image ir,c at grid location (r, c), its inferred entity êr,c = Φ(ir,c ) equals the ground-truth entity er,c . • Example 1 (KenKen): An agent is presented with a visual cage containing the clue “7+". Successful composition requires generating the entity set {(digit, 7), (operator, +)}. An output of {(digit, 1), (operator, +)} would represent a critical failure in entity recognition. • Example 2 (Futoshiki): Given a grid of MNIST digits and > symbols, a successful agent must parse the entire initial state P0 into a set of symbolic facts, such as {Value(r1 , c1 , 5), Constraint(r2 , c2 , >)...}. Misclassifying a handwritten digit or an operator indicates a failure at this basic compositional level. 2. Relational Composition is the ability to apply a set of universal relational rules, R, to the set of entities E to infer new facts or validate state transitions. A rule R ∈ R is a predicate over one or more entities that must hold true for a state to be valid. An agent’s action at at state St is valid only if the resulting state St+1 satisfies all rules, i.e., ∀R ∈ R, R(St+1 ) = true. An illegal move signals a failure in relational composition. • Example 1 (Futoshiki): Given the symbolic facts Constraint(c1 , c2 , >) and Value(c2 , 4), the agent must apply the rule: ∀c1 , c2 , v1 , v2 : (Value(c1 , v1 ) ∧ Value(c2 , v2 ) ∧ Constraint(c1 , c2 , >)) → v1 > v2 By composing the rule with the known facts, a successful agent infers that the candidate set for c1 is now constrained, Candidates(c1 ) ⊆ {5, 6, 7, 8, 9}. • Example 2 (Sudoku): An agent in a state with Value(1, 2, 7) considers the action at = place(1, 5, 7). To validate this, it must apply the row-uniqueness rule: ∀r, c1 , c2 , v : (c1 ̸= c2 ∧ Value(r, c1 , v)) → ¬Candidate(v, r, c2 ) Since this rule is violated by the proposed action, a successful agent would prune this action from its policy. 7
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
3. Procedural Composition This is the highest form of compositionality, representing the ability to construct a new procedure (strategy), snew , by sequencing a set of known, simpler procedures {s1 , ..., sk } ⊆ Sknown . Formally, snew := sk ◦ ... ◦ s1 , where ◦ represents sequential application or functional composition. We train an agent on puzzles Pbase solvable only by procedures in Sbase . We then test it on puzzles Pcomp that require at least one procedure sc ∈ / Sbase , where sc is a known composition of procedures from Sbase . Success on Pcomp provides direct evidence of procedural composition. • Example 1 (Sudoku): An agent knows the procedure spattern_rec (recognize when two cells in a row have candidates {2, 8}) and selimination (apply constraint propagation). It must compose these to form a novel strategy, snaked_pair := selimination ◦ spattern_rec , where the output of the pattern recognition (the cells and candidates to eliminate) becomes the input for the elimination procedure. • Example 2 (Kakuro): An agent knows sunique_sum (e.g., a 2-cell sum of 3 must be {1, 2}) and scross_ref (use a confirmed value to constrain an intersecting block). Faced with intersecting blocks, it must compose a new procedure: first, apply sunique_sum to reduce one block’s candidates to {1, 2}; then, apply scross_ref using a known digit from the second block to disambiguate the first. This chain of dependent procedures is a hallmark of procedural composition. 3.6
Implementation and Accessibility
To maximize reproducibility and ease of adoption, the ClassicLogic benchmark is implemented with a strong focus on accessibility and a streamlined setup process. The entire suite is developed in Python 3 and its dependencies are explicitly managed. A key feature is the unified environment setup. We provide automated scripts designed to create a self-contained virtual environment and install all necessary packages with a single command. The repository includes ‘unified_env_setup.py’ (for POSIX systems) and unified_env_quick_setup.bat (for Windows), which handle the environment creation and dependency installation listed in the ‘requirements.txt’ file. This eliminates common setup hurdles and ensures that researchers can begin experimentation with minimal friction. Furthermore, environment configurations are managed through a central ‘classic_games_env_info.json’ file. This file contains metadata and settings for the benchmark, allowing for easy modification and inspection of the environment’s parameters without altering the core source code. The framework is also designed with modularity and extensibility in mind. Adding a new puzzle to the suite follows a well-defined template, primarily requiring the implementation of the game’s state transition logic and its corresponding strategy knowledge base. This structure encourages community contributions and the long-term expansion of ClassicLogic with new reasoning challenges. The entire framework, including the source code, setup scripts, and documentation, is publicly available under an MIT License on GitHub1 to encourage open collaboration and extension for the research community.
4
Experiments
We conducted a set of experiments to demonstrate how this benchmark can be utilized to evalute an agent’s compositional reasoning abilities using ClassicLogic. 4.1
Preliminary Validation of the Difficulty Metric
Objective Before using ClassicLogic to evaluate AI agents, we first conducted a preliminary experiment to empirically validate that our theoretical difficulty metric, D(P ), derived from the Knowledge Base, correlates with practical computational hardness. To establish both internal and external validity, we measured performance using two distinct automated solvers. Methodology For this validation study, we focused on Sudoku as a representative environment, given its wellunderstood properties and rich strategy space. We generated a validation set of 99 Sudoku puzzles, comprising 33 unique instances for each difficulty category (Easy, Moderate, Hard). We then used two distinct automated solvers to solve each puzzle: • Glass-Box Solver: Our implemented baseline agent that greedily applies strategies from the Knowledge Base K. We measured the total number of distinct strategies applied to reach a solution. • Black-Box Solver: A standard, optimized Constraint Satisfaction Problem (CSP) solver. This solver is unaware of our KB. We measured the wall-clock solve time in milliseconds. 1
https://github.com/Place-Beyond-Bytes/classic_games_benchmark.git
8
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
Our hypothesis is that as the difficulty category progresses from Easy to Hard, the metrics from both solvers will increase significantly. We treated the categories as ranks (Easy=1, Moderate=2, Hard=3) and computed the Spearman’s rank correlation coefficient (ρ). Results The results, summarized in Table 2 and visualized in Figure 3, confirm our hypothesis. The number of strategies applied by the glass-box solver and the solve time for the black-box CSP solver both increase substantially with each difficulty category, demonstrating a strong, positive, and monotonic relationship. Table 2: Empirical validation results for the three difficulty categories using the Sudoku environment. Mean strategies applied ("glass-box" solver) and mean solve time ("black-box" solver) are shown. Standard deviations are in parentheses. Difficulty Category Mean Strategies Applied Mean Solve Time (ms) Easy Moderate Hard
5.4 (±1.5) 12.8 (±3.2) 24.7 (±5.9)
2.1 (±0.6) 15.8 (±4.2) 75.6 (±18.9)
The strong correlation with an independent, black-box solver (ρ = 0.98, p < 0.01) provides the evidence that our formal difficulty metric is a valid proxy for intrinsic computational hardness. This validation of our methodology on a representative puzzle provides confidence that the difficulty scaling is a robust feature of the entire benchmark suite.
Figure 3: Correlation between the difficulty categories and empirical measures. The bars (left axis) show the increase in strategies applied by our “glass-box" solver, while the line plot (right axis) shows the exponential increase in solve time for an independent “black-box" CSP solver.
4.2
Evaluating Compositional Generalization
We evaluated three representative neuro-symbolic (NeSy) models using the ClassicLogic benchmark to assess their compositional generalization capabilities. The models were chosen to represent different approaches to integrating neural and symbolic reasoning: • SATNet Wang et al. (2019): An architecture that integrates a differentiable MAX-SAT solver, allowing a neural network to learn the logical constraints of a problem. • Neural Module Network (NMN) Andreas et al. (2016): A model that dynamically assembles a custom neural network from smaller, specialized modules to create a task-specific reasoning pipeline. • Logical Neural Network (LNN) Riegel et al. (2020): A framework where each neuron has a clear logical meaning (e.g., AND, OR), creating a highly interpretable network that adheres to formal logic. 9
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
The following experiments are intended to demonstrate the benchmark’s utility in evaluating and differentiating the capabilities of various models across all four game environments. We conducted two distinct sets of experiments to probe different facets of compositional generalization. First, in Section 4.3, we evaluated the ability of models to perform zero-shot transfer of perceptual and relational knowledge from a single training game to three unseen games. Second, in Section 4.4, we test for in-domain procedural generalization, evaluating if models can compose known strategies into novel, more complex ones within each game environment. 4.3
Entity and Relational Composition Performance
Training Protocol To rigorously test for zero-shot generalization, all models were trained exclusively on the Sudoku environment. For Entity Composition, the models’ perceptual frontends were trained to recognize the MNIST digits used as clues in Sudoku puzzles. For Relational Composition, the models were trained only on Sudoku’s specific rule set: the uniqueness constraint within rows, columns, and 3x3 blocks. Their performance was then evaluated in a zero-shot setting on the unseen visual and logical structures of KenKen, Kakuro, and Futoshiki. Results The results, summarized in Table 3, reveal the profound challenge of out-of-domain generalization for these models. In Entity Composition, while all models learned to parse Sudoku digits well, their accuracy dropped significantly on the other games. The LNN performed best, maintaining accuracy in the low 80s, but all models struggled, indicating that their visual representations were not abstract enough to generalize to the novel layouts and symbols (e.g., cages, operators) in the other puzzles. The performance on Relational Composition tells a similar story. The models found it extremely difficult to transfer the learned Sudoku rules to the fundamentally different constraints of the other games. The LNN was the most robust, maintaining the lowest illegal move rate, which is consistent with its logic-based architecture. However, even it made frequent errors when faced with the arithmetic and ordinal logic of KenKen and Futoshiki. SATNet and NMN struggled even more, with illegal move rates reaching as high as 45.5% for the NMN in the Kakuro environment. This demonstrates a critical failure to generalize abstract logical principles, a key weakness that this benchmark effectively exposes. 4.4
Procedural Composition Performance
Training Protocol This experiment tests the most challenging facet of reasoning: composing known rules into novel, multi-step strategies. Unlike the previous zero-shot transfer task, this is a test of in-domain procedural generalization. For each of the four games, all three models were trained on a curriculum of “Easy" and “Moderate" puzzles. This training corpus exposed them to all the base and moderate-level strategies in the Knowledge Base. The models were then tested on a set of “Hard" puzzles, which are guaranteed to require composed strategies in sequences not seen during training. Results The results, shown in Figure 4, are striking and reveal a critical failure point for all tested architectures. Despite their good performance on adhering to static rules (Relational Composition), all models showed an inability to compose those rules into novel, multi-step strategies. The success rates on the Hard puzzles collapsed to below 25% across the board. This demonstrates a stark disconnect between knowing the rules of a game and knowing how to play it strategically. The LNN, which was the most robust in the relational task, remains the top performer here, but its low success rate (20-24%) underscores the immense difficulty of the challenge. The NMN, which might have been expected to perform well due to its modularity, struggled the most, suggesting its dynamic assembly process failed to generalize to more complex procedures. These results powerfully illustrate that even models with strong logical priors are not inherently equipped for the flexible, sequential planning required by our benchmark. Table 3: Entity and Relational composition results across all four game environments. Models were trained only on Sudoku. The results show that models are generalizing well across other games. Entity Parsing Accuracy (%)
Illegal Move Rate (%)
Model
Sudoku
KenKen
Kakuro
Futoshiki
Sudoku
KenKen
Kakuro
Futoshiki
SATNet NMN LNN
79.7 67.5 86.8
70.6 60.4 82.7
74.7 61.7 80.8
70.5 61.4 84.7
6.8 15.7 5.8
17.8 31.8 6.8
25.0 45.5 10.0
9.5 17.1 5.5
10
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
5
Discussion
Our experiments demonstrate that ClassicLogic can effectively diagnose a critical failure mode in modern neurosymbolic systems. The ability to pinpoint this specific gap between relational and procedural generalization is a direct result of the benchmark’s design, which provides a unified framework for evaluating these distinct layers of compositionality in a single, coherent environment. While models adept at learning static facts and rules, they remain brittle at composing those rules into dynamic, multi-step procedures. The severe performance collapse on “Hard" puzzles is not merely a quantitative failure; it is a qualitative one that exposes a deep gap between pattern recognition and true strategic reasoning. This finding suggests that many current architectures, even those with strong logical priors like LNNs and SATNet, lack the mechanisms for flexible, sequential planning. Knowing the rules of chess (relational composition) is fundamentally different from knowing how to play it well (procedural composition). Ultimately, this validates ClassicLogic not just as another benchmark, but as a necessary course correction for the field. It challenges the community to move beyond tasks that can be solved with static rule application and to focus on the more difficult, more human-like skill of composing knowledge into novel plans. We believe that progress on the kind of challenges presented in our benchmark is a prerequisite for building the next generation of robust, trustworthy, and truly intelligent AI systems.
6
Limitations
While ClassicLogic provides a comprehensive framework, it is important to acknowledge its scope and inherent limitations to properly situate its contributions and guide future work. The four puzzles in the suite were selected to cover a diverse range of logical constraints (e.g., arithmetic, relational, spatial). However, they represent only a subset of the vast world of logic puzzles. The benchmark does not currently include other families such as graph-coloring puzzles, temporal logic puzzles, or those requiring extensive common-sense knowledge. Moreover, we have curated a hierarchically structured KB for each game based on well-documented human strategies. However, we do not claim this KB is exhaustive. Humans may employ novel or idiosyncratic strategies not captured in our formal system. These limitations do not diminish the benchmark’s utility but rather clarify its intended purpose: to provide a deep, diagnostic tool for a specific, vital, and currently under-evaluated facet of artificial intelligence. We believe these focused evaluations are a prerequisite for building more general and robust AI systems, and we welcome community contributions to expand the benchmark’s scope in the future.
Figure 4: Procedural composition results across all games. Success rate defines the accurate formation and application of “Hard" strategies required to solve the game. A dramatic "generalization gap" can be observed as a key failure in procedural composition. 11
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
7
Conclusion
In this work, we introduced ClassicLogic, which to best of our knowledge is the first benchmark to provide a unified framework for evaluating the full stack of compositional reasoning: from Entity Composition (perception) to Relational Composition (rule-following) and finally to Procedural Composition (strategic planning). Our illustrative experiments revealed a profound gap: while current neuro-symbolic models excel at adhering to static rules, they fail catastrophically when required to compose known procedures into novel, multi-step plans. This finding validates ClassicLogic as a crucial diagnostic tool that moves beyond simple rule-following to probe the deeper challenge of strategic reasoning. By providing a clear and challenging measure of procedural generalization, we hope to guide the community toward building the next generation of AI that can not only learn facts but can compose them into robust and trustworthy strategies.
References Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. (2016). Neural module networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Berthier, D. (2013). Pattern-based constraint satisfaction and logic puzzles. arXiv preprint arXiv:1304.1628. Brown, N. and Sandholm, T. (2019). Superhuman AI for multiplayer poker. Science, 365(6456):885–890. Cao, P., Men, T., Liu, W., Zhang, J., Li, X., Lin, X., Sui, D., Cao, Y., Liu, K., and Zhao, J. (2025). Large language models for planning: A comprehensive and systematic survey. arXiv preprint arXiv:2505.19683. Cosmides, L. and Tooby, J. (1997). The modular nature of human intelligence. The origin and evolution of intelligence, pages 71–101. Dong, H., Mao, J., Lin, T., Wang, C., Lih, L., and Zhou, D. (2019). Neural logic machines. In International Conference on Learning Representations (ICLR). Fodor, J. A. and Pylyshyn, Z. W. (1988). Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-2):3–71. Garcez, A. d. and Lamb, L. C. (2023). Neurosymbolic ai: The 3 rd wave. Artificial Intelligence Review, 56(11):12387– 12406. Giadikiaroglou, P., Lymperaiou, M., Filandrianos, G., and Stamou, G. (2024). Puzzle solving using reasoning of large language models: A survey. arXiv preprint arXiv:2402.11291. Hitzler, P. and Sarker, M. K. (2022). Neuro-symbolic artificial intelligence: The state of the art. Hudson, D. A. and Manning, C. D. (2019). GQA: A new dataset for real-world visual reasoning and compositional question answering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Zitnick, C. L., and Girshick, R. (2017). CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2901–2910. Keysers, D., Schärli, N., Scales, N., Buisman, H., Furrer, D., Kashubin, S., Momchev, N., Sinopalnikov, D., Stafiniak, L., Tihon, T., et al. (2019). Measuring compositional generalization: A comprehensive method on realistic data. arXiv preprint arXiv:1912.09713. Keysers, D., Schärli, N., Kale, N., Cer, D., Firat, O., Mourad, A., Riesa, J., Bapna, A., Caswell, I., and Hassan, H. (2020). Measuring compositional generalization: A comprehensive method on realistic data. In International Conference on Learning Representations (ICLR). Kim, N. and Linzen, T. (2020). COGS: A compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9107–9123. Lake, B. M. and Baroni, M. (2018). Generalization without systematicity: On the compositional skills of sequence-tosequence recurrent networks. In International Conference on Machine Learning (ICML), pages 2873–2882. Liang, B., Wang, Y., and Tong, C. (2025). Ai reasoning in deep learning era: From symbolic ai to neural–symbolic ai. Mathematics, 13(11):1707. Manhaeve, R., Dumančić, S., Kimmig, A., Demeester, T., and De Raedt, L. (2018). DeepProblog: Neural probabilistic logic programming. In Advances in Neural Information Processing Systems (NeurIPS). Marcus, G. (2018). Deep learning: A critical appraisal. arXiv preprint arXiv:1801.00631. 12
ClassicLogic: B ENCHMARK OF C LASSIC P UZZLE G AMES FOR C OMPOSITIONAL G ENERALIZATION
Mitra, A. and Baral, C. (2015). Learning to automatically solve logic grid puzzles. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1023–1033. Patil, A. and Jadon, A. (2025). Advancing reasoning in large language models: Promising methods and approaches. arXiv preprint arXiv:2502.03671. Piette, C., Piette, E., Stephenson, M., Soemers, D. J., and Browne, C. (2019). Ludii and xcsp: playing and solving logic puzzles. In 2019 IEEE Conference on Games (CoG), pages 1–4. IEEE. Qefalija, E., Snopce, H., and Dermaku, A. (2024). Literature review on constraint satisfaction problems solving. In 2024 8th International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), pages 1–6. IEEE. Riegel, R., Gray, A., Luus, F., Khan, N., Makondo, N., Akhalwaya, I. Y., Yarkoni, T., Koco, Z., and Mvelase, P. (2020). Logical neural networks. Ruis, L., Andreas, J., Baroni, M., Dagan, I., and Goldberg, Y. (2020). A benchmark for systematic generalization in grounded language understanding. In International Conference on Machine Learning (ICML). Russell, S. J. and Norvig, P. (2010). Artificial Intelligence: A Modern Approach. Pearson Education, 3rd edition. Sakr, C., Hitzler, P., and Sheth, A. (2022). Neuro-symbolic ai star: A tale of two worlds. AI Magazine, 43(4):406–419. Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., and Hassabis, D. (2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489. Sternberg, R. J. (1984). Toward a triarchic theory of human intelligence. Behavioral and Brain Sciences, 7(2):269–287. Wang, P.-W., Donti, P., Wilder, B., and Kolter, Z. (2019). SATNet: Bridging deep learning and logical reasoning using a differentiable MAX-SAT solver. In International Conference on Machine Learning (ICML). Wang, W., Yang, Y., and Wu, F. (2024). Towards data-and knowledge-driven ai: a survey on neuro-symbolic computing. IEEE Transactions on Pattern Analysis and Machine Intelligence. Wiedemer, T., Mayilvahanan, P., Bethge, M., and Brendel, W. (2023). Compositional generalization from first principles. Advances in Neural Information Processing Systems, 36:6941–6960. Yi, K., Gan, C., Li, Y., Torralba, A., Kohli, P., and Tenenbaum, J. (2020). CLEVRER: Collision events for video representation and reasoning. In International Conference on Learning Representations (ICLR). Zhao, W. X., Zhou, K., Li, J., Tang, T., Wang, X., Hou, Y., Min, Y., Zhang, B., Zhang, J., Dong, Z., et al. (2023). A survey of large language models. arXiv preprint arXiv:2303.18223, 1(2).
13