### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

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

### Site Stats

- 166,224 hits

Programming Enigma Puzzles

10 March 2013

Posted by on **From New Scientist #1212, 31st July 1980** [link]

If you place Queens (as many as you like) on an ordinary 8 × 8 chessboard, in such a way that you have the greatest possible number of moves open to you, you will find you cannot do better than put a Queen on each border square. You thus use 28 Queens in all. Each of the 36 unoccupied squares can then be moved to by just 8 Queens. Total moves available: 36 × 8 = 288. And you cannot achieve 288 with fewer than 28 Queens.

Suppose I now ask you to do the same on a 4 × 4 board. If you place a Queen on each border square, you will as the diagram shows, achieve 4 × 8 = 32 possible moves. Can you do better? Remember that your prime purpose is to maximise the number of possible moves; subject to that you want to use as few Queens as you can.

How many possible moves can you get on a 4 × 4 board? And how will you place your Queens?

[enigma69]

Advertisements

%d bloggers like this:

This recursive solution implemented in Python runs in 1.95s for the 4×4 case.

Solution:On a 4×4 board the maximum number of moves achievable is 40, using 6 Queens. An example layout is shown below (rotations and reflections of the this solution will also work).40 moves is also achievable with 7 or 8 Queens.

This algorithm is OK for solving a 4×4 board, but it quickly gets bogged down on larger boards, as it considers each possible combination of placing

nQueens for values ofnfrom 1 to N² (on an N×N board). For a 5×5 board this takes 15 minutes (the answer is 76 moves, using 11 Queens). So I was unable to verify the given solution for an 8×8 board using this program.If the strategy of placing queens on the border squares for N>5 produces the best solution we get:

I wrote a more efficient version of my program (eliminating symmetrically equivalent positions, using bit vectors to store positions on the board and pre-computing moves), which solves the 4×4 board in 189ms and the 5×5 board in 19s, so it is around 150× faster than my original approach. And although the algorithm is still pathologically slow, this is enough to verify that 128 moves is maximal for the 6×6 board using 20 queens in the “border configuration” (with about 14h of CPU time).

Here’s a summary of the maximal number of moves I have computed for various board configurations:

The maximal number of moves for each board configuration are denoted with asterisks.

Border configurations are denoted with square brackets.

The (presumed) maximal values for the 7×7 and 8×8 boards are marked with a question mark, as these have not been verified by my program.