snake-mip-solver 0.1.0

A Snake puzzle solver using Mixed Integer Programming (MIP)

Snake MIP Solver

A Snake puzzle solver using mathematical programming.

Overview

Snake is a logic puzzle where you must create a single connected path on a grid according to these rules:

• Single connected path - the snake forms one continuous line from start to end cell
• No self-touching - the snake body never touches itself, neither orthogonally nor diagonally
• Row and column constraints - each row/column must have a specific number of filled cells
  • Missing constraints variant - supports puzzles where some row/column constraints are unknown (specified as None)

This solver models the puzzle as a Mixed Integer Programming (MIP) problem to find solutions.

Installation

pip install snake-mip-solver

Requirements

• Python 3.9+
• Google OR-Tools
• pytest (for testing)

Example Puzzles

6x6 Easy Puzzle

This 6x6 puzzle demonstrates a straightforward Snake puzzle:

Puzzle	Solution

def example_6x6_easy():
    """6x6 easy example"""
    puzzle = SnakePuzzle(
        row_sums=[1, 1, 1, 3, 2, 5],
        col_sums=[4, 3, 1, 1, 1, 3],
        start_cell=(0, 0),
        end_cell=(3, 5)
    )
    return puzzle

12x12 Evil Puzzle with Missing Constraints

This 12x12 puzzle demonstrates a challenging large-scale puzzle with missing row/column constraints:

Puzzle	Solution

def example_12x12_evil():
    """12x12 'Evil' puzzle from https://gridpuzzle.com/snake/evil-12"""
    puzzle = SnakePuzzle(
        row_sums=[11, 2, 7, 4, 4, None, None, None, 3, 2, None, 5],
        col_sums=[9, 7, None, 2, 5, 6, None, None, 5, None, None, None],
        start_cell=(2, 6),
        end_cell=(7, 5)
    )
    return puzzle

Usage

from snake_mip_solver import SnakePuzzle, SnakeSolver
import time

def solve_puzzle(puzzle, name):
    """Solve a snake puzzle and display results"""
    print(f"\n" + "="*60)
    print(f"SOLVING {name.upper()}")
    print("="*60)
    
    # Create and use the solver
    solver = SnakeSolver(puzzle)
    
    print("Solver information:")
    info = solver.get_solver_info()
    for key, value in info.items():
        print(f"  {key}: {value}")
    
    print("\nSolving...")
    start_time = time.time()
    solution = solver.solve(verbose=False)
    solve_time = time.time() - start_time
    
    if solution:
        print(f"\nSolution found in {solve_time:.3f} seconds!")
        print(f"Solution has {len(solution)} filled cells")
        print(f"Solution: {sorted(list(solution))}")
        
        # Display the board with solution
        print("\nPuzzle with solution:")
        print(puzzle.get_board_visualization(solution, show_indices=False))
        
        # Validate solution
        if puzzle.is_valid_solution(solution):
            print("✅ Solution is valid!")
        else:
            print("❌ Solution validation failed!")
    else:
        print(f"\nNo solution found (took {solve_time:.3f} seconds)")

# Load and solve example puzzles
puzzle_6x6 = example_6x6_easy()
solve_puzzle(puzzle_6x6, "6x6 Easy")

puzzle_12x12 = example_12x12_evil()
solve_puzzle(puzzle_12x12, "12x12 Evil")

Output

============================================================
SOLVING 6X6 EASY
============================================================
Solver information:
  solver_type: SCIP 9.2.2 [LP solver: SoPlex 7.1.3]
  num_variables: 36
  num_constraints: 159
  puzzle_size: 6x6
  start_cell: (0, 0)
  end_cell: (3, 5)

Solving...

Solution found in 0.002 seconds!
Solution has 13 filled cells
Solution: [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 5), (4, 1), (4, 5), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]

Puzzle with solution:
  4 3 1 1 1 3
1 S _ _ _ _ _
1 x _ _ _ _ _
1 x _ _ _ _ _
3 x x _ _ _ E
2 _ x _ _ _ x
5 _ x x x x x
✅ Solution is valid!

============================================================
SOLVING 12X12 EVIL
============================================================
Solver information:
  solver_type: SCIP 9.2.2 [LP solver: SoPlex 7.1.3]
  num_variables: 144
  num_constraints: 665
  puzzle_size: 12x12
  start_cell: (2, 6)
  end_cell: (7, 5)

Solving...

Solution found in 0.255 seconds!
Solution has 49 filled cells
Solution: [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11), (1, 1), (1, 11), (2, 0), (2, 1), (2, 6), (2, 8), (2, 9), (2, 10), (2, 11), (3, 0), (3, 5), (3, 6), (3, 8), (4, 0), (4, 1), (4, 5), (4, 8), (5, 1), (5, 5), (5, 6), (5, 7), (5, 8), (6, 0), (6, 1), (7, 0), (7, 5), (8, 0), (8, 4), (8, 5), (9, 0), (9, 4), (10, 0), (10, 4), (11, 0), (11, 1), (11, 2), (11, 3), (11, 4)]

Puzzle with solution:
   9 7 ? 2 5 6 ? ? 5 ? ? ?
11 _ x x x x x x x x x x x
 2 _ x _ _ _ _ _ _ _ _ _ x
 7 x x _ _ _ _ S _ x x x x
 4 x _ _ _ _ x x _ x _ _ _
 4 x x _ _ _ x _ _ x _ _ _
 ? _ x _ _ _ x x x x _ _ _
 ? x x _ _ _ _ _ _ _ _ _ _
 ? x _ _ _ _ E _ _ _ _ _ _
 3 x _ _ _ x x _ _ _ _ _ _
 2 x _ _ _ x _ _ _ _ _ _ _
 ? x _ _ _ x _ _ _ _ _ _ _
 5 x x x x x _ _ _ _ _ _ _
✅ Solution is valid!

Running the example

The repository includes a complete example in main.py:

python main.py

Testing

The project uses pytest for testing:

pytest
pytest --cov=snake_mip_solver # Run with coverage

Mathematical Model

The solver uses Mixed Integer Programming (MIP) to model the puzzle constraints. Google OR-Tools provides the optimization framework, with SCIP as the default solver.

The mathematical formulation includes six types of constraints:

1. Start and End Cell Constraints - fixing the path endpoints
2. Row Sum Constraints - ensuring correct number of cells per row
3. Column Sum Constraints - ensuring correct number of cells per column
4. Snake Path Connectivity Constraints - forming a single connected path
5. Diagonal Non-Touching Constraints - preventing diagonal self-contact
6. No 2×2 Block Constraints - preventing disconnected filled blocks

See the complete formulation in Complete Mathematical Model Documentation

License

This project is open source and available under the MIT License.