Welcome to NRICH.

 
Maths for solving puzzles and jigsaws
By Anonymous on Friday, December 15, 2000 - 08:02 pm:

As Mathematics is usually about a lot of different puzzles and the studying of such puzzles/problems, I was wondering if anybody knows of a branch of maths that can help you solve mechanical puzzles and jigsaw puzzles elegantly. This might seem like and ambiguous question and so I shall suggest particular examples.

The Rubik's cube was first a puzzling curiosity sold in the millions to many different children all over the world ( and a lot of adults too!). It wasn't long before people began writing books giving general solutions to the cube, such solutions can be easily found on the internet-but are these solutions just mathematical solutions in a different guise? Can anybody find arrangements of the Rubik's cube for which there are no algorithms that solve the cube within a 'reasonable' time frame (you can consider algorithmic complexity if you like)?

Also, I have recently been solving certain 2-D and 3-D jigsaw puzzles. Some of these take a LONG time. Is there a branch of maths which makes these puzzles easier to solve?
Thanks for any discussion on this very general question on puzzles!

By Dan Goodman (Dfmg2) on Friday, December 15, 2000 - 11:20 pm:

It seems unlikely to me that there is a neat way of solving them (in general). The reason for this is that there is a puzzle (called "Eternity") which has only recently been solved by two mathematicians (who received £1,000,000 for their efforts)! [See here for more about this. - The Editor] This suggests that it's a hard problem in general.

However, there are some techniques, and many jigsaw puzzles are amenable to algorithmic approaches. I had a jigsaw which was almost impossible to solve by hand (it was called Impuzzable) as it was one colour with no edges and 9 pieces with 4 different types of holes / sticking out bits. However, I wrote a computer program (it took about 25 minutes to write) which solved the puzzle in about 2 seconds. [See here for Dan's article about this. - The Editor]

Maybe the sort of puzzle you're considering is an order of complexity higher than this?

By Brad Rodgers (P1930) on Saturday, December 16, 2000 - 11:07 pm:

Along these lines, is there a methodical way to solve those slide puzzles? This one is not a particularly good example to solve algorithmically, but imagine one where a side can be clearly shown to match another side, you just don't know how to get the two together.

Brad

By Hal 2001 (P3046) on Sunday, December 17, 2000 - 11:17 am:

Size of grid? If this increases does it mathematically make it more complicated? Or not?

By Mrs. Toni Beardon (Lab11) on Sunday, December 17, 2000 - 03:28 pm:

The classics in this field accessible to the non-specialist reader are 'On Numbers and Games' and 'Winning Ways' both by John Horton Conway. Yes there is a branch of maths called Game Theory and non trivial it is too, though the proverbial 'man in the street' might not appreciate why.
Toni

By The Editor:

Going back to the original question, the Rubik's cube can definitely be analysed mathematically, using permutations and group theory. I believe there is a theoretical maximum on how many moves are needed to solve it. In fact, most solvers will be very unlikely to do it by the most efficient method: they usually memorise a set of moves which rearrange particular sets of pieces without affecting the others. If you are interested in learning more, try putting "Rubik's cube" and "group theory" into a search engine.

With regard to jigsaw puzzles, I use a certain amount of mathematical thinking with any difficult jigsaw.
For instance, most jigsaws have a large number of pieces of type (a), and far fewer of the other types. As soon as I see a straight edge with two lugs (the sticking out bits) in a row, I know that I will need either a type (b) or a type (c) piece. I nearly always rely on sorting the sky(/sea/grass) pieces by shape, and concentrating on the more unusual piece types.