n-queens Mexican Standoff

The first day back at work has proved fruitful in the form of someone coming up with the opposite of the traditional n-queens problem: the n-queens Mexican standoff. Instead of minimising the number of mutually attacking queens (to zero), the objective of the standoff version is to maximise the number of attacks.

We haven’t done an exhaustive search yet, but I’ve been running a simulated-annealing-ish script for a while, and it looks like the most attacks is 34 (17 pairs of mutual attacks), in two configurations:

QQ.    .QQ.
QQQ or QQQQ
QQQ    .QQ.

…either of which can be expanded by adding gaps between the queens, or rotating by multiples of 45 degrees.

Q.Q..   .Q.Q.   Q...Q..
.....   Q.Q.Q   .......
Q.Q.Q   .Q.Q.   ..Q...Q
.....   ..Q..   .......
Q.Q.Q           Q...Q..
                .......
                ..Q...Q

Q...Q...

Update: Python code below the fold.

import random
from numpy import array, exp

def print_board((n, queens, board)):
    for row in board:
        for val in row:
            print ('.','#')[val],
        print

def new_board(n=8):
    board = array([[False] * n for i in range(n)])
    queens = []
    while len(queens) < n:
        x = random.randint(0, n-1)
        y = random.randint(0, n-1)
        if not (x,y) in queens:
            queens.append((x, y))
            board[x,y] = True
    return (n, queens, board)

def eval_attack((n, queens, board)):
    attacks = 0
    for (x,y) in queens:
        for (dx,dy) in ((-1,-1),(-1,0),(-1,1),
                        (0,-1),(0,1),
                        (1,-1),(1,0),(1,1)):
            (cx, cy) = (x, y)
            while True:
                cx += dx
                cy += dy
                if cx < 0 or cx >= n or cy < 0 or cy >= n:
                    break
                if board[cx,cy]:
                    attacks += 1
                    break
    return attacks

def move_queen((n, queens, board), q=None, dest=None):
    if q is None:
        q = random.randint(0, n-1)
    if dest is None:
        while True:
            x = random.randint(0, n-1)
            y = random.randint(0, n-1)
            if not board[x,y]:
                dest = (x,y)
                break
    prev = queens[q]
    queens[q] = dest
    board[prev] = False
    board[dest] = True
    return (q, prev)

def find_most_attack(board=None, n=8, temp=2.0, threshold=10000):
    if board is None:
        board = new_board(n)

    best = 0
    meta_best = best
    since_improve = 0
    while True:
        (prev_q, prev_pos) = move_queen(board)
        score = eval_attack(board)
        if score > best:
            best = score
            since_improve = 0
            if best >= meta_best:
                meta_best = best
                print_board(board)
                print score
        else:
            since_improve += 1
            if since_improve > threshold:
                since_improve = 0
                board = new_board(n)
                best = 0
            elif random.random() >= exp((score - best)/temp):
                move_queen(board, prev_q, prev_pos)