Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Maximizing the Number of Pieces On a Chess Board Without Any Attacking
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 ''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment