{"id":448,"date":"2018-01-16T09:27:28","date_gmt":"2018-01-16T17:27:28","guid":{"rendered":"http:\/\/alexboisvert.com\/musings\/?p=448"},"modified":"2018-02-19T13:40:21","modified_gmt":"2018-02-19T21:40:21","slug":"solving-star-battle-puzzles","status":"publish","type":"post","link":"https:\/\/alexboisvert.com\/musings\/2018\/01\/16\/solving-star-battle-puzzles\/","title":{"rendered":"Solving Star Battle Puzzles"},"content":{"rendered":"

UPDATE: There is now a JavaScript Star Battle Solver!<\/a> 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.<\/p>\n

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.<\/p>\n

Anyway, one member of our team designed a pretty cool logo:
\n\"\"<\/a>
\nIt’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:<\/p>\n

\r\nimport numpy as np\r\n# pip install python-constraint\r\nfrom constraint import Problem\r\n\r\nclass StarBattle:\r\n    '''\r\n    A class for storing, solving, and printing star battle problems\r\n    '''\r\n    def __init__(self,matrix=None,stars=1):\r\n        self.matrix = matrix\r\n        self.stars = stars\r\n        self.solutions = None\r\n        \r\n    def set_matrix(self,matrix):\r\n        self.matrix=matrix\r\n        \r\n    def solve(self):\r\n        M = self.matrix\r\n        problem = Problem()\r\n        \r\n        myvars = np.unique(M)\r\n        \r\n        # The variables are the elements in the matrix\r\n        # The domain for each variable is where it can be\r\n        def where(M,i):\r\n            coords = np.array(np.where(np.isin(M,i))).T\r\n            return [tuple(j) for j in coords]\r\n        \r\n        for i in myvars:\r\n            problem.addVariable(i,where(M,i))\r\n        \r\n        def is_not_adjacent(xy1,xy2):\r\n            # Return true if two stars are not adjacent, in the same row, or same column.\r\n            x1,y1 = xy1; x2,y2 = xy2\r\n            if abs((x2-x1)*(y2-y1)) <= 1:\r\n                return False\r\n            else:\r\n                return True\r\n            \r\n        # Problem constraints\r\n        for i in myvars:\r\n            for j in myvars:\r\n                if i < j:\r\n                    problem.addConstraint(is_not_adjacent,(i,j))\r\n\r\n        self.solutions = problem.getSolutions()\r\n        \r\n    def display_solutions(self):\r\n        # This is an ugly but effective way to display solutions\r\n        # DIsplay\r\n        if self.solutions is not None:\r\n            for s in self.solutions:\r\n                N = np.zeros_like(self.matrix)\r\n                for k,v in s.iteritems():\r\n                    N[v] = 1\r\n                print N\r\n                print\r\n    \r\n    def display(self):\r\n        print self.matrix\r\n#END class StarBattle\r\n\r\nif __name__ == '__main__':\r\n    M = np.array([\r\n    [0,0,0,1,1,2,1],\r\n    [3,0,1,1,1,1,1],\r\n    [3,0,4,4,1,6,1],\r\n    [3,3,4,5,5,6,1],\r\n    [3,3,4,5,5,6,1],\r\n    [3,4,4,5,6,6,6],\r\n    [3,3,3,3,3,3,3]\r\n    ])\r\n\r\n    star_battle = StarBattle()\r\n    star_battle.set_matrix(M)\r\n    star_battle.display()\r\n    print\r\n    star_battle.solve()\r\n    star_battle.display_solutions()\r\n<\/pre>\n
This works very fast, so I'm happy with it.  It also gave me a chance to learn about the python-constraint<\/a> library.  However, there are two things I'd like to do to improve it.<\/p>\n
(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.<\/p>\n
(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<\/a> so I feel the code should ideally be written there.<\/p>\n
Any takers to help solve either of these issues?<\/p>\n","protected":false},"excerpt":{"rendered":"
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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5],"tags":[],"class_list":["post-448","post","type-post","status-publish","format-standard","hentry","category-coding","category-puzzles"],"_links":{"self":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/448","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/comments?post=448"}],"version-history":[{"count":7,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/448\/revisions"}],"predecessor-version":[{"id":461,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/posts\/448\/revisions\/461"}],"wp:attachment":[{"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/media?parent=448"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/categories?post=448"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/alexboisvert.com\/musings\/wp-json\/wp\/v2\/tags?post=448"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}