Board Generation
Discover how ChromaPath creates infinite unique puzzles with exactly one solution
How It Works
ChromaPath generates puzzles by creating a grid, placing colored endpoints, generating paths between them, and ensuring the final puzzle has exactly one solution. The process becomes more computationally intensive as board size increases due to the exponential growth in possible path combinations.
Generation Process
Grid Creation
We start with a blank grid of the specified size (5x5 to 12x12). The grid serves as the canvas where we'll place endpoints and generate paths. Larger grids provide more space for complex puzzles but require significantly more computation.
Path Generation
For each pair of matching endpoints, we generate a valid path that connects them. Paths must be continuous, avoid crossing other paths, and respect the constraint that every cell must eventually be filled. We use weighted random walks that favor straight paths with occasional turns to create natural-looking solutions.
Constraint Validation
After placing each path, we validate that the board still has potential for a complete solution. This includes checking that remaining empty regions are large enough for additional paths, that no cells become isolated, and that the total number of paths needed doesn't exceed what can fit in the remaining space.
Solution Verification
Once the grid is fully filled, we verify that the puzzle has exactly one solution. This involves checking if removing any combination of paths would allow for alternative solutions. If multiple solutions exist, the board is rejected and we start over. This step is the most computationally expensive, especially for larger boards.
Path Constraints & Requirements
Grid Filling Requirements
- • Complete Coverage: Every cell must be filled with a path
- • No Crossings: Paths cannot intersect or overlap
- • Continuous Paths: Each path must be a single connected line
- • Endpoint Pairs: Each color must have exactly two endpoints
Validation Checks
- • Region Analysis: Check that empty regions can accommodate remaining paths
- • Isolation Prevention: Ensure no cells become unreachable
- • Path Length Validation: Verify minimum and maximum path lengths
- • Solution Uniqueness: Confirm exactly one valid solution exists
Computational Complexity
The generation process becomes exponentially more complex as board size increases. This is due to the combinatorial explosion of possible path arrangements and the need to verify solution uniqueness.
Generation times vary based on complexity and solution verification requirements. Larger boards require more attempts to find valid configurations.
Generation Demo
In the actual game, boards are generated server-side and cached for instant delivery. The generation process typically takes 50ms to 5 seconds depending on board size and complexity.