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?