### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,115)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,357 hits

Programming Enigma Puzzles

16 June 2015

Posted by on **From New Scientist #2381, 8th February 2003** [link]

First draw a chessboard. Now number the horizontal rows 1, 2, …, 8 from top to bottom and number the vertical columns 1, 2, …, 8 from left to right. You have to put a whole number in each of the sixty-four squares, subject to the following:

1. No two rows are exactly the same.

2. Each row is equal to one of the columns, but not to the column with the same number as the row.

3. IfNis the largest number you write on the chessboard then you must also write 1, 2, …,N−1 on the chessboard.The sum of the sixty-four numbers you write on the chessboard is called your total.

What is the largest total you can obtain?

See also **Enigma 1248**.

[enigma1225]

Advertisements

%d bloggers like this:

A similar problem was published as

Enigma 1248, so, having already solved that I was able to adapt my code to solve this problem.This Python program runs in 664ms.

Solution:The largest possible total for an 8×8 grid is 544.Here’s an example layout:

In this instance the correspondence between rows and columns is (1, 2, 3, 4, 5, 6, 7, 8) → (2, 1, 4, 3, 6, 5, 8, 7), i.e. alternate pairs are swapped. Each number from 1 to 16 appears 4 times, hence the sum is 4×T(16) = 544.

This puzzle seems to have attracted the attention of academia, and is mentioned in several papers (including a 50 page chapter on a solution in Prolog). In particular:

The first of these paper uses Prolog’s unification mechanism to process the problem (which is essentially the same process I use in the

grid()function to equate the rows and columns). The second paper uses a constraint based programming language.While these papers go on to develop more sophisticated algorithms to attack this particular problem (but they don’t apply to

Enigma 1248), it is perhaps surprising how poorly their initial attempts perform. In [2009] it is stated that the run time of their initial algorithm forN=6 is greater than 1 hour, and in [2005] the run time of their initial algorithm forN=8 is 209.6s.I dug out my 12″ Powerbook (from 2005, so contemporary with the earlier paper) and ran my Python program (using Python 2.7.2) and it runs the

N=8 case in 13.5s. Although I don’t pretend my algorithm is sophisticated and will quickly get bogged down for larger values ofN.Here’s an alternative program that uses the same technique as my original program to compute the value of the grid, but instead of considering all possible mappings between rows and columns only considers “representative” mappings (as described in the paper [2005]).

This runs much faster and allows us to consider larger grids. For example for

N=8 my original program constructed 14833 grids. The program below only constructs 7 grids. So it runs in 46ms for theN=8 case and can be used to consider much larger values forN. (This program deals with values up to 42 in less than a minute).As noted in paper [2009] the maximal solution observed is always the smallest viable decomposition of

N. Which would mean (as the decompositions are generated in lexicographical order) that as soon as a solution is found the program could exit. If we do this we can find solutions up toN=450 in under a minute.I forget to mention that, for reasons I haven’t worked out yet, my solution above doesn’t work for odd N.