Creating Acrostic Puzzles – Crossword Nexus Blog

The Crossword Nexus Solver has supported acrostic puzzles for a while now, but acrostic puzzles remain relatively uncommon in the indie puzzle community. This is a shame, because acrostic puzzles are very fun, and I for one want to see more of them. So what’s holding constructors back?

Constructors may not know how to create a JPZ of an acrostic puzzle, but there’s good news there. Jeff Davidson’s kotwords site has an acrostic puzzle JPZ creation tool, which is very user-friendly. Just plug in your values and you’ve got a JPZ ready to make available on your site, or even embedded on your site.

Potentially a bigger challenge, though, comes with the creation of an acrostic puzzle. There’s no easily available tool to help with the creation of these things, and though it’s not too hard by hand, that may be a barrier to entry for new constructors. Well, we’ve got good news there too! Say hello to the Acrostic Generator, a Python script that will take your quote, author, and work, and spit out an acrostic for you, usually in under a minute. Don’t like one of the words in the result? Tell the generator that and it will make another one for you with that word excluded. You can use your own word list for this process and set the minimum score threshold within.

I don’t generally like releasing tools in Python, though, as it presents a barrier to entry for some people. I’ve tried writing this script in JavaScript but it was too slow for general use. But thanks to the magic of python anywhere, now anyone with a web browser can generate acrostic puzzles in this way.

Head on over to this link to leverage the Python script for yourself. It’s very user-friendly and will generally spit out a solution to your acrostic in well under a minute. In addition to the solution, it will also give you inputs to Jeff’s JPZ generator, so you can just copy/paste the data into that site. We’ll be making more puzzles like this soon, and we hope you do too. Enjoy!

Too many people to thank here, but let’s start with Parker supplying a first take on a solution to this problem, Jeremy for being a sounding board for ideas, and Joon for collaborating on getting acrostics into the JPZ format in the first place.

Most of you can stop reading here but if you want to know the technical nitty-gritty about how this got done, read on …

I tried several ways to get an efficient acrostic generator but nothing worked. Nearing the end of my rope, I ran across this Redditor’s solution to the star battle problem in which they cast the problem as an integer linear programming (ILP) one and simply applied an existing ILP solver. Now, integer programming is NP-complete, but that doesn’t mean there aren’t good heuristics for solving them, so I figured if I could simply cast this problem as an ILP one, I could leverage an existing solver just like the star battle solution did.

Now about ILP: my math brain likes to think of these problems as “maximize c^Tx subject to Ax=b” but I realize that’s not everyone’s cup of tea. Instead, you can think of an ILP problem like this: you have a large set of variables from which you want to choose only those that meet some constraint. Then within those that meet that constraint, you want to maximize some value.

How does this work in our case? Let’s set the variables to be the words in our word list, and the constraints are (1) the number of letters in the word, and (2) the starting letter of the word. You can visualize this like so:

[
  {
    "word": "theater"
  , "a": 1
  , "e": 2
  , "h": 1
  , "r": 1
  , "t": 2
  , "t_first": 1
  // all other variables 0
  }
, {
    "word": "help"
  , "e": 1
  , "h": 1
  , "l": 1
  , "p": 1
  , "h_first": 1
  // all other variables 0
  }
  ...
]

In our case,we have two constraints: the total sum of our letters must match the letter counts from the quote, and the first letter counts must match the letter counts from the source. So the constraints might look like

{
  "a": 4
, "b": 2
...
, "a_first": 2
, "b_first: 0
...
}

Side note: this might be how the Internet Anagram Server works?

That’s basically it. Construct those variables, plug them in to an ILP solver and you’re done. But wait — we’re not maximizing anything! All we’re doing here is taking any old solution that works, but we could be maximizing score (from our word list), or minimizing deviation from the mean word length, or any number of things. This is an obvious extension to our code, and I hope someone jumps on it.

Related Posts