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    .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..

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],

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),
            (cx, cy) = (x, y)
            while True:
                cx += dx
                cy += dy
                if cx < 0 or cx >= n or cy < 0 or cy >= n:
                if board[cx,cy]:
                    attacks += 1
    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)
    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 score
            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)

Leave a Comment