Box Relatives

Thoughts about puzzles, math, coding, and miscellaneous

Solving Star Battle Puzzles

| 6 Comments

UPDATE: There is now a JavaScript Star Battle Solver! It’ll solve fairly simply ones no problem. Don’t expect miracles on harder puzzles, though — more likely than not they will just crash your browser.

This past weekend I “attended” my first MIT Mystery Hunt as part of Test Solution Please Ignore. I didn’t do much solving but what I did do was a lot of fun. Maybe I’ll attend in person next year; it’s always nice having an excuse to go to Boston.

Anyway, one member of our team designed a pretty cool logo:

It’s a “TSPI”-themed star battle puzzle! You solve it by placing one star in each row, column, and region. I thought it was pretty cool, but I’m better at coding than solving, so I thought I’d write a quickie program in Python to solve it (and others). Here it is:

import numpy as np
# pip install python-constraint
from constraint import Problem

class StarBattle:
    '''
    A class for storing, solving, and printing star battle problems
    '''
    def __init__(self,matrix=None,stars=1):
        self.matrix = matrix
        self.stars = stars
        self.solutions = None
        
    def set_matrix(self,matrix):
        self.matrix=matrix
        
    def solve(self):
        M = self.matrix
        problem = Problem()
        
        myvars = np.unique(M)
        
        # The variables are the elements in the matrix
        # The domain for each variable is where it can be
        def where(M,i):
            coords = np.array(np.where(np.isin(M,i))).T
            return [tuple(j) for j in coords]
        
        for i in myvars:
            problem.addVariable(i,where(M,i))
        
        def is_not_adjacent(xy1,xy2):
            # Return true if two stars are not adjacent, in the same row, or same column.
            x1,y1 = xy1; x2,y2 = xy2
            if abs((x2-x1)*(y2-y1)) <= 1:
                return False
            else:
                return True
            
        # Problem constraints
        for i in myvars:
            for j in myvars:
                if i < j:
                    problem.addConstraint(is_not_adjacent,(i,j))

        self.solutions = problem.getSolutions()
        
    def display_solutions(self):
        # This is an ugly but effective way to display solutions
        # DIsplay
        if self.solutions is not None:
            for s in self.solutions:
                N = np.zeros_like(self.matrix)
                for k,v in s.iteritems():
                    N[v] = 1
                print N
                print
    
    def display(self):
        print self.matrix
#END class StarBattle

if __name__ == '__main__':
    M = np.array([
    [0,0,0,1,1,2,1],
    [3,0,1,1,1,1,1],
    [3,0,4,4,1,6,1],
    [3,3,4,5,5,6,1],
    [3,3,4,5,5,6,1],
    [3,4,4,5,6,6,6],
    [3,3,3,3,3,3,3]
    ])

    star_battle = StarBattle()
    star_battle.set_matrix(M)
    star_battle.display()
    print
    star_battle.solve()
    star_battle.display_solutions()

This works very fast, so I'm happy with it. It also gave me a chance to learn about the python-constraint library. However, there are two things I'd like to do to improve it.

(1) Star battle puzzles with a single star in each row, column, and region are easily solved above. But what about more advanced ones, with two or more stars? I'm not sure how to rewrite the code to do that, and I'd like to.

(2) Python is fine, but ideally this would be done in JavaScript so people could solve in their browsers. There's a port of the Python library in JavaScript so I feel the code should ideally be written there.

Any takers to help solve either of these issues?

6 Comments

  1. Hi Alex,
    Sorry this comment is off topic but, you seem to have forgotten more about puzzles than I will ever know or understand.
    I am a prof in a Dept. of Chemistry (hence my profound ignorance of puzzle things) but I am giving an introductory course where I have students fill in a x-word puzzle to help them with the vocabulary. They seem to enjoy it and it is useful. The current class enrollment is about 50 but is expected to go >300 when it goes on-line next year. I currently have about 20 different versions of the same puzzle (to help limit communal solutions) and correcting them manually is slow. I can’t imagine correcting hundreds.
    Do you, perchance, know of a tool/software that can create electronically fillable crossword puzzles that the students could then submit electronically for grading? Ideally I could then load the file and verify the answers electronically too but a workable solution would be to extract the student’s answers into a list that I can side-by-side compare to the word list used to generate that puzzle. Creating a Word or PDF “form” allows text to be entered and extracted but I can’t get a fillable puzzle into either format.
    I have played around with a few puzzle tools but most of them generate static images of the puzzle which aren’t fillable or HTML files that also contain the answers to the puzzle which the students will find “helpful” when completing the puzzle.
    Any suggestions would be welcome.

    Thanks,
    Cameron
    P.S. I’ll be coming back for your machine learning material in R. I’m just starting to learn R (matlab is my usual) and I have a few chemometric problems in biomarker discovery that are well suited to unsupervised machine learning.

  2. Hey There. I discovered your blog using msn. That is a very smartly written article. I will make sure to bookmark it and come back to read more of your useful information. Thanks for the post. I will certainly return.

  3. I don’t know Python enough to figure out your code, but with simple backtracking, you can do multi-star puzzles just as easily as single-star ones.

    The algorithm is as follows:
    – Start in upper left corner and try to place a star.
    – If you can, without violating any constraints, mark that space as starred, and recurse starting at the next square, otherwise just move on to the next square in the row.
    – After the recursion returns, skip that square, and proceed to the next in the row.
    If you get all the way to the end without violating the constraints you have found a solution.

    If you reach the end of a row and haven’t placed enough stars in that row,
    there is no need to go further.

    Here is some pseudo-code:
    function solve(row, column)
    {
    for (c = column to end-of-row)
    {
    if (reached the last row, last square) {show-solution(); return;}
    if (can put a star square [row, c] )
    {
    place star in square;
    if (row is FULL) solve(row+1, 0) # go to next row immediately
    else if (not end of row) solve(row, c+1)
    remove star;}
    } # end if placed
    } # end loop
    } # end function
    solve(0, 0);

  4. I have found difficulty using this algorithm to solve puzzles with different dimensions. Do you have any advice on how to solve this?

  5. Hi, I’ve been having trouble using the program to solve puzzles with different dimensions. Do you know how to adjust it so that it works with any size array?

Leave a Reply

Required fields are marked *.


This site uses Akismet to reduce spam. Learn how your comment data is processed.