OddThinking

A blog for odd things and odd thoughts.

Puzzling over Puzzles

Let’s divide the world of puzzles into the type that are real dilemmas versus the type people do for fun, and look at the latter for a while.

Let’s divide the fun puzzles into the type they put in newspapers each day versus the type they don’t. The distinction is important – the type they put into newspapers each day can’t be the sort of puzzle like “Estimate the number of grooves on an vinyl 33 1/3 rpm LP album.” They have to be the sort where they can generate new ones each day following the standard structure.

These newspaper style puzzles can be divided up again along a spectrum from the type that require general knowledge (like trivia quizzes) to the type that require the ability to solve logic problems. Crosswords and Target words fit somewhere in the middle.

I only attempt the trivia type puzzles occasionally. I feel little sense of failure for being ignorant of a useless fact or an unusual word, so I have limited motivation to finish a crossword.

So let’s look at the logic puzzles at the other end of the spectrum.

To open up a newspaper and to solve a puzzle in it is an achievement… in a way… I guess.

However, being a algorithm geek, I don’t think you haven’t really solved a puzzle until you constructed a repeatable process to solve the class of puzzles…

…and being a software geek, I don’t think you have really, truly beaten the puzzle until there is some software to completely automate the process finding the solution.

I have annoyed people with this approach before – it tends to kill dead any amusement from the puzzle in the future.

I was given a tiling puzzle as a gift once, and while I was grateful for the thought behind the gift, I never actually took it out of its packaging. I read the rules, and suspected that the puzzle was NP-complete [Ref]; I didn’t see any point in playing with it, if I couldn’t solve it algorithmically.

Perhaps I was too hasty – I have whiled away some time with Microsoft’s Minesweeper, in the past, but now I have learnt that Minesweeper is NP-complete. I currently find myself with no urge to play it ever again – I wonder if that feeling will pass.

A good compromise is to write some software to assist you in solving the puzzle – performing the drudgery of mundane calculations without actually stepping over the mark and simply searching through the solution space for an answer.

It has been an approach I have used in the past for puzzles like Codewords and Solitaire Battleships. [To my horror, Solitaire Battleships is probably NP-complete too. Oooops.]

Casey once made a similar point about some software he was writing to solve a puzzle. He simply refused to use “backtracking” in his algorithm.

Backtracking is a term to describe letting your computer play a trial-and-error guessing game. The computer can guess a a solution first and then check to see if the result is right. If not, it “backtracks” and guesses again. If a computer can make thousands of semi-educated guesses a minute, it may not take that long to find a solution to a particular puzzle.

If you use backtracking, then you have given up trying to skillfully pick the lock to the door that separates you from a general solution, and are instead are using the sheer weight of your computer as a battering ram.

So to summarize:

If you can automate the process without backtracking, you have solved it, and and the puzzle is probably no longer interesting.

If you can automate half of the process without backtracking, you may have a useful tool to assist you in solving some of the more challenging problems.

Alternatively, it may just be NP-complete. While it might be amusing to solve particular instances, you are never going to really beat it.


Comments

  1. Do you know, is there any software available for the construction and solving of codewords as opposed to using crossword compilers.

  2. Peter,

    For the construction of codewords? I don’t know – I’ve never looked.

    For the solution of codewords? As I mentioned above, I wrote one myself. It didn’t attempt to solve the puzzle, but just to assist.

    It performed three key functions:

    1) It allowed you to type in a letter corresponding to a number, and have it immediately fill in all the locations of that number. Similarly, you could undo a guess, and have it clear it immediately, and would get a visual warning if you used the same letter twice.

    2) It produced a frequency list for each number. This would greatly assist the location of “e” and “t”, and also helped focus on the best numbers to guess next.

    3) It assumed that “q” was always followed by a “u”, and tried to find numbers that might be “q” because they were always followed by the same corresponding number which would therefore be the “u”. It would highlight these as “q-candidates”. Normally there would be two or three, but on one occasion there was only one. That made the value for “u” obvious, and gave a big help for the rest of the puzzle.

    Now the bad news. I wrote this in early 1991 in QBASIC (possibly GWBASIC? I would have to check the historical timelines of those languages.) The executable no longer runs; it is missing a run-time library I no longer have. I still have the source, but it is in a binary format that I can’t read. I am not really that motivated to work through the issues here: to find a tool to load it in, save it as ASCII and then learn enough Visual Basic to port it across. It would be faster to re-write it from scratch, and that would be less distressing than looking at what passed for my coding style 14 years ago!

    Good luck with your search; sorry I can’t be more help. Please feel free to post your results here.

  3. thanks for taking the trouble to reply
    i am still looking but what you describe is basically what i am looking for as it is very laborious inserting each letter individually

  4. I finally found a program that solves Codewords, but unfortunately it doe’s not show you a grid.
    It is very effective, as it will solve a single letter or the entire puzzle. Coded Crossword Magic 2.1 by XL Software Ltd. having spotted it on eBay and bought it for the princely sum of £5.98

Leave a comment

You must be logged in to post a comment.

Web Mentions

  1. OddThinking »

  2. girtby.net » Blog Archive » FreeBSD considered handful

  3. OddThinking » Beating the Clock Solitaire

  4. OddThinking » Pursuing Sudoku with Pseudo-code

  5. OddThinking » Beating the Clock Solitaire

  6. OddThinking » Pursuing Sudoku with Pseudo-code

  7. OddThinking » Beating the Clock Solitaire

  8. Puzzled by Software Development

  9. OddThinking » Solitaire Battleships

  10. OddThinking » Solving the Four Fours Puzzle

  11. OddThinking » Virus 2: A Puzzle

  12. OddThinking » Solving Slitherlinks with Software

  13. OddThinking » Solving the Circuit Game

  14. OddThinking » Solving Nonograms

  15. OddThinking » OTTF Solver