Here’s a game. It only has one rule, but you also need to know how to set it up. The headings that follow are taken from Monopoly.

SETUP

Take some coins. Shake them up, and spread them on a flat surface. Flatness isn’t that important. But you don’t want the coins to be sliding around – a sticky surface would work too.

PLAYING THE GAME

Keep doing this: Pick any pair of adjacent coins. If one of them is ‘heads’ and the other is ‘tails’, turn one of them over so they both agree (this is the persuasion).

WINNING THE GAME

If you notice that heads and tails are clustering, you’re winning. And, if you’re using thousands of 3-sided coins, whose sides are coloured black, red and white, and you see a pattern like the picture up there on the right, that’s good too.

RULES FOR A SHORT GAME

Just click here for a Processing sketch which takes millions of turns per minute.

I’m going to get the video games bit out of the way now, so that I can get back to the original point of these posts.

I finished the last post talking about how a Hard (Packing) Problem can be made into a slow, time consuming, puzzle. Tetris turned the same type of puzzle into an arcade game. A deep analysis of how that was done is something I’d like to return to at some point, but it mainly comes down to incremental rewards for good moves – small areas of perfect packing are rewarded with a little more time – just enough time to fix areas of pretty good packing.

I assume Tetris wasn’t designed to be a ‘gateway game’ – to lure the player into the world of packing puzzles. It simply uses mathematics as a rich source of complexity, for fun.

And, really, that was the point I was trying to make.

There are a lot of hard problems which can be used as a source of complexity for puzzles and games. And, since many of them are geometric, you have a good idea what they’ll look like before you start.

- Oh, the reason this post is in two parts is because I was trying to find a reference to the polyomino puzzle toy which is supposed to have inspired Tetris. Couldn’t find one, sorry.

I’m going to start by talking about games. It may be a while before I talk about Problems. Eventually, I’ll get to video games. So, don’t be put-off if I start with something like Noughts and Crosses.

Some games we all know are considered children’s games. A few that spring to mind are: Noughts and Crosses; “One potato, two potato..” (the playground selection game); and, a variety of games where you take away a number of coins/pebbles and the loser/winner is the player who takes the last one.

If you were to ask an adult why they don’t play Noughts and Crosses, I Imagine many would say it’s because it’s “too simple”, “boring” or “too easy”. I’d argue that it’s the last of these which is nearest the truth. Noughts and Crosses is fun if you don’t know how to win, and most adults do know.

The counting games I mentioned are a little different. There are simple winning strategies, but fewer people know them. But, if you were playing the games for money every friday night, with a few drinks and nibbles, you’d soon learn them.

So, what about a harder game, like Chess? Chess remains interesting for adults because no-one knows how to win. (That sentence should probably have started with the words ‘I think that…’.) Note that I said ‘interesting’ rather than ‘fun’ – many people find chess “boring” and, presumably, those who can’t find a suitable opponent may also think it’s “too easy”.

By now, the nearest I’ve got to connecting (1)’Hard Problems’ and (2)’Good Games’ is to say that Chess is (1) a ‘Hard Game’ and (2) an ‘Interesting Game’. So, really, I need to bring in the words ‘Problem’ and ‘Good’.

So, Problems. There are lots of very hard problems which can be grouped under the heading ‘Packing Problems’. With these problems, you start with a container (knapsack, 2d-shape, box,…) and a bunch of ‘things’ of varying shape, size, weight etc., and you have to find the best or only way to put some or all of the things into the container, possibly satisfying some conditions.

If you just have a few ‘things’, and you know there’s only one solution, you can solve these problems by trying every possible combination (and arrangement) of the things until you get the one that fits, and then stop. But if you have lots of things, this is impractical, it would just take too long.

In my opening sentence, I mentioned various things that I intended to talk about, but I forgot a couple – Toys and Puzzles.

Packing Problems are good example of how a ‘Hard Problem’ can make a ‘Good Toy’, or even a ‘Good Puzzle’. A good and reasonably well known example of this would be the Tangram; another might be the humble Jigsaw Puzzle. Most people know good strategies for tackling Jigsaws which, along with guess-work and a few other things, allow Jigsaw Puzzles to be completed before the heat death of the universe.

But still, such puzzles require a good deal of time and patience. There’s a few things we need to do to get from ‘Good Puzzle’ to ‘Good Game’, and that will happen in Part 2.

I often wonder about the difference between a Problem and a Puzzle.

e.g. Why is ‘how long does it take to fill the bath?’ a problem, but ‘how far does the fly travel?’ a puzzle? (That last part will make more sense shortly, when we get to the fly puzzle.)

I suppose the simple answer is: ‘puzzles are fun’, but that won’t fill a page. So, instead, I’ll make some observations on things that many puzzles seem to have in common which help to differentiate them from problems.

The first is: a puzzle is usually easier to solve than you initially think. This is the case with both the ‘Two Trains One Fly’ puzzle, and with this geometry puzzle from Richard Wiseman (at the bottom of the page). The first of these is especially interesting because there’s a famous story about John von Neumann solving the fly puzzle ‘the hard way’.

Another thing, which often goes hand-in-hand with the first is: misdirection. For example, phrasing the puzzle in such a way that it seems to be harder than it is, or giving a hint which sends you in the wrong direction. The ‘Seven Dots Problem’ is a good example of the latter.

A third thing is: beauty. This is harder to define, but it might be that the way you find the answer is remarkably simple; or there may be something interesting about the answer itself – a nice round number, or even just the number you first thought of. A good example is the ‘Weigh The Pearls Problem’ - I think that this problem would be harder if there were 8 pearls rather than 9 (because the 8 will misdirect the player), but the solution is more beautiful with 9.

The title of this post originally included the word ‘Game’ – because I had planned to also discuss how hard problems can make good games – but I’ll leave that for another post.

Langton’s Ant is an interesting machine. It has simple rules, and makes nice patterns. So, it was an ideal test program for my 8080 emulator. When the finished program came-in at around 90 bytes, I realised that, if I could make it just a little smaller, it would fit in a tweet. (You can have 140 characters in a tweet, but because I wanted to tweet a hex-dump, I needed 2 characters per byte, so my target was 70 bytes.)

As you can see, I managed to get it down to exactly 70 bytes. I then spent a few hours trying to get it even smaller (so that I could fit a message in the tweet too), but eventually gave up.

Before showing the program running, I should, perhaps, explain what it does.

Langton’s Ant lives in a world of black and white squares. When he stands on a square, he changes its colour from black to white, or white to black. He then turns 90 degrees to the right if the square is black, or 90 degrees to the left if it’s white. Then he takes one step forward onto another square and does it all again.

The program should work as-is on any 8080 (or z80) emulator which has 32K of RAM. If you want to try it you need to load the program at address 0×0000, and watch for the output in the address range 0×4000 to 0×41ff. If you want to play with the source code it’s here. A slightly larger version with better animation is here.

Fortunately, the output happens to be exactly where the video memory is on my emulator. So, here’s a video of it in action.

The new header logo broke the tabs.

[edit] Oh, actually, no.. tabs have now been fixed by kaeladan.

(Thanks!)

This counting puzzle from Matt Parker looks like the kind you should write a program to solve:

Imagine f(n) that counts the occurrences of the digit “1″ in {1,2,3…n}.

Eg f(13)=6

For what values of n does f(n)=n?

That’s all well and good – until you find yourself in a car park, waiting twenty minutes for a taxi. Under these circumstances, it’s reasonable to consider the first few values of f(n)…

Well, f(n)=1 for n=1,2,3,…9. Then you get a lot of changes in a row – f(10)=2, f(11)=4 and so on up to f(19)=12. And, since the next changes are far apart – 21,31,41… – that’s the closest f(n) and n will be for some time.

It’s been ages since the last post. So, here’s a puzzle. And, if you want to compare solutions, look here.

There’s a new version of Zupple in the App Store with an updated movie list and a new icon. The Zupple product page is here. Man, that’s terse.

This video shows the history of Zupple – from prototype to finished game – in about a minute.

Here’s a link to the video on youtube.