If you thought this notebook was going to be about a video game like StarCraft®, I'm sorry to disapoint you. Instead it is about Star Battle puzzles, a genre of Sudoku-like puzzles with these properties:
Here is a board (S=2, N=10) and its solution from a helpful Star Battle Rules and Info page:
This “24”-themed puzzle was created by Thomas Snyder for the 24-Hours Puzzle Championship in Hungary in 2012.
Here's how I will represent Star Battle puzzles:
range(N * N)
.N
: the number of cells on each side of the N×N board.S
: the number of stars per unit in a solution.units
: a list of all the units on the board.units_for
: a dict where units_for[c]
is a list of the units that cell c
is in.pic
: a string; a graphical picture of the differently-shaped boxes.units
: list of units that have not yet been filled with S stars each.stars
: set of cells that have been determined (or guessed) to contain a star.unknowns
: set of cells that might contain either a star or a blank.None
.from collections import namedtuple
from functools import lru_cache
from typing import Optional, Iterator, Set, List
Cell = int
Board = namedtuple('Board', 'N, S, units, units_for, pic')
State = namedtuple('State', 'units, stars, unknowns')
We can describe the differently-shaped boxes with a picture consisting of of N lines of N non-whitespace characters, where each of N distinct characters in the picture corresponds to a box, as in this picture of a 5×5 board with 5 boxes:
, + ' ' '
, + : : '
, + : : .
, . . . .
, . . . .
def make_board(S, picture) -> Board:
"""Create a `Board` from a picture of the boxes."""
pic = ''.join(picture.split()) # eliminate whitespace from picture
N = int(len(pic) ** 0.5) # N is √(number of cells)
assert len(pic) == N * N
side = range(0, N)
cols = [{N * r + c for r in side} for c in side]
rows = [{N * r + c for c in side} for r in side]
boxes = [indexes(pic, ch) for ch in set(pic)]
units = cols + rows + boxes
units_for = {c: [u for u in units if c in u]
for c in range(N * N)}
return Board(N, S, units, units_for, pic)
def indexes(sequence, item) -> Set[int]:
"""All indexes in sequence where item appears."""
return {i for i in range(len(sequence)) if sequence[i] == item}
Here's the 5×5 board, and the board Barry Hayes shared to introduce me to this type of puzzle, and the "24" board. Note that in the "24" board the boxes "2" and "t" form interlocking figure 2s and the boxes "4" and "f" form interlocking figure 4s.
board5x5 = make_board(1, """
, + ' ' '
, + : : '
, + : : .
, . . . .
, . . . .
""")
board1 = make_board(2, """
` . . . . . | ; ; ;
` . . . . . | ; ; ;
` ` ` . . . | ; ; ;
` , ` . . . . ; ; ;
, , , . . + + = = =
, , : : + + + + + +
, : : ' ' ' ' ' ' +
, : : - - ' ' ' ' '
, : : : - - - ' ' '
, , , - - - - ' ' '
""")
board24 = make_board(2, """
. . . ' ' , , , , ,
. 2 2 2 ' 4 , 4 , -
. . . 2 ' 4 , 4 - -
. 2 2 2 ' 4 4 4 - -
. 2 t t t ; f 4 f -
. 2 2 2 t ; f 4 f -
. . t t t ; f f f -
: : t ; ; ; ; ; f -
: : t t t : - ; f -
: : : : : : - - - -
""")
I will solve puzzles using depth-first search with constraint propagation.
By "depth-first search" I mean a procedure that starts from a current state, then creates a new state with a guess that a star should go into some cell c, and then tries to solve the rest of the puzzle from the new state. If there is no solution, back up to the old state and guess a different cell for the star.
By "constraint propagation" I mean that whenever a star is placed, check what implications this has for the rest of the board: what blanks and/or stars must be placed in what cells. Constraint propagation may be able to prove that the original guess leads to failure, and it may make future guesses easier.
Note that search always creates a new state for each guess (leaving the old state unaltered so that we can back up to it) and constraint propagation always mutates the state (because the changes are inevitable consequences, not guesses).
The constraint propagation rules are:
When we put a star in a cell:
None
).When we put a blank in a cell:
def put_star(cell, board, state) -> Optional[State]:
"""Put a star on the board in the given cell. Mutates state.
Return `None` if it is not possible to place star."""
if cell in state.stars:
return state # Already put star in cell
state.unknowns.remove(cell)
state.stars.add(cell)
for unit in board.units_for[cell]:
if count_stars(unit, state) > board.S:
return None
for c in neighbors(cell, board.N):
if c in state.stars or not put_blank(c, board, state):
return None
return state
def put_blank(cell, board, state) -> Optional[State]:
"""Put a blank on the board in the given cell. Mutates state.
Return `None` if it is not possible to place blank."""
if cell not in state.unknowns:
return state # Already put blank in cell
state.unknowns.remove(cell)
for unit in board.units_for[cell]:
s = count_stars(unit, state)
unknowns = unit & state.unknowns
if s + len(unknowns) < board.S:
return None
if s + len(unknowns) == board.S:
if not all(put_star(c, board, state) for c in unknowns):
return None
return state
def count_stars(unit, state) -> int: return len(unit & state.stars)
@lru_cache()
def neighbors(cell, N) -> Set[Cell]:
"""The set of cells that neighbor a given cell on an N×N board."""
dxs = {0, +1 if cell % N != N - 1 else 0, -1 if cell % N != 0 else 0}
dys = {0, +N if cell + N < N ** 2 else 0, -N if cell >= N else 0}
return {cell + dx + dy
for dy in dys for dx in dxs if dx or dy}
Here are the two more main functions to do search:
solve(board)
: a wrapper function that calls search
and prints the results.search(board, state)
: where the real work of searching for a solution is done.def solve(board) -> Set[Cell]:
"""Call `search` with an initial state; print board and return solution stars.
Raise an error if there is no solution."""
stars = next(search(board, initial_state(board))).stars
print_board(board, stars)
return stars
def search(board, state) -> Iterator[State]:
"""Recursive depth-first search for solution(s) to a Star Battle puzzle."""
while state.units and count_stars(state.units[0], state) == board.S:
state.units.pop(0) # Discard filled unit(s)
if not state.units: # Succeed
yield state
else: # Guess and recurse
for c in state.units[0] & state.unknowns:
guess_state = put_star(c, board, copy_state(state))
if guess_state is not None:
yield from search(board, guess_state)
The inputs to search
are the static board
and the dynamic state
of computation, but what the output should be is less obvious; I considered two choices:
search
returns the first state that represents a solution, or None
if there is no solution.search
is a generator that yields all states that represent a solution.I decided on the second choice for search
, even though solve
only looks at the first solution. That way search
could be used to verify that puzzles are well-formed, for example.search
works as follows:
Below are the remaining minor functions. Note: in initial_state
, the units
are sorted
smallest-unit first, because if, say, a board has S=2 and the smallest unit has 3 cells, then you have a 2/3 chance of guessing correctly where the 2 stars should go. With larger units you would be more likely to guess wrong and waste time backing up, so better to do small units first and large units later, when constraint propagation has eliminated some unknown cells.
def copy_state(s: State): return State(s.units[:], set(s.stars), set(s.unknowns))
def initial_state(board) -> State:
"""The initial state to start the search for a solution to `board`."""
return State(units=sorted(board.units, key=len),
stars=set(), unknowns=set(range(board.N ** 2)))
def print_board(board, stars) -> None:
"""Print a representation of the board before and after placing the stars.
The output is not beautiful, but it is readable."""
N = board.N
def row(chars, i) -> str: return ' '.join(chars[i * N:(i + 1) * N])
filled = [('*' if c in stars else ch) for c, ch in enumerate(board.pic)]
for i in range(N):
print(row(board.pic, i), ' ' * N, row(filled, i))
print('Valid' if is_solution(board, stars) else 'Invalid', 'solution')
def is_solution(board, stars) -> bool:
"""Verify that all units have S stars and that stars are non-adjacent."""
return (all(len(stars & unit) == board.S
for unit in board.units) and
all(c1 not in neighbors(c2, board.N)
for c1 in stars for c2 in stars))
solve(board5x5)
solve(board1)
` . . . . . | ; ; ; ` . . . . . * ; * ; ` . . . . . | ; ; ; ` * . . * . | ; ; ; ` ` ` . . . | ; ; ; ` ` ` . . . * ; * ; ` , ` . . . . ; ; ; * , * . . . . ; ; ; , , , . . + + = = = , , , . . + + * = * , , : : + + + + + + , , : * + * + + + + , : : ' ' ' ' ' ' + , * : ' ' ' ' ' ' * , : : - - ' ' ' ' ' , : : * - * ' ' ' ' , : : : - - - ' ' ' * : : : - - - * ' ' , , , - - - - ' ' ' , , * - * - - ' ' ' Valid solution
{6, 8, 11, 14, 26, 28, 30, 32, 47, 49, 53, 55, 61, 69, 73, 75, 80, 87, 92, 94}
solve(board24)
. . . ' ' , , , , , . . . ' ' , * , , * . 2 2 2 ' 4 , 4 , - . 2 * 2 * 4 , 4 , - . . . 2 ' 4 , 4 - - * . . 2 ' 4 , * - - . 2 2 2 ' 4 4 4 - - . 2 * 2 * 4 4 4 - - . 2 t t t ; f 4 f - . 2 t t t ; f * f * . 2 2 2 t ; f 4 f - * 2 2 2 t * f 4 f - . . t t t ; f f f - . . t * t ; f f * - : : t ; ; ; ; ; f - : * t ; ; * ; ; f - : : t t t : - ; f - : : t * t : - ; * - : : : : : : - - - - : * : : : : * - - - Valid solution
{6, 9, 12, 14, 20, 27, 32, 34, 47, 49, 50, 55, 63, 68, 71, 75, 83, 88, 91, 96}
%%time
for board in (board5x5, board1, board24):
assert next(search(board, initial_state(board))).stars
CPU times: user 195 ms, sys: 2.98 ms, total: 198 ms Wall time: 197 ms