Maximizing the Number of Pieces On a Chess Board Without Any Attacking

chess-max-pieces.py

import pulp, random
from collections import defaultdict

# Some convenience functions for messing with PULP

# This lets us reference variables by any number of strings, numbers etc.
__Variables = {}
def baseVariable(name_tuple, varType):
  name = '_'.join( map(str, name_tuple) )
  if name not in __Variables:
    __Variables[name] = pulp.LpVariable(name, cat=varType)
  return __Variables[name]

def binaryVariable(*args):
  name = tuple(args)
  return baseVariable(name, pulp.LpBinary)

def realVariable(*args):
  name = tuple(args)
  return baseVariable(name, pulp.LpContinuous)

# Lazy short aliases :)
B, R = binaryVariable, realVariable

# A=1 -> B=0
def implies10(a, b): return a + b <= 1

# A=1 -> B=1
def implies11(a, b): return a - b <= 0

#################################################

problem = pulp.LpProblem('Maximum Chess Pieces', pulp.LpMaximize)

# Board size
n = 8
squares = [(i,j) for i in xrange(n) for j in xrange(n)]

# Define relative movements that pieces can make
movements = defaultdict(set)
for i in xrange(n):
  movements['Q'].update([ (0,-i), (0,i), (-i,0), (i,0), (i,i), (i,-i), (-i,i), (-i,-i) ])
  movements['R'].update([ (0,-1), (0,i), (-i,0), (i,0) ])
  movements['B'].update([ (i,i), (i,-i), (-i,i), (-i,-i) ])
movements['P'].update([ (1,1), (-1,1) ])
movements['N'].update([ (-2,-1), (-2,1), (-1,2), (1,2), (2,1), (2,-1), (1,-2), (-1,-2)  ])
movements['K'].update([ (-1,1), (0,1), (1,1), (-1,0), (1,0), (-1,-1), (0,-1), (1,-1) ])

# Add the constraints associated with a given piece to a problem instance
def piece(name, prob):
  new_assignments = []

  # For each square on the chess board
  for si in squares:

    # Find all the squares it could attack on the board if it were placed
    for delta in movements[name]:
      sj = (si[0] + delta[0], si[1] + delta[1])

      if si == sj: continue
      if sj not in squares: continue

      # si can attack sj...

      new_assignments.append( B(name, si) )

      # If we assign this piece here, we can place nothing in the attacked square
      prob += implies10( B(name,si), B(sj) )

      # If we assign this piece here, mark it in the over-all mapping
      prob += implies11( B(name,si), B(si) )

  return new_assignments

# These are the pieces the solver gets to consider placing on the chess board
# You can change it to just 'B' to see how many bishops alone can be fit on the board.
pieces_to_consider = set('QRBPNK')

# Add all the constraints regarding which squares a piece occupies and attacks
for piece_name in pieces_to_consider:
  piece(piece_name, problem)

# Make sure we never assign more than one piece to a square
for si in squares:
  problem += sum(B(p, si) for p in pieces_to_consider) <= 1
  problem += B(si) - sum(B(p, si) for p in pieces_to_consider) <= 0

problem += sum( B(si) for si in squares )

solver = pulp.solvers.PULP_CBC_CMD(maxSeconds=60 * 15, msg=1, presolve=True, threads=4)
problem.solve(solver)

for i in xrange(n):
  for j in xrange(n):
    S = '.'
    for p in pieces_to_consider:
        if B(p, (j,n-1-i)).varValue == 1: S = p
    print S,
  print ''