### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,818 hits

Advertisements

Programming Enigma Puzzles

8 May 2013

Posted by on **From New Scientist #2916, 11th May 2013** [link]

In the 4×4 grid shown, you must place all the unused arrow cards on the unshaded squares of the grid, such that by moving from card to card the number of squares in the direction shown on each, you complete a circuit visiting all 12 unshaded squares.

What are the numbers on the cards, from left to right, in the bottom row?

[enigma1748]

Advertisements

%d bloggers like this:

Here’s a recursive solution in Python. It runs in 43ms.

Solution:The numbers on the cards on the bottom row are 1, 3, 2, 1.Here is my version, which is also recursive:

In my solution I was originally going to use integers 0 to 15 to represent the cells, and then just use differences to represent the arrows, but I was worried about wraparound at the edges of the grid. So, for instance, the program might try 1R in square 7 (2nd row down, 4th column) to get to square 8 (3rd row down, 1st column), which I don’t think should be allowed. In the end I used (row,column) pairs so this problem doesn’t arise, rather than explicitly code around it.

I rewrote my program to use integers and it gives the same unique solution, so it looks like there are no solutions where this problem arises.

Actually the code to eliminate the wraparounds is probably worth the simplification gained from not using pairs. Here’s my revised Python program.

As you suggest, I should have avoided wraparounds but I was lucky and found that there was only one solution anyway and hence no false ones caused by them. I agree that this is a bit sloppy.

Here it is again with wraparound elimination:

And you can eliminate having to check for any potential wrap arounds by representing the grid by the centre of a 10×4 grid, then the horizontal moves can’t make it out of their own row.

The two middle cells in the top row can readily be deduced, so only 432 permutations are possible for the remaining cells, only 6 of which use all the arrow cards.

A simplified version, representing the cells as numbers 0 to 15

it is a depth-first search used in my algorithm and it is a recursive approach.