Peter Norvig
Aug 2021

Star Battle Puzzles¶

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:

Like Sudoku, you start with an N×N board and fill in cells.
Like Sudoku, an N×N board has 3N units: N columns, N rows, and N boxes.
Like Sudoku, a well-formed puzzle has exactly one solution.
Unlike Sudoku, the boxes have irregular shapes (not squares) and differing numbers of cells.
Unlike Sudoku, there are only 2 possible values for each cell: star or blank (not 9 digits).
Unlike Sudoku,
The constraints are:
- Each unit (column, row, or box) must have exactly S stars.
- Two stars cannot be adjacent (not even diagonally).

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.

Representation¶

Here's how I will represent Star Battle puzzles:

A cell is an integer in range(N * N).
- The top row is cells 0, 1, 2, ... left-to-right; the second row is N, N + 1, N + 2, ...; etc.
A unit is a set of cells.
A board is a named tuple with the attributes:
- 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.
An intermediate state in a search for a solution is a named tuple with the attributes:
- 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.
A solution is a set of cells where the stars go.
A failure to find a solution is indicated by None.

In [ ]:

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')

Representing Boards¶

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:

, + ' ' '
, + : : '
, + : : .
, . . . .
, . . . .

In [ ]:

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.

In [ ]:

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 -
: : : : : : - - - -
""")

Solving Strategy¶

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).

Constraint Propagation¶

The constraint propagation rules are: When we put a star in a cell:

Mutate the current state by adding the cell to the set of stars and removing it from the unknowns.
If any of the cell's units has more than S stars, then fail (return None).
Put a blank in each adjacent cell. If you can't, fail.

When we put a blank in a cell:

Mutate the current state by removing the cell from the unknowns.
For each of the cell's units:
- If the number of stars plus unknown cells in the unit is less than S, then fail.
- If the number equals S, then put stars in the unknown cells. If you can't, fail.

In [ ]:

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

In [ ]:

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}

Depth-First Search¶

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.

In [ ]:

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:

While the state's first unit is already filled with S stars, discard that unit and move on to the next one.
If the state has no remaining unfilled units, then succeed: yield the state.
Otherwise, guess and recurse: for each unknown cell c in the first unit, create a new state with a star in cell c, and if placing the star does not lead to constraint-propagation failure then recursively search from that state.

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.

In [ ]:

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))

Solutions¶

In [ ]:

solve(board5x5)

In [9]:

solve(board1)

` . . . . . | ; ; ;            ` . . . . . * ; * ;
` . . . . . | ; ; ;            ` * . . * . | ; ; ;
` ` ` . . . | ; ; ;            ` ` ` . . . * ; * ;
` , ` . . . . ; ; ;            * , * . . . . ; ; ;
, , , . . + + = = =            , , , . . + + * = *
, , : : + + + + + +            , , : * + * + + + +
, : : ' ' ' ' ' ' +            , * : ' ' ' ' ' ' *
, : : - - ' ' ' ' '            , : : * - * ' ' ' '
, : : : - - - ' ' '            * : : : - - - * ' '
, , , - - - - ' ' '            , , * - * - - ' ' '
Valid solution

Out[9]:

{6, 8, 11, 14, 26, 28, 30, 32, 47, 49, 53, 55, 61, 69, 73, 75, 80, 87, 92, 94}

In [10]:

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

Out[10]:

{6, 9, 12, 14, 20, 27, 32, 34, 47, 49, 50, 55, 63, 68, 71, 75, 83, 88, 91, 96}

In [11]:

%%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