Sam Loyd was a famous puzzle creator of the 19th century. He studied to become a mechanical and train engineer but found ways to apply his knowledge of mathematics and logic to create interesting puzzles. He was an editor for Chess Monthly by 1860, and in 1878 he published his book Chess Strategy, which had chess puzzles to be solved.

Of the over 10,000 puzzles he developed, his most famous puzzle, which you have almost certainly played today in some form or other, was the 15 Puzzle, invented in 1878. This puzzle involves a 4 X 4 grid of tiles, numbered from one to fifteen, with the sixteenth tile removed. The 14th and 15th numbers were reversed, and you had to slide the tiles into the blank spot, one by one, and get the pattern to line up numerically, like so:

``` *************
* 1* 2* 3* 4*
*************
* 5* 6* 7* 8*
*************
* 9*10*11*12*
*************
*13*14*15*XX*
*************
```

Sam convinced the publishers to put a \$1,000 reward for the correct solution by offering up his own money for the reward, betting that nobody could solve it. The gimmick worked, and everybody thought they could solve it. Think Rubik's Cube, but with money on the line. This puzzle took all of Europe by storm, and was described as a "greater scourge than alcohol or tobacco."

In his own words:

"The old dwellers of the realm of aptitude will remember how in the early 1870s I made the whole world rack its brain over a tray of movable counters, that came to be known as the Fifteen puzzle. The fifteen counters were arranged in order in the tray with only 14 and 15 counters inverted. The puzzle was to get the counters into the normal arrangement by individually sliding them so that the 14 and 15 were permuted.

"The \$1000 reward offered for the first correct solution remained unretrieved although everybody was busy on it. Funny stories were told of shop-keepers who forget for this reason to open their shops, of respectful officials who stood throughout the night under a street lamp seeking a way to solve it. Nobody wanted to give up as everyone was confident of imminent success. It was said that navigators allowed their ships to run aground, engine drivers took their trains past stations, and farmers neglected their ploughs."

The fifteen fever didn't abate until other mathematicians discovered that puzzles laid out on a grid like this came in two possible configurations. Solvable, where the grid had been created from the solution and then scrambled by sliding the pieces, and unsolvable, where two adjacent pieces were transposed.

Another of Loyd's more devious puzzles is recreated here. The goal is to start at the highlighted three in the center, and work your way out so that your last move just takes you past the edge of the circle. You do so by moving a number of spaces indicated by your current square, in any direction (up, down, left, right, or diagonally). The solution is below the puzzle:

```                   4 7 7
5 4 4 8 3 3 4 6 3
1 4 5 1 1 1 4 5 1 7 1 3 5
4 9 4 9 6 7 5 5 5 8 7 6 6 8 5
3 7 2 9 8 3 5 6 7 3 9 1 8 7 5 8 5
1 4 7 8 4 2 9 2 7 1 1 8 2 2 7 6 3
7 2 1 8 5 5 3 1 1 3 1 3 3 4 2 8 6 1 3
4 2 6 7 2 5 2 4 2 2 5 4 3 2 8 1 7 7 3
4 1 6 5 1 1 1 9 1 4 3 4 4 3 1 9 8 2 7
4 3 5 2 3 2 2 3 2 4 2 5 3 5 1 1 3 5 5 3 7
2 7 1 5 1 1 3 1 5 3 3 2 4 2 3 7 7 5 4 2 7
2 5 2 2 6 1 2 4 4 6 3 4 1 2 1 2 6 5 1 8 8
4 3 7 5 1 9 3 4 4 5 2 9 4 1 9 5 7 4 8
4 1 6 7 8 3 4 3 4 1 3 1 2 3 2 3 6 2 4
7 3 2 6 1 5 3 9 2 3 2 1 5 7 5 8 9 5 4
1 6 7 3 4 8 1 2 1 2 1 2 2 8 9 4 1
2 5 4 7 8 7 5 6 1 3 5 7 8 7 2 9 3
6 5 6 4 6 7 2 5 2 2 6 3 4 7 4
2 3 1 2 3 3 3 2 1 3 2 1 1
7 4 4 5 7 3 4 4 7
3 3 4
```

Solution: SW, SW, NE, NE, NE, SW, SW, SW, NW

Sources
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Loyd.html - biography of Sam Loyd
http://www.cut-the-knot.com/pythagoras/history15.shtml - history of the 15 puzzle
http://thinks.com/puzzles/loyd/loyd.htm - a collection of Sam Loyd puzzles
The Joy of Mathematics, Theoni Pappas