Efficient solvers for countless (90+) types of puzzles (like Sudoku, Minesweeper, etc.) with a simple python API.
Project description
Python Puzzle Solver
Solve countless (90+) classical logic puzzles automatically in Python.
Can also tell you if a partial puzzle has a single unique solution or not (and retrieves all possible solutions).
Install
pip install multi-puzzle-solver
🕹️ Puzzle Gallery
These are all the puzzles that are implemented in this repo.
Click on any of them to go to that Puzzle's README.
Introduction
The aim of this repo is to provide very efficient solvers (i.e. not brute force solvers) for countless (90+) popular pencil logic puzzles like Nonograms, Sudoku, Minesweeper, and many more lesser known ones.
If you happen to have a puzzle similar to the ones listed below and want to solve it (or see how many potential solutions a partially covered board has), then this repo is perfect for you.
The simple use-case of this repo is if you want to solve a puzzle given the state of the board. But the other interesting use-cases is if you want to check if removing a clue would still result in a unique solution or would make the puzzle ambiguous and have multiple solutions.
Why? There are countless python packages that can solve the popular puzzles below, so a valid question to ask is why would I want to use this package and why did you create it?. The answer is that there are multiple problems with most of those packages which this package solves which are:
- Sophisticated solvers: A lot of available online solvers are incredibly inefficient as they implement naive algorithms that brute force and backtrack through all possible solutions. This package solves that issue as all the solvers included here never use naive algorithms and instead use a very efficient CP-SAT solver which is a more sophisticated solver than any one person could possibly write.
- Numerous puzzles: Most of the available python solvers are only designed for a single type of puzzle and each one requires a different way to encode the input and extract the solution. This package solves both those issues as this package provides solvers for many puzzles all with a similar interface that encodes the input and extracts the solution in a similar way.
- Esoteric puzzles: Most packages you can find online are only designed for popular puzzles. This package partially solves this issue by providing solvers for many puzzles. I'm open to suggestions for implementing solvers for more puzzles.
- All possible solutions: The available solvers often lack uniqueness checks and simply stop at the first possible solution without verifying uniqueness or completeness. This package supports checking whether puzzles are uniquely solvable, ambiguous, or unsolvable for all the puzzles.
Play most of the puzzles online in the website listed in the Puzzle List.
Almost all the solvers in this repo use the CP-SAT solver from Google OR-Tools.
Quick Start
Install
pip install multi-puzzle-solver
Use:
from puzzle_solver import nonograms_solver as solver
top_numbers = [[8, 2], [5, 4], [2, 1, 4], [2, 4], [2, 1, 4], [2, 5], [2, 8], [3, 2], [1, 6], [1, 9], [1, 6, 1], [1, 5, 3], [3, 2, 1], [4, 2], [1, 5]]
side_numbers = [[7, 3], [7, 1, 1], [2, 3], [2, 3], [3, 2], [1, 1, 1, 1, 2], [1, 6, 1], [1, 9], [9], [2, 4], [8], [11], [7, 1, 1], [4, 3], [3, 2]]
binst = solver.Board(top=top_numbers, side=side_numbers)
solutions = binst.solve_and_print()
Output:
Solution found
[['B' 'B' 'B' 'B' 'B' 'B' 'B' ' ' 'B' 'B' 'B' ' ' ' ' ' ' ' ']
['B' 'B' 'B' 'B' 'B' 'B' 'B' ' ' ' ' ' ' ' ' ' ' 'B' ' ' 'B']
['B' 'B' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'B' 'B' 'B' ' ']
['B' 'B' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'B' 'B' 'B']
['B' 'B' 'B' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'B' 'B']
['B' ' ' ' ' ' ' 'B' ' ' 'B' ' ' ' ' 'B' ' ' ' ' ' ' 'B' 'B']
['B' ' ' ' ' ' ' ' ' ' ' 'B' 'B' 'B' 'B' 'B' 'B' ' ' ' ' 'B']
['B' ' ' ' ' ' ' ' ' ' ' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B']
[' ' ' ' ' ' ' ' ' ' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' ' ']
[' ' ' ' ' ' ' ' ' ' 'B' 'B' ' ' 'B' 'B' 'B' 'B' ' ' ' ' ' ']
[' ' ' ' ' ' ' ' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' ' ' ' ' ' ']
['B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' 'B' ' ' ' ' ' ' ' ']
['B' 'B' 'B' 'B' 'B' 'B' 'B' ' ' ' ' 'B' ' ' 'B' ' ' ' ' ' ']
[' ' 'B' 'B' 'B' 'B' ' ' ' ' ' ' ' ' 'B' 'B' 'B' ' ' ' ' ' ']
[' ' 'B' 'B' 'B' ' ' ' ' ' ' ' ' ' ' ' ' ' ' 'B' 'B' ' ' ' ']]
Solutions found: 1
status: OPTIMAL
Time taken: 0.04 seconds
(Note: Printing can be turned off by setting verbose=False)
Table of Contents
- Python Puzzle Solver
- Puzzles
- Sudoku (Puzzle Type #2)
- Filling (Puzzle Type #7)
- Singles (Puzzle Type #10)
- Range (Puzzle Type #13)
- Tracks (Puzzle Type #16)
- Pearl (Puzzle Type #19)
- Inertia (Puzzle Type #21)
- Guess (Puzzle Type #22)
- Chess Melee (Puzzle Type #25)
- Aquarium (Puzzle Type #27)
- Stitches (Puzzle Type #28)
- Battleships (Puzzle Type #29)
- Star Battle Shapeless (Puzzle Type #32)
- Lits (Puzzle Type #33)
- Galaxies (Puzzle Type #35)
- Slitherlink (Puzzle Type #39)
- Rectangles (Puzzle Type #42)
- Palisade (Puzzle Type #43)
- Heyawake (Puzzle Type #46)
- Shingoki (Puzzle Type #47)
- Shakashaka (Puzzle Type #50)
- Sudoku Killer (Puzzle Type #53)
- Flood It (Puzzle Type #54)
- Pipes (Puzzle Type #55)
- Connect the Dots (Puzzle Type #56)
- Nonograms Colored (Puzzle Type #57)
- Split Ends (Puzzle Type #60)
- N-Queens (Puzzle Type #61)
- Suguru (Puzzle Type #66)
- Yajilin (Puzzle Type #68)
- NumberMaze (Puzzle Type #69)
- Link-a-Pix (Puzzle Type #70)
- Vectors (Puzzle Type #72)
- Vermicelli (Puzzle Type #73)
- Cow and Cactus (Puzzle Type #74)
- Ripple Effect (Puzzle Type #76)
- Area 51 (Puzzle Type #77)
- All other Puzzles
- Other
Puzzles
Each puzzle in this repo have a simple example input board followed by the code to utilize this package and solve the puzzle, followed by the scripts output, and finally the solved puzzle.
Some of the puzzles implemented are shown below.
Sudoku (Puzzle Type #2)
Also known as Number Place or Solo.
The code can:
- Solve arbitrarily sized valid board sizes, thus can be used to solve:
- Hex Sudoku (a 16x16 variant)
- Kidoku (a kid-friendly sudoku variant)
- Solve the "Sandwich" sudoku variant using the optional parameter
sandwich={'side': [...], 'bottom': [...]} - Solve the "Sudoku-X" variant using the optional parameter
unique_diagonal=True
Rules
You have a square grid, which is divided into as many equally sized sub-blocks as the grid has rows. Each square must be filled in with a digit from 1 to the size of the grid, in such a way that
- every row contains only one occurrence of each digit
- every column contains only one occurrence of each digit
- every block contains only one occurrence of each digit.
You are given some of the numbers as clues; your aim is to place the rest of the numbers correctly.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import sudoku_solver as solver
board = np.array([
[' ', '7', '5', '4', '9', '1', 'c', 'e', 'd', 'f', ' ', ' ', '2', ' ', '3', ' '],
[' ', ' ', ' ', ' ', 'f', 'a', ' ', ' ', ' ', '6', ' ', 'c', ' ', ' ', '8', 'b'],
[' ', ' ', '1', ' ', ' ', '6', ' ', ' ', ' ', '9', ' ', ' ', ' ', 'g', ' ', 'd'],
[' ', '6', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '5', 'g', 'c', '7', ' ', ' '],
['4', 'a', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '9', ' ', ' ', ' ', ' '],
[' ', 'g', 'f', ' ', 'e', ' ', ' ', '5', '4', ' ', ' ', '1', ' ', '9', ' ', '8'],
[' ', ' ', ' ', ' ', 'a', '3', 'b', '7', 'c', 'g', ' ', '6', ' ', ' ', ' ', '4'],
[' ', 'b', ' ', '7', ' ', ' ', ' ', ' ', 'f', ' ', '3', ' ', ' ', 'a', ' ', '6'],
['2', ' ', 'a', ' ', ' ', 'c', ' ', '1', ' ', ' ', ' ', ' ', '7', ' ', '6', ' '],
['8', ' ', ' ', ' ', '3', ' ', 'e', 'f', '7', '5', 'c', 'd', ' ', ' ', ' ', ' '],
['9', ' ', '3', ' ', '7', ' ', ' ', 'a', '6', ' ', ' ', '2', ' ', 'b', '1', ' '],
[' ', ' ', ' ', ' ', '4', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'e', 'f'],
[' ', ' ', 'g', 'd', '2', '9', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' '],
['a', ' ', 'b', ' ', ' ', ' ', '5', ' ', ' ', ' ', 'd', ' ', ' ', '8', ' ', ' '],
['e', '8', ' ', ' ', '1', ' ', '4', ' ', ' ', ' ', '6', '7', ' ', ' ', ' ', ' '],
[' ', '3', ' ', '9', ' ', ' ', 'f', '8', 'a', 'e', 'g', '5', 'b', 'c', 'd', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
assert len(solutions) == 1, f'unique solutions != 1, == {len(solutions)}'
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│ g │ 7 │ 5 │ 4 │ 9 │ 1 │ c │ e │ d │ f │ b │ 8 │ 2 │ 6 │ 3 │ a │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ 3 │ 9 │ d │ e │ f │ a │ 7 │ g │ 2 │ 6 │ 4 │ c │ 5 │ 1 │ 8 │ b │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│ b │ c │ 1 │ 8 │ 5 │ 6 │ 3 │ 2 │ e │ 9 │ 7 │ a │ 4 │ g │ f │ d │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│ f │ 6 │ 2 │ a │ b │ 8 │ d │ 4 │ 1 │ 3 │ 5 │ g │ c │ 7 │ 9 │ e │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│ 4 │ a │ e │ 3 │ 8 │ f │ 1 │ 6 │ 5 │ b │ 2 │ 9 │ g │ d │ c │ 7 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ 6 │ g │ f │ c │ e │ d │ 2 │ 5 │ 4 │ 7 │ a │ 1 │ 3 │ 9 │ b │ 8 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│ d │ 1 │ 9 │ 2 │ a │ 3 │ b │ 7 │ c │ g │ 8 │ 6 │ e │ f │ 5 │ 4 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ 5 │ b │ 8 │ 7 │ g │ 4 │ 9 │ c │ f │ d │ 3 │ e │ 1 │ a │ 2 │ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│ 2 │ e │ a │ b │ d │ c │ g │ 1 │ 3 │ 8 │ 9 │ f │ 7 │ 4 │ 6 │ 5 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
9│ 8 │ 4 │ 6 │ 1 │ 3 │ b │ e │ f │ 7 │ 5 │ c │ d │ a │ 2 │ g │ 9 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
10│ 9 │ f │ 3 │ g │ 7 │ 5 │ 8 │ a │ 6 │ 4 │ e │ 2 │ d │ b │ 1 │ c │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
11│ c │ d │ 7 │ 5 │ 4 │ 2 │ 6 │ 9 │ g │ a │ 1 │ b │ 8 │ 3 │ e │ f │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
12│ 7 │ 5 │ g │ d │ 2 │ 9 │ a │ b │ 8 │ c │ f │ 3 │ 6 │ e │ 4 │ 1 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
13│ a │ 2 │ b │ 6 │ c │ e │ 5 │ 3 │ 9 │ 1 │ d │ 4 │ f │ 8 │ 7 │ g │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
14│ e │ 8 │ c │ f │ 1 │ g │ 4 │ d │ b │ 2 │ 6 │ 7 │ 9 │ 5 │ a │ 3 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
15│ 1 │ 3 │ 4 │ 9 │ 6 │ 7 │ f │ 8 │ a │ e │ g │ 5 │ b │ c │ d │ 2 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.04 seconds
Solved puzzle
Filling (Puzzle Type #7)
Also known as Fillomino
Rules
You have a grid of squares, some of which contain digits, and the rest of which are empty. Your job is to fill in digits in the empty squares, in such a way that each connected region of squares all containing the same digit has an area equal to that digit.
(‘Connected region’, for the purposes of this game, does not count diagonally separated squares as adjacent.)
For example, it follows that no square can contain a zero, and that two adjacent squares can not both contain a one. No region has an area greater than 9 (because then its area would not be a single digit).
Note: It may take a few seconds for the model to be built.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import filling_solver as solver
board = np.array([
[' ', '4', '2', ' ', ' ', '2', ' '],
[' ', ' ', '7', ' ', ' ', '3', ' '],
[' ', ' ', ' ', ' ', '4', ' ', '3'],
[' ', '6', '6', ' ', '3', ' ', ' '],
[' ', '7', ' ', '6', '4', '5', ' '],
[' ', '6', ' ', ' ', ' ', ' ', '4'],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6
┌───────┬───────┬───┬───────┐
0│ 4 4 │ 2 2 │ 4 │ 2 2 │
│ ├───┬───┘ ├───────┤
1│ 4 4 │ 7 │ 4 4 │ 3 3 │
├───────┘ ├───┐ ├───┐ │
2│ 7 7 7 │ 3 │ 4 │ 5 │ 3 │
│ ┌───────┤ └───┤ └───┤
3│ 7 │ 6 6 │ 3 3 │ 5 5 │
│ └───┐ └───┬───┤ │
4│ 7 7 │ 6 6 │ 4 │ 5 5 │
├───┬───┘ ┌───┤ └───────┤
5│ 1 │ 6 6 │ 1 │ 4 4 4 │
└───┴───────┴───┴───────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.15 seconds
Solved puzzle
Singles (Puzzle Type #10)
Also known as Hitori.
You have a grid of white squares, all of which contain numbers. Your task is to colour some of the squares black (removing the number) so as to satisfy all of the following conditions:
- No number occurs more than once in any row or column.
- No black square is horizontally or vertically adjacent to any other black square.
- The remaining white squares must all form one contiguous region (connected by edges, not just touching at corners).
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import singles_solver as solver
board = np.array([
[1, 6, 5, 4, 9, 8, 9, 3, 5, 1, 3, 7],
[2, 8, 5, 7, 1, 1, 4, 3, 6, 3, 10, 7],
[6, 7, 7, 11, 2, 6, 3, 10, 10, 2, 3, 3],
[11, 9, 4, 3, 6, 1, 2, 5, 3, 10, 7, 8],
[5, 5, 4, 9, 7, 9, 6, 6, 11, 5, 4, 11],
[1, 3, 7, 9, 12, 5, 4, 2, 9, 6, 12, 4],
[6, 11, 1, 3, 6, 4, 11, 2, 2, 10, 8, 10],
[3, 11, 12, 6, 2, 9, 9, 1, 4, 8, 12, 5],
[4, 8, 8, 5, 11, 3, 3, 6, 5, 9, 1, 4],
[2, 4, 6, 2, 1, 10, 1, 10, 8, 5, 4, 6],
[5, 1, 6, 10, 9, 4, 8, 4, 8, 3, 2, 12],
[11, 2, 12, 10, 8, 3, 5, 4, 10, 4, 8, 11],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1
0 1 2 3 4 5 6 7 8 9 0 1
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│▒▒▒│ 6 │▒▒▒│ 4 │▒▒▒│ 8 │ 9 │▒▒▒│ 5 │ 1 │ 3 │ 7 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ 2 │ 8 │ 5 │ 7 │ 1 │▒▒▒│ 4 │ 3 │ 6 │▒▒▒│10 │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│▒▒▒│ 7 │▒▒▒│11 │▒▒▒│ 6 │▒▒▒│10 │▒▒▒│ 2 │▒▒▒│ 3 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│11 │ 9 │ 4 │▒▒▒│ 6 │ 1 │ 2 │ 5 │ 3 │10 │ 7 │ 8 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│▒▒▒│ 5 │▒▒▒│ 9 │ 7 │▒▒▒│ 6 │▒▒▒│11 │▒▒▒│ 4 │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ 1 │ 3 │ 7 │▒▒▒│12 │ 5 │▒▒▒│ 2 │ 9 │ 6 │▒▒▒│ 4 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│ 6 │▒▒▒│ 1 │ 3 │▒▒▒│ 4 │11 │▒▒▒│ 2 │▒▒▒│ 8 │10 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ 3 │11 │▒▒▒│ 6 │ 2 │ 9 │▒▒▒│ 1 │ 4 │ 8 │12 │ 5 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│ 4 │▒▒▒│ 8 │ 5 │11 │▒▒▒│ 3 │ 6 │▒▒▒│ 9 │ 1 │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
9│▒▒▒│ 4 │▒▒▒│ 2 │▒▒▒│10 │ 1 │▒▒▒│ 8 │ 5 │▒▒▒│ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
10│ 5 │ 1 │ 6 │10 │ 9 │▒▒▒│ 8 │ 4 │▒▒▒│ 3 │ 2 │12 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
11│▒▒▒│ 2 │12 │▒▒▒│ 8 │ 3 │ 5 │▒▒▒│10 │ 4 │▒▒▒│11 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.04 seconds
Solved puzzle
Range (Puzzle Type #13)
Also known as Kurodoko.
Rules
You have a grid of squares; some squares contain numbers. Your job is to colour some of the squares black, such that several criteria are satisfied:
- no square with a number is coloured black.
- no two black squares are adjacent (horizontally or vertically).
- for any two white squares, there is a path between them using only white squares.
- for each square with a number, that number denotes the total number of white squares reachable from that square going in a straight line in any horizontal or vertical direction until hitting a wall or a black square; the square with the number is included in the total (once).
For instance, a square containing the number one must have four black squares as its neighbors by the last criterion; but then it's impossible for it to be connected to any outside white square, which violates the second to last criterion. So no square will contain the number one.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import range_solver as solver
clues = np.array([
[' ', '4 ', '2 ', ' ', ' ', '3 ', ' ', ' ', ' ', '8 ', ' ', ' ', ' ', ' ', '6 ', ' '],
[' ', ' ', ' ', ' ', ' ', '13', ' ', '18', ' ', ' ', '14', ' ', ' ', '22', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '12', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '12', ' ', '11', ' ', ' ', ' ', '9 ', ' ', ' ', ' ', ' ', ' '],
['7 ', ' ', ' ', ' ', ' ', ' ', '6 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '12', ' ', ' ', ' ', ' ', ' ', '5 '],
[' ', ' ', ' ', ' ', ' ', '9 ', ' ', ' ', ' ', '9 ', ' ', '4 ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '6 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', '10', ' ', ' ', '7 ', ' ', ' ', '13', ' ', '10', ' ', ' ', ' ', ' ', ' '],
[' ', '7 ', ' ', ' ', ' ', ' ', '6 ', ' ', ' ', ' ', '6 ', ' ', ' ', '13', '5 ', ' '],
])
binst = solver.Board(clues)
solutions = binst.solve_and_print()
Script Output
Solution:
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│▒▒▒│ 4 │ 2 │▒▒▒│ │ 3 │▒▒▒│ │▒▒▒│ 8 │▒▒▒│ │▒▒▒│ │ 6 │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ │ │▒▒▒│ │ │13 │ │18 │ │ │14 │ │ │22 │ │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│▒▒▒│ │ │ │ │▒▒▒│ │ │ │ │ │12 │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│ │▒▒▒│ │▒▒▒│12 │ │11 │ │ │ │ 9 │▒▒▒│ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│ 7 │ │ │ │ │▒▒▒│ 6 │ │▒▒▒│ │▒▒▒│ │ │ │▒▒▒│ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ │ │▒▒▒│ │ │ │ │ │ │ │ │▒▒▒│ │ │ │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│▒▒▒│ │ │ │▒▒▒│ │▒▒▒│ │ │12 │ │ │▒▒▒│ │ │ 5 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ │ │ │ │ │ 9 │ │▒▒▒│ │ 9 │▒▒▒│ 4 │ │ │▒▒▒│ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│ │▒▒▒│ │ │ 6 │▒▒▒│ │ │ │▒▒▒│ │▒▒▒│ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
9│ │ │10 │ │ │ 7 │▒▒▒│ │13 │ │10 │ │ │ │ │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
10│▒▒▒│ 7 │ │ │ │ │ 6 │▒▒▒│ │ │ 6 │ │▒▒▒│13 │ 5 │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.07 seconds
Solved puzzle
Tracks (Puzzle Type #16)
Rules
Complete the track from A to B so that the rows and columns contain the same number of track segments as are indicated in the clues to the top and right of the grid. There are only straight and 90-degree curved rail sections, and the track may not cross itself.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import tracks_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LD', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LD', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', 'LD', 'UD', 'DR', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ],
['DR', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'DR', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'DR', ' ', ' ', ' ', ' ', ' ', ' ', ],
[' ', ' ', 'UL', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LR', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LD', ' ', ' ', ' ', 'UD', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'UR', ' ', ' ', ' ', ' ', 'UD', 'UD', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LR', ' ', ' ', ' ', ' ', ' ', ],
['UL', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'LR', 'LR', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'DR', ' ', ],
])
side = np.array([9, 7, 7, 7, 11, 10, 9, 8, 9, 10, 7, 9, 9, 2, 2])
top = np.array([6, 5, 7, 3, 3, 2, 7, 8, 13, 8, 9, 8, 10, 13, 14])
binst = solver.Board(board=board, top=top, side=side)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
0 . . . . . . ┌───────────────────────┐ ┌───┐
│ │ │ │
1 . . . . . . │ . ┌───────┐ . └───┘ │
│ │ │ │
2 . . . . . . │ . │ . └───────────────┘
│ │
3 . . ┌───┐ ┌───┐ │ ┌───┘ . . . . . .
│ │ │ │ │ │
4 ┌───────┘ │ │ └───┘ └───┐ . . . . ┌───┐
│ │ │ │ │ │
5 └───────┐ └───┘ . . ┌───┘ . . . ┌───┘ │
│ │ │ │
6 . . │ . . . ┌───┘ ┌───────────────┘ . │
│ │ │ │
7 . ┌───┘ . . . └───────┘ . . . ┌───────┘
│ │
8 . └───┐ . . . . . ┌───────────┐ │ ┌───┐
│ │ │ │ │ │
9 ┌───────┘ . . . . . │ ┌───┐ └───┘ │ │
│ │ │ │ │ │
10 │ . . . . . . . └───┘ └───┐ . │ │
│ │ │ │
11 │ . . . . . . ┌───────────────┘ ┌───┘ │
│ │ │ │
12──┘ . . . . . . └───────────────────┘ ┌───┘
│
13 . . . . . . . . . . . . . └───┐
│
14 . . . . . . . . . . . . . ┌───┘
│
Solutions found: 1
status: OPTIMAL
Time taken: 1.01 seconds
Solved puzzle
Pearl (Puzzle Type #19)
Also known as Masyu
Rules
You have a grid of squares. Your job is to draw lines between the centres of horizontally or vertically adjacent squares, so that the lines form a single closed loop. In the resulting grid, some of the squares that the loop passes through will contain corners, and some will be straight horizontal or vertical lines. (And some squares can be completely empty – the loop doesn't have to pass through every square.)
Some of the squares contain black and white circles, which are clues that the loop must satisfy.
A black circle in a square indicates that that square is a corner, but neither of the squares adjacent to it in the loop is also a corner.
A white circle indicates that the square is a straight edge, but at least one of the squares adjacent to it in the loop is a corner.
(In both cases, the clue only constrains the two squares adjacent in the loop, that is, the squares that the loop passes into after leaving the clue square. The squares that are only adjacent in the grid are not constrained.)
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import pearl_solver as solver
board = np.array([
['B', ' ', ' ', 'W', ' ', ' ', 'W', ' ', 'B', ' ', ' ', 'B'],
[' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' '],
[' ', 'B', ' ', 'B', ' ', 'W', ' ', 'B', ' ', 'B', 'W', ' '],
[' ', ' ', 'B', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', 'W', 'W', ' ', ' ', 'B'],
[' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['B', ' ', ' ', ' ', ' ', 'B', 'B', ' ', ' ', ' ', ' ', 'B'],
])
binst = solver.Board(board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1
0 1 2 3 4 5 6 7 8 9 0 1
0 B───────────W───┐ ┌───W───┐ B───────────B
│ │ │ │ │ │
1 │ ┌───────B └───┘ ┌───┘ │ ┌───┐ │
│ │ │ │ │ │ │ │
2 └───┘ . │ ┌───┐ └───────B │ │ │
│ │ │ │ │ │
3 . B───────B │ W . B───────B W │
│ │ │ │ │ │
4 . │ B───────B └───┐ │ ┌───┐ └───┘
│ │ │ │ │ │
5 ┌───┘ │ . ┌───┐ │ W W └───────B
│ │ │ │ │ │ │ │
6 │ . B───────┘ │ │ └───┘ . . │
│ │ │ │
7 B───────────────────B B───────────────────B
Solutions found: 1
status: OPTIMAL
Time taken: 0.12 seconds
Solved puzzle
Inertia (Puzzle Type #21)
This solver is a bit different from the other solvers in this repo because this game does not have a unique solution (you simply move the ball to collect all the gems).
Thus the solver was developed with the additional much harder goal of collecting all the gems with the least number of moves.
It does so using the following high level steps:
- Model the board as a directed graph where the cells are nodes and legal moves as directed edges with unit cost. Each gem has to a group of edges where traversing any one of them collects that gem.
- Model step (1) as a Generalized Traveling Salesman Problem (GTSP), where each gem's edge group forms a cluster.
- Apply the Noon–Bean transformation (Noon & Bean, 1991) to convert the GTSP from step (2) into an equivalent Asymmetric TSP (ATSP) that can be solved with OR-Tools' routing solver. (Noon-Bean transformation is mentioned but not described in the TSP wikipedia page.)
- Use a Vehicle Routing Problem (VRP) solver using the OR-Tools VRP solver to solve the ATSP.
This achieves a final sequence of moves that is empirically always faster than the website's solution.
Rules
You are a small green ball sitting in a grid full of obstacles. Your aim is to collect all the gems without running into any mines.
You can move the ball in any orthogonal or diagonal direction. Once the ball starts moving, it will continue until something stops it. A wall directly in its path will stop it (but if it is moving diagonally, it will move through a diagonal gap between two other walls without stopping). Also, some of the squares are ‘stops’; when the ball moves on to a stop, it will stop moving no matter what direction it was going in. Gems do not stop the ball; it picks them up and keeps on going.
Running into a mine is fatal. Even if you picked up the last gem in the same move which then hit a mine, the game will count you as dead rather than victorious.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note: there is a script that parses a screenshot of the board and outputs the below array that the solver uses. The script uses classical computer vision techniques and is called parse_map.py)
import numpy as np
from puzzle_solver import inertia_solver as solver
board = np.array([
['O', 'O', 'M', ' ', 'G', 'O', 'G', 'O', ' ', ' ', 'M', ' ', ' ', 'O', 'G', 'G', 'W', 'O', 'O', 'O'],
['O', ' ', 'W', ' ', 'W', 'O', 'G', 'M', ' ', ' ', ' ', 'G', 'M', 'O', 'W', 'G', ' ', 'M', 'M', 'O'],
['O', 'M', 'O', 'O', ' ', 'M', ' ', 'W', 'W', 'M', 'G', 'W', ' ', ' ', 'G', ' ', 'W', 'G', 'O', 'G'],
['O', ' ', 'O', 'M', 'G', 'O', 'W', 'G', 'M', 'O', ' ', ' ', 'G', 'G', 'G', ' ', 'M', 'W', 'M', 'O'],
['M', 'M', 'O', 'G', ' ', 'W', ' ', ' ', 'O', 'G', ' ', 'M', 'M', ' ', 'W', 'W', ' ', 'W', 'W', 'O'],
['G', ' ', 'G', 'W', 'M', 'W', 'W', ' ', 'G', 'G', 'W', 'M', 'G', 'G', ' ', 'G', 'O', 'O', 'M', 'M'],
['M', ' ', 'M', ' ', 'W', 'W', 'M', 'M', 'M', 'O', 'M', 'G', 'O', 'M', 'M', 'W', 'B', 'O', 'W', 'M'],
['G', 'G', ' ', 'W', 'M', 'M', 'W', 'O', 'W', 'G', 'W', 'O', 'O', 'M', ' ', 'W', 'W', 'G', 'G', 'M'],
[' ', 'M', 'M', ' ', ' ', ' ', 'G', 'G', 'M', 'O', 'M', 'O', 'M', 'G', 'W', 'M', 'W', ' ', 'O', ' '],
['G', ' ', 'M', ' ', ' ', ' ', 'W', 'O', 'W', 'W', 'M', 'M', 'G', 'W', ' ', ' ', 'W', 'M', 'G', 'W'],
['G', 'O', 'M', 'M', 'G', 'M', 'W', 'O', 'O', 'G', 'W', 'M', 'M', 'G', 'G', ' ', 'O', ' ', 'W', 'W'],
['G', 'G', 'W', 'G', 'M', ' ', 'G', 'W', 'W', ' ', 'G', ' ', 'O', 'W', 'G', 'G', 'O', ' ', 'M', 'M'],
['W', 'M', 'O', ' ', 'W', 'O', 'O', 'M', 'M', 'O', 'G', 'W', ' ', 'G', 'O', 'G', 'G', 'O', 'O', 'W'],
['W', 'W', 'W', ' ', 'W', 'O', 'W', 'M', 'O', 'M', 'G', 'O', 'O', ' ', ' ', 'W', 'W', 'G', 'W', 'W'],
['O', 'W', 'O', 'M', 'O', 'G', ' ', 'O', 'O', 'M', 'O', ' ', 'M', 'M', 'O', 'G', 'W', 'G', 'M', ' '],
['M', 'G', 'O', 'G', 'O', 'G', 'O', 'G', ' ', 'W', 'W', 'G', 'O', ' ', 'W', 'M', 'G', ' ', 'W', ' ']
])
start_pos, edges, edges_to_direction, gems_to_edges = solver.parse_nodes_and_edges(board)
optimal_walk = solver.solve_optimal_walk(start_pos, edges, gems_to_edges)
moves = solver.get_moves_from_walk(optimal_walk, edges_to_direction, verbose=True)
Script Output
Note that the output is the sequence of moves to collect all the gems. This particular solution is 106 moves, which is 15 moves better than the website's solution.
number of moves 106
↗ ↖ ↖ ↙ ↙ ↖ ↖ ↙ → ↘
↙ → ↖ → ↙ ↓ → ↘ ↗ ↓
↘ → ↘ ↓ ↗ ↓ ↑ → ↗ ↖
↑ ↗ ↑ ↗ → ↓ ← ↙ ↖ ↗
↓ ↙ ↙ ↑ ← ↘ ↙ ↓ → ↘
↘ ↙ ↖ ↙ ↗ ↘ ↗ ↘ ↑ ↘
↖ ↑ ↗ → → ↘ → ↘ ↗ ↑
← ↑ ↖ ↖ ↗ → ↘ ↓ ↖ ←
↖ ↓ ← ↓ ↓ ↑ ↖ → ↗ ↗
↘ ↘ ↙ ↘ ↓ ↗ ↖ ↘ ↙ ←
↘ ↖ ↗ ↑ ↗ →
Time taken: 13.92 seconds
Solved puzzle
This picture won't mean much as the game is about the sequence of moves not the final frame as shown here.
Guess (Puzzle Type #22)
Rules
You have a set of coloured pegs, and have to reproduce a predetermined sequence of them (chosen by the computer) within a certain number of guesses.
Each guess gets marked with the number of correctly-coloured pegs in the correct places (in black), and also the number of correctly-coloured pegs in the wrong places (in white).
Unlike most other puzzles in this repo, 'Guess' is very different. Similar to minesweeper, Guess is a limited information dynamic puzzle where the next best move depends on information revealed by previous moves (The similarities to minesweeper stop here).
The solver is designed to take the state of the board at any timestep and always gives the next optimal guess. This might seem like an impossible task at first but it's actually not too bad. The optimal guess is defined to be the one that maximizes the Shannon entropy (i.e. maximizes the expected information gain).
The steps below formaly describe the algorithm that is also used in this amazing 3Blue1Brown video on solving Wordle using information theory. Where 3Blue1Browne describes the same steps below but for a slightly harder problem to solve wordle (a very similar game). The video intuitively justifies this algorithm and builds it from scratch using basic intuition.
To formalize the algorithm, let's first define our three inputs as
- $N :=$ the number of pegs (the length of every guess)
- must have $N \geq 1$ and by default $N = 4$ in the game
- $C :=$ the set of possible colors
- what actually matters is $|C|$, the number of possible choices for each peg, i.e. the number of colors
- by default in the game, $C = {R,Y,G,B,O,P}$ (six distinct symbols; only $|C|$ matters) for Red, Yellow, Green, Blue, Orange, and Purple.
- $\mathrm{MR} := ((m_1, r_1), (m_2, r_2), ..., (m_k, r_k))$ be the sequence of previous guesses and results where $(m_i, r_i)$ is the previous guess and result at round $i$ and $k\geq 0$ is the number of previous guesses the player has made
- Note that $m_i$ has length $N$ and each element is $\in C$ by definition
- $r_i$ is a triplet of non-negative integers that sum to $N$ by definition. This corresponds to counts of exact-match positions, color-only matches, and non-matches (visualized as black, white, and grey dots)
The algorithm is as follows
-
Define $G$ as the set of every possible guess that can be made
$$G := {(c_1, \dots, c_N) \mid \forall i \in {1, \dots, N},\ c_i \in C }$$
-
Note that $|G| = |C|^N$
-
Note that $m_i \in G$ for all $i \in {1, 2, ..., k}$ by definition.
-
-
Define $T$ as the set of every possible result triplet
$$T := {(t_1, t_2, t_3) \in \mathbb{N}_0^3 : t_1 + t_2 + t_3 = N}$$
- Note that $r_i \in T$ for all $i \in {1, 2, ..., k}$ by definition.
- Note that $|T|=\binom{N+2}{2}$ (stars-and-bars)
- By default, $N = 4$ in the game so $|T|=15$
-
Define $f : G \times G \to T$ by $f(g_{\text{guess}}, g_{\text{truth}}) = t$ as the result triplet $(t_1, t_2, t_3)$ obtained when guessing $g_{\text{guess}}$ against ground truth $g_{\text{truth}}$. It is trivial to algorithmically make this function which simply counts from $g_1$ and $g_2.$ Look at the function
get_tripletsfor a naive implementation of this. -
Define $S$ as the subset of $G$ that is consistent with the previous guesses $m_i$ and results $r_i$
$$ S := {g \in G : \forall i \in {1, 2, ..., k}, f(m_i, g) = r_i} $$
- Note that if there aren't previous guesses ($\mathrm{MR} = \emptyset$) then $S = G$
- Note that if $S = \emptyset$ then something is wrong with the previous guesses $\mathrm{MR}$ and there is no possible solution to the puzzle. The algorithm stops here and informs the user that the puzzle is unsolvable with the given guesses $\mathrm{MR}$ and that this should never happen unless there is a typo in the guesses $\mathrm{MR}$ (which is usually the case).
-
For each possible guess $g \in G$ and each triplet $t \in T$, count the number of possible solutions $s \in S$ that result in the triplet $t$ when guessing $g$. i.e.
$$D(g, t) := |{s \in S: f(g, s) = t}|$$
-
Calculate the entropy for each possible guess $g \in G$ as the sum of probability times the self-information for every triplet $t \in T$. i.e.
$$H : G \to \mathbb{R}, \quad H(g) = -\sum_{t \in T} P(t \mid g) \log_2 P(t \mid g)$$
- where $P(t \mid g) = \frac{D(g, t)}{|S|}$
- By convention, terms with $P(t \mid g)=0$ contribute $0$ to the sum (interpreting $0\log 0 := 0)$.
-
Return the guess $g \in G$ that maximizes the entropy $H(g)$ (to break ties, choose $g$ that is also in $S$ such that it's possibly the correct solution as well, break further ties arbitrarily).
- i.e. return any $g^*\in (\mathrm{argmax}_{g\in G}\ H(g) \cap S)$ if exists
- otherwise return any $g\in \mathrm{argmax}_{g\in G}\ H(g)$.
If you are at all interested in the above steps and want to understand more, I highly recommend watching this amazing 3Blue1Brown video on solving Wordle using information theory where he describes the same steps but a bits more complicated problem to solve Wordle (a very similar game).
Below is an example of how to utilize the solver while in the middle of a puzzle.
(This is the only solver that under the hood does not utilize any packages besides numpy)
Unsolved puzzle
Let's say we start and made two guesses to end up with the following puzzle:
Code to utilize this package and solve the puzzle:
We encode the puzzle as a Board object then retrieve the optimal next guess:
from puzzle_solver import guess_solver as solver
binst = solver.Board()
binst.add_guess(('R', 'Y', 'G', 'B'), (1, 1, 2)) # 1 black dot, 1 white dot, 2 grey dots
binst.add_guess(('R', 'G', 'O', 'P'), (0, 2, 2)) # 0 black dots, 2 white dots, 2 grey dots
binst.best_next_guess()
Note: the three numbers in each guess is the result of the guess: (# of black dots, # of white dots, # of grey dots)
Note: by default, the board will have 4 circles and 6 possible colors (R: Red, Y: Yellow, G: Green, B: Blue, O: Orange, P: Purple) but both of these are optional parameters to the Board to change behavior.
Script Output 1/2
Note that the output is next optimal guess that has the maximum Shannon entropy.
out of 1296 possible ground truths, only 57 are still possible.
max entropy guess is: ['P', 'Y', 'Y', 'G'] with entropy 3.4511
So we make our next guess as (Purple, Yellow, Yellow, Green) and let's say we get this result: (2 black, 1 white, 1 grey)
So we input that again to the solver to retrieve the next optimal guess:
from puzzle_solver import guess_solver as solver
binst = solver.Board()
binst.add_guess(('R', 'Y', 'G', 'B'), (1, 1, 2)) # 1 black dot, 1 white dot, 2 grey dots
binst.add_guess(('R', 'G', 'O', 'P'), (0, 2, 2)) # 0 black dots, 2 white dots, 2 grey dots
binst.add_guess(('P', 'Y', 'Y', 'G'), (2, 1, 1)) # 2 black dots, 1 white dot, 1 grey dot
binst.best_next_guess()
Script Output 2/2
out of 1296 possible ground truths, only 3 are still possible.
max entropy guess is: ['G', 'Y', 'Y', 'O'] with entropy 1.5850
So we make our fourth guess as (Green, Yellow, Yellow, Orange)
When we input the guess, we see that we correctly solve the puzzle!
Note that in this case, the correct guess was among multiple possible guesses
In the case when there's only one possible choice left, the solver will inform you that it's the garunteed solution.
Chess Melee (Puzzle Type #25)
Rules
You are given a chess board with $N$ pieces distributed on it (equal white and black pieces, one more black if $N$ is odd). Your aim is to make $N-1$ sequence of moves where each move is a legal chess move and captures another piece of the opposite color and end up with a single piece on the board. White starts and colors alternate as usual.
- Pieces move as standard chess pieces.
- White moves first.
- You can perform only capture moves. A move that does not capture another piece of the opposite color is not allowed.
- The goal is to end up with one single piece on the board.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note that this puzzle does not typically have a unique solution. Thus, we specify here that we only want the first valid solution that the solver finds.)
from puzzle_solver import chess_melee_solver as solver
# algebraic notation
board = ['Pb7', 'Nc7', 'Bc6', 'Ne6', 'Pb5', 'Rc4', 'Qb3', 'Rf7', 'Rb6', 'Pe5', 'Nc3', 'Pd3', 'Nf3']
colors = ['B', 'B', 'B', 'B', 'B', 'B', 'B', 'W', 'W', 'W', 'W', 'W', 'W']
binst = solver.Board(board, colors)
solutions = binst.solve_and_print()
Script Output
The output is in the form of "pos -> pos" where "pos" is the algebraic notation of the position.
Solution found
['Rf7->Nc7', 'Ne6->Rc7', 'Pd3->Rc4', 'Qb3->Nc3', 'Pc4->Pb5', 'Qc3->Pe5', 'Nf3->Qe5', 'Nc7->Pb5', 'Ne5->Bc6', 'Pb7->Nc6', 'Rb6->Nb5', 'Pc6->Rb5']
Solutions found: 1
status: OPTIMAL
Time taken: 6.24 seconds
Solved puzzle
Aquarium (Puzzle Type #27)
Rules
The puzzle is played on a rectangular grid divided into blocks called "aquariums"
You have to "fill" the aquariums with water up to a certain level or leave it empty.
The water level in each aquarium is one and the same across its full width
The numbers outside the grid show the number of filled cells horizontally and vertically.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import aquarium_solver as solver
board = np.array([
['01', '01', '01', '01', '02', '02', '02', '03', '03', '03', '03', '04', '05', '05', '05'],
['01', '02', '02', '02', '02', '06', '07', '07', '03', '08', '03', '04', '04', '05', '09'],
['01', '01', '02', '11', '06', '06', '06', '12', '12', '08', '13', '13', '13', '09', '09'],
['01', '11', '11', '11', '14', '06', '06', '12', '12', '15', '15', '13', '09', '09', '09'],
['01', '01', '11', '11', '14', '12', '12', '12', '16', '16', '15', '13', '13', '17', '09'],
['45', '11', '11', '14', '14', '12', '42', '42', '42', '15', '15', '13', '13', '17', '18'],
['45', '11', '11', '14', '14', '12', '12', '43', '15', '15', '20', '13', '13', '17', '18'],
['46', '46', '11', '19', '19', '19', '43', '43', '44', '20', '20', '20', '13', '17', '18'],
['46', '22', '23', '23', '23', '19', '43', '21', '21', '24', '24', '24', '25', '17', '17'],
['22', '22', '22', '23', '19', '19', '26', '24', '24', '24', '28', '28', '25', '17', '33'],
['22', '22', '23', '23', '27', '27', '26', '26', '24', '24', '29', '29', '25', '25', '33'],
['22', '22', '35', '27', '27', '26', '26', '26', '26', '30', '30', '30', '25', '34', '34'],
['37', '22', '35', '35', '35', '35', '35', '26', '26', '30', '31', '31', '32', '32', '40'],
['37', '37', '37', '36', '36', '35', '26', '26', '26', '40', '40', '40', '40', '40', '40'],
['37', '37', '37', '37', '35', '35', '38', '38', '39', '39', '40', '40', '40', '41', '41'],
])
top = np.array([6, 6, 5, 3, 3, 4, 7, 6, 9, 6, 3, 4, 9, 6, 7])
side = np.array([3, 5, 1, 2, 5, 3, 10, 10, 5, 3, 7, 3, 7, 8, 12])
binst = solver.Board(board=board, top=top, side=side)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───────────────┬───────────┬───────────────┬───┬───────────┐
0│ │ │ │ │ O O O │
│ ┌───────────┘ ┌───┬───┴───┐ ┌───┐ │ └───┐ ┌───┤
1│ │ │ │ │ O │ │ O │ O O │ O │ │
│ └───┐ ┌───┬───┘ └───┬───┴───┤ ├───┴───────┼───┘ │
2│ │ │ │ │ │ O │ │ │
│ ┌───┴───┘ ├───┐ │ ├───┴───┐ ┌───┘ │
3│ │ │ │ O O │ │ │ │ │
│ └───┐ │ ├───────┘ ┌───┴───┐ │ └───┬───┐ │
4│ O O │ │ │ │ O O │ │ │ │ O │
├───┬───┘ ┌───┘ │ ┌───────┴───┬───┘ │ │ ├───┤
5│ │ │ │ │ O O O │ │ │ │ │
│ │ │ │ └───┬───┬───┘ ┌───┤ │ │ │
6│ O │ O O │ │ O O │ │ O O │ │ O O │ │ O │
├───┴───┐ ├───────┴───┬───┘ ├───┬───┘ └───┐ │ │ │
7│ O O │ O │ │ O O │ │ O O O │ O │ │ O │
│ ┌───┼───┴───────┐ │ ┌───┴───┼───────────┼───┤ └───┤
8│ O │ │ │ │ O │ O O │ │ O │ │
├───┘ └───┐ ┌───┘ ├───┼───────┘ ┌───────┤ │ ┌───┤
9│ │ │ O O │ │ │ │ O │ │ │
│ ┌───┘ ├───────┤ └───┐ ├───────┤ └───┤ │
10│ │ O O │ │ │ O O │ │ O O │ O │
│ ├───┬───┘ ┌───┘ └───┬───┴───────┤ ┌───┴───┤
11│ │ │ │ │ │ O │ O O │
├───┐ │ └───────┴───────┐ │ ┌───────┼───┴───┬───┤
12│ │ O │ │ O O │ │ O O │ O O │ │
│ └───┴───┬───────┐ ┌───┘ ├───┴───────┴───────┘ │
13│ O O O │ O O │ │ O O O │ │
│ └───┬───┘ ├───────┬───┴───┐ ┌───────┤
14│ O O O O │ O O │ O O │ O O │ │ O O │
└───────────────┴───────┴───────┴───────┴───────────┴───────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.02 seconds
Solved puzzle
Stitches (Puzzle Type #28)
Rules
- Connect each block with ALL its neighbor blocks with exactly 1 "stitch" each.
- A "stitch" connects 2 orthogonally adjacent cells from different blocks.
- 2 stitches cannot share a hole.
- The clues outside the grid indicate the number of holes on that row/column
- For 2÷ puzzles, you have to use 2 stitches to connect neighbor blocks, for 3÷ puzzles - 3 stitches etc.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import stitches_solver as solver
board = np.array([
["00", "00", "00", "00", "00", "01", "01", "01", "01", "01", "01", "01", "01", "02", "02"],
["00", "03", "03", "04", "00", "00", "01", "05", "05", "05", "05", "05", "01", "01", "02"],
["00", "03", "04", "04", "04", "00", "05", "05", "05", "05", "05", "05", "05", "05", "02"],
["00", "03", "04", "04", "04", "04", "05", "05", "06", "05", "02", "02", "02", "02", "02"],
["07", "03", "03", "03", "03", "04", "06", "06", "06", "06", "06", "06", "06", "02", "02"],
["07", "07", "07", "03", "03", "04", "04", "06", "08", "08", "08", "06", "02", "02", "02"],
["07", "07", "03", "03", "03", "04", "04", "08", "08", "08", "08", "06", "06", "06", "02"],
["07", "07", "07", "07", "07", "08", "08", "08", "09", "09", "08", "06", "08", "06", "02"],
["10", "10", "07", "07", "09", "09", "09", "09", "09", "09", "08", "08", "08", "11", "02"],
["10", "10", "07", "09", "09", "09", "09", "09", "09", "09", "09", "08", "08", "11", "02"],
["10", "09", "09", "09", "12", "12", "12", "13", "09", "09", "11", "11", "11", "11", "11"],
["10", "10", "10", "09", "12", "12", "12", "13", "09", "11", "11", "11", "13", "13", "11"],
["14", "15", "10", "12", "12", "16", "17", "13", "13", "11", "13", "13", "13", "13", "11"],
["14", "15", "10", "12", "16", "16", "17", "17", "13", "13", "13", "13", "13", "13", "11"],
["14", "15", "15", "12", "16", "16", "17", "17", "17", "17", "17", "13", "13", "13", "13"]
])
top = np.array([6, 6, 9, 5, 3, 8, 9, 3, 1, 4, 4, 1, 4, 8, 5])
side = np.array([0, 10, 6, 4, 4, 1, 5, 8, 2, 6, 5, 11, 4, 3, 7])
binst = solver.Board(board=board, top=top, side=side)
solutions = binst.solve_and_print()
Note: solver.Board accepts an optional connection_count=N parameter to specify the (÷N) stitches puzzle (by default, 1 stitch).
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───────────────────┬───────────────────────────────┬───────┐
0│ . . . . . │ . . . . . . . . │ . . │
│ ┌───────┬───┐ └───┐ ┌───────────────────┐ └───┐ │
1│ O─┼─O O │ O─┼─O O─┼─O │ . . . . . │ O O─┼─O │
│ │ ┌─┼─┘ └───┐ ├───┘ └─┼─────┤ │
2│ . │ . │ O . . │ O─┼─O . . . . . O O─┼─O │
│ │ │ └───┤ ┌───┐ ┌───────────────┘ │
3│ O │ . │ . . . O─┼─O . │ . │ O │ . . . . . │
├─┼─┤ └───────────┐ ├───────┘ └─┼─┴───────────┐ │
4│ O │ . . . . │ O─┼─O . . O . . . │ . . │
│ └───────┐ │ └───┐ ┌───────────┐ ┌───┘ │
5│ . . . │ . . │ . . │ . │ . . . │ . │ . O . │
│ ┌───┘ │ ├───┘ │ └─────┼─┐ │
6│ . . │ O . . │ . O─┼─O . O . │ . . O │ . │
│ └─┼─────────┼───────┘ ┌─────┼─┐ │ ┌───┐ │ │
7│ . O O . O─┼─O . . │ . O │ . │ O─┼─O │ O │ . │
├─────┼─┐ ┌───┴───────────┘ │ └───┘ ├─┼─┤ │
8│ . O │ . . │ . . . . . . │ . . . │ O │ . │
│ │ ┌───┘ └───┐ │ │ │
9│ . . │ O─┼─O . . . . . . O │ . O─┼─O │ O │
│ ┌───┴───┘ ┌───────────┬───┐ ┌─┼─┴───────┘ └─┼─┤
10│ . │ . O . │ . . O─┼─O │ . . │ O . . . O │
│ └─────┼─┐ │ │ │ ┌───┘ ┌───────┐ │
11│ O O O │ O─┼─O O O │ O─┼─O │ . . . │ . O─┼─O │
├─┼─┬─┼─┐ ├───┘ ┌─┼─┬─┼─┤ └───┤ ┌───────┘ │ │
12│ O │ O │ . │ . . │ O │ O │ . . │ . │ . . . . │ . │
│ │ │ │ ┌───┘ │ └───┐ └───┘ │ │
13│ . │ . │ O─┼─O │ . . │ . . │ . . O . . . │ . │
│ │ └───┤ │ │ └─────────┼─┐ └───┤
14│ O─┼─O O─┼─O │ . O─┼─O . . . O │ . . . . │
└───┴───────┴───┴───────┴───────────────────┴───────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.01 seconds
Solved puzzle
Battleships (Puzzle Type #29)
Rules
- You have to find the location of the battleships hidden in the grid. Some battleships may be partially revealed.
- A battleship is a straight line of consecutive black cells.
- The number of the battleships from each size is shown in the legend.
- 2 battleships cannot touch each other (even diagonally)
- The numbers outside the grid show the number of cells occupied by battleships on that row/column.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import battleships_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', 'S', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'S', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'O', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['W', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', 'O', ' ', ' ', ' ', ' ', 'W', ' ', ' ', 'R'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'U', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', 'L', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'S'],
])
top = np.array([2, 2, 4, 2, 1, 2, 1, 2, 4, 1, 3, 2, 5, 2, 2])
side = np.array([1, 2, 1, 1, 0, 7, 0, 9, 2, 2, 5, 1, 3, 0, 1])
ship_counts = {1: 5, 2: 4, 3: 3, 4: 2, 5: 1}
binst = solver.Board(board=board, top=top, side=side, ship_counts=ship_counts)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│ │ │ │ │ │▒▒▒│ │ │ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ │ │ │ │ │ │ │ │ │ │▒▒▒│ │▒▒▒│ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│ │ │ │ │ │ │ │ │ │ │ │ │▒▒▒│ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│ │ │ │ │ │ │ │ │ │ │ │ │▒▒▒│ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ │▒▒▒│▒▒▒│▒▒▒│▒▒▒│ │ │ │ │ │ │▒▒▒│▒▒▒│▒▒▒│ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ │ │▒▒▒│ │ │▒▒▒│▒▒▒│▒▒▒│▒▒▒│▒▒▒│ │ │▒▒▒│▒▒▒│▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│▒▒▒│ │▒▒▒│ │ │ │ │ │ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
9│ │ │ │ │ │ │ │ │▒▒▒│ │ │▒▒▒│ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
10│▒▒▒│▒▒▒│▒▒▒│▒▒▒│ │ │ │ │▒▒▒│ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
11│ │ │ │ │ │ │ │ │ │ │▒▒▒│ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
12│ │ │ │ │ │ │ │▒▒▒│▒▒▒│ │▒▒▒│ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
13│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
14│ │ │ │ │ │ │ │ │ │ │ │ │ │ │▒▒▒│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.09 seconds
Solution found
Solved puzzle
Star Battle Shapeless (Puzzle Type #32)
Rules
You have to place stars on the grid according to the rules:
- 2 stars cannot be adjacent horizontally, vertically or diagonally.
- For 1★ puzzles, you have to place 1 star on each row and column.
- For 2★ puzzles, the stars per row and column must be 2 etc.
- Some places begin with a black square and cannot have stars placed on them.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
The star_count parameter depenends on the puzzle type.
import numpy as np
from puzzle_solver import star_battle_shapeless as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' '],
['B', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' '],
['B', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', 'B', ' '],
['B', ' ', ' ', ' ', ' ', ' ', ' ', 'B', 'B', ' '],
['B', 'B', ' ', ' ', ' ', ' ', 'B', 'B', 'B', ' '],
['B', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board=board, star_count=2)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
┌───────────────────────────────────────┐
0│ X . . . X . . . . . │
├───┐ │
1│ │ . . . . . X . X . │
│ │ ┌───┐ │
2│ │ . X . X . . . │ │ . │
│ └───┐ ┌───┐ └───┘ │
3│ │ . . │ │ . . X . X │
│ │ │ │ │
4│ │ X . │ │ X . . . . │
├───────┘ └───┘ │
5│ X . . . . . . . X . │
│ ┌───┐ ┌───┐ │
6│ . . . X │ │ . X . │ │ . │
├───┐ └───┘ ┌───┘ │ │
7│ │ X . . . . . │ │ X │
│ └───┐ ┌───┘ │ │
8│ │ . X . X │ │ . │
│ ┌───┘ ┌───┐ └───────────┘ │
9│ │ X . . │ │ . . X . . │
└───┴───────────┴───┴───────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.02 seconds
Solved puzzle
Lits (Puzzle Type #33)
Rules
You have to place one tetromino in each region in such a way that:
- 2 tetrominoes of matching types cannot touch each other horizontally or vertically. Rotations and reflections count as matching.
- The shaded cells should form a single connected area.
- 2x2 shaded areas are not allowed.
- Tetromino is a shape made of 4 connected cells. There are 5 types of tetrominoes, which are usually named L, I, T, S and O, based on their shape. The O tetromino is not used in this puzzle because it is a 2x2 shape, which is not allowed.
Note: The solver is capable of solving variations where the puzzle pieces the made up of more than 4 cells (e.g., pentominoes for 5 with polyomino_degrees=5, or hexominoes for 6 with polyomino_degrees=6, etc.). By default the degree is set to 4 thus only tetrominoes are used.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import lits_solver as solver
board = np.array([
['00', '00', '00', '01', '01', '02', '02', '02', '03', '03', '03', '04', '04', '05', '06', '07', '07', '08', '08', '09'],
['00', '00', '00', '00', '01', '02', '03', '03', '03', '10', '04', '04', '05', '05', '06', '07', '08', '08', '09', '09'],
['11', '11', '11', '01', '01', '02', '02', '03', '10', '10', '04', '04', '05', '06', '06', '07', '07', '07', '09', '12'],
['11', '13', '13', '13', '01', '02', '03', '03', '03', '10', '04', '04', '06', '06', '06', '07', '12', '09', '09', '12'],
['11', '11', '11', '13', '14', '14', '03', '15', '15', '10', '04', '04', '06', '16', '16', '12', '12', '09', '12', '12'],
['17', '13', '13', '13', '14', '14', '03', '03', '15', '15', '04', '04', '16', '16', '16', '12', '12', '12', '12', '18'],
['17', '13', '19', '13', '20', '14', '03', '03', '15', '04', '04', '16', '16', '21', '21', '22', '23', '23', '23', '18'],
['17', '17', '19', '19', '20', '20', '03', '03', '24', '24', '24', '25', '25', '25', '21', '22', '23', '23', '18', '18'],
['17', '26', '19', '19', '20', '20', '20', '24', '24', '20', '20', '25', '25', '21', '21', '22', '22', '23', '23', '18'],
['26', '26', '26', '19', '19', '20', '20', '20', '20', '20', '25', '25', '21', '21', '21', '21', '21', '23', '27', '18'],
['28', '28', '28', '29', '29', '29', '29', '20', '20', '30', '30', '25', '31', '32', '32', '32', '21', '27', '27', '27'],
['28', '33', '28', '28', '28', '28', '29', '34', '34', '35', '30', '30', '31', '31', '31', '32', '32', '36', '36', '27'],
['28', '33', '33', '28', '28', '29', '29', '34', '34', '35', '35', '30', '31', '31', '31', '32', '36', '36', '27', '27'],
['28', '33', '37', '37', '28', '29', '34', '34', '35', '35', '38', '38', '39', '39', '40', '40', '40', '40', '27', '41'],
['28', '37', '37', '37', '42', '34', '34', '34', '43', '38', '38', '38', '39', '39', '44', '44', '40', '40', '27', '41'],
['37', '37', '42', '42', '42', '34', '34', '43', '43', '43', '38', '39', '39', '39', '44', '44', '27', '27', '27', '41'],
['45', '45', '45', '42', '46', '34', '34', '34', '34', '38', '38', '47', '47', '47', '44', '44', '44', '27', '27', '41'],
['48', '45', '45', '46', '46', '46', '46', '34', '49', '49', '49', '47', '44', '44', '44', '27', '44', '50', '27', '27'],
['48', '48', '45', '46', '46', '51', '46', '52', '52', '49', '49', '53', '44', '53', '44', '27', '50', '50', '50', '27'],
['48', '51', '51', '51', '51', '51', '52', '52', '52', '49', '53', '53', '53', '53', '44', '27', '27', '27', '27', '27']
])
binst = solver.Board(board)
solutions = binst.solve_then_constrain() # solve_then_constrain NOT solve_and_print (to use #1 instead of #2 in https://github.com/google/or-tools/discussions/3347, its faster in this case)
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
┌───────────┬───────┬───────────┬───────────┬───────┬───┬───┬───────┬───────┬───┐
0│▒▒▒ ▒▒▒ ▒▒▒│ │▒▒▒ ▒▒▒ ▒▒▒│ │ │▒▒▒│ │▒▒▒ │▒▒▒ ▒▒▒│ │
│ └───┐ │ ┌───────┘ ┌───┬───┘ ┌───┘ │ │ ┌───┘ ┌───┘ │
1│ ▒▒▒ │▒▒▒│▒▒▒│ │▒▒▒│ │▒▒▒ ▒▒▒│ │▒▒▒│▒▒▒ ▒▒▒│ │
├───────────┬───┘ │ └───┐ ┌───┘ │ │ ┌───┘ │ └───────┤ ┌───┤
2│▒▒▒ ▒▒▒ ▒▒▒│▒▒▒ ▒▒▒│ │▒▒▒│▒▒▒ ▒▒▒│ │▒▒▒│ │▒▒▒ │▒▒▒│ │
│ ┌───────┴───┐ │ ┌───┘ └───┐ │ ├───┘ │ ┌───┬───┘ │ │
3│▒▒▒│ │▒▒▒│ │▒▒▒ ▒▒▒ │▒▒▒│▒▒▒ │▒▒▒ ▒▒▒ ▒▒▒│▒▒▒│ │▒▒▒ ▒▒▒│ │
│ └───────┐ ├───┴───┤ ┌───────┤ │ │ ┌───────┼───┘ │ ┌───┘ │
4│ │▒▒▒│▒▒▒ ▒▒▒│▒▒▒│ ▒▒▒│ │▒▒▒ │▒▒▒│ │ │▒▒▒│ │
├───┬───────┘ │ │ └───┐ └───┤ ├───┘ │ └───┘ ┌───┤
5│▒▒▒│ ▒▒▒ ▒▒▒│ ▒▒▒│ │▒▒▒ ▒▒▒│▒▒▒ │▒▒▒ ▒▒▒ │▒▒▒ ▒▒▒ ▒▒▒ ▒▒▒│ │
│ │ ┌───┐ ├───┐ │ │ ┌───┘ ┌───┘ ┌───────┼───┬───────────┤ │
6│▒▒▒│ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ ▒▒▒│▒▒▒ ▒▒▒│ │▒▒▒│ │▒▒▒│
│ └───┤ └───┤ └───┤ ├───┴───────┼───────┴───┐ │ │ ┌───┘ │
7│▒▒▒ ▒▒▒│ ▒▒▒│ ▒▒▒│ │▒▒▒ ▒▒▒ │▒▒▒ │ │▒▒▒│ ▒▒▒│ ▒▒▒│
│ ┌───┤ │ └───┬───┘ ┌───────┤ ┌───┘ │ └───┐ └───┐ │
8│ │▒▒▒│ ▒▒▒│ ▒▒▒ ▒▒▒│▒▒▒ ▒▒▒│ │▒▒▒ │▒▒▒ ▒▒▒│▒▒▒ ▒▒▒│▒▒▒ ▒▒▒│▒▒▒│
├───┘ └───┐ └───┐ └───────┘ ┌───┘ ┌───┘ └───────┤ ┌───┤ │
9│▒▒▒ ▒▒▒ ▒▒▒│▒▒▒ ▒▒▒│▒▒▒ │▒▒▒ ▒▒▒│▒▒▒ ▒▒▒ │▒▒▒│ │▒▒▒│
├───────────┼───────┴───────┐ ┌───┴───┐ ├───┬───────────┐ ├───┘ └───┤
10│ │ ▒▒▒ ▒▒▒│ │ ▒▒▒│ │ │▒▒▒ ▒▒▒ ▒▒▒│ │ │
│ ┌───┐ └───────────┐ ├───────┼───┐ └───┤ └───────┐ └───┼───────┐ │
11│ │▒▒▒│ ▒▒▒ ▒▒▒ │▒▒▒│ │▒▒▒│▒▒▒ ▒▒▒│ ▒▒▒ │▒▒▒ │▒▒▒ ▒▒▒│ │
│ │ └───┐ ┌───┘ │ │ └───┐ │ │ ┌───┘ ┌───┘ │
12│ │▒▒▒ ▒▒▒│ ▒▒▒│ ▒▒▒│ │▒▒▒ │▒▒▒│▒▒▒ ▒▒▒ ▒▒▒│ │▒▒▒ ▒▒▒│ │
│ │ ┌───┴───┐ │ ┌───┘ ┌───┘ ┌───┴───┼───────┬───┴───┴───────┤ ┌───┤
13│ │▒▒▒│ │▒▒▒│ │▒▒▒ │▒▒▒ ▒▒▒│▒▒▒ │▒▒▒ │▒▒▒ ▒▒▒ ▒▒▒ │ │▒▒▒│
│ ├───┘ ├───┼───┘ ├───┬───┘ │ ├───────┐ │ │ │
14│ │▒▒▒ ▒▒▒ │▒▒▒│ ▒▒▒ │▒▒▒│ ▒▒▒ │▒▒▒ ▒▒▒│ │▒▒▒ │ │▒▒▒│
├───┘ ┌───────┘ │ ┌───┘ └───┐ ┌───┘ │ ├───────┘ │ │
15│▒▒▒ ▒▒▒│ ▒▒▒ ▒▒▒│ ▒▒▒│▒▒▒ ▒▒▒ ▒▒▒│▒▒▒│ ▒▒▒│ │▒▒▒ ▒▒▒ │▒▒▒│
├───────┴───┐ ┌───┤ └───────┬───┘ ├───────────┤ └───┐ │ │
16│ ▒▒▒ ▒▒▒│▒▒▒│ │ ▒▒▒ │ ▒▒▒│▒▒▒ ▒▒▒ ▒▒▒│▒▒▒ │▒▒▒ ▒▒▒│▒▒▒│
├───┐ ├───┘ └───────┐ ┌───┴───────┤ ┌───────┘ ┌───┐ ├───┐ └───┤
17│▒▒▒│ ▒▒▒│ ▒▒▒ ▒▒▒ ▒▒▒│ │▒▒▒ ▒▒▒ │▒▒▒│ ▒▒▒│ │ │▒▒▒│ │
│ └───┐ │ ┌───┐ ├───┴───┐ ├───┤ ┌───┐ │ ├───┘ └───┐ │
18│▒▒▒ ▒▒▒│▒▒▒│ ▒▒▒│ │ │▒▒▒ │▒▒▒ │▒▒▒│ │ │▒▒▒│ │▒▒▒ ▒▒▒ ▒▒▒│ │
│ ┌───┴───┴───────┘ ├───┘ │ ┌───┘ └───┘ │ │ └───────────┘ │
19│▒▒▒│ ▒▒▒ ▒▒▒ ▒▒▒ ▒▒▒│▒▒▒ ▒▒▒ ▒▒▒│▒▒▒│▒▒▒ ▒▒▒ ▒▒▒ │▒▒▒│ │
└───┴───────────────────┴───────────┴───┴───────────────┴───┴───────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.09 seconds
Solved puzzle
Galaxies (Puzzle Type #35)
Also known as Tentai Show, Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix.
Rules
You have a rectangular grid containing a number of dots. Your aim is to partition the rectangle into connected regions of squares, in such a way that every region is 180° rotationally symmetric, and contains exactly one dot which is located at its centre of symmetry.
To enter your solution, you draw lines along the grid edges to mark the boundaries of the regions. The puzzle is complete when the marked lines on the grid are precisely those that separate two squares belonging to different regions.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
Note: The number are arbitrary and simply number each galaxy as an integer.
import numpy as np
from puzzle_solver import galaxies_solver as solver
galaxies = np.array([
[' ', ' ', '00', ' ', ' ', '01', '01', '02', '02', '03', '03', ' ', '04', '04', ' '],
['05', '05', ' ', ' ', '06', '01', '01', '02', '02', ' ', ' ', ' ', '07', ' ', ' '],
['08', ' ', ' ', ' ', '06', ' ', '09', '09', ' ', ' ', '10', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '11', '11', '12', ' ', ' ', ' ', ' ', '13', '13'],
['14', ' ', ' ', ' ', '15', ' ', '11', '11', ' ', ' ', ' ', ' ', '16', ' ', ' '],
[' ', '17', ' ', ' ', '15', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '16', ' ', '18'],
[' ', '17', '19', ' ', ' ', ' ', ' ', ' ', ' ', '20', ' ', ' ', ' ', '21', '18'],
[' ', '22', ' ', ' ', '23', ' ', ' ', ' ', ' ', '20', ' ', '24', '24', '21', '25'],
['26', '27', '27', '28', '28', '29', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '30', '30'],
[' ', '27', '27', '28', '28', '31', '31', ' ', ' ', ' ', ' ', '32', ' ', '30', '30'],
[' ', ' ', ' ', '33', '33', '31', '31', '34', ' ', ' ', '35', ' ', ' ', ' ', ' '],
['36', ' ', ' ', '33', '33', ' ', ' ', '34', ' ', ' ', ' ', ' ', ' ', '37', ' '],
[' ', ' ', '38', '38', ' ', '39', ' ', '40', '40', '41', '41', '42', ' ', '37', ' '],
['43', '44', '38', '38', '45', '45', '46', '40', '40', '41', '41', '42', ' ', ' ', ' '],
['43', ' ', ' ', ' ', ' ', ' ', ' ', '47', ' ', ' ', ' ', ' ', '48', '48', ' ']
])
binst = solver.Board(galaxies=galaxies)
solutions = binst.solve_and_print()
Script Output
As the instructions say, the solution to this puzzle is not garunteed to be unique.
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───────────────────┬───────┬───────┬───────┬───────────────┐
0│ . │ . . │ . . │ . . │ . . │
├───────┬───┬───────┤ │ ├───────┼───────────┬───┤
1│ . . │ │ . │ . . │ . . │ │ . │ │
├───┬───┘ └───┐ └───┬───┴───┬───┘ └───────┬───┘ │
2│ . │ │ . │ . . │ . │ │
├───┤ └───────┼───────┼───┬───┐ ┌───┤ │
3│ │ │ . . │ . │ │ │ │ . . │
│ │ │ ├───┘ └───────┤ │ │
4│ . │ . │ . . │ │ . │ │
│ ├───────┐ └───────┤ │ │ ┌───┤
5│ │ . │ . │ │ . │ │ . │
├───┘ ┌───┤ │ ┌───┤ ├───┤ │
6│ . │ . │ │ . │ │ │ . │ . │
├───┬───┼───┴───┬───┐ │ │ └───┤ ├───┤
7│ │ . │ │ . │ │ . │ . . │ . │ . │
│ ├───┘ ┌───┴───┼───┐ ┌───┘ ├───┐ ├───┴───┤
8│ . │ . . │ . . │ . │ │ │ │ │ . . │
│ │ │ ├───┴───┤ │ ├───┤ │
9│ │ . . │ . . │ . . │ │ . │ │ . . │
├───┘ ┌───┴───────┤ ├───────┐ ┌───┤ │ └───────┤
10│ │ . . │ . . │ . │ │ . │ │ │
├───┬───┴───┐ └───┬───┘ ┌───┴───┴───┴───┤ │
11│ . │ │ . . │ . │ │ . │
├───┴───┐ └───┬───┬───┼───┬───┴───┐ ┌───┤ │
12│ │ . . │ │ . │ │ . . │ . . │ . │ . │
├───┐ │ │ └───┤ │ │ │ │ │
13│ . │ . │ . . │ . . │ . │ . . │ . . │ . │ │
│ │ └───┐ └───┐ │ ├───┬───┘ └───┼───────┐ │
14│ . │ │ │ │ │ . │ │ . . │ │
└───┴───────┴───────┴───┴───┴───┴───────────────┴───────┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.06 seconds
Solved puzzle
Applying the solution to the puzzle visually:
Slitherlink (Puzzle Type #39)
Also known as Fences, Loop the Loop, or Loopy.
Rules
You have to draw lines between the dots to form a single loop without crossings or branches. The numbers indicate how many lines surround it.
A line forming a single loop without crossings or branches means that every corner has either 2 or 0 lines touching it.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import slitherlink_solver as solver
board = np.array([
['3', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', '1', ' '],
[' ', ' ', '3', ' ', '3', ' ', ' ', ' ', '3', ' ', '2', '2', ' ', '2', ' ', '2', '2', ' ', '2', '3'],
['2', '2', ' ', ' ', ' ', '2', '1', ' ', '1', '1', ' ', ' ', '3', '1', ' ', '2', ' ', ' ', ' ', '2'],
[' ', ' ', '2', ' ', ' ', '2', '2', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', '2', '2', '3', ' '],
['1', '2', '1', ' ', ' ', ' ', '2', '1', ' ', '3', '2', ' ', '3', '2', '2', '3', ' ', '3', '2', '2'],
[' ', '3', '2', '2', '1', '2', ' ', '3', ' ', ' ', ' ', ' ', '2', '2', '3', ' ', '1', '1', ' ', '2'],
['1', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', '2', ' ', '1', '3', ' ', ' ', ' ', ' ', '2', '2', '2'],
[' ', '3', ' ', '2', '0', '1', '2', '1', ' ', '1', '3', ' ', '2', ' ', ' ', '2', ' ', '2', '1', ' '],
['2', ' ', ' ', ' ', '2', ' ', '3', ' ', ' ', ' ', ' ', '2', ' ', ' ', '1', '2', ' ', ' ', '1', '3'],
[' ', ' ', '1', ' ', ' ', ' ', ' ', '2', '0', ' ', '1', ' ', '2', ' ', '0', ' ', '2', ' ', '3', '2'],
[' ', '3', ' ', '3', ' ', '1', '3', ' ', '3', ' ', '2', ' ', ' ', '2', '2', '2', '3', ' ', ' ', ' '],
['3', ' ', ' ', ' ', ' ', ' ', ' ', '0', '2', '1', ' ', ' ', '2', ' ', ' ', '1', ' ', '0', '2', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', '3', '2', '3', ' ', ' ', '2', ' ', '1', ' ', ' ', ' ', ' '],
['2', '2', ' ', '3', '0', ' ', ' ', '3', ' ', ' ', '2', ' ', ' ', ' ', ' ', '2', '2', ' ', '3', ' '],
[' ', '2', '0', ' ', ' ', '3', ' ', '1', ' ', ' ', '2', ' ', '2', '2', ' ', ' ', ' ', '2', ' ', '2'],
[' ', ' ', '1', '3', '1', ' ', ' ', ' ', ' ', ' ', '2', ' ', '2', '1', ' ', '1', '2', '2', ' ', ' '],
['2', ' ', '2', '2', ' ', '1', '3', ' ', '2', ' ', '3', '1', '2', ' ', '3', '2', ' ', '1', '1', ' '],
[' ', ' ', '2', ' ', '1', ' ', ' ', ' ', '2', ' ', ' ', ' ', '2', ' ', '1', '0', ' ', ' ', ' ', '3'],
[' ', '2', ' ', ' ', '2', ' ', '2', '3', '2', ' ', '2', '2', ' ', '3', '2', '2', '3', '3', '1', ' '],
['0', '0', ' ', '3', '2', ' ', ' ', ' ', ' ', ' ', '2', '1', '2', '1', ' ', ' ', ' ', '2', '1', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
┌───┐ ┌───────┐ ┌───────────────────┐ ┌───────┐ ┌───┐ ┌───────────┐
0│ 3 │ · │ · 2 │ · │ · · · · 3 │ · · │ · · │ · │ 3 │ · │ · 1 · │
│ │ └───┐ │ │ ┌───────┐ ┌───┘ ┌───┘ ┌───┘ │ │ └───┐ ┌───┘
1│ · │ · 3 │ · │ 3 │ · │ · · │ 3 │ · 2 │ 2 · │ 2 · │ 2 │ 2 · │ 2 │ 3
│ │ ┌───┘ └───┘ │ └───┘ ┌───┘ ┌───┘ │ └───────┘ └───┐
2│ 2 │ 2 │ · · · 2 │ 1 · 1 1 │ · · │ 3 1 · │ 2 · · · 2 │
│ │ │ ┌───────────┘ ┌───┐ └───┐ └───────┐ └───────┐ ┌───┐ │
3│ · │ · │ 2 │ · · 2 2 │ · │ · · 3 │ · · · │ · · 2 │ 2 │ 3 │ · │
│ └───┘ └───────────────┘ └───┐ ┌───┘ ┌───┐ │ ┌───┐ │ │ │ │
4│ 1 2 1 · · · 2 1 · │ 3 │ 2 · │ 3 │ 2 │ 2 │ 3 │ · │ 3 │ 2 │ 2 │
│ ┌───────────────────────────┐ └───┘ ┌───┘ │ │ │ │ └───┘ │ │
5│ · │ 3 2 2 1 2 · 3 │ · · · │ · 2 │ 2 │ 3 │ · │ 1 1 · │ 2 │
│ └───────────┐ ┌───────────┘ ┌───────┘ ┌───┘ └───┘ │ ┌───┘ │
6│ 1 · · · │ · │ · 2 · · │ 2 · 1 │ 3 · · · │ · 2 │ 2 2 │
│ ┌───────────┘ └───────────────┘ ┌───┐ └───────────┐ └───────┘ ┌───┘
7│ · │ 3 · 2 0 1 2 1 · 1 │ 3 │ · 2 · · │ 2 · 2 1 │ ·
│ └───┐ ┌───┐ ┌───┐ ┌───┐ │ └───────────┐ └───┐ ┌───┐ └───┐
8│ 2 · │ · │ · │ 2 · │ 3 │ · │ · │ · │ · 2 · · │ 1 2 │ · │ · │ 1 3 │
└───┐ └───┘ └───┐ │ └───┘ └───┘ ┌───┐ ┌───┘ └───┘ │ ┌───┘
9 · │ · 1 · · │ · │ · 2 0 · 1 │ · │ 2 │ · 0 · 2 · │ 3 │ 2
└───┐ ┌───────┘ │ ┌───┐ ┌───┐ │ │ │ ┌───────┐ └───┘
10 · 3 │ · │ 3 · 1 │ 3 │ · │ 3 │ · │ 2 │ · │ · │ 2 2 │ 2 3 │ · · ·
┌───────┘ └───────┐ └───┘ └───┘ │ │ │ └───────┘ ┌───┘ ┌───┐
11│ 3 · · · · │ · · 0 2 1 │ · │ · │ 2 · · 1 │ · 0 2 │ · │
└───┐ ┌───────┐ │ ┌───┐ ┌───┐ │ │ └───┐ ┌───┐ └───┐ ┌───┘ │
12 · │ · │ · · │ · │ · │ 3 │ · │ 3 │ 2 │ 3 │ · · │ 2 │ · │ 1 · │ · │ · · │
┌───┘ │ ┌───┘ └───┘ │ │ │ └───┘ ┌───┘ │ │ ┌───┘ └───┐ │
13│ 2 2 │ · │ 3 0 · · │ 3 │ · │ · 2 · │ · · │ · │ 2 │ 2 · 3 │ · │
│ ┌───┘ └───┐ ┌───┐ └───┘ └───────────┘ ┌───┘ │ │ ┌───────┘ │
14│ · │ 2 0 · │ · │ 3 │ · 1 · · 2 · 2 │ 2 · │ · │ · │ 2 · 2 │
│ │ ┌───┘ │ │ ┌───────────────────┘ └───┘ │ ┌───────┘
15│ · │ · 1 │ 3 1 │ · │ · · │ · · 2 · 2 1 · 1 2 │ 2 │ · ·
│ └───┐ └───┐ │ └───┐ │ ┌───────────────────┐ ┌───┘ └───────┐
16│ 2 · │ 2 2 │ · │ 1 3 │ · │ 2 · │ 3 1 2 · 3 │ 2 │ · 1 1 · │
└───┐ └───┐ └───┘ ┌───┘ └───┐ └───┐ ┌───────────┘ └───────┐ ┌───┘
17 · │ · 2 │ · 1 · │ · · 2 │ · · │ · │ 2 · 1 0 · · │ · │ 3
└───┐ └───┐ ┌───┘ ┌───┐ │ │ │ ┌───┐ ┌───┐ │ └───┐
18 · 2 │ · · │ 2 │ · 2 │ 3 │ 2 │ · 2 │ 2 │ · │ 3 │ 2 2 │ 3 │ 3 │ 1 · │
└───┐ │ │ ┌───┘ │ └───────┘ └───┘ └───────┘ └───┘ │
19 0 0 · │ 3 │ 2 │ · │ · · │ · · 2 1 2 1 · · · 2 1 · │
└───┘ └───┘ └───────────────────────────────────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 2.39 seconds
Solved puzzle
Applying the solution to the puzzle visually:
Rectangles (Puzzle Type #42)
Also known as Shikaku or CellBlocks.
Rules
You have a grid of squares, with numbers written in some (but not all) of the squares. Your task is to subdivide the grid into rectangles of various sizes, such that both:
- (a) every rectangle contains exactly one numbered square
- (b) the area of each rectangle is equal to the number written in its numbered square.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import rectangles_solver as solver
board = np.array([
['3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '15',' ', ' ', ' ', ' ' ],
[' ', ' ', '2', '2', ' ', ' ', ' ', ' ', ' ', ' ', '11',' ', ' ', ' ', ' ', ' ', ' ', '3', '2' ],
[' ', ' ', ' ', ' ', '2', ' ', ' ', ' ', '11',' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ' ],
[' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', '6', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '28','4', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '10',' ', '10',' ', ' ', ' ', ' ', '45',' ' ],
[' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', '22',' ', ' ', ' ', ' ', ' ', '28',' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '17'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', '8', '3', ' ', ' ', '2', '2', ' ', ' ', ' ', '5', ' ', ' ', '4', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', '4', ' ', ' ', '8', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ' ],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
['2', ' ', ' ', ' ', '12',' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
['2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ' ],
[' ', ' ', '3', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '60',' ', ' ', ' ', ' ', ' ', '4', ' ' ],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8
┌───────────┬───────────────────────────────────────────────────────────┬───┐
0│ 3 │ 15 │ │
├───────┬───┼───┬───────────────────────────────────────────┬───────────┤ │
1│ │ 2 │ 2 │ 11 │ 3 │ 2 │
│ │ │ ├───┬───────────────────────────────────────┴───┬───────┼───┤
2│ │ │ │ 2 │ 11 │ 2 │ │
│ ├───┴───┤ ├───────────────────────┬───┬───┬───────────┴───────┤ │
3│ │ 2 │ │ 6 │ │ │ │ │
│ ├───────┴───┴───────────────┬───┬───┤ │ │ │ │
4│ │ │ │ │ 3 │ │ │ │
│ │ │ │ │ │ │ │ │
5│ │ │ │ 2 │ │ │ │ │
│ │ │ ├───┴───┤ │ │ │
6│ │ │ │ 2 │ │ │ │
│ │ │ ├───────┤ │ │ │
7│ │ 28 │ 4 │ │ │ │ │
│ ├───┬───────────────────────┴───┤ │ │ │ │
8│ │ │ │10 │10 │ 45 │ │
│ │ │ │ │ │ │ │
9│ │ 3 │ │ │ │ │ │
│ │ │ │ │ │ │ │
10│ 22 │ │ 28 │ │ │ │17 │
│ ├───┤ │ │ │ │ │
11│ │ │ │ │ │ │ │
├───────┤ ├───────┬───┬───┬───────────┴───────┤ ├───────────────┬───┤ │
12│ 8 │ 3 │ │ 2 │ 2 │ 5 │ │ 4 │ │ │
│ │ │ │ │ ├───────────────────┴───┴───────┬───────┤ │ │
13│ │ │ 4 │ │ │ 8 │ 2 │ │ │
│ ├───┴───────┼───┴───┴───────────────────────────────┴───────┤ │ │
14│ │ │ │ 3 │ │
│ │ │ ├───┤ │
15│ │ │ │ │ │
├───────┤ │ │ │ │
16│ 2 │ 12 │ │ │ │
├───────┤ │ │ │ │
17│ 2 │ │ │ │ │
├───────┴───┬───────┤ │ │ │
18│ 3 │ 2 │ 60 │ 4 │ │
└───────────┴───────┴───────────────────────────────────────────────┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.01 seconds
Solved puzzle
Applying the solution to the puzzle visually:
Palisade (Puzzle Type #43)
Rules
You're given a grid of N squares and a region size M, some of which contain numbers. Your goal is to subdivide the grid into (N/M) contiguous regions, where every region is of size M, such that each square containing a number is adjacent to exactly that many edges (including those between the inside and the outside of the grid).
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note: it takes a few seconds for the model to be built if the region size is larger than 8 and around 10 seconds for a region size of 10)
import numpy as np
from puzzle_solver import palisade_solver as solver
board = np.array([
['2', ' ', ' ', ' ', ' ', '3', ' ', ' ', '1', '1', '3', ' ', ' ', ' ', ' '],
['3', '2', '1', ' ', '2', '3', ' ', ' ', ' ', ' ', ' ', '2', ' ', '0', ' '],
[' ', ' ', ' ', '1', '1', ' ', ' ', '1', ' ', ' ', ' ', '1', ' ', ' ', ' '],
[' ', '3', '2', ' ', ' ', ' ', ' ', '2', '3', ' ', ' ', ' ', '1', ' ', ' '],
[' ', '0', '1', ' ', '2', ' ', ' ', '0', ' ', ' ', ' ', '1', ' ', '3', '2'],
['1', '0', ' ', ' ', ' ', '2', '2', ' ', '2', ' ', '3', ' ', '0', '2', ' '],
[' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' '],
[' ', '1', ' ', ' ', ' ', '3', '1', ' ', '1', ' ', ' ', ' ', ' ', '1', ' '],
[' ', ' ', ' ', '0', ' ', ' ', '0', ' ', ' ', '1', '2', ' ', ' ', ' ', '3'],
[' ', ' ', ' ', ' ', ' ', ' ', '1', ' ', ' ', '2', ' ', ' ', '1', '2', '1'],
[' ', ' ', ' ', ' ', '1', ' ', '2', '3', '1', ' ', ' ', ' ', '2', ' ', '1'],
['2', ' ', '1', ' ', '2', '2', '1', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board, region_size=10)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───────────────────┬───────────────────────┬───────────────┐
0│ 2 · · · · │ 3 · · 1 1 3 │ · · · · │
│ ┌───────────┐ ├───────┬───┐ ┌───┴───┐ │
1│ 3 │ 2 1 · │ 2 │ 3 · │ · │ · · │ · 2 │ · 0 · │
├───┘ │ └───┐ │ └───┐ └───┐ └───┐ │
2│ · · · 1 │ 1 · │ · │ 1 · │ · · │ 1 · │ · · │
│ ┌───┐ │ ┌───┘ │ ┌───┴───────┘ └───┐ │
3│ · │ 3 │ 2 · │ · │ · · │ 2 │ 3 · · · 1 · │ · │
├───┘ └───────┼───┘ ┌───┘ └───┬───────────────┬───┴───┤
4│ · 0 1 · │ 2 · │ · 0 · │ · · 1 · │ 3 2 │
│ ┌───┘ │ │ ┌───┐ └───┐ │
5│ 1 0 · │ · · 2 │ 2 · 2 │ · │ 3 │ · 0 2 │ · │
│ ┌───┴───────────┼───┬───────┴───┤ ├───┐ │ │
6│ · · │ · · · 3 │ · │ · · 2 │ · │ · │ · · │ · │
├───────┘ ┌───────────┤ └───┐ │ │ └───────┘ │
7│ · 1 · │ · · 3 │ 1 · │ 1 · │ · │ · · 1 · │
│ ┌───┘ ┌───┘ │ │ └───────┐ ┌───┤
8│ · · │ · 0 · │ · 0 · │ · 1 │ 2 · · │ · │ 3 │
│ ┌───┘ ┌───┤ ├───┐ └───┐ ├───┘ │
9│ · │ · · · │ · │ · 1 · │ · │ 2 · │ · 1 │ 2 1 │
├───┤ ┌───────┘ ├───────┐ │ └───┐ │ │ │
10│ · │ · │ · · 1 │ · 2 │ 3 │ 1 · │ · │ · 2 │ · 1 │
│ └───┘ │ └───┘ ├───┴───────┘ │
11│ 2 · 1 · 2 │ 2 1 · · 2 │ · · · · · │
└───────────────────┴───────────────────┴───────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 11.94 seconds
Solved puzzle
Applying the solution to the puzzle visually:
Heyawake (Puzzle Type #46)
Rules
You have to color the cells of the grid in black and white according to the rules:
- Regions with a number should contain black cells matching the number.
- 2 black cells cannot be adjacent horizontally or vertically.
- A straight (orthogonal) line of connected white cells cannot span across more than 2 regions.
- All white cells should be connected in a single group.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import heyawake_solver as solver
board = np.array([
['00', '01', '02', '03', '04', '04', '04', '04', '04', '04', '04', '04', '04', '04', '05', '05', '06', '06', '07', '07'],
['00', '08', '02', '03', '09', '09', '10', '10', '10', '11', '11', '12', '12', '12', '05', '05', '06', '06', '07', '07'],
['00', '08', '02', '03', '09', '09', '13', '13', '13', '11', '11', '12', '12', '12', '14', '14', '14', '15', '15', '16'],
['17', '17', '17', '03', '09', '09', '18', '18', '19', '11', '11', '20', '20', '21', '21', '22', '22', '15', '15', '16'],
['17', '17', '17', '23', '23', '23', '23', '23', '19', '11', '11', '24', '24', '21', '21', '25', '25', '25', '25', '26'],
['27', '28', '28', '23', '23', '23', '23', '23', '29', '29', '30', '31', '32', '32', '32', '25', '25', '25', '25', '26'],
['27', '28', '28', '33', '34', '34', '35', '35', '35', '36', '30', '31', '32', '32', '32', '25', '25', '25', '25', '26'],
['27', '28', '28', '33', '34', '34', '35', '35', '35', '37', '37', '31', '32', '32', '32', '25', '25', '25', '25', '38'],
['27', '28', '28', '39', '39', '39', '40', '40', '40', '41', '41', '31', '42', '42', '42', '42', '42', '43', '43', '38'],
['27', '28', '28', '39', '39', '39', '40', '40', '40', '41', '41', '44', '44', '44', '44', '44', '44', '43', '43', '38'],
['27', '45', '45', '39', '39', '39', '46', '46', '47', '41', '41', '44', '44', '44', '44', '44', '44', '48', '48', '48'],
['49', '45', '45', '50', '50', '50', '46', '46', '47', '41', '41', '51', '52', '52', '52', '52', '53', '53', '53', '54'],
['49', '55', '56', '57', '57', '57', '58', '58', '58', '41', '41', '51', '52', '52', '52', '52', '53', '53', '53', '54'],
['49', '55', '59', '57', '57', '57', '58', '58', '58', '60', '60', '61', '61', '62', '62', '63', '63', '63', '63', '54'],
['49', '64', '64', '57', '57', '57', '58', '58', '58', '60', '60', '61', '61', '62', '62', '63', '63', '63', '63', '54'],
['49', '64', '64', '65', '65', '66', '58', '58', '58', '60', '60', '61', '61', '67', '67', '63', '63', '63', '63', '54'],
['49', '64', '64', '65', '65', '66', '58', '58', '58', '60', '60', '61', '61', '67', '67', '68', '68', '69', '70', '54'],
['49', '71', '71', '72', '72', '72', '73', '74', '74', '74', '75', '76', '76', '67', '67', '68', '68', '69', '77', '54'],
['49', '71', '71', '72', '72', '72', '73', '74', '74', '74', '75', '78', '78', '78', '78', '79', '80', '80', '77', '54'],
['81', '81', '81', '81', '81', '81', '81', '82', '82', '82', '75', '83', '83', '83', '83', '79', '80', '80', '77', '54']
])
region_to_clue = {
'04': 4, '09': 0, '06': 0, '16': 0, '13': 2, '24': 0, '32': 5, '27': 3, '34': 0,
'39': 3, '37': 0, '41': 3, '38': 2, '43': 0, '44': 4, '54': 3, '53': 2, '70': 1,
'80': 2, '67': 1, '83': 2, '82': 2, '73': 0, '72': 1, '71': 2, '64': 1, '56': 1,
'45': 0, '57': 2, '58': 5, '66': 0, '60': 3, '61': 2
}
binst = solver.Board(board=board, region_to_clue=region_to_clue)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
┌───┬───┬───┬───┬───────────────────────────────────────┬───────┬───────┬───────┐
0│ │ │▒▒▒│ │ 4 ▒▒▒ 4 ▒▒▒ 4 4 ▒▒▒ 4 ▒▒▒ 4 │ ▒▒▒│ 0 0 │ │
│ ├───┤ │ ├───────┬───────────┬───────┬───────────┤ │ │ │
1│▒▒▒│ │ │▒▒▒│ 0 0 │ │▒▒▒ │ │▒▒▒ │ 0 0 │▒▒▒ │
│ │ │ │ │ ├───────────┤ │ ├───────┴───┬───┴───┬───┤
2│ │ │▒▒▒│ │ 0 0 │▒▒▒ 2 ▒▒▒│ │ ▒▒▒ │ ▒▒▒ │▒▒▒ │ 0 │
├───┴───┴───┤ │ ├───────┬───┤ ├───────┬───┴───┬───────┤ │ │
3│ ▒▒▒ │▒▒▒│ 0 0 │ ▒▒▒│ │ │▒▒▒ │▒▒▒ │ ▒▒▒│ │ 0 │
│ ├───┴───────┴───────┤ │ ├───────┤ ├───────┴───────┼───┤
4│ │ ▒▒▒ │▒▒▒│ ▒▒▒│ 0 0 │ │▒▒▒ │▒▒▒│
├───┬───────┤ ├───┴───┬───┼───┬───┴───────┤ │ │
5│▒▒▒│ │ ▒▒▒ │ ▒▒▒│ │ │▒▒▒ 5 ▒▒▒│ ▒▒▒│ │
│ │ ├───┬───────┬───────┴───┬───┤ │ │ │ │ │
6│ 3 │ ▒▒▒│ │ 0 0 │▒▒▒ │ │▒▒▒│ │ 5 ▒▒▒ 5 │ ▒▒▒ │ │
│ │ │ │ │ ├───┴───┤ │ │ ├───┤
7│▒▒▒│ │▒▒▒│ 0 0 │ ▒▒▒│ 0 0 │ │▒▒▒ 5 ▒▒▒│ ▒▒▒ │▒▒▒│
│ │ ├───┴───────┼───────────┼───────┤ ├───────────┴───────┬───────┤ │
8│ 3 │ ▒▒▒│ 3 ▒▒▒ 3 │ ▒▒▒ │▒▒▒ 3 │▒▒▒│ ▒▒▒│ 0 0 │ 2 │
│ │ │ │ │ ├───┴───────────────────┤ │ │
9│ 3 │▒▒▒ │ 3 3 ▒▒▒│ │ 3 ▒▒▒│ 4 4 ▒▒▒ 4 ▒▒▒ 4 │ 0 0 │▒▒▒│
│ ├───────┤ ├───────┬───┤ │ ├───────┴───┤
10│▒▒▒│ 0 0 │ 3 ▒▒▒ 3 │▒▒▒ │ │▒▒▒ 3 │▒▒▒ 4 4 ▒▒▒ 4 4 │ ▒▒▒ │
├───┤ ├───────────┤ │ │ ├───┬───────────────┬───┴───────┬───┤
11│ │ 0 0 │▒▒▒ │ │▒▒▒│ 3 3 │ │▒▒▒ ▒▒▒│ 2 ▒▒▒ 2 │ 3 │
│ ├───┬───┼───────────┼───────┴───┤ │ │ │ │ │
12│ │ │▒▒▒│ 2 2 ▒▒▒│ 5 ▒▒▒ 5 │ 3 3 │▒▒▒│ │▒▒▒ 2 2 │▒▒▒│
│ │ ├───┤ │ ├───────┼───┴───┬───────┬───┴───────────┤ │
13│ │▒▒▒│ │ 2 2 2 │▒▒▒ 5 5 │▒▒▒ 3 │ 2 2 │▒▒▒ │ ▒▒▒ │ 3 │
│ ├───┴───┤ │ │ │ │ │ │ │
14│ │ 1 ▒▒▒│ 2 2 ▒▒▒│ 5 ▒▒▒ 5 │ 3 ▒▒▒│ 2 2 │ ▒▒▒│ │▒▒▒│
│ │ ├───────┬───┤ │ │ ├───────┤ │ │
15│▒▒▒│ 1 1 │ ▒▒▒│ 0 │ 5 5 5 │▒▒▒ 3 │▒▒▒ 2 │ 1 1 │▒▒▒ │ 3 │
│ │ │ │ │ │ │ │ ├───────┬───┬───┤ │
16│ │ 1 1 │▒▒▒ │ 0 │▒▒▒ 5 ▒▒▒│ 3 3 │ 2 ▒▒▒│ 1 1 │ ▒▒▒│ │▒▒▒│ 3 │
│ ├───────┼───────┴───┼───┬───────┴───┬───┼───────┤ │ │ ├───┤ │
17│ │ 2 ▒▒▒│ 1 1 1 │ 0 │▒▒▒ │ │▒▒▒ │▒▒▒ 1 │ │▒▒▒│ │ 3 │
│ │ │ │ │ │ ├───────┴───────┼───┬───┴───┤ │ │
18│ │▒▒▒ 2 │ 1 1 ▒▒▒│ 0 │ │▒▒▒│ │ │▒▒▒ 2 │ │▒▒▒│
├───┴───────┴───────────┴───┼───────────┤ ├───────────────┤ │ │ │ │
19│ ▒▒▒ │▒▒▒ 2 ▒▒▒│ │ 2 ▒▒▒ 2 ▒▒▒│ │ 2 ▒▒▒│ │ 3 │
└───────────────────────────┴───────────┴───┴───────────────┴───┴───────┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 6.72 seconds
Solved puzzle
Shingoki (Puzzle Type #47)
Also known as Semaphores.
Rules
You have to draw lines between the dots to form a single loop without crossings or branches. The loop should pass through all black and white circles in such a way that:
- White circles must be passed through in a straight line
- Black circles must be turned upon
- The numbers in the circles show the sum of the lengths of the 2 straight lines going out of that circle.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import shingoki_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', '4B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '5B', ' ', ' ', '2B', ' ', ' ', '3B', ' ', ' ', ' ', '3W', ' ', ' ', ' ', ' ', '2B', ' '],
['2B', '2B', ' ', '2W', ' ', ' ', ' ', ' ', ' ', ' ', '2B', ' ', '2B', ' ', ' ', ' ', '3B', '5W', ' ', ' ', '11W'],
[' ', ' ', ' ', ' ', ' ', '3B', ' ', '3B', ' ', ' ', ' ', ' ', '2B', ' ', ' ', ' ', ' ', ' ', '3W', ' ', ' '],
[' ', '2W', ' ', ' ', '2B', ' ', '2W', ' ', '3W', ' ', '2W', '2B', '2B', ' ', ' ', ' ', ' ', ' ', ' ', '8W', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '6B', ' ', ' ', ' ', ' ', '4B', '2W', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '2B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2W', ' ', ' ', ' ', '4B', ' ', ' '],
[' ', '2B', '2W', ' ', ' ', ' ', '3B', ' ', ' ', ' ', ' ', '3W', ' ', ' ', ' ', ' ', ' ', ' ', '3B', ' ', ' '],
['4W', '3B', ' ', ' ', '3W', ' ', ' ', ' ', ' ', ' ', '3B', ' ', '6B', ' ', ' ', ' ', '2B', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2W', '7B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '3W', ' ', '3W', '4W', '5B', ' ', ' ', ' ', ' ', '5W', ' ', '4W', ' ', ' ', ' ', '2W', ' ', ' '],
['7B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3B', ' '],
[' ', ' ', ' ', ' ', '2B', ' ', '4W', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '5B', ' ', ' ', ' '],
[' ', ' ', '2W', ' ', ' ', '2B', ' ', '4W', '3W', ' ', ' ', ' ', ' ', ' ', ' ', '5B', '2B', ' ', '3W', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3B', ' ', '7W', ' ', '2B', '5B', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', '3B', '2B', ' ', ' ', ' ', '3W', ' ', '2B', ' ', ' ', ' ', '2W', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '2W', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3B', ' '],
[' ', '4W', ' ', ' ', '2B', '3B', ' ', ' ', ' ', '2B', '4B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3W', ' ', ' '],
['7W', ' ', '3B', ' ', ' ', '2B', ' ', ' ', ' ', '4B', ' ', ' ', ' ', ' ', '2W', '3B', ' ', '2B', ' ', ' ', ' '],
[' ', ' ', ' ', '3W', ' ', '3W', ' ', ' ', '2B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3W', ' ', '2W', ' ', ' '],
[' ', '2B', ' ', ' ', ' ', ' ', '5W', ' ', ' ', ' ', ' ', '5W', ' ', ' ', ' ', '6B', ' ', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Note that the solver is much slower for large puzzles like this example and take ~3 minutes to find a valid solution and ~7 minutes to verify that no other solutions exist.
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
0 . . . . . 4B───────────┐ ┌───────────────────────────┐ ┌───┐ ┌───┐
│ │ │ │ │ │ │ │
1 ┌──────────────5B └───┐ 2B───┘ │ 3B───────┐ ┌──3W───────┘ │ └──2B │
│ │ │ │ │ │ │ │ │ │
2 2B──2B ┌──2W───┘ ┌───┘ └───┐ │ 2B───┐ 2B───┘ . ┌──3B 5W ┌───┐ 11W
│ │ │ │ │ │ │ │ │ │ │ │
3 ┌───┘ └───┐ . 3B──────3B │ │ ┌───┘ 2B───┐ ┌───┘ │ │ 3W │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │
4 └──2W───┐ └──2B ┌──2W───┘ 3W │ 2W 2B──2B └───┘ ┌───┘ │ │ 8W │
│ │ │ │ │ │ │ │ │ │ │ │
5 ┌───────┘ ┌───┘ └───────┐ └──6B └───┘ ┌──────4B 2W . └───┘ │ │
│ │ │ │ │ │ │ │
6 └───┐ ┌──2B . ┌───┐ └───────────────────┘ . 2W └──────────4B │ │
│ │ │ │ │ │ │ │
7 ┌──2B 2W . ┌───┘ 3B───────┐ . ┌──3W───────┐ └───┐ ┌──────3B │ │
│ │ │ │ │ │ │ │ │ │
8 4W 3B───┘ . 3W ┌───────┐ └──────3B ┌──6B │ ┌───┘ 2B───┐ . │ │
│ │ │ │ │ │ │ │ │ │ │ │
9 │ │ . . │ │ ┌───┘ ┌──2W──7B │ │ │ │ ┌───┐ │ . │ │
│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
10 │ └──────3W───┘ 3W 4W 5B───┘ . │ │ 5W │ 4W │ │ └──2W───┘ │
│ │ │ │ │ │ │ │ │ │ │ │
11 7B───────────┐ ┌───┘ │ │ . . │ │ │ │ │ │ └───────┐ 3B───┘
│ │ │ │ │ │ │ │ │ │ │ │
12 ┌───┐ . └──2B . 4W │ ┌───┐ │ │ │ └───┘ │ ┌──5B │ │ .
│ │ │ │ │ │ │ │ │ │ │ │ │ │
13 │ └──2W───┐ . 2B───┘ 4W 3W │ │ │ └───┐ . 5B──2B │ 3W └───┐
│ │ │ │ │ │ │ │ │ │ │ │
14 │ ┌───┐ │ . └───────┘ │ 3B───┘ 7W ┌──2B 5B───────┐ │ └───┐ │
│ │ │ │ │ │ │ │ │ │ │ │
15 │ │ │ └──────3B 2B───┐ └──────3W───┘ 2B───┐ │ . 2W │ ┌───┘ │
│ │ │ │ │ │ │ │ │ │ │ │
16 │ │ └──2W───┐ └───┘ │ . ┌───┐ . . │ │ . └───┘ │ 3B───┘
│ │ │ │ │ │ │ │ │ │
17 │ 4W . ┌──2B 3B───────┘ ┌──2B 4B───────────┘ └───┐ ┌───┐ 3W │ .
│ │ │ │ │ │ │ │ │ │
18 7W └──3B │ ┌──2B . ┌───┘ 4B───────────┐ ┌──2W──3B │ 2B───┘ └───┐
│ │ │ │ │ │ │ │ │ │
19 └───┐ │ 3W └──3W───────┘ 2B───┘ ┌───────┘ └───────┐ 3W ┌──2W───┐ │
│ │ │ │ │ │ │ │ │ │
20 . 2B───┘ └──────────5W───────┘ . └──5W──────────────6B └───┘ . └───┘
Solutions found: 1
status: OPTIMAL
Time taken: 72.80 seconds
Solved puzzle
Shakashaka (Puzzle Type #50)
Also known as Proof of Quilt.
Rules
Shakashaka is played on a rectangular grid. The grid has both black cells and white cells in it. The objective is to place black triangles in the white cell in such a way so that they form white rectangular (or square) areas.
- The triangles are right angled and occupy half of the white square divided diagonally.
- You can place triangles only in white cells
- The numbers in the black cells indicate how many triangles are adjacent, vertically and horizontally.
- The white rectangles can be either straight or rotated at 45°
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import shakashaka_solver as solver
board = np.array([
[' ', ' ', 'B', ' ', '1', ' ', ' ', '1', ' ', ' ', 'B', 'B', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', 'B', ' ', 'B', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', 'B'],
['1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' ', ' ', ' ', ' '],
[' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' '],
[' ', ' ', ' ', '1', ' ', ' ', '2', ' ', ' ', ' ', ' ', 'B', ' ', '3', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', '4', ' ', ' ', ' ', 'B'],
[' ', 'B', '2', ' ', ' ', 'B', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' ', ' '],
['B', ' ', ' ', ' ', ' ', 'B', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['0', ' ', ' ', 'B', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', 'B', 'B', 'B', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', 'B'],
['0', ' ', ' ', 'B', ' ', ' ', ' ', 'B', ' ', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2', ' ', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', 'B', ' ', 'B', ' ', 'B', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '4', ' ', ' ', '3', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', '4', ' ', ' ', ' ', ' '],
[' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', '3', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', '3'],
['B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '4', ' ', ' ', ' '],
[' ', ' ', 'B', ' ', 'B', ' ', ' ', '2', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '0', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' '],
['B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '2', 'B', ' ', ' ', '2', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' ', '1', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '3', ' ', ' ', ' ', '2', ' ', ' ', '1', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', 'B', ' ', ' ', ' ', ' '],
[' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', 'B', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', '2'],
['2', ' ', ' ', 'B', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'B', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '3', ' ', ' ', ' ', ' ', ' ', '2', ' ', ' ', ' ', ' ', '0', ' ', ' ', ' ', ' ', ' ', '2', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
(Note: It took so long to find a good text-based visualization to the solution that is both readable and looks good, this isn't the best but it finally does the job)
Solution found
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ /█│█\ │ │██████│ │ /█│█\ │ │██████│██████│ │ │██████│ /█│█\ │ │██████│ /█│█\ │██████│ │██████│ │ /█│█\ │
│ /███│███\ │ . │██████│ 1 │ /███│███\ │ 1 │██████│██████│ . │ . │██████│ /███│███\ │ 2 │██████│ /███│███\ │██████│ . │██████│ . │ /███│███\ │
│/█████│█████\│ │██████│ │/█████│█████\│ │██████│██████│ │ │██████│/█████│█████\│ │██████│/█████│█████\│██████│ │██████│ │/█████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│\█████│█████/│ /█│█\ │██████│\█████│█████/│██████│ /█│█\ │██████│ │██████│\█████│██████│█\ │ │\█████│██████│█\ │██████│ /█│█\ │\█████│█████/│
│ \███│███/ │ /███│███\ │██████│ \███│███/ │██████│ /███│███\ │██████│ . │██████│ \███│██████│███\ │ . │ \███│██████│███\ │██████│ /███│███\ │ \███│███/ │
│ \█│█/ │/█████│█████\│██████│ \█│█/ │██████│/█████│█████\│██████│ │██████│ \█│██████│█████\│ │ \█│██████│█████\│██████│/█████│█████\│ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│ /█│██████│██████│█\ │ /█│█\ │ │\█████│██████│█\ │██████│ /█│█\ │\█████│██████│█\ │ │\█████│█████/│ /█│██████│██████│█\ │██████│
│██████│ /███│██████│██████│███\ │ /███│███\ │ 3 │ \███│██████│███\ │██████│ /███│███\ │ \███│██████│███\ │ 4 │ \███│███/ │ /███│██████│██████│███\ │██████│
│██████│/█████│██████│██████│█████\│/█████│█████\│ │ \█│██████│█████\│██████│/█████│█████\│ \█│██████│█████\│ │ \█│█/ │/█████│██████│██████│█████\│██████│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│\█████│██████│██████│█████/│\█████│█████/│ /█│█\ │\█████│█████/│ │\█████│█████/│██████│\█████│██████│█\ │ │██████│\█████│██████│██████│█████/│ │
│██████│ \███│██████│██████│███/ │ \███│███/ │ /███│███\ │ \███│███/ │ . │ \███│███/ │██████│ \███│██████│███\ │ 3 │██████│ \███│██████│██████│███/ │ . │
│██████│ \█│██████│██████│█/ │ \█│█/ │/█████│█████\│ \█│█/ │ │ \█│█/ │██████│ \█│██████│█████\│ │██████│ \█│██████│██████│█/ │ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│\█████│█████/│ /█│█\ │ /█│██████│█████/│██████│ │ /█│█\ │ /█│█\ │██████│\█████│█████/│ /█│█\ │ │\█████│█████/│██████│██████│
│ 1 │██████│ \███│███/ │ /███│███\ │ /███│██████│███/ │██████│ 2 │ /███│███\ │ /███│███\ │██████│ \███│███/ │ /███│███\ │ 4 │ \███│███/ │██████│██████│
│ │██████│ \█│█/ │/█████│█████\│/█████│██████│█/ │██████│ │/█████│█████\│/█████│█████\│██████│ \█│█/ │/█████│█████\│ │ \█│█/ │██████│██████│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ /█│█\ │ │██████│\█████│█████/│\█████│█████/│ /█│█\ │██████│\█████│█████/│\█████│█████/│ /█│█\ │██████│\█████│█████/│ /█│█\ │ │ /█│█\ │
│ /███│███\ │ 3 │██████│ \███│███/ │ \███│███/ │ /███│███\ │██████│ \███│███/ │ \███│███/ │ /███│███\ │██████│ \███│███/ │ /███│███\ │ . │ /███│███\ │
│/█████│█████\│ │██████│ \█│█/ │ \█│█/ │/█████│█████\│██████│ \█│█/ │ \█│█/ │/█████│█████\│██████│ \█│█/ │/█████│█████\│ │/█████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│\█████│██████│█\ │ │██████│██████│ │ /█│██████│██████│█\ │ │██████│ │ /█│██████│█████/│ │ /█│█\ │\█████│██████│█\ │\█████│█████/│
│ \███│██████│███\ │ 1 │██████│██████│ 2 │ /███│██████│██████│███\ │ . │██████│ 3 │ /███│██████│███/ │ . │ /███│███\ │ \███│██████│███\ │ \███│███/ │
│ \█│██████│█████\│ │██████│██████│ │/█████│██████│██████│█████\│ │██████│ │/█████│██████│█/ │ │/█████│█████\│ \█│██████│█████\│ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│\█████│█████/│ │██████│██████│ │\█████│██████│██████│█████/│██████│ /█│█\ │\█████│█████/│ │██████│\█████│█████/│ │\█████│█████/│██████│ │
│██████│ \███│███/ │ . │██████│██████│ . │ \███│██████│██████│███/ │██████│ /███│███\ │ \███│███/ │ 3 │██████│ \███│███/ │ 4 │ \███│███/ │██████│ . │
│██████│ \█│█/ │ │██████│██████│ │ \█│██████│██████│█/ │██████│/█████│█████\│ \█│█/ │ │██████│ \█│█/ │ │ \█│█/ │██████│ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│ │ │ /█│█\ │ │██████│██████│\█████│█████/│ │ /█│██████│█████/│ │██████│ /█│█\ │ /█│█\ │ /█│█\ │ │ /█│█\ │
│██████│ . │ 2 │ /███│███\ │ . │██████│██████│ \███│███/ │ 3 │ /███│██████│███/ │ 2 │██████│ /███│███\ │ /███│███\ │ /███│███\ │ 4 │ /███│███\ │
│██████│ │ │/█████│█████\│ │██████│██████│ \█│█/ │ │/█████│██████│█/ │ │██████│/█████│█████\│/█████│█████\│/█████│█████\│ │/█████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│██████│\█████│█████/│ │██████│██████│ │██████│██████│\█████│█████/│██████│██████│ /█│██████│█████/│\█████│█████/│\█████│█████/│ /█│██████│█████/│
│ . │██████│██████│ \███│███/ │ . │██████│██████│ 1 │██████│██████│ \███│███/ │██████│██████│ /███│██████│███/ │ \███│███/ │ \███│███/ │ /███│██████│███/ │
│ │██████│██████│ \█│█/ │ │██████│██████│ │██████│██████│ \█│█/ │██████│██████│/█████│██████│█/ │ \█│█/ │ \█│█/ │/█████│██████│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│██████│ │ /█│█\ │██████│██████│ │ /█│█\ │██████│ │ │ │\█████│█████/│ /█│█\ │ │██████│ /█│██████│█████/│ │
│ 0 │██████│██████│ . │ /███│███\ │██████│██████│ . │ /███│███\ │██████│ . │ . │ . │ \███│███/ │ /███│███\ │ 3 │██████│ /███│██████│███/ │ . │
│ │██████│██████│ │/█████│█████\│██████│██████│ │/█████│█████\│██████│ │ │ │ \█│█/ │/█████│█████\│ │██████│/█████│██████│█/ │ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│██████│ │\█████│██████│█\ │ │ /█│██████│█████/│ │██████│ /█│█\ │██████│ /█│██████│██████│█\ │██████│\█████│█████/│ │██████│
│ 0 │██████│██████│ . │ \███│██████│███\ │ . │ /███│██████│███/ │ 1 │██████│ /███│███\ │██████│ /███│██████│██████│███\ │██████│ \███│███/ │ 3 │██████│
│ │██████│██████│ │ \█│██████│█████\│ │/█████│██████│█/ │ │██████│/█████│█████\│██████│/█████│██████│██████│█████\│██████│ \█│█/ │ │██████│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│ /█│█\ │ /█│█\ │\█████│██████│█\ │\█████│█████/│ │██████│ │\█████│█████/│ │\█████│██████│██████│██████│█\ │ │ /█│█\ │██████│
│██████│ /███│███\ │ /███│███\ │ \███│██████│███\ │ \███│███/ │ 2 │██████│ . │ \███│███/ │ . │ \███│██████│██████│██████│███\ │ . │ /███│███\ │██████│
│██████│/█████│█████\│/█████│█████\│ \█│██████│█████\│ \█│█/ │ │██████│ │ \█│█/ │ │ \█│██████│██████│██████│█████\│ │/█████│█████\│██████│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ /█│██████│█████/│\█████│█████/│ │\█████│█████/│ │██████│ │██████│ │██████│ │ /█│█\ │\█████│██████│██████│█████/│██████│\█████│██████│█\ │
│ /███│██████│███/ │ \███│███/ │ . │ \███│███/ │ . │██████│ . │██████│ . │██████│ . │ /███│███\ │ \███│██████│██████│███/ │██████│ \███│██████│███\ │
│/█████│██████│█/ │ \█│█/ │ │ \█│█/ │ │██████│ │██████│ │██████│ │/█████│█████\│ \█│██████│██████│█/ │██████│ \█│██████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│\█████│█████/│ /█│█\ │ │ /█│█\ │ │██████│ │██████│ /█│█\ │ /█│█\ │\█████│█████/│ │\█████│█████/│ │ /█│█\ │\█████│█████/│
│ \███│███/ │ /███│███\ │ 4 │ /███│███\ │ 3 │██████│ . │██████│ /███│███\ │ /███│███\ │ \███│███/ │ . │ \███│███/ │ 4 │ /███│███\ │ \███│███/ │
│ \█│█/ │/█████│█████\│ │/█████│█████\│ │██████│ │██████│/█████│█████\│/█████│█████\│ \█│█/ │ │ \█│█/ │ │/█████│█████\│ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│ │\█████│██████│█\ │\█████│█████/│ /█│█\ │██████│ │\█████│█████/│\█████│█████/│ │ /█│█\ │ │ /█│█\ │\█████│██████│█\ │ │
│██████│ . │ \███│██████│███\ │ \███│███/ │ /███│███\ │██████│ . │ \███│███/ │ \███│███/ │ 3 │ /███│███\ │ . │ /███│███\ │ \███│██████│███\ │ 3 │
│██████│ │ \█│██████│█████\│ \█│█/ │/█████│█████\│██████│ │ \█│█/ │ \█│█/ │ │/█████│█████\│ │/█████│█████\│ \█│██████│█████\│ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│██████│\█████│█████/│██████│██████│\█████│█████/│ │ /█│█\ │██████│ │██████│██████│\█████│██████│█\ │\█████│█████/│ │\█████│██████│█\ │
│ . │██████│██████│ \███│███/ │██████│██████│ \███│███/ │ . │ /███│███\ │██████│ 1 │██████│██████│ \███│██████│███\ │ \███│███/ │ 4 │ \███│██████│███\ │
│ │██████│██████│ \█│█/ │██████│██████│ \█│█/ │ │/█████│█████\│██████│ │██████│██████│ \█│██████│█████\│ \█│█/ │ │ \█│██████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ /█│█\ │ │██████│ │██████│██████│ │██████│ /█│██████│██████│█\ │ │██████│██████│ │\█████│█████/│ │ /█│█\ │██████│\█████│█████/│
│ /███│███\ │ . │██████│ . │██████│██████│ 2 │██████│ /███│██████│██████│███\ │ . │██████│██████│ . │ \███│███/ │ . │ /███│███\ │██████│ \███│███/ │
│/█████│█████\│ │██████│ │██████│██████│ │██████│/█████│██████│██████│█████\│ │██████│██████│ │ \█│█/ │ │/█████│█████\│██████│ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│\█████│█████/│██████│ /█│█\ │██████│██████│ /█│█\ │\█████│██████│██████│██████│█\ │██████│██████│ │██████│ /█│█\ │\█████│█████/│ │ /█│█\ │
│ \███│███/ │██████│ /███│███\ │██████│██████│ /███│███\ │ \███│██████│██████│██████│███\ │██████│██████│ 0 │██████│ /███│███\ │ \███│███/ │ . │ /███│███\ │
│ \█│█/ │██████│/█████│█████\│██████│██████│/█████│█████\│ \█│██████│██████│██████│█████\│██████│██████│ │██████│/█████│█████\│ \█│█/ │ │/█████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │██████│ /█│██████│█████/│██████│██████│\█████│█████/│ │\█████│██████│██████│█████/│██████│██████│ │ /█│██████│█████/│██████│██████│██████│\█████│█████/│
│ . │██████│ /███│██████│███/ │██████│██████│ \███│███/ │ . │ \███│██████│██████│███/ │██████│██████│ . │ /███│██████│███/ │██████│██████│██████│ \███│███/ │
│ │██████│/█████│██████│█/ │██████│██████│ \█│█/ │ │ \█│██████│██████│█/ │██████│██████│ │/█████│██████│█/ │██████│██████│██████│ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│ /█│██████│█████/│ /█│█\ │ │ │██████│██████│ │\█████│█████/│ /█│█\ │ │ /█│██████│█████/│██████│ │ /█│█\ │ /█│█\ │
│██████│ /███│██████│███/ │ /███│███\ │ 2 │ . │██████│██████│ 2 │ \███│███/ │ /███│███\ │ . │ /███│██████│███/ │██████│ 1 │ /███│███\ │ /███│███\ │
│██████│/█████│██████│█/ │/█████│█████\│ │ │██████│██████│ │ \█│█/ │/█████│█████\│ │/█████│██████│█/ │██████│ │/█████│█████\│/█████│█████\│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ /█│██████│█████/│ │\█████│██████│█\ │ │██████│██████│ │ /█│█\ │\█████│█████/│██████│\█████│█████/│ │██████│ │\█████│█████/│\█████│█████/│
│ /███│██████│███/ │ 3 │ \███│██████│███\ │ 2 │██████│██████│ 1 │ /███│███\ │ \███│███/ │██████│ \███│███/ │ . │██████│ . │ \███│███/ │ \███│███/ │
│/█████│██████│█/ │ │ \█│██████│█████\│ │██████│██████│ │/█████│█████\│ \█│█/ │██████│ \█│█/ │ │██████│ │ \█│█/ │ \█│█/ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│\█████│█████/│ │██████│██████│\█████│██████│█\ │██████│██████│ │\█████│██████│█\ │ │ /█│█\ │ │ /█│█\ │██████│██████│ /█│█\ │ │
│ \███│███/ │ . │██████│██████│ \███│██████│███\ │██████│██████│ . │ \███│██████│███\ │ . │ /███│███\ │ . │ /███│███\ │██████│██████│ /███│███\ │ 2 │
│ \█│█/ │ │██████│██████│ \█│██████│█████\│██████│██████│ │ \█│██████│█████\│ │/█████│█████\│ │/█████│█████\│██████│██████│/█████│█████\│ │
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│ │ /█│█\ │ │ /█│█\ │\█████│██████│█\ │ /█│█\ │ │\█████│██████│█\ │\█████│█████/│██████│\█████│█████/│ │ /█│██████│█████/│██████│
│ 2 │ /███│███\ │ . │ /███│███\ │ \███│██████│███\ │ /███│███\ │ 3 │ \███│██████│███\ │ \███│███/ │██████│ \███│███/ │ . │ /███│██████│███/ │██████│
│ │/█████│█████\│ │/█████│█████\│ \█│██████│█████\│/█████│█████\│ │ \█│██████│█████\│ \█│█/ │██████│ \█│█/ │ │/█████│██████│█/ │██████│
├──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┼──────┤
│██████│\█████│█████/│██████│\█████│█████/│ │\█████│█████/│\█████│█████/│██████│ │\█████│█████/│██████│██████│ │██████│██████│██████│\█████│█████/│ │██████│
│██████│ \███│███/ │██████│ \███│███/ │ 3 │ \███│███/ │ \███│███/ │██████│ 2 │ \███│███/ │██████│██████│ 0 │██████│██████│██████│ \███│███/ │ 2 │██████│
│██████│ \█│█/ │██████│ \█│█/ │ │ \█│█/ │ \█│█/ │██████│ │ \█│█/ │██████│██████│ │██████│██████│██████│ \█│█/ │ │██████│
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.36 seconds
Solved puzzle
Sudoku Killer (Puzzle Type #53)
Rules
- The basic Sudoku rules apply.
- The sum of all numbers in a cage must match the small number printed in its corner.
- No number appears more than once in a cage.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note: the ids are arbitrary and simply represent cells that share a cage)
import numpy as np
from puzzle_solver import sudoku_solver as solver
board = np.full((9, 9), ' ')
killer_board = np.array([
['01', '01', '03', '03', '03', '12', '12', '13', '14'],
['02', '01', '04', '16', '16', '17', '17', '13', '14'],
['02', '02', '04', '18', '19', '19', '15', '15', '14'],
['11', '11', '05', '18', '19', '19', '20', '15', '23'],
['10', '10', '05', '30', '31', '32', '20', '22', '23'],
['08', '07', '06', '30', '31', '32', '21', '22', '24'],
['08', '07', '06', '29', '31', '33', '21', '24', '24'],
['09', '34', '34', '29', '28', '33', '26', '26', '25'],
['09', '34', '34', '28', '28', '27', '27', '25', '25'],
])
killer_clues = {
'01': 16, '02': 11, '03': 24, '04': 10, '05': 11, '06': 7, '07': 10, '08': 10, '09': 16,
'10': 11, '11': 10, '12': 7, '13': 11, '14': 16, '15': 16, '16': 8, '17': 12, '18': 8, '19': 15,
'20': 7, '21': 10, '22': 5, '23': 13, '24': 16, '25': 9, '26': 14, '27': 15, '28': 13, '29': 11,
'30': 9, '31': 15, '32': 13, '33': 11, '34': 15,
}
binst = solver.Board(board=board, block_size=(3, 3), killer=(killer_board, killer_clues))
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6 7 8
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│ 5 │ 4 │ 8 │ 7 │ 9 │ 1 │ 6 │ 2 │ 3 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ 3 │ 7 │ 1 │ 6 │ 2 │ 8 │ 4 │ 9 │ 5 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│ 2 │ 6 │ 9 │ 5 │ 4 │ 3 │ 1 │ 7 │ 8 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│ 1 │ 9 │ 4 │ 3 │ 6 │ 2 │ 5 │ 8 │ 7 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│ 8 │ 3 │ 7 │ 1 │ 5 │ 9 │ 2 │ 4 │ 6 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ 6 │ 2 │ 5 │ 8 │ 7 │ 4 │ 3 │ 1 │ 9 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│ 4 │ 8 │ 2 │ 9 │ 3 │ 5 │ 7 │ 6 │ 1 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ 7 │ 1 │ 3 │ 2 │ 8 │ 6 │ 9 │ 5 │ 4 │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│ 9 │ 5 │ 6 │ 4 │ 1 │ 7 │ 8 │ 3 │ 2 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.02 seconds
Solved puzzle
Flood It (Puzzle Type #54)
Rules
The game is a combinatorial puzzle played on a colored N by N grid where the goal is to make the entire grid a single color using the minimum number of moves.
A move consists of picking a new color, which then floods the connected component of the player's current area that has that chosen color.
The player's current area is the top-leftmost corner of the grid along with any similarly colored orthogonal cells connected to the current area.
This game has a lot of interesting mathematical properties related to Graph Theory (for example many details are referenced in this 2022 Graph Theory paper)
Finding an optimal solution for any graph is NP-hard.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note: the ids are arbitrary and simply represent cells that share a cage)
import numpy as np
from puzzle_solver import flood_it_solver as solver
board = np.array([
['B', 'Y', 'G', 'Y', 'R', 'B', 'Y', 'Y', 'G', 'B', 'R', 'P'],
['P', 'G', 'G', 'Y', 'B', 'O', 'Y', 'O', 'B', 'Y', 'R', 'O'],
['B', 'R', 'P', 'Y', 'O', 'R', 'G', 'G', 'G', 'R', 'R', 'Y'],
['O', 'G', 'P', 'G', 'Y', 'Y', 'P', 'P', 'O', 'Y', 'B', 'B'],
['G', 'Y', 'G', 'O', 'R', 'G', 'R', 'P', 'G', 'O', 'B', 'R'],
['R', 'G', 'B', 'G', 'O', 'B', 'O', 'G', 'B', 'O', 'O', 'B'],
['G', 'B', 'P', 'R', 'Y', 'P', 'R', 'B', 'Y', 'B', 'Y', 'P'],
['G', 'B', 'G', 'P', 'O', 'Y', 'R', 'Y', 'P', 'P', 'O', 'G'],
['R', 'P', 'B', 'O', 'B', 'G', 'Y', 'O', 'Y', 'R', 'P', 'O'],
['G', 'P', 'P', 'P', 'P', 'Y', 'G', 'P', 'O', 'G', 'O', 'R'],
['Y', 'Y', 'B', 'B', 'R', 'B', 'O', 'R', 'O', 'O', 'R', 'O'],
['B', 'G', 'B', 'G', 'R', 'B', 'P', 'Y', 'P', 'B', 'R', 'G']
])
solution = solver.solve_minimum_steps(board=board)
Script Output
Trying with exactly 16 moves... Not possible!
Trying with exactly 32 moves... Possible!
Solution: ['Y', 'G', 'B', 'Y', 'B', 'R', 'B', 'Y', 'G', 'Y', 'G', 'B', 'B', 'G', 'Y', 'Y', 'R', 'B', 'Y', 'G', 'Y', 'B', 'Y', 'B', 'Y', 'B', 'G', 'Y', 'B', 'G', 'R', 'Y']
Trying with exactly 24 moves... Possible!
Solution: ['Y', 'G', 'B', 'Y', 'B', 'R', 'B', 'R', 'Y', 'G', 'R', 'Y', 'R', 'B', 'G', 'B', 'G', 'Y', 'G', 'B', 'Y', 'G', 'R', 'Y']
Trying with exactly 20 moves... Possible!
Solution: ['Y', 'G', 'B', 'Y', 'B', 'R', 'B', 'G', 'Y', 'G', 'B', 'G', 'Y', 'B', 'Y', 'R', 'B', 'G', 'R', 'Y']
Trying with exactly 18 moves... Possible!
Solution: ['Y', 'G', 'B', 'Y', 'R', 'B', 'R', 'Y', 'B', 'G', 'R', 'Y', 'R', 'B', 'G', 'R', 'Y', 'B']
Trying with exactly 17 moves... Not possible!
Best Horizon is: T=18
Best solution is: ['Y', 'G', 'B', 'Y', 'R', 'B', 'R', 'Y', 'B', 'G', 'R', 'Y', 'R', 'B', 'G', 'R', 'Y', 'B']
Time taken: 3.10 seconds
Solved puzzle
This picture won't mean much as the game is about the sequence and number of moves not the final frame as shown here.
Note that the solved solution on the bottom left says that only 18 moves were used (based on the above output) despite the website saying 20 total moves are permitted (and the puzzle settings specified 0 extra moves permitted). Thus the solver managed to find a more optimal solution than the website.
Pipes (Puzzle Type #55)
Also known as Net or Network.
Rules
You are given a grid of cells where each cell has 1, 2, 3, or 4 connections to its neighbors. Each cell can be freely rotated in multiple of 90 degrees, thus your can rotate the cells to be one of four possible states.
The goal is to create a single fully connected graph where each cell's connection must be towards another cell's connection. No loose ends or loops are allowed.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
(Note: cells with 1 or 3 active connections only have 1 unique orientation under rotational symmetry. However, cells with 2 active connections can be either a straight line (2I) or curved line (2L))
import numpy as np
from puzzle_solver import pipes_solver as solver
board=np.array([
[ '1 ', '3 ', '3 ', '3 ', '1 ', '1 ', '2L', '2L', '2I', '1 ' ],
[ '1 ', '1 ', '1 ', '3 ', '2I', '1 ', '2I', '3 ', '2I', '1 ' ],
[ '2I', '1 ', '1 ', '3 ', '2L', '1 ', '3 ', '2I', '1 ', '1 ' ],
[ '2I', '2I', '1 ', '3 ', '3 ', '3 ', '2L', '3 ', '3 ', '2L' ],
[ '3 ', '3 ', '2I', '3 ', '1 ', '3 ', '2I', '2L', '1 ', '2L' ],
[ '1 ', '1 ', '3 ', '2I', '3 ', '2L', '1 ', '1 ', '2L', '2L' ],
[ '1 ', '1 ', '3 ', '1 ', '1 ', '1 ', '3 ', '3 ', '3 ', '2L' ],
[ '3 ', '2I', '3 ', '3 ', '2L', '3 ', '3 ', '2I', '2L', '1 ' ],
[ '1 ', '1 ', '3 ', '3 ', '3 ', '3 ', '1 ', '2L', '3 ', '2L' ],
[ '1 ', '2I', '3 ', '2I', '1 ', '1 ', '1 ', '3 ', '1 ', '1 ' ],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
0 O───┬───┬───┬───O O───┐ ┌───────O
│ │ │ │ │
1 O O O ├───────O │ ├───────O
│ │ │ │
2 │ O O───┴───┐ O───┤ │ O O
│ │ │ │ │ │ │
3 │ │ O───┬───┴───┬───┘ ├───┴───┘
│ │ │ │ │
4 ├───┴───────┴───O ├───────┘ O───┐
│ │ │
5 O O───┬───────┬───┘ O O ┌───┘
│ │ │ │ │
6 O O───┤ O O O ├───┴───┴───┐
│ │ │ │ │ │
7 ├───────┴───┤ ┌───┴───┴───────┐ O
│ │ │ │
8 O O───┬───┴───┴───┬───O ┌───┴───┐
│ │ │ │
9 O───────┴───────O O O───┴───O O
Solutions found: 1
status: OPTIMAL
Time taken: 5.65 seconds
Solved puzzle
Connect the Dots (Puzzle Type #56)
Also known as Numberlink.
Rules
You are given a grid of empty cells and 2 filled cell per color. The goal is to connect the dots of the same color to form a single fully connected graph for each color.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import connect_the_dots_solver as solver
board = np.array([
['R', ' ', 'B', ' ', ' ', ' ', ' ', ' '],
['Y', ' ', ' ', 'R', 'G', ' ', 'G', ' '],
[' ', 'M', ' ', ' ', ' ', 'P', ' ', ' '],
[' ', 'O', ' ', ' ', ' ', 'M', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['Br', 'B', ' ', ' ', 'Y', 'O', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', 'P', ' ', ' '],
[' ', ' ', ' ', 'Br', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6 7
┌───────┬───────────────────────┐
0│ R R │ B B B B B B │
├───┐ └───────┬───────────┐ │
1│ Y │ R R R │ G G G │ B │
│ ├───────────┴───┬───────┤ │
2│ Y │ M M M M │ P P │ B │
│ ├───────────┐ └───┐ │ │
3│ Y │ O O O │ M M │ P │ B │
│ └───────┐ └───────┤ │ │
4│ Y Y Y │ O O O │ P │ B │
├───┬───┐ └───────┐ │ │ │
5│Br │ B │ Y Y Y │ O │ P │ B │
│ │ └───────────┼───┘ │ │
6│Br │ B B B B │ P P │ B │
│ └───────────┐ └───────┘ │
7│Br Br Br Br │ B B B B │
└───────────────┴───────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.07 seconds
Solved puzzle
Nonograms Colored (Puzzle Type #57)
Also known as Nonogrids, Numbergrids, Picross, Hanjie, Paint by Numbers, Griddlers, or Pic-a-Pix.
Rules
You have a grid of squares, which must all be filled in either white or one of the specified colors. Beside each row of the grid are listed, in order, the lengths of the runs of the specified colors on that row; above each column are listed, in order, the lengths of the runs of the specified colors in that column. Your aim is to fill in the entire grid white or one of the specified colors.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver.puzzles.nonograms import nonograms_colored as solver
top = [
['5M'], ['8M'], ['1M', '3R', '6M'], ['1M', '5R', '5M'], ['8R', '4M'],
['10R', '4M'], ['10R', '4M'], ['1G', '2M', '2R', '3P', '7R', '3M'], ['1L', '2G', '1G', '2F', '3M', '1R', '5P', '6R', '3M'], ['2L', '2G', '2F', '4M', '1R', '6P', '5R', '3M'],
['3L', '1F', '1R', '2M', '8P', '5R', '3M'], ['1G', '1L', '1F', '1R', '2M', '8P', '5R', '3M'], ['1G', '2L', '2R', '1M', '8P', '5R', '3M'], ['1L', '1G', '3R', '1M', '8P', '5R', '3M'], ['1L', '3R', '2M', '7P', '6R', '3M'],
['1L', '3R', '1M', '8P', '5R', '4M'], ['1L', '3R', '1M', '8P', '5R', '4M'], ['2R', '1M', '9P', '5R', '3M'], ['1R', '9P', '5R', '3M'], ['10P', '5R', '3M'],
['1G', '1R', '9P', '5R', '4M'], ['1L', '1G', '1F', '2R', '8P', '5R', '6M'], ['1L', '2F', '3R', '6P', '5R', '7M'], ['1L', '1G', '1F', '4R', '5P', '5R', '3M', '3P', '2M'], ['1L', '1F', '6R', '2P', '6R', '3M', '4P', '2M'],
['1L', '1F', '12R', '4M', '6P', '1M'], ['1L', '1F', '1R', '3L', '1M', '3R', '7M', '7P', '1M'], ['1G', '3L', '1G', '11M', '7P', '1R', '1M'], ['1L', '1L', '3G', '11M', '1R', '6P', '2R'], ['1G', '3L', '1G', '4F', '6M', '9R'],
['3G', '2F', '2L', '1F', '4M', '7R'], ['4G', '1F', '4L'], ['1L', '1G', '1F', '1L', '2L'], ['2F', '1L']
]
side = [
['1L', '1G'], ['1L', '1G'], ['1L', '2G'], ['6L', '1G', '2L', '2G'], ['2L', '1G', '3F', '1L', '2G', '1F', '1G'],
['1G', '1L', '1G', '2F', '3R', '1L', '1G', '2F', '1G', '1L'], ['2G', '1L', '1G', '2F', '3R', '2L', '1G', '1F', '1L', '1F', '1G'], ['1G', '1L', '2G', '4L', '5R', '1L', '1G', '1M', '1F', '2L', '1F'], ['1G', '1F', '3L', '1G', '4R', '6R', '1L', '2M', '2F', '2L', '1F'], ['4F', '1L', '6R', '3P', '4R', '5M', '1L', '1F'],
['1G', '1F', '1M', '7R', '1M', '6P', '3R', '4M', '2L'], ['5M', '2R', '3M', '8P', '2R', '4M', '2L'], ['8M', '10P', '2R', '4M'], ['2M', '14P', '2R', '4M'], ['3R', '14P', '2R', '4M'],
['3R', '15P', '3R', '3M'], ['3R', '15P', '4R', '3M'], ['1M', '3R', '14P', '4R', '4M'], ['1M', '4R', '13P', '5R', '3M', '2R'], ['1M', '6R', '10P', '6R', '3M', '2P', '2R'],
['1M', '7R', '5P', '9R', '3M', '3P', '2R'], ['2M', '20R', '3M', '4P', '2R'], ['3M', '18R', '3M', '5P', '2R'], ['4M', '16R', '3M', '6P', '2R'], ['5M', '13R', '5M', '6P', '2R'],
['7M', '8R', '8M', '5P', '3R'], ['24M', '2P', '3R'], ['16M', '7M'], ['12M']
]
binst = solver.Board(top=top, side=side)
solutions = binst.solve_and_print(visualize_colors={
'M': 'darkmagenta',
'R': 'magenta',
'G': 'green',
'P': 'pink',
'L': 'lime',
'F': 'forestgreen',
})
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
0│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ L │ G │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
1│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ L │ G │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
2│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ L │ G │ G │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
3│ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ L │ L │ L │ L │ L │ L │ G │ L │ L │ G │ G │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
4│ │ │ │ │ │ │ │ │ L │ L │ │ │ │ │ │ │ │ │ │ │ │ │ │ G │ F │ F │ F │ L │ G │ G │ F │ G │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
5│ │ │ │ │ │ │ │ │ G │ L │ │ │ │ │ │ │ │ │ │ │ │ G │ F │ F │ R │ R │ R │ L │ G │ F │ F │ G │ L │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
6│ │ │ │ │ │ │ │ │ G │ G │ L │ │ │ │ │ │ │ │ │ │ G │ F │ F │ R │ R │ R │ L │ L │ G │ F │ L │ F │ G │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
7│ │ │ │ │ │ │ │ │ │ G │ L │ G │ G │ L │ L │ L │ L │ │ │ │ │ R │ R │ R │ R │ R │ L │ G │ M │ F │ L │ L │ F │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
8│ │ │ │ │ │ │ │ │ G │ F │ L │ L │ L │ G │ R │ R │ R │ R │ │ │ R │ R │ R │ R │ R │ R │ L │ M │ M │ F │ F │ L │ L │ F │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
9│ │ │ │ │ │ │ │ │ F │ F │ F │ F │ L │ R │ R │ R │ R │ R │ R │ P │ P │ P │ R │ R │ R │ R │ M │ M │ M │ M │ M │ L │ │ F │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
10│ │ │ │ │ │ │ │ G │ F │ M │ R │ R │ R │ R │ R │ R │ R │ M │ P │ P │ P │ P │ P │ P │ R │ R │ R │ M │ M │ M │ M │ L │ L │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
11│ │ │ │ │ │ │ │ M │ M │ M │ M │ M │ R │ R │ M │ M │ M │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ M │ M │ M │ M │ │ L │ L │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
12│ │ │ │ │ │ │ │ M │ M │ M │ M │ M │ M │ M │ M │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ M │ M │ M │ M │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
13│ │ │ │ │ │ │ │ │ M │ M │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ M │ M │ M │ M │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
14│ │ │ │ │ │ │ │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ M │ M │ M │ M │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
15│ │ │ │ │ │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ R │ M │ M │ M │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
16│ │ │ │ │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ R │ R │ M │ M │ M │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
17│ │ │ │ M │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ R │ R │ M │ M │ M │ M │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
18│ │ │ M │ R │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ R │ R │ R │ M │ M │ M │ R │ R │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
19│ │ M │ R │ R │ R │ R │ R │ R │ P │ P │ P │ P │ P │ P │ P │ P │ P │ P │ R │ R │ R │ R │ R │ R │ M │ M │ M │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
20│ │ M │ R │ R │ R │ R │ R │ R │ R │ P │ P │ P │ P │ P │ R │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ P │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
21│ M │ M │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ P │ P │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
22│ M │ M │ M │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ P │ P │ P │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
23│ M │ M │ M │ M │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ P │ P │ P │ P │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
24│ M │ M │ M │ M │ M │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ M │ M │ P │ P │ P │ P │ P │ P │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
25│ M │ M │ M │ M │ M │ M │ M │ R │ R │ R │ R │ R │ R │ R │ R │ M │ M │ M │ M │ M │ M │ M │ M │ P │ P │ P │ P │ P │ R │ R │ R │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
26│ │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ P │ P │ R │ R │ R │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
27│ │ │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ │ │ │ M │ M │ M │ M │ M │ M │ M │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤
28│ │ │ │ │ │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ M │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.40 seconds
The script also visualizes the solution:
Solved puzzle
Split Ends (Puzzle Type #60)
Rules
Each row and column contains four unique Y shapes (four different orientations) and two Os. Ys should not form straight lines by touching other Ys.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
Note: the 4 letters ("U", "L", "D", "R") represent the 4 shapes, each letter corresponds to the direction of the cardinal line, so the "Y" shape for example is "D" because the cardinal line is down.
import numpy as np
from puzzle_solver import split_ends_solver as solver
board = np.array([
['O', ' ', 'O', 'L', ' ', 'U'],
[' ', ' ', ' ', ' ', ' ', ' '],
[' ', 'R', ' ', ' ', 'O', ' '],
[' ', 'O', ' ', ' ', 'L', ' '],
[' ', ' ', ' ', ' ', ' ', ' '],
['U', ' ', 'L', 'D', ' ', 'R'],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5
┌───┬───┬───┬───┬───┬───┐
0│ O │ D │ O │ L │ R │ U │
├───┼───┼───┼───┼───┼───┤
1│ O │ L │ D │ R │ U │ O │
├───┼───┼───┼───┼───┼───┤
2│ D │ R │ O │ U │ O │ L │
├───┼───┼───┼───┼───┼───┤
3│ R │ O │ U │ O │ L │ D │
├───┼───┼───┼───┼───┼───┤
4│ L │ U │ R │ O │ D │ O │
├───┼───┼───┼───┼───┼───┤
5│ U │ O │ L │ D │ O │ R │
└───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.01 seconds
Solved puzzle
N-Queens (Puzzle Type #61)
Can also solve puzzles such as 7-Queens.
Rules
7-Queens Variant: Within each of the seven realms lives a lone queen. To maintain the peace, queens must not threaten each other: no row, column, diagonal, nor region may have more than one queen!
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import n_queens_solver as solver
board = np.array([
['00', '00', '00', '00', '01', '01', '02', '02'],
['00', '00', '03', '03', '01', '01', '02', '04'],
['00', '00', '03', '03', '01', '01', '01', '04'],
['03', '03', '03', '03', '01', '01', '01', '05'],
['03', '03', '03', '03', '01', '01', '01', '05'],
['03', '03', '06', '06', '06', '05', '05', '05'],
['06', '06', '06', '06', '06', '06', '05', '05'],
['06', '06', '06', '06', '06', '06', '05', '05']
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6 7
┌───┬───┬───┬───┬───┬───┬───┬───┐
0│ │ │ │ │ │ │▒▒▒│ │
├───┼───┼───┼───┼───┼───┼───┼───┤
1│▒▒▒│ │ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┤
2│ │ │ │ │ │ │ │▒▒▒│
├───┼───┼───┼───┼───┼───┼───┼───┤
3│ │ │ │ │▒▒▒│ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┤
4│ │▒▒▒│ │ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┤
5│ │ │ │ │ │▒▒▒│ │ │
├───┼───┼───┼───┼───┼───┼───┼───┤
6│ │ │▒▒▒│ │ │ │ │ │
├───┼───┼───┼───┼───┼───┼───┼───┤
7│ │ │ │ │ │ │ │ │
└───┴───┴───┴───┴───┴───┴───┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.00 seconds
Solved puzzle
Suguru (Puzzle Type #66)
Rules
Heavy lines indicate areas, called cages, from 1 to 6 squares in size. Fill each n-sized cage with the numbers 1-n.
So for example a 2-square cage contains the numbers 1 and 2; and a 5-square cage contains the numbers from 1 to 5.
Adjacent (touching) squares, even ones that touch diagonally, may never contain the same number.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import suguru_solver as solver
id_board = np.array([
['00', '00', '00', '00', '00', '01', '01', '02', '02', '02', '03', '03', '03', '03', '04'],
['00', '05', '05', '06', '06', '06', '01', '02', '02', '03', '03', '07', '07', '04', '04'],
['08', '08', '05', '06', '06', '01', '01', '02', '09', '09', '09', '09', '07', '04', '04'],
['08', '05', '05', '06', '10', '01', '11', '11', '12', '13', '13', '07', '07', '14', '04'],
['08', '05', '15', '16', '10', '10', '17', '17', '12', '12', '13', '07', '14', '14', '18'],
['08', '15', '15', '16', '16', '10', '10', '17', '12', '13', '13', '19', '19', '14', '18'],
['15', '15', '20', '20', '16', '10', '17', '17', '12', '13', '21', '21', '19', '22', '18'],
['15', '23', '23', '20', '16', '16', '17', '24', '24', '24', '21', '19', '19', '22', '18'],
['23', '23', '20', '20', '25', '25', '24', '24', '26', '24', '21', '19', '22', '22', '18'],
['23', '23', '20', '25', '25', '25', '25', '26', '26', '26', '21', '21', '22', '22', '18']
])
num_board = np.array([
[' ', '4', ' ', ' ', ' ', ' ', '4', ' ', '3', ' ', ' ', ' ', ' ', ' ', '6'],
['6', ' ', '3', ' ', '4', ' ', ' ', ' ', ' ', ' ', '6', ' ', '5', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '5', '6', '2', ' ', ' ', ' ', ' ', ' ', '3'],
[' ', ' ', '5', ' ', '2', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '1'],
['5', ' ', ' ', ' ', ' ', '6', ' ', ' ', '5', ' ', ' ', '1', ' ', '2', '6'],
[' ', ' ', ' ', '6', '3', ' ', ' ', ' ', ' ', ' ', ' ', '5', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', '5', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['2', '6', ' ', '4', ' ', ' ', ' ', '1', ' ', ' ', '2', '4', ' ', '5', ' '],
['4', '3', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['2', ' ', ' ', '3', ' ', ' ', '5', '4', ' ', ' ', '1', ' ', ' ', '2', '3'],
])
binst = solver.Board(id_board=id_board, num_board=num_board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───────────────────┬───────┬───────────┬───────────────┬───┐
0│ 2 4 5 1 3 │ 2 4 │ 2 3 4 │ 5 4 3 2 │ 6 │
│ ┌───────┬───────┴───┐ │ ┌───┘ ┌───────┬───┘ │
1│ 6 │ 1 3 │ 2 4 1 │ 3 │ 1 5 │ 1 6 │ 2 5 │ 4 5 │
├───┴───┐ │ ┌───┘ │ ┌───┴───────┴───┐ │ │
2│ 3 2 │ 4 │ 6 5 │ 6 5 │ 6 │ 2 4 3 1 │ 3 │ 2 3 │
│ ┌───┘ │ ┌───┤ ┌───┴───┼───┬───────┬───┘ ├───┐ │
3│ 1 │ 6 5 │ 3 │ 2 │ 1 │ 2 1 │ 3 │ 6 5 │ 4 6 │ 4 │ 1 │
│ │ ┌───┼───┤ └───┼───────┤ └───┐ │ ┌───┘ ├───┤
4│ 5 │ 2 │ 4 │ 1 │ 5 6 │ 5 4 │ 5 1 │ 2 │ 1 │ 3 2 │ 6 │
│ ├───┘ │ └───┐ └───┐ │ ┌───┘ ├───┴───┐ │ │
5│ 4 │ 6 5 │ 6 3 │ 4 3 │ 1 │ 2 │ 3 4 │ 5 6 │ 1 │ 5 │
├───┘ ┌───┴───┐ │ ┌───┘ │ │ ┌───┴───┐ ├───┤ │
6│ 3 1 │ 3 1 │ 5 │ 1 │ 2 6 │ 4 │ 1 │ 6 3 │ 2 │ 3 │ 4 │
│ ┌───┴───┐ │ └───┤ ┌───┴───┴───┤ ┌───┘ │ │ │
7│ 2 │ 6 5 │ 4 │ 2 4 │ 3 │ 1 5 3 │ 2 │ 4 1 │ 5 │ 2 │
├───┘ ┌───┘ ├───────┼───┘ ┌───┐ │ │ ┌───┘ │ │
8│ 4 3 │ 2 6 │ 1 6 │ 2 6 │ 2 │ 4 │ 5 │ 3 │ 6 4 │ 1 │
│ │ ┌───┘ └───┬───┘ └───┤ └───┤ │ │
9│ 2 1 │ 5 │ 3 2 4 5 │ 4 1 3 │ 1 4 │ 1 2 │ 3 │
└───────┴───┴───────────────┴───────────┴───────┴───────┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.03 seconds
Solved puzzle
Yajilin (Puzzle Type #68)
Rules
The aim of a Yajilin puzzle is to draw a single closed loop passing through every non-filled and non-clue cell.
-
The clues tell you exactly how many filled cells are in the given direction.
-
Filled cells cannot touch each other (diagonally is fine).
-
There can't be any empty cells - each cell must be a clue, filled, or contain the loop.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import yajilin_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'D1'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['D1', ' ', ' ', ' ', ' ', 'D1', ' ', ' ', ' '],
[' ', ' ', ' ', 'R2', ' ', ' ', ' ', 'L1', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', 'U1', ' ', ' '],
[' ', 'U0', ' ', 'D0', ' ', ' ', ' ', ' ', ' '],
['R2', ' ', 'U2', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', 'U0', ' ', ' ', 'D0', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6 7 8
┌───────────────────────────────────┐
0│ ┌───────────────────────────┐ 1↓ │
│ │ │ │
1│ └───┐ ▒▒▒ ┌───────────┐ └───┐ │
│ │ │ │ │ │
2│1↓ └───┐ └───┐ 1↓ └───────┘ │
│ │ │ │
3│ ┌───────┘ 2→ └───┐ ▒▒▒ 1← ▒▒▒│
│ │ │ │
4│ └───────────────┐ │ 1↑ ┌───┐ │
│ │ │ │ │ │
5│▒▒▒ 0↑ ▒▒▒ 0↓ │ └───┐ │ │ │
│ │ │ │ │ │
6│2→ ▒▒▒ 2↑ ┌───┘ ▒▒▒ └───┘ │ │
│ │ │ │
7│ ┌───────────┘ 0↑ ┌───┐ 0↓ │ │
│ │ │ │ │ │
8│ └───────────────────┘ └───────┘ │
└───────────────────────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.07 seconds
Solved puzzle
NumberMaze (Puzzle Type #69)
Also known as Dot Stream.
Rules
Your aim is to draw a single line starting from the number 1 through all of the numbers, covering all of the cells in the grid as you go.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import numbermaze_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', '3', ' ', '5', ' ', ' ', '4', ' ', '7'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', '#', ' ', ' ', '#', ' ', '6', '8', ' '],
['2', ' ', '#', '#', ' ', ' ', ' ', ' ', ' '],
['#', ' ', '1', ' ', ' ', '#', ' ', '#', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['9', ' ', '10', ' ', ' ', ' ', '#', ' ', '#'],
['#', ' ', ' ', '11', '#', ' ', ' ', ' ', '#'],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6 7 8
┌───────────────────────────────────┐
0│ ┌───────────────────────┐ ┌───┐ │
│ │ │ │ │ │
1│ └───3 ┌───5───────────4 │ 7 │
│ │ │ │ │ │
2│ ┌───┘ │ ┌───────┐ ┌───┘ │ │
│ │ │ │ │ │ │ │
3│ │ ▒▒▒ └───┘ ▒▒▒ └───6 8───┘ │
│ │ │ │
4│ 2───┐ ▒▒▒ ▒▒▒ ┌───────┐ └───┐ │
│ │ │ │ │ │
5│▒▒▒ └───1 ┌───┘ ▒▒▒ │ ▒▒▒ │ │
│ │ │ │ │
6│ ┌───────────┘ ┌───────┘ ┌───┘ │
│ │ │ │ │
7│ 9───┐ 10───┐ └───┐ ▒▒▒ │ ▒▒▒│
│ │ │ │ │ │ │
8│▒▒▒ └───┘ 11 ▒▒▒ └───────┘ ▒▒▒│
└───────────────────────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.05 seconds
Solved puzzle
Link-a-Pix (Puzzle Type #70)
Rules
The rules of Link-a-Pix are to link pairs of identical numbers (or color-number) on a grid with a single, continuous path of the length of the number.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
Note: the letter before the _ is the color and is arbitrary as long as the same colors in the board are consistent.
import numpy as np
from puzzle_solver import link_a_pix_solver as solver
board = np.array([
[ '' , '' , '' , '' , '' , '' , '' , 'B_7' , '' , '' , '' , '' , '' , 'B_7' , '' , '' , '' , '' , '' , '' , '' ],
[ '' , '' , '' , '' , '' , '' , 'B_1' , '' , 'K_10', 'K_3' , 'K_1' , '' , '' , 'K_6' , 'B_1' , '' , '' , '' , '' , '' , '' ],
[ '' , '' , '' , '' , '' , 'B_1' , '' , '' , 'K_3' , '' , '' , '' , 'K_5' , '' , '' , 'B_1' , '' , '' , '' , '' , '' ],
[ '' , '' , '' , 'B_8' , '' , '' , '' , 'B_3' , '' , 'B_3' , 'K_6' , 'B_3' , '' , 'B_3' , '' , 'K_5' , '' , 'B_8' , '' , '' , '' ],
[ '' , '' , 'B_1' , 'K_7' , '' , '' , 'B_2' , '' , '' , '' , 'B_2' , '' , '' , '' , 'B_3' , 'K_5' , '' , 'K_6' , 'B_1' , '' , '' ],
[ '' , 'B_1' , '' , '' , '' , '' , 'B_2' , '' , 'B_3' , '' , 'B_2' , '' , 'B_3' , '' , '' , '' , '' , '' , 'K_7' , 'B_1' , '' ],
[ 'B_11', 'K_7' , '' , 'K_6' , '' , '' , 'B_2' , '' , '' , '' , 'B_2' , '' , '' , '' , 'B_3' , '' , '' , '' , '' , 'K_7' , 'B_11' ],
[ '' , '' , '' , '' , '' , 'K_10', 'B_2' , '' , 'B_3' , 'B_1' , 'B_2' , 'B_1' , 'B_3' , 'B_1' , 'K_5' , '' , '' , '' , '' , '' , '' ],
[ '' , 'K_8' , '' , '' , '' , 'B_1' , '' , 'K_7' , 'K_7' , '' , '' , 'K_3' , 'K_3' , 'K_1' , 'K_5' , 'B_1' , '' , '' , '' , '' , '' ],
[ '' , '' , '' , 'K_6' , 'B_8' , 'K_5' , '' , 'K_7' , '' , '' , 'K_3' , 'K_3' , '' , '' , '' , 'K_7' , 'B_8' , 'K_6' , '' , '' , '' ],
[ '' , '' , 'K_8' , 'B_6' , '' , '' , '' , '' , '' , 'B_5' , 'B_1' , 'B_5' , 'K_5' , '' , 'K_4' , '' , '' , 'B_6' , '' , 'K_8' , '' ],
[ '' , '' , '' , '' , '' , 'K_5' , '' , 'K_2' , 'K_2' , '' , '' , '' , 'K_4' , '' , '' , 'K_1' , '' , '' , '' , '' , '' ],
[ '' , '' , '' , '' , 'K_7' , '' , '' , '' , 'K_6' , '' , 'B_3' , '' , 'K_10', '' , 'K_2' , '' , '' , '' , 'K_8' , '' , '' ],
[ '' , 'K_6' , '' , '' , '' , 'K_7' , 'K_7' , '' , '' , '' , '' , '' , '' , '' , 'K_2' , 'K_4' , '' , '' , '' , 'K_6' , '' ],
[ '' , 'K_3' , '' , '' , '' , '' , '' , 'K_6' , 'K_6' , 'K_1' , 'B_3' , 'K_2' , 'K_2' , '' , '' , '' , 'K_7' , '' , '' , 'K_3' , '' ],
[ '' , '' , '' , 'B_6' , '' , '' , '' , '' , '' , 'B_1' , 'K_5' , 'B_1' , '' , '' , 'K_3' , '' , 'K_4' , 'B_6' , '' , '' , '' ],
[ 'B_11', 'K_3' , '' , 'K_2' , 'B_3' , 'K_6' , '' , 'K_3' , 'K_1' , '' , '' , 'K_10', '' , 'K_2' , '' , 'K_3' , 'B_3' , 'K_2' , '' , 'K_3' , 'B_11' ],
[ '' , 'B_1' , 'K_6' , 'K_2' , '' , 'B_3' , 'K_3' , '' , 'K_5' , '' , 'K_3' , '' , 'K_3' , 'K_2' , 'K_1' , 'B_3' , '' , 'K_2' , 'K_6' , 'B_1' , '' ],
[ '' , '' , 'B_2' , 'B_2' , '' , '' , 'B_9' , '' , '' , '' , '' , '' , '' , '' , 'B_9' , '' , '' , 'B_2' , 'B_2' , '' , '' ],
[ '' , '' , '' , '' , '' , '' , 'R_4' , '' , '' , 'R_4' , 'Y_1' , 'R_4' , '' , '' , 'R_4' , '' , '' , '' , '' , '' , '' ],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
┌───────────────────────────┬───────────────────────────┬───────────────────────────┐
0│ │ 7 7 7 7 7 7 7 │ │
│ ┌───┼───────┬───┬───┬───────────┼───┐ │
1│ │ 1 │10 10 │ 3 │ 1 │ 6 6 6 │ 1 │ │
│ ┌───┼───┘ ┌───┘ ├───┘ ┌───────┴───┼───┐ │
2│ │ 1 │10 10 │ 3 3 │ 6 6 │ 5 5 5 │ 1 │ │
│ ┌───────┼───┘ ┌───┴───────┤ ┌───┴───────┐ └───┼───────┐ │
3│ │ 8 8 │10 10 │ 3 3 3 │ 6 │ 3 3 3 │ 5 5 │ 8 8 │ │
│ ┌───┼───┐ │ ┌───┼───────────┼───┼───────────┼───┬───┤ ┌───┼───┐ │
4│ │ 1 │ 7 │ 8 │10 │ 2 │ │ 2 │ │ 3 │ 5 │ 8 │ 6 │ 1 │ │
│ ┌───┼───┘ │ │ │ │ ┌───┐ │ │ ┌───┐ │ │ │ │ ├───┼───┐ │
5│ │ 1 │ 7 7 │ 8 │10 │ 2 │ │ 3 │ │ 2 │ │ 3 │ │ 3 │ 5 │ 8 │ 6 │ 7 │ 1 │ │
├───┼───┘ ┌───┤ │ ├───┤ │ │ ├───┤ │ │ │ │ │ │ │ └───┼───┤
6│11 │ 7 7 │ 6 │ 8 │10 │ 2 │ │ 3 │ │ 2 │ │ 3 │ │ 3 │ 5 │ 8 │ 6 │ 7 7 │11 │
│ │ │ │ │ │ │ │ ├───┤ ├───┤ ├───┼───┘ │ │ │ │ │
7│11 │ 7 7 │ 6 │ 8 │10 │ 2 │ │ 3 │ 1 │ 2 │ 1 │ 3 │ 1 │ 5 5 │ 8 │ 6 │ 7 7 │11 │
│ ├───┬───┘ │ ├───┼───┴───┼───┴───┼───┴───┼───┼───┼───┬───┤ │ │ │ │
8│11 │ 8 │ 6 6 │ 8 │ 1 │ 7 7 │ 7 7 │ 3 3 │ 3 │ 1 │ 5 │ 1 │ 8 │ 6 │ 7 7 │11 │
│ │ │ │ ├───┤ ┌───┘ │ ┌───┘ ├───┘ ├───┤ │ ├───────┤ │
9│11 │ 8 │ 6 6 │ 8 │ 5 │ 7 │ 7 7 7 │ 3 │ 3 3 │ 5 5 │ 7 │ 8 │ 6 │ 8 8 │11 │
│ │ └───┬───┼───┘ │ │ ┌───┼───┼───┬───┘ ┌───┤ └───┼───┤ │ │
10│11 │ 8 8 │ 6 │ 5 5 │ 7 │ 7 7 │ 5 │ 1 │ 5 │ 5 5 │ 4 │ 7 7 │ 6 │ 8 8 │11 │
│ │ │ │ │ ├───────┤ └───┘ ├───────┘ ├───┐ │ │ │ │
11│11 │ 8 8 │ 6 │ 5 5 │ 7 │ 2 2 │ 5 5 5 │ 4 4 4 │ 1 │ 7 │ 6 │ 8 8 │11 │
│ │ │ ├───┬───┤ ├───┬───┴───┬───┬───┴───┬───┬───┼───┤ │ │ │ │
12│11 │ 8 8 │ 6 │ 7 │ │ 7 │ │ 6 6 │ 3 │10 10 │ │ 2 │ │ 7 │ 6 │ 8 8 │11 │
│ ├───────┤ │ └───┤ ├───┘ │ │ └───┤ ├───┤ │ ├───────┤ │
13│11 │ 6 6 │ 6 │ 7 7 │ 7 │ 6 6 6 │ 3 │10 10 10 │ 2 │ 4 │ 7 │ 6 │ 6 6 │11 │
│ ├───┐ │ │ ├───┤ ┌───┬───┤ ├───────┐ ├───┤ │ │ │ ┌───┤ │
14│11 │ 3 │ 6 │ 6 │ 7 7 │ │ 6 │ 6 │ 1 │ 3 │ 2 2 │10 │ │ 4 │ 7 │ 6 │ 6 │ 3 │11 │
│ │ │ │ │ ├───┴───┘ ├───┼───┼───┬───┘ ├───┤ └───┤ │ │ │ │
15│11 │ 3 │ 6 │ 6 │ 7 7 │ 6 6 6 │ 1 │ 5 │ 1 │10 10 │ 3 │ 4 4 │ 6 │ 6 │ 3 │11 │
│ │ │ ├───┼───┬───┘ ┌───┬───┼───┘ ├───┘ ┌───┤ └───┬───┼───┤ │ │ │
16│11 │ 3 │ 6 │ 2 │ 3 │ 6 6 │ 3 │ 1 │ 5 5 │10 10 │ 2 │ 3 3 │ 3 │ 2 │ 6 │ 3 │11 │
├───┼───┤ │ │ └───┬───┘ ├───┘ ┌───┴───────┤ ├───┬───┘ │ │ ├───┼───┤
17│ │ 1 │ 6 │ 2 │ 3 3 │ 3 3 │ 5 5 │ 3 3 3 │ 2 │ 1 │ 3 3 │ 2 │ 6 │ 1 │ │
│ └───┼───┴───┼───────┼───────┴───────┴───────────┴───┴───┼───────┼───┴───┼───┘ │
18│ │ 2 2 │ │ 9 9 9 9 9 9 9 9 9 │ │ 2 2 │ │
│ └───────┘ ├───────────────┬───┬───────────────┤ └───────┘ │
19│ │ 4 4 4 4 │ 1 │ 4 4 4 4 │ │
└───────────────────────┴───────────────┴───┴───────────────┴───────────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.01 seconds
Solved puzzle
Vectors (Puzzle Type #72)
Rules
The puzzle grid consists of a series of numbered black squares. Your task is to draw arrows starting from each of these black squares in such a way so that the total number of white squares covered by arrows emanating from any black square equals exactly the number displayed. Arrows can go up, down, left or right, but can never cross another arrow. You must also fill every empty square on the grid with one arrow segment. Each puzzle has only one unique solution, and each can be solved using pure logical deduction.
- Every numbered black square must have exactly that number of combined arrow lengths emanating from it in the final solution.
- No two arrows can cross each other.
- Every square on the grid must be filled with an arrow.
- A number will turn green once it has arrows emanating from it with the correct combined length, but that does not necessarily mean those arrows are placed correctly.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import vectors_solver as solver
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', '11', ' ', ' ', ' ', ' ', ' ', ' ', '1 ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '6 ', ' ', ' '],
['5 ', ' ', ' ', '1 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '5 ', ' ', '1 ', ' '],
[' ', ' ', '5 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '11'],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '5 ', ' ', ' ', '9 ', ' '],
[' ', ' ', '2 ', ' ', ' ', '13', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['1 ', ' ', ' ', ' ', ' ', ' ', ' ', '12', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '2 ', ' ', ' ', ' ', ' '],
['2 ', ' ', ' ', '5 ', ' ', '5 ', ' ', ' ', ' ', '2 ', ' ', '6 ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '2 ', ' ', '6 ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', '2 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '5 ', ' ', ' ', ' ', ' '],
['3 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '1 ', ' ', ' ', ' ', ' ', '6 '],
[' ', '15', ' ', '4 ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '3 ', ' ', ' ', '2 ', ' ', ' ', ' ', ' ', '1 '],
[' ', ' ', '1 ', ' ', '15', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '13', ' ', ' '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4
┌───┬───┬───┬───────────────────────────────────┬───┬───────┐
0│ │ │ │ 11 │ │ 1 │
│ │ │ ├───┬───┬───┐ ┌───────────────────┘ ├───┬───┤
1│ │ │ │ │ │ │ │ 6 │ │ │
│ │ │ │ │ │ │ ├───────────────────────┤ │ │
2│ 5 │ │ │ 1 │ │ │ │ 5 │ 1 │ │
│ │ │ └───┤ │ │ ├───────────────────────┴───┘ │
3│ │ │ 5 │ │ │ │ 11 │
│ │ │ ┌───┤ │ ├───┴───────────────────┬───────┐ │
4│ │ │ │ │ │ │ 5 │ 9 │ │
│ │ ├───┤ │ │ └───────────────────────┴───┐ │ │
5│ │ │ 2 │ │ │13 │ │ │
├───┤ │ │ │ │ ┌───────────────────────────┤ ├───┤
6│ 1 │ │ │ │ │ │ 12 │ │ │
│ │ │ │ │ │ ├───┐ ┌───┬───┬───────────┤ │ │
7│ │ │ │ │ │ │ │ │ │ │ 2 │ │ │
├───┤ ├───┘ │ ├───┤ │ │ │ └───┬───────┤ │ │
8│ 2 │ │ 5 │ │ 5 │ │ │ │ 2 │ 6 │ │ │
│ │ ├───┬───┤ │ │ │ │ └───┬───┤ ┌───┤ │ │
9│ │ │ │ │ │ │ 2 │ │ 6 │ │ │ │ │ │
│ │ │ │ │ │ ├───┤ │ ┌───┘ │ │ │ │ │
10│ │ │ 2 │ │ │ │ │ │ │ 5 │ │ │ │ │
├───┤ │ │ │ │ │ │ │ ├───┐ │ │ │ │ │
11│ 3 │ │ │ │ │ │ │ │ │ 1 │ │ │ │ │ 6 │
│ │ └───┤ │ │ │ │ │ │ │ │ │ │ │ │
12│ │15 │ 4 │ │ │ │ │ │ │ │ │ │ │ │
│ │ ┌───┤ │ │ │ ├───┴───┴───┤ │ │ ├───┴───┤
13│ │ │ │ │ │ │ 3 │ 2 │ │ │ │ 1 │
│ │ │ ├───┘ └───┼───┴───────────┴───┴───┘ └───────┤
14│ │ │ 1 │ 15 │ 13 │
└───┴───┴───┴───────────┴───────────────────────────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.03 seconds
Solved puzzle
Vermicelli (Puzzle Type #73)
Rules
Connect worms to make a loop that visits every square in the grid. The worm can’t fork nor cross itself, and it can't go through walls.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import vermicelli_solver as solver
walls = np.array([
[' ', ' ', ' ', 'D ', ' ', ' ', 'R ', ' ', ' ', ' '],
[' ', 'D ', ' ', ' ', ' ', 'R ', 'D ', ' ', ' ', ' '],
['R ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', 'D ', ' ', ' ', ' ', ' ', ' ', 'R ', ' '],
['D ', ' ', 'R ', 'D ', ' ', 'DR', ' ', 'R ', 'D ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', 'D ', 'R ', 'D ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', 'R ', ' ', ' ', 'U ', ' '],
])
binst = solver.Board(walls=walls)
solutions = binst.solve_and_print()
Script Output
Solution found
0 0 0 0 0 0 0 0 0 0
0 1 2 3 4 5 6 7 8 9
│
0 ┌───┐ ┌───────┐ ┌───┐ │ ┌───────┐
│ │ │ ───── │ │ │ │ │ │ │
1 │ └───┘ ┌───┘ │ │ └───┘ ┌───┘
│ ┌──── │ │ └──── │
2 │ │ ┌───────┘ ┌───┘ ┌───┐ └───┐
│ │ │ │ │ │ │ │
3 │ └───────┐ └───┐ │ └───┐ │ │
│ ────┐ │ │ │ │ │ │ │ │
4 └───────┐ │ └───────┘ │ └───┐ │ └───┘
───── │ └──── ────┘ │ └────
5 ┌───┐ │ ┌───────────┐ │ ┌───┐
│ │ │ │ │ │ │ │ │
6 │ └───┘ │ └───────┐ │ └───┘ │
│ ───── └──── │ │ │ ───── │
7 └───────────────────┘ │ └───────────┘
│
Solutions found: 1
status: OPTIMAL
Time taken: 0.04 seconds
Solved puzzle
Cow and Cactus (Puzzle Type #74)
Rules
You are building a fence for your ranch. The fence must separate the cows inside, from the cacti outside.
The finished fence must make an enclosed circuit without touching or crossing itself.
Numbers inside dotted-circles are corral clues. These squares must be inside the fence. The number shows how many cells can be seen up, down, left, and right (plus itself) from that location before reaching a fence.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
Note: W refers to a cow and P refers to a cactus (sadly both words start with 'C' so we have to avoid using that)
import numpy as np
from puzzle_solver import cow_and_cactus_solver as solver
board = np.array([
[' ', ' ', '15', ' ', '11', '9 ', '8 ', '11'],
[' ', ' ', ' ', 'P ', ' ', ' ', ' ', ' '],
['W ', '3 ', ' ', ' ', ' ', ' ', ' ', ' '],
['W ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
['W ', ' ', ' ', ' ', ' ', 'W ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '4 ', ' '],
['W ', ' ', ' ', ' ', 'W ', 'W ', 'P ', 'W '],
['P ', 'W ', ' ', ' ', 'W ', 'W ', ' ', 'P '],
])
binst = solver.Board(board=board)
solutions = binst.solve_and_print()
Script Output
Solution:
0 1 2 3 4 5 6 7
┌───────────────────────────────┐
0│ 15 11 9 8 11 │
├───────┐ ┌───┐ ┌───┐ │
1│ │ │ P │ │ │ │
├───────┘ │ │ ┌───┘ │ │
2│ W 3 │ │ │ │ │
│ ┌───┐ │ │ └───┐ │ │
3│ W │ │ │ │ │ │ │
│ │ │ │ └───┐ │ └───┤
4│ W │ │ │ │ W │ │
├───┘ │ │ ┌───┘ └───────┤
5│ │ │ │ 4 │
├───────┘ │ │ ┌───┐ │
6│ W │ │ W W │ P │ W │
├───┐ │ │ │ └───┤
7│ P │ W │ │ W W │ P │
└───┴───────┴───┴───────┴───────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.04 seconds
Solved puzzle
Ripple Effect (Puzzle Type #76)
Rules
Heavy lines indicate areas, called cages, from 1 to 9 cells in size.
Fill each cage with unique digits, counting up from 1. So for example a 2-cell cage contains the numbers 1 and 2; and a 5-cell cage contains all the numbers from 1 to 5.
If two identical numbers appear in the same row or column, at least that many cells must separate them. For example, if two 3s appear in the same column, they must be separated by at least three other cells that do not contain 3.
This puzzle is a variant of Suguru in which the clues create curious cascading effects.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import ripple_effect_solver as solver
id_board = np.array([
['00', '01', '02', '02', '03', '03', '04'],
['00', '05', '05', '02', '03', '06', '06'],
['07', '07', '05', '08', '03', '03', '06'],
['09', '07', '07', '07', '03', '10', '10'],
['11', '11', '12', '12', '13', '13', '10'],
['14', '11', '14', '12', '13', '15', '15'],
['14', '14', '14', '16', '13', '13', '15']
])
board = np.array([
[' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', '5', ' '],
[' ', ' ', '4', ' ', '6', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', ' ', '1'],
[' ', ' ', '1', ' ', ' ', ' ', ' '],
[' ', '4', ' ', ' ', ' ', ' ', ' '],
])
binst = solver.Board(board=board, id_board=id_board)
solutions = binst.solve_and_print()
Script Output
Solution found
0 1 2 3 4 5 6
┌───┬───┬───────┬───────┬───┐
0│ 2 │ 1 │ 3 1 │ 4 2 │ 1 │
│ ├───┴───┐ │ ┌───┴───┤
1│ 1 │ 3 1 │ 2 │ 1 │ 3 2 │
├───┴───┐ ├───┤ └───┐ │
2│ 3 1 │ 2 │ 1 │ 3 5 │ 1 │
├───┐ └───┴───┤ ┌───┴───┤
3│ 1 │ 2 4 5 │ 6 │ 2 3 │
├───┴───┬───────┼───┴───┐ │
4│ 2 1 │ 3 1 │ 5 4 │ 1 │
├───┐ ├───┐ │ ┌───┴───┤
5│ 5 │ 3 │ 1 │ 2 │ 1 │ 3 2 │
│ └───┘ ├───┤ └───┐ │
6│ 3 4 2 │ 1 │ 3 2 │ 1 │
└───────────┴───┴───────┴───┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.05 seconds
Solved puzzle
Area 51 (Puzzle Type #77)
Rules
You are building a labyrinthian fence enclosing Area 51. The fence must separate the aliens, kept inside, from the cacti, which are outside. The finished fence must make an enclosed circuit without touching or crossing itself.
A cell containing an uncircled digit must be surrounded by that many pieces of fence.
Numbers inside dotted-circles must be inside the fence and show how many cells can be seen up, down, left, and right (plus itself) from that cell before reaching a fence.
On black circles the fence must have a 90 degree turn with two straight sections before and after. On white circles the fence must continue straight with at least one turn immediately before or after the circle.
Unsolved puzzle
Code to utilize this package and solve the puzzle:
import numpy as np
from puzzle_solver import area_51_solver as solver
board = np.array([
[' ', 'A ', ' ', ' ', ' ', ' ', ' ', 'O4'],
[' ', ' ', ' ', '2 ', ' ', ' ', ' ', ' '],
[' ', ' ', ' ', '1 ', ' ', '1 ', '3 ', 'C '],
[' ', ' ', ' ', ' ', ' ', ' ', '2 ', ' '],
[' ', ' ', '2 ', '1 ', '2 ', '1 ', ' ', ' '],
[' ', ' ', ' ', '2 ', '3 ', ' ', '2 ', ' '],
[' ', ' ', '1 ', ' ', ' ', ' ', '3 ', ' '],
[' ', ' ', ' ', ' ', '1 ', ' ', ' ', ' '],
[' ', ' ', '1 ', ' ', ' ', ' ', ' ', '2 '],
['3 ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
])
dots = {
get_pos(x=1, y=1): 'B',
get_pos(x=5, y=7): 'B',
get_pos(x=5, y=1): 'W', get_pos(x=0, y=5): 'W', get_pos(x=1, y=6): 'W', get_pos(x=1, y=7): 'W',
get_pos(x=7, y=7): 'W',
get_pos(x=6, y=8): 'W',
get_pos(x=6, y=9): 'W',
get_pos(x=2, y=10): 'W',
}
binst = solver.Board(board=board, dots=dots)
solutions = binst.solve_and_print()
Script Output
Solution:
0 1 2 3 4 5 6 7
┌───────────────┐ ┌───────────┐
0│ A │ │ O4 │
│ ┌───────┐ │ │ │
1│ │ │ 2 │ │ │
│ │ ┌───┘ └───┘ ┌───────┘
2│ │ │ 1 1 │ 3 C
└───┘ └───────────┐ └───────┐
3 │ 2 │
┌───┐ ┌───────────┘ ┌───────┘
4│ │ │ 2 1 2 1 │
│ └───┘ ┌───┐ └───────┐
5│ 2 │ 3 │ 2 │
└───────────────┘ │ ┌───────┘
6 1 │ │ 3
┌───────┐ ┌───────┘ └───────┐
7│ │ │ 1 │
└───┐ └───┘ ┌───────────┘
8 │ 1 │ 2
┌───┘ ┌───┐ └───────────┐
9│ 3 │ │ │
└───────────┘ └───────────────┘
Solutions found: 1
status: OPTIMAL
Time taken: 0.05 seconds
Solved puzzle
All other Puzzles
The examples above showcase just a few of the many puzzle types this solver can handle. The repository includes solvers for countless unique challenges.
Visit the Puzzle Gallery to explore all supported puzzle types, view their rule summaries, and see visual examples of each one in action.
Aliases
Here is a list of all the puzzles along with some of their aliases:
- Nonograms (Also known as Nonogrids, Numbergrids, Picross, Hanjie, Paint by Numbers, Griddlers, or Pic-a-Pix)
- Sudoku (Also known as Number Place or Solo)
- Minesweeper
- Dominosa
- Light Up (Also known as Akari or Lasergrids)
- Tents
- Filling (Also known as Fillomino)
- Keen (Also known as KenKen, CalcuDoku, Mathdoku, Inkies, or Inky)
- Towers (Also known as Skyscrapers)
- Singles (Also known as Hitori)
- Magnets
- Signpost
- Range (Also known as Kurodoko, Kuromasu, or "Where is Black Cells?")
- UnDead (Also known as Haunted or Haunted Mirror Maze)
- Unruly (Also known as "3-In-A-Row")
- Tracks
- Mosaic (Also known as ArtMosaico, Count and Darken, Cuenta Y Sombrea, Fill-a-Pix, Fill-In, Komsu Karala, Magipic, Majipiku, Mosaico, Mosaik, Mozaiek, Nampre Puzzle, Nurie-Puzzle, Oekaki-Pix, or Voisimage)
- Map
- Pearl (Also known as Masyu)
- Bridges (Also known as Hashiwokakero)
- Inertia
- Guess
- Chess Range
- Chess Solo
- Chess Melee
- Thermometers
- Aquarium
- Stitches
- Battleships
- Kakurasu
- Star Battle
- Star Battle Shapeless
- Lits
- Black Box
- Galaxies (Also known as Tentai Show, Tentaisho, Galaxies, Spiral Galaxies, or Sym-a-Pix)
- Slant
- Unequal (Also known as Futoshiki, the Adjacent variant is also known as Renzoku or Neighbours)
- Norinori
- Slitherlink (Also known as Fences, Loop the Loop, or Loopy)
- Yin-Yang
- Binairo (Also known as Takuzu, Binero, Tohu-Wa-Vohu (Formless and Empty), Eins und Zwei (One and Two), Binary Puzzles, Binoxxo, Binox, Zernero, Tic-Tac-Logic, TicTacToe, or Sudoku Binary)
- Rectangles (Also known as Shikaku or CellBlocks)
- Palisade
- Flip
- Nurikabe
- Heyawake
- Shingoki (Also known as Semaphores)
- Tapa
- Binairo Plus
- Shakashaka (Also known as Proof of Quilt)
- Kakuro
- Sudoku Jigsaw
- Sudoku Killer
- Flood It
- Pipes (Also known as Net or Network)
- Connect the Dots (Also known as Numberlink)
- Nonograms Colored (Also known as Nonogrids, Numbergrids, Picross, Hanjie, Paint by Numbers, Griddlers, or Pic-a-Pix)
- ABC View (Also known as "Easy as ABC", "ABC End View", or "Last Man Standing")
- Mathema Grids (Also known as SetSquare grid)
- Split Ends
- N-Queens
- Troix
- Dumplings
- Hidoku
- Suko
- Suguru
- Number Path
- Yajilin (Also known as Yalooniq or Arrow Ring)
- NumberMaze (Also known as Dot Stream)
- Link-a-Pix
- Trees Logic
- Vectors (Also known as "Four Winds" or "Line Game")
- Vermicelli
- Cow and Cactus
- Kropki
- Ripple Effect (Also known as Hakyuu)
- Area 51
- Circle 9
- Krypto Kakuro
- Snail
- Hidden Stars
- Branches
- Tatami (Also known as Patchwork)
- Linesweeper (Also known as "Loop")
- Clouds (Also known as Rain Clouds or Radar)
- Walls
- Rooms (Also known as Seethrough, Doors, or "Open Office")
- Mathrax
- Arrows
- Sumscrapers
- Tenner Grid (Also known as "From 1 to 10", "Zehnergitter", "Grid Ten")
- Archipelago (Also known as "Akiperago")
Other
Why SAT / CP-SAT?
Because it is extremely faster than naive solutions and many pencil puzzles can be modeled with:
- Boolean decisions (e.g., black/white, place item/not place item)
- Linear constraints (counts, separations, adjacency)
- All-different / visibility / reachability constraints
This repo builds those constraints in Python and uses SAT/CP-SAT (e.g., OR-Tools) to search efficiently. It both demonstrates the modeling and provides usable solvers.
Testing
To run the tests, simply run the following (to create a fresh conda environment and install the dev dependencies):
conda create -p ./env python=3.11
conda activate ./env
pip install -r requirements.txt
pip install -r ./tests/requirements-dev.txt
pytest
the pytest.ini file is used to configure the pytest command to use -n 4 to have 4 workers.
Contributing
Issues and PRs welcome!
-
Python version
>= 3.9required. -
Keep puzzle folders self-contained (solver, README.md, other files if needed).
-
Prefer small, readable encodings with comments explaining each constraint.
-
If you add a new puzzle:
- Create a directory in
src/puzzle_solver/puzzles/<name>/, - Add a minimal test script in
tests/test_<name>.py, - Document the modeling in code comments,
- Create a directory in
Build and push to PyPI
- First make sure all the tests pass (see Testing)
- Update the version in
src/puzzle_solver/__init__.py - Build and push:
- Bash:
./scripts/build.sh - Powershell:
./scripts/build.ps1
- Bash:
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
multi_puzzle_solver-1.1.10.tar.gz
(331.9 kB
view details)
Built Distribution
Filter files by name, interpreter, ABI, and platform.
If you're not sure about the file name format, learn more about wheel file names.
Copy a direct link to the current filters
File details
Details for the file multi_puzzle_solver-1.1.10.tar.gz.
File metadata
- Download URL: multi_puzzle_solver-1.1.10.tar.gz
- Upload date:
- Size: 331.9 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/6.2.0 CPython/3.11.4
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
10fcb60a42e8912a8760f1b78a16abd90f4c546c63524d37a3a0e2872f450c53
|
|
| MD5 |
8db47a2a80add4779642600416147b68
|
|
| BLAKE2b-256 |
ffba9c21f8918630b444b6e53478f2de2498963d2a07a0407cf98fcb3fbc4ed2
|
File details
Details for the file multi_puzzle_solver-1.1.10-py3-none-any.whl.
File metadata
- Download URL: multi_puzzle_solver-1.1.10-py3-none-any.whl
- Upload date:
- Size: 256.6 kB
- Tags: Python 3
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/6.2.0 CPython/3.11.4
File hashes
| Algorithm | Hash digest | |
|---|---|---|
| SHA256 |
27e0cba29362e66b6ded4871321dab531dc39da8113c1cad26cfcbe9fec4dcb3
|
|
| MD5 |
1e2832f969cac241c5df05d8fd5d4d7e
|
|
| BLAKE2b-256 |
0c4282573d727079b5b751486250fb84e227b18112d02ea8dbbadc5d3c43c5f4
|
