# Tents and Trees MIP Solver
[](https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver/actions/workflows/CI.yml)
[](https://codecov.io/gh/DenHvideDvaerg/tents-and-trees-mip-solver)
<!-- [](https://pypi.org/project/tents-and-trees-mip-solver/) -->
<!-- [](https://pypi.org/project/tents-and-trees-mip-solver/) -->
[](https://opensource.org/licenses/MIT)
A Tents and Trees puzzle solver using mathematical programming.
## Overview
Tents and Trees is a logic puzzle where you must place tents on a grid according to specific rules:
- **Each tree must have exactly one adjacent tent** (horizontally or vertically)
- **Each tent must be adjacent to exactly one tree**
- **Tents cannot touch each other** (even diagonally)
- **Row and column constraints** specify how many tents must be in each row/column
This solver models the puzzle as a **Mixed Integer Programming (MIP)** problem to find solutions.
## Installation
```bash
pip install tents-and-trees-mip-solver
```
## Requirements
- Python 3.9+
- Google OR-Tools
- pytest (for testing)
## Usage
```python
from tents_and_trees_mip_solver import TentsAndTreesPuzzle, TentsAndTreesSolver
# Define a puzzle
puzzle = TentsAndTreesPuzzle(
row_sums=[1, 1, 0, 2, 1], # Tents per row
col_sums=[2, 0, 1, 1, 1], # Tents per column
tree_positions={(1,1), (1,3), (3,0), (3,1), (4,4)} # Tree locations
)
# Display the puzzle
print("Puzzle:")
print(puzzle.display_board())
# Solve the puzzle
solver = TentsAndTreesSolver(puzzle)
solution = solver.solve()
if solution:
print(f"\nSolution found! Tent positions: {solution}")
# Validate the solution
is_valid, errors = puzzle.validate_solution(solution)
print(f"Solution is valid: {is_valid}")
# Display the solved board
print("\nSolved puzzle:")
print(puzzle.display_board(tent_positions=solution))
# Get solver information
info = solver.get_solver_info()
print(f"\nModel consists of {info['variables']} variables and {info['constraints']} constraints")
else:
print("No solution exists")
```
### Output
```
Puzzle:
2 0 1 1 1
1 _ _ _ _ _
1 _ T _ T _
0 _ _ _ _ _
2 T T _ _ _
1 _ _ _ _ T
Solution found! Tent positions: {(4, 0), (3, 4), (0, 3), (1, 0), (3, 2)}
Solution is valid: True
Solved puzzle:
2 0 1 1 1
1 _ _ _ @ _
1 @ T _ T _
0 _ _ _ _ _
2 T T @ _ @
1 @ _ _ _ T
Model consists of 13 variables and 36 constraints
Legend: T=Tree, @=Tent, _=Empty
```
## Testing
The project uses pytest for testing:
```bash
pytest # Run all tests
pytest --cov=puzzle --cov=solver # Run with coverage
```
## Algorithm Details
The solver uses **Mixed Integer Programming (MIP)** to model the puzzle with:
- **Binary decision variables** for each potential tent position
- **Seven constraint types** ensuring all puzzle rules are satisfied:
1. Tent-tree balance (equal counts)
2. Tree adjacency (each tree has ≥1 adjacent tent)
3. Tent separation (no adjacent tents)
4. Row sum constraints
5. Column sum constraints
6. Tree group balance constraints
7. Unshared tile constraints
**Solver Backend**: Uses Google OR-Tools with SCIP optimizer by default.
**Mathematical Model**: See the complete formulation in **[Mathematical Model Documentation](https://github.com/DenHvideDvaerg/tents-and-trees-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": "tents-and-trees-mip-solver",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.9",
"maintainer_email": null,
"keywords": "puzzle, solver, mixed-integer-programming, optimization, tents-and-trees",
"author": "Rasmus \u00d8rnstrup Mikkelsen",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/9c/28/7d86e0de09e1321d00b65fe7b3b7aa7402076547af292356df0dbc7a6501/tents_and_trees_mip_solver-0.1.1.tar.gz",
"platform": null,
"description": "# Tents and Trees MIP Solver\r\n\r\n[](https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver/actions/workflows/CI.yml)\r\n[](https://codecov.io/gh/DenHvideDvaerg/tents-and-trees-mip-solver)\r\n<!-- [](https://pypi.org/project/tents-and-trees-mip-solver/) -->\r\n<!-- [](https://pypi.org/project/tents-and-trees-mip-solver/) -->\r\n[](https://opensource.org/licenses/MIT)\r\n\r\nA Tents and Trees puzzle solver using mathematical programming.\r\n\r\n## Overview\r\n\r\nTents and Trees is a logic puzzle where you must place tents on a grid according to specific rules:\r\n\r\n- **Each tree must have exactly one adjacent tent** (horizontally or vertically)\r\n- **Each tent must be adjacent to exactly one tree** \r\n- **Tents cannot touch each other** (even diagonally)\r\n- **Row and column constraints** specify how many tents must be in each row/column\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 tents-and-trees-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## Usage\r\n\r\n```python\r\nfrom tents_and_trees_mip_solver import TentsAndTreesPuzzle, TentsAndTreesSolver\r\n\r\n# Define a puzzle\r\npuzzle = TentsAndTreesPuzzle(\r\n row_sums=[1, 1, 0, 2, 1], # Tents per row\r\n col_sums=[2, 0, 1, 1, 1], # Tents per column \r\n tree_positions={(1,1), (1,3), (3,0), (3,1), (4,4)} # Tree locations\r\n)\r\n\r\n# Display the puzzle\r\nprint(\"Puzzle:\")\r\nprint(puzzle.display_board())\r\n\r\n# Solve the puzzle\r\nsolver = TentsAndTreesSolver(puzzle)\r\nsolution = solver.solve()\r\n\r\nif solution:\r\n print(f\"\\nSolution found! Tent positions: {solution}\")\r\n \r\n # Validate the solution\r\n is_valid, errors = puzzle.validate_solution(solution)\r\n print(f\"Solution is valid: {is_valid}\")\r\n \r\n # Display the solved board\r\n print(\"\\nSolved puzzle:\")\r\n print(puzzle.display_board(tent_positions=solution))\r\n \r\n # Get solver information\r\n info = solver.get_solver_info()\r\n print(f\"\\nModel consists of {info['variables']} variables and {info['constraints']} constraints\")\r\nelse:\r\n print(\"No solution exists\")\r\n```\r\n\r\n### Output\r\n\r\n```\r\nPuzzle:\r\n 2 0 1 1 1\r\n1 _ _ _ _ _\r\n1 _ T _ T _\r\n0 _ _ _ _ _\r\n2 T T _ _ _\r\n1 _ _ _ _ T\r\n\r\nSolution found! Tent positions: {(4, 0), (3, 4), (0, 3), (1, 0), (3, 2)}\r\nSolution is valid: True\r\n\r\nSolved puzzle:\r\n 2 0 1 1 1\r\n1 _ _ _ @ _\r\n1 @ T _ T _\r\n0 _ _ _ _ _\r\n2 T T @ _ @\r\n1 @ _ _ _ T\r\n\r\nModel consists of 13 variables and 36 constraints\r\n\r\nLegend: T=Tree, @=Tent, _=Empty\r\n```\r\n\r\n## Testing\r\n\r\nThe project uses pytest for testing:\r\n\r\n```bash\r\npytest # Run all tests\r\npytest --cov=puzzle --cov=solver # Run with coverage\r\n```\r\n\r\n## Algorithm Details\r\n\r\nThe solver uses **Mixed Integer Programming (MIP)** to model the puzzle with:\r\n\r\n- **Binary decision variables** for each potential tent position\r\n- **Seven constraint types** ensuring all puzzle rules are satisfied:\r\n 1. Tent-tree balance (equal counts)\r\n 2. Tree adjacency (each tree has \u22651 adjacent tent) \r\n 3. Tent separation (no adjacent tents)\r\n 4. Row sum constraints\r\n 5. Column sum constraints\r\n 6. Tree group balance constraints\r\n 7. Unshared tile constraints\r\n\r\n**Solver Backend**: Uses Google OR-Tools with SCIP optimizer by default.\r\n\r\n**Mathematical Model**: See the complete formulation in **[Mathematical Model Documentation](https://github.com/DenHvideDvaerg/tents-and-trees-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 Tents and Trees puzzle solver using Mixed Integer Programming (MIP)",
"version": "0.1.1",
"project_urls": {
"Bug Reports": "https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver/issues",
"Documentation": "https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver/blob/main/model.md",
"Homepage": "https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver",
"Source": "https://github.com/DenHvideDvaerg/tents-and-trees-mip-solver"
},
"split_keywords": [
"puzzle",
" solver",
" mixed-integer-programming",
" optimization",
" tents-and-trees"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "4fcca598341653a58eb4767dc99c6af6d23188d3eb33e349dcfb17d8b2aff1ed",
"md5": "d4db8e598ab9faf864c29f6eb6d592d3",
"sha256": "ea1d42abd5284324a8a8f364a855acf1cbefea29d7e3011aeb9f11809deefc85"
},
"downloads": -1,
"filename": "tents_and_trees_mip_solver-0.1.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "d4db8e598ab9faf864c29f6eb6d592d3",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.9",
"size": 10219,
"upload_time": "2025-08-17T14:02:05",
"upload_time_iso_8601": "2025-08-17T14:02:05.105349Z",
"url": "https://files.pythonhosted.org/packages/4f/cc/a598341653a58eb4767dc99c6af6d23188d3eb33e349dcfb17d8b2aff1ed/tents_and_trees_mip_solver-0.1.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "9c287d86e0de09e1321d00b65fe7b3b7aa7402076547af292356df0dbc7a6501",
"md5": "a6b7a760c173539c825384ef093e7a9a",
"sha256": "15d06fed38beddc48d76d13ce098741285a89fffe805f2d475248dfa787fef9a"
},
"downloads": -1,
"filename": "tents_and_trees_mip_solver-0.1.1.tar.gz",
"has_sig": false,
"md5_digest": "a6b7a760c173539c825384ef093e7a9a",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.9",
"size": 13214,
"upload_time": "2025-08-17T14:02:06",
"upload_time_iso_8601": "2025-08-17T14:02:06.676862Z",
"url": "https://files.pythonhosted.org/packages/9c/28/7d86e0de09e1321d00b65fe7b3b7aa7402076547af292356df0dbc7a6501/tents_and_trees_mip_solver-0.1.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2025-08-17 14:02:06",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "DenHvideDvaerg",
"github_project": "tents-and-trees-mip-solver",
"travis_ci": false,
"coveralls": true,
"github_actions": true,
"requirements": [
{
"name": "ortools",
"specs": []
},
{
"name": "pytest",
"specs": []
},
{
"name": "pytest-cov",
"specs": []
}
],
"lcname": "tents-and-trees-mip-solver"
}
JSON
