# The French Peasant's Lock and Gray Code

The French Peasant's lock puzzle has appeared in lots of different forms: "The chinese rings" puzzle being the most famous. There is even a version with elephants to get in a line and march off.

Gray code can help spot when errors have been made

The solution to the lock is actually something know to Computer Scientists as Gray Code: a code used in modern digital TV. Whatever, their physical form all the variations of the lock puzzle have the same solution and are logically (and so their solutions algorithmically) identical. Solve one and you've solved them all (Computer Scientist's love pulling that trick with problems!)

Each piece on the bolt can be of one of two kinds (it can be in one of two "states"): a disc or a sideways T. For simplicity let's refer to the discs as 0 and the T shapes as 1. Now every state of the bolt as a whole can be thought of as a series of 1s and 0s. The starting state has a single T at one end but otherwise is all zeros: the state 1 000 000. The end state when the bolt is free has all discs so is 0 000 000. The problem is to move from 1 000 000 to 0 000 000 by following the restrictions of the lock. They mean that only two pieces can be swapped at any time (either the end one or the piece immediately after the first T), but also that only a single 1 or 0 can be changed in any move. For example, the first move might be to flip the end piece from a disc to a T. We get new position 1 000 001. Only a single position (or bit as a computer scientist would call it) has changed.

## Agreeing what it all means

Computers represent all information like this as sequences as 1s and 0s. Not just states of a puzzle, but the characters making up a word processor document, the individual points or pixels in an image, the sounds in a downloaded track. Everything. That of course includes numbers too. Each kind of document holding information uses a code over what the 1s and 0s represent. The code in our puzzle is that 0 means a disc in that position and 1 means a T piece. For one computer to be able to share information with another they have to agree on the code - how to interpret the 1s and 0s. There are a whole series of standard codes. For example, with simple numbers computers mostly use a special sequence that counts 0=0000, 1=0001, 2=0010, 3=0011, 4=0100, and so on. This isn't an arbitrary code. It uses the same mechanism as we use for decimal numbers. If I write the number 340, what I mean is 3x100 + 4x10 + 0x1. Each position is a different power of 10. The system computers use is the same but you multiply by 2 not 10. So a number like 1001 in binary stands for the number 1x8 + 0x4 + 0x2 + 1x1 = 9. Using this coding our start position in the lock puzzle (1 000 000) is also the number 64. That shows too that a particular bit pattern can mean different things in different situations - it all depends on the code you use to unscramble it.