Box Relatives

Thoughts about puzzles, math, coding, and miscellaneous

January 16, 2018
by Alex
6 Comments

Solving Star Battle Puzzles

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?

November 16, 2016
by Alex
0 comments

The new alexboisvert.com

If you’re a regular visitor to this website, you probably noticed that the front page isn’t there anymore, having been replaced by this blog. Well, that’s because all the stuff that used to be there has been refactored in JavaScript and moved to Crossword Nexus. Here are the specific links:

I think you’ll like the new versions better — they’re faster than the old code and nothing is ever uploaded to our servers.  Enjoy and tell me what you think!

September 13, 2015
by Alex
0 comments

Introducing Crossword Dash

Yesterday, at the September 2015 Southern California Puzzle Party, I introduced a game called Crossword Dash. It’s a bluffing game along the lines of Balderdash (TM), but instead of guessing the definition to a word, the players guess a clue corresponding to an entry from a terrible crossword. Aside from a few technical snafus, the game went well and it appeared people had a good time.

If this sounds fun to you but you couldn’t be there yesterday, I have good news! You can play this game any time you like at http://www.crosswordnexus.com/dash. The game is completely free, and pre-loaded with 150+ pairs of terrible clues/answers. I don’t think people will get a lot of use out of it since it is a pretty niche game, but if you’re ever around like-minded crossword people (say, at a crossword tournament or puzzle hunt) it turns out to be a pretty fun party game. You just need one person to host, and everyone playing has to have an internet-connected device.

Please do try it out and give me your feedback! This was a fun thing to make and I hope people have some fun playing it.

May 21, 2015
by Alex
0 comments

NPR Puzzle for 2015-05-17: Solving With Python

Here’s this week’s NPR puzzle:

Name a country with at least three consonants. These are the same consonants, in the same order, as in the name of a language spoken by millions of people worldwide. The country and the place where the language is principally spoken are in different parts of the globe. What country and what language are these?

Let’s see what the NLTK can do for us here.
Continue Reading →

April 30, 2015
by Alex
12 Comments

HTML5 Solver Feedback

At this point the HTML5 Crossword Solver is basically done, so I’m taking it out of its brief “beta” phase. There is now a recommended way to embed it in websites, like I’ve done above. And it will even automatically resize itself if you shrink your window — go ahead, try it out! Once again, I can’t thank Alex Shpak enough for coding all of this up.

But Alex S. can only take me so far. Now I need your help. I would really, really appreciate it if you would take five minutes or so and solve a puzzle in the solver, either the embedded one above, or one of your own JPZs at the official site. Is there anything in the interface you can’t live without? A “check” feature and timer come to mind, but maybe there’s something else. Are there any keyboard shortcuts that are missing? Do all the keys behave like you’d expect them to? The hope is that this will be everyone’s go-to interface for JPZ solving, so if there’s a reason you would be hesitant to use this, I want to know about it. (Or, if you just LOVE it, you can leave a comment saying that too.)

I can’t thank you enough for doing this. Together we can make this the best crossword solver there is!

April 18, 2015
by Alex
2 Comments

Introducing the Crossword Nexus HTML5 Solver

People seem to agree that JPZ files are the future of crossword solving. JPZs are extremely flexible, well-documented, and supported by the most popular crossword-making software. The problem thus far with JPZs has been solving them. XWord is great but only available for PCs. Crossword Solver is cross-platform, but many are somewhat less than enamored with its solving interface.

Somehow, the state of online solvers is even worse. If you want to embed puzzles in your website, what can you do? You can get a java version and deal with all the overhead and security risks that come there. You can buy Crossword Compiler and they’ll give you a license to use their HTML5 solver, but its interface isn’t any better than Crossword Solver’s, and it can’t handle all of the JPZ features you might want.

We decided to kill two birds with one stone. Introducing the Crossword Nexus Solver (currently in beta). It runs in your HTML5-compliant browser on any platform you may have (Windows, Mac, Linux, etc.) Just choose a .jpz file and it will render it for you, allowing you to solve it with an interface you’ll like. It can handle wacky JPZ files like Marching Bands no problem. And if you know any CSS you can modify it to run on your website — but we hope to have an “official” version like that out soon.

The best part? The code behind the solver is completely free, released under the BSD-3 License, and available on Github. If you know any Javascript, feel free to fork it and work on improving it. With the whole crossword community behind it, this solver will be improved much faster than it would with just one person. I’m really looking forward to seeing what this becomes.

Huge thanks to Alex Shpak, who did a great job doing the heavy lifting for the coding. Enjoy!

October 20, 2014
by Alex
2 Comments

Rot-13 Bookmarklet

Rot-13

Drag this link into the bookmark toolbar of Firefox or Chrome. When you highlight text in your browser and click the bookmarklet, it will automatically be encrypted (or decrypted) with Rot-13. Want to try it out? Highlight the following and click the bookmarklet.

Url, pbatenghyngvbaf, vg ybbxf yvxr vg’f jbexvat!

The code is based on the Rot-13 bookmarklet found here, with extra functionality for selecting more highlighted info from this StackOverflow answer.

September 14, 2014
by Alex
3 Comments

Puzzle Party Idea

Here in the Los Angeles area, puzzle-minded people like myself gather every two months for what we like to call a “puzzle party.” Several regulars will bring puzzles or games and we’ll solve them as a group. In the most recent one I presented a pairs solving puzzle (but one that’s doable solo) — you can download the PDF by clicking here.

Still, I got to thinking about what I might present for a future installment, and I came up with a game I’d like to call “Crosswordash.” I need some help perfecting the idea, though. If you’re interested in adding your thoughts, I’d love to hear them. Details after the jump …
Continue Reading →

August 14, 2014
by Alex
9 Comments

NPR Puzzle for August 10, 2014: solving with Python!

Here’s this past week’s NPR puzzle:

Name a well-known movie of the past — two words, seven letters in total. These seven letters can be rearranged to spell the name of an animal plus the sound it makes. What animal is it?

Brute-forcing this puzzle is easy but ineffective. We can get a list of movies from IMDB and see which of the seven-letter ones can anagram into two words. But you don’t want to do this, because it will force you to sift through a ton of results. Can we do better? (Yes, we can.)
Continue Reading →