The Berkeley Crossword Solver | Hacker News Reader

The Berkeley Crossword Solver

bair.berkeley.edu

71 pointsgeox42 comments

For those who do cryptic crosswords, CrosswordGenius [1] on iOS (Android coming apparently) will solve clues for you - and explain the logic it used!

This is extremely helpful when you aren’t familiar with a particular setter’s style. If you’ve guessed an answer (and if you’re on a mobile app you might have already been able to verify that it’s correct) you may not be sure how the clue maps to it.

Example:

Digital projection tempered elation (7)

I believe the answer is:

TOENAIL 'digital projection' is the definition. (protection on a digit of the foot)

'tempered elation' is the wordplay. 'tempered' indicates an anagram (temper can mean to adjust or modify). 'elation' is an anagram of 'TOENAIL'.

[1] https://www.crosswordgenius.com/

Usually my approach is: 1) try to answer straight away, 2) try to answer once I have some letters from other clues, 3) use a thesaurus, 4) use an anagram solver, 5) wait for tomorrow's paper. I already feel wretched about 3/4, I'm not sure I want to cheat more than that.

But sometimes this completely falls down and I have no idea where something comes from, e.g.: "Theatre of war where activity was uncovered (8)" is WINDMILL which still baffles me.

fifteensquared.net is great for explained answers, see eg http://www.fifteensquared.net/2018/03/09/independent-9798-ph... for the WINDMILL explanation.

Oh, lovely, thank you. I figured it had to be the theatre and still didn't get it. This hobby regularly makes me feel dumb. :)

btw, do you happen to be British?

The reason I ask is that only British people seem to add "lovely" in their sentences.

Also, I now learnt that the WINDMILL answer refers to something in London. I don't know how outsiders — say a random person from Argentina — is supposed to know that.

Yeah sometimes they test vocabulary, sometimes they test general knowledge (or at least your ability to google or have an anagram solver). So you do learn while solving, which is a plus.

Also yes, your Britometer is operating correctly.

You probably meant "Britometre" :)

Don't forget the question mark at the end of the clue, it's quite significant!

My approach was to try to write a bunch of cryptic clues of my own. That way I got more practiced at recognizing the various wordplay indicators.

Crossword genius is outstandingly good at cryptics.

Is there much new work being done on automatic crossword puzzle generation?

I could only find one paper in a very brief Google search:

> AUTOMATIC GENERATION OF CROSSWORD PUZZLES

> LEONARDO RIGUTINI, MICHELANGELO DILIGENTI, MARCO MAGGINI and MARCO GORI

https://doi.org/10.1142/S0218213012500145

There are plenty of automatically generated puzzles. Most of the crossword puzzle books in the supermarket (without an editor or bylines) are completely auto-generated. They are like verbal Sudoku with trivia. They have no soul.

"Real" crosswords have a fresh theme (the 3-5 longest entries that usually stretch across the entire puzzle) and fresh clues if not answers for the fill. Maybe GPT-x could come up with fresh clues (though you would still need an editor), but coming up with a fresh theme would be the truly challenging part.

I am neither good at crossword puzzles nor at making them.

I am curious about how hard it is to make a simple one.

I'm planning to put together a sort of activity book for a user group meeting this fall, for the open source package "RDKit", which is used in cheminformatics and related fields.

I thought it might be fun to have a cheminformatics crossword puzzle, with words and ideas from my field.

For example, "Ran for US President" with the answer "[Au].O"; those being a way to denote "Gold" and "water" in the SMILES notation.

Saying with SMILES, there are some interesting permutation possibilities, like O=S or S=O for sulfur monoxide.

With a theme around, say, edible chemicals (caffeine = "Cn1c(=O)c2c(ncn2C)n(C)c1=O" and permutations thereof, vanillin = "c1(C=O)cc(OC)c(O)cc1", etc).

So I've got an esoteric theme, and am looking for pointers on how to put them together.

So if I had to come up with a crossword solver, the first (dumb) approach I would try is the following:

- Come up with guesses for each clue (somehow—let's ignore the "how" for now)

- Prune all guesses whose letters mismatch with all the guesses for overlapping words

- Hopefully, you now have only one consistent solution set

Could someone explain why this approach doesn't work, and why you need probabilistic approaches?

How do you decide which guess to prune? Likely almost every guess would have a conflict, so if the space of possibly changes would be combinatorially large.

If your guesses for 1-across are AAA and BBB, and your guesses for 1-down are ABC and DEF, and they share their first letters in common, then you necessarily have to prune DEF and BBB. I don't think there's a combinatorial explosion anywhere here right?

In your contrived example, you only know the right answer after considering all four possible combinations. That is a combinatorial explosion when there are only two choices to make.

No, you don't need to do it with such a slow algorithm like that. There are only 26 possibilities for a given square. All you need is to track the set of possible letters for each square in each direction (52 bits of information—you can even literally fit it into a 64-bit integer). Then for each guess going across, cross it off your list if its corresponding letter isn't in the set of letters going down, and vice-versa. It should be pretty darn quick without any exponential growth.

How do you select the first guess? e.g. the clue is "popular yellow cartoon bear", and the answer is "pooh". You can satisfy the crossword using random words and a dictionary somewhat easily, but that's not really the task at hand.

This solution would work if there were only one valid configuration for your set of possible guesses, but there will be many valid configurations. But you're right, it's not an exponential in the number of possible guesses, rather possibly an exponential in the number of possible guesses that lead to a valid configuration.

> In your contrived example, you only know the right answer after considering all four possible combinations.

This is basically correct.

> That is a combinatorial explosion when there are only two choices to make.

But this isn't; you're being misled by the fact that 2×2 is equal to 2+2. The described algorithm is doing rows + columns amount of work, not rows × columns. If you had 14 guesses across and 3 guesses down, you'd know which ones to prune (according to this algorithm) after looking at 17 things. This is not a combinatorial explosion.

The issue is going to be in whittling down conflicts, there can be many clues which have at least one valid cross for each cross. If there are even a modest number of rows/columns (say, N) each with a modest number of solutions (say, M), your performance for checking is going to be very poor. You'll have to backtrack through the solution space I believe trying different possibilities, which should be m^n. For example for n=20 and m=3 you'll have 3^20, which is 3,486,784,401. Certainly not the worst, but this is quite sensitive to the numbers. If you have say 5 solutions on average you're instead looking at 9 * 10^13.

I’m not sure but I’d guess that step 1 is usually too difficult. So you can either:

- produce short lists of candidates, in which case your pruning will often end up with no solution at all because you’re missing the correct answer in your list of candidates for some of the clues.

- produce long lists of candidates, in which case your pruning won’t converge to a unique solution.

Using probabilistic approaches, I think you can

- include the possibility that a given clue’s solution isn’t on your list at all (i.e. your solver will occasionally deduce a solution from crosses only)

- use the probabilities of your other candidates list to have a better chance of guessing these unknown words and of choosing the right solution when your pruning doesn’t give a unique solution.

Is this a totally different thing than Dr. Fill [1]?

[1]: https://slate.com/technology/2021/04/american-crossword-puzz...

It is. The results section indicate that BCS performs better than Dr. Fill by a significant amount.

I'm curious how well this performs on the New York Times Thursday puzzles, and specifically whether or not it can handle rebus answers where multiple letters can exist in a single square.

Or something like November 26, 2020, with what is kind of an anti-rebus and letters that span more than one cell, or January 27, 2022 with musical notation for repeated letters in a word, or February 7, 2019 which involved writing outside the puzzle grid.

Thursdays can sometimes hurt my head.

How does the "competition" work? Is it "live"? Is it online? Is there an accuracy component? I'm intrigued how the NYT ran a crossword competition with thousands of competitors.

> Proverb and Dr. Fill. Proverb is a 1998 system that ranked 213th out of 252 competitors in the tournament.

> Dr. Fill’s first competition was in ACPT 2012, and it ranked 141st out of 650 competitors.

> We teamed up with Dr. Fill’s creator Matt Ginsberg and combined an early version of our QA system with Dr. Fill’s search procedure to win first place in the 2021 ACPT against over a thousand competitors.

If I remember correctly my dad would go to New York City to compete in person. If you make mistakes you're not going to win.

I'd like to see its performance on New York Times crosswords split into decades. I suspect they've been getting dumbed down.

I'm looking for a good online cryptic crossword. Something harder than Lovatt's Cryptic. The Guardian is no good, I can look at their solutions and still have no idea why those are the answers.

May be the Guardian one needs a Chambers dictionary to solve it?

But still, is there a good guide to get into Cryptics?

Cracking the Cryptic, e.g.: https://youtu.be/ecytVCusIeY

It's mostly a variant sudoku channel but Mark Goodliffe is an insanely good cryptic crossword solver, and both Simon and Mark are good teachers.

Beyond the intro the key skills are: parsing the clues into definition and wordplay, knowing signifiers for different types of wordplay, recognising common abbreviations (there are lists a web search away), recalling short synonyms, and anagramming.

If you want to get your mind blown I highly recommend spending the $2 for Cracking the Cryptic's Patreon to watch Mark solve the Monthly Club Special using almost pure wordplay and whatever string manipulation coprocessor he has in his head (which also seems to work for sudoku too).

That youtube channel seems to have veered into mostly Sudoku style puzzles than Cryptics.

Yes I said that. Still -- many, many hours of cryptic crosswords being solved and explained if you want to see how the best in the world does it.

There’s a subreddit on UK-style crosswords that will help you with understanding clues: r/crosswords. NB that r/crossword is for the US style.

You might find the Telegraph easier than the Graun to start with.

You just need to ask someone /read guides about solving cryptic crosswords. Once you get used to it, it makes sense, but there can a surprising amount of 'unofficial' knowledge (abbreviations, 'common' crossword answers, etc), or things which are uk-specific and are not straightforward if you're not from the uk.

Some compilers are also easier than others / will make more sense to you (I like brendan, nutmeg, vulcan, and philistine).

More useful than just the solutions on the Grauniad's site is https://www.fifteensquared.net/ which has solutions with explanations of most of the UK newspaper cryptic crosswords, including the Guardian.

This seems believable. I've been solving the saturdays at a higher rate over time.

Perhaps your skill is improving...

I once posted somewhere about this and was met with an avalanche of insistence that I was wrong.

For anyone who doubts this, I suggest doing a few puzzles from this book of old Mondays from the 90s. This will very quickly dispel any doubt about this proposition. The puzzles in this book are Wednesday/Thursday-level and sometimes even harder.

https://www.amazon.com/New-York-Times-Favorite-Crosswords/dp...

I wrote some of my thoughts on the BCS here. tldr: I don’t think BCS outperforms humans.

https://twitter.com/_eigenfoo/status/1528427650187943941

Are there any nontrivial connections to term rewriting in this work?

Reply on news.ycombinator.com