# Snake MIP Solver
[](https://github.com/DenHvideDvaerg/snake-mip-solver/actions/workflows/ci.yml)
[](https://codecov.io/gh/DenHvideDvaerg/snake-mip-solver)
[](https://pypi.org/project/snake-mip-solver/)
[](https://pypi.org/project/snake-mip-solver/)
[](https://opensource.org/licenses/MIT)
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
```bash
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 |
|--------|----------|
| <img src="https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/6x6_Easy.png" width="400"> | <img src="https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/6x6_Easy_solution.png" width="400"> |
```python
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 |
|--------|----------|
| <img src="https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/12x12_Evil.png" width="400"> | <img src="https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/12x12_Evil_solution.png" width="400"> |
```python
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
```python
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`:
```bash
python main.py
```
## Testing
The project uses pytest for testing:
```bash
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
**Connectivity Enforcement:** Even with these constraints it is still theoretically possible to have disconnected components in a solution. Therefore, the solver uses an **iterative cutting planes approach** to ensure true connectivity.
See the complete formulation in **[Complete Mathematical Model Documentation](https://github.com/DenHvideDvaerg/snake-mip-solver/blob/main/model.md)**
## License
This project is open source and available under the [MIT License](LICENSE).
Raw data
{
"_id": null,
"home_page": null,
"name": "snake-mip-solver",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "puzzle, solver, mixed-integer-programming, optimization, snake",
"author": "Rasmus \u00d8rnstrup Mikkelsen",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/61/a6/405b53c0674863bccdb4a7dedeee5e2295772f4a95cdafff9b5b066c041a/snake_mip_solver-0.2.0.tar.gz",
"platform": null,
"description": "# Snake MIP Solver\r\n\r\n[](https://github.com/DenHvideDvaerg/snake-mip-solver/actions/workflows/ci.yml)\r\n[](https://codecov.io/gh/DenHvideDvaerg/snake-mip-solver)\r\n[](https://pypi.org/project/snake-mip-solver/)\r\n[](https://pypi.org/project/snake-mip-solver/)\r\n[](https://opensource.org/licenses/MIT)\r\n\r\nA Snake puzzle solver using mathematical programming.\r\n\r\n## Overview\r\n\r\nSnake is a logic puzzle where you must create a single connected path on a grid according to these rules:\r\n\r\n- **Single connected path** - the snake forms one continuous line from start to end cell\r\n- **No self-touching** - the snake body never touches itself, neither orthogonally nor diagonally\r\n- **Row and column constraints** - each row/column must have a specific number of filled cells\r\n - **Missing constraints variant** - supports puzzles where some row/column constraints are unknown (specified as `None`)\r\n\r\nThis solver models the puzzle as a **Mixed Integer Programming (MIP)** problem to find solutions.\r\n\r\n## Installation\r\n\r\n```bash\r\npip install snake-mip-solver\r\n```\r\n\r\n## Requirements\r\n\r\n- Python 3.9+\r\n- Google OR-Tools\r\n- pytest (for testing)\r\n\r\n## Example Puzzles\r\n\r\n### 6x6 Easy Puzzle\r\n\r\nThis 6x6 puzzle demonstrates a straightforward Snake puzzle:\r\n\r\n| Puzzle | Solution |\r\n|--------|----------|\r\n| <img src=\"https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/6x6_Easy.png\" width=\"400\"> | <img src=\"https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/6x6_Easy_solution.png\" width=\"400\"> |\r\n\r\n```python\r\ndef example_6x6_easy():\r\n \"\"\"6x6 easy example\"\"\"\r\n puzzle = SnakePuzzle(\r\n row_sums=[1, 1, 1, 3, 2, 5],\r\n col_sums=[4, 3, 1, 1, 1, 3],\r\n start_cell=(0, 0),\r\n end_cell=(3, 5)\r\n )\r\n return puzzle\r\n```\r\n\r\n### 12x12 Evil Puzzle with Missing Constraints\r\n\r\nThis 12x12 puzzle demonstrates a challenging large-scale puzzle with missing row/column constraints:\r\n\r\n| Puzzle | Solution |\r\n|--------|----------|\r\n| <img src=\"https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/12x12_Evil.png\" width=\"400\"> | <img src=\"https://github.com/DenHvideDvaerg/snake-mip-solver/raw/main/images/12x12_Evil_solution.png\" width=\"400\"> |\r\n\r\n```python\r\ndef example_12x12_evil():\r\n \"\"\"12x12 'Evil' puzzle from https://gridpuzzle.com/snake/evil-12\"\"\"\r\n puzzle = SnakePuzzle(\r\n row_sums=[11, 2, 7, 4, 4, None, None, None, 3, 2, None, 5],\r\n col_sums=[9, 7, None, 2, 5, 6, None, None, 5, None, None, None],\r\n start_cell=(2, 6),\r\n end_cell=(7, 5)\r\n )\r\n return puzzle\r\n```\r\n\r\n## Usage\r\n\r\n```python\r\nfrom snake_mip_solver import SnakePuzzle, SnakeSolver\r\nimport time\r\n\r\ndef solve_puzzle(puzzle, name):\r\n \"\"\"Solve a snake puzzle and display results\"\"\"\r\n print(f\"\\n\" + \"=\"*60)\r\n print(f\"SOLVING {name.upper()}\")\r\n print(\"=\"*60)\r\n \r\n # Create and use the solver\r\n solver = SnakeSolver(puzzle)\r\n \r\n print(\"Solver information:\")\r\n info = solver.get_solver_info()\r\n for key, value in info.items():\r\n print(f\" {key}: {value}\")\r\n \r\n print(\"\\nSolving...\")\r\n start_time = time.time()\r\n solution = solver.solve(verbose=False)\r\n solve_time = time.time() - start_time\r\n \r\n if solution:\r\n print(f\"\\nSolution found in {solve_time:.3f} seconds!\")\r\n print(f\"Solution has {len(solution)} filled cells\")\r\n print(f\"Solution: {sorted(list(solution))}\")\r\n \r\n # Display the board with solution\r\n print(\"\\nPuzzle with solution:\")\r\n print(puzzle.get_board_visualization(solution, show_indices=False))\r\n \r\n # Validate solution\r\n if puzzle.is_valid_solution(solution):\r\n print(\"\u2705 Solution is valid!\")\r\n else:\r\n print(\"\u274c Solution validation failed!\")\r\n else:\r\n print(f\"\\nNo solution found (took {solve_time:.3f} seconds)\")\r\n\r\n# Load and solve example puzzles\r\npuzzle_6x6 = example_6x6_easy()\r\nsolve_puzzle(puzzle_6x6, \"6x6 Easy\")\r\n\r\npuzzle_12x12 = example_12x12_evil()\r\nsolve_puzzle(puzzle_12x12, \"12x12 Evil\")\r\n```\r\n\r\n### Output\r\n\r\n```\r\n============================================================\r\nSOLVING 6X6 EASY\r\n============================================================\r\nSolver information:\r\n solver_type: SCIP 9.2.2 [LP solver: SoPlex 7.1.3]\r\n num_variables: 36\r\n num_constraints: 159\r\n puzzle_size: 6x6\r\n start_cell: (0, 0)\r\n end_cell: (3, 5)\r\n\r\nSolving...\r\n\r\nSolution found in 0.002 seconds!\r\nSolution has 13 filled cells\r\nSolution: [(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)]\r\n\r\nPuzzle with solution:\r\n 4 3 1 1 1 3\r\n1 S _ _ _ _ _\r\n1 x _ _ _ _ _\r\n1 x _ _ _ _ _\r\n3 x x _ _ _ E\r\n2 _ x _ _ _ x\r\n5 _ x x x x x\r\n\u2705 Solution is valid!\r\n\r\n============================================================\r\nSOLVING 12X12 EVIL\r\n============================================================\r\nSolver information:\r\n solver_type: SCIP 9.2.2 [LP solver: SoPlex 7.1.3]\r\n num_variables: 144\r\n num_constraints: 665\r\n puzzle_size: 12x12\r\n start_cell: (2, 6)\r\n end_cell: (7, 5)\r\n\r\nSolving...\r\n\r\nSolution found in 0.255 seconds!\r\nSolution has 49 filled cells\r\nSolution: [(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)]\r\n\r\nPuzzle with solution:\r\n 9 7 ? 2 5 6 ? ? 5 ? ? ?\r\n11 _ x x x x x x x x x x x\r\n 2 _ x _ _ _ _ _ _ _ _ _ x\r\n 7 x x _ _ _ _ S _ x x x x\r\n 4 x _ _ _ _ x x _ x _ _ _\r\n 4 x x _ _ _ x _ _ x _ _ _\r\n ? _ x _ _ _ x x x x _ _ _\r\n ? x x _ _ _ _ _ _ _ _ _ _\r\n ? x _ _ _ _ E _ _ _ _ _ _\r\n 3 x _ _ _ x x _ _ _ _ _ _\r\n 2 x _ _ _ x _ _ _ _ _ _ _\r\n ? x _ _ _ x _ _ _ _ _ _ _\r\n 5 x x x x x _ _ _ _ _ _ _\r\n\u2705 Solution is valid!\r\n```\r\n\r\n### Running the example\r\n\r\nThe repository includes a complete example in `main.py`:\r\n\r\n```bash\r\npython main.py\r\n```\r\n\r\n## Testing\r\n\r\nThe project uses pytest for testing:\r\n\r\n```bash\r\npytest\r\npytest --cov=snake_mip_solver # Run with coverage\r\n```\r\n\r\n## Mathematical Model\r\n\r\nThe solver uses **Mixed Integer Programming (MIP)** to model the puzzle constraints. Google OR-Tools provides the optimization framework, with SCIP as the default solver.\r\n\r\nThe mathematical formulation includes six types of constraints:\r\n1. **Start and End Cell Constraints** - fixing the path endpoints\r\n2. **Row Sum Constraints** - ensuring correct number of cells per row\r\n3. **Column Sum Constraints** - ensuring correct number of cells per column \r\n4. **Snake Path Connectivity Constraints** - forming a single connected path\r\n5. **Diagonal Non-Touching Constraints** - preventing diagonal self-contact\r\n6. **No 2\u00d72 Block Constraints** - preventing disconnected filled blocks\r\n\r\n**Connectivity Enforcement:** Even with these constraints it is still theoretically possible to have disconnected components in a solution. Therefore, the solver uses an **iterative cutting planes approach** to ensure true connectivity.\r\n\r\nSee the complete formulation in **[Complete Mathematical Model Documentation](https://github.com/DenHvideDvaerg/snake-mip-solver/blob/main/model.md)**\r\n\r\n## License\r\n\r\nThis project is open source and available under the [MIT License](LICENSE).\r\n",
"bugtrack_url": null,
"license": null,
"summary": "A Snake puzzle solver using Mixed Integer Programming (MIP)",
"version": "0.2.0",
"project_urls": {
"Bug Reports": "https://github.com/DenHvideDvaerg/snake-mip-solver/issues",
"Documentation": "https://github.com/DenHvideDvaerg/snake-mip-solver/blob/main/model.md",
"Homepage": "https://github.com/DenHvideDvaerg/snake-mip-solver",
"Source": "https://github.com/DenHvideDvaerg/snake-mip-solver"
},
"split_keywords": [
"puzzle",
" solver",
" mixed-integer-programming",
" optimization",
" snake"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "0f1e79cbf063c97d49319ea95d169b76e4ab00070f92f8bfa6c58241e1ca7db4",
"md5": "7f541d47aac09b0444e5ea3e22182fd0",
"sha256": "3a78248a55d456a60f70e67f109a9ce443bf01930ec71a015a20406c05407e8a"
},
"downloads": -1,
"filename": "snake_mip_solver-0.2.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "7f541d47aac09b0444e5ea3e22182fd0",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 12496,
"upload_time": "2025-09-03T09:26:03",
"upload_time_iso_8601": "2025-09-03T09:26:03.317562Z",
"url": "https://files.pythonhosted.org/packages/0f/1e/79cbf063c97d49319ea95d169b76e4ab00070f92f8bfa6c58241e1ca7db4/snake_mip_solver-0.2.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "61a6405b53c0674863bccdb4a7dedeee5e2295772f4a95cdafff9b5b066c041a",
"md5": "f05fb9674910bbfd11f9755c7c7e718d",
"sha256": "1f1d6a0e61d6cceaa462ea618ad7d9a1975da31b3d4a838c386fb57ac6fb69c1"
},
"downloads": -1,
"filename": "snake_mip_solver-0.2.0.tar.gz",
"has_sig": false,
"md5_digest": "f05fb9674910bbfd11f9755c7c7e718d",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 17734,
"upload_time": "2025-09-03T09:26:04",
"upload_time_iso_8601": "2025-09-03T09:26:04.165722Z",
"url": "https://files.pythonhosted.org/packages/61/a6/405b53c0674863bccdb4a7dedeee5e2295772f4a95cdafff9b5b066c041a/snake_mip_solver-0.2.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-09-03 09:26:04",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "DenHvideDvaerg",
"github_project": "snake-mip-solver",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "ortools",
"specs": []
},
{
"name": "pytest",
"specs": []
},
{
"name": "pytest-cov",
"specs": []
}
],
"lcname": "snake-mip-solver"
}
JSON
