Box Relatives

Thoughts about puzzles, math, coding, and miscellaneous

Solving Star Battle Puzzles

| 1 Comment

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?

One Comment

  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.

Leave a Reply

Required fields are marked *.