Instantly share code, notes, and snippets.

# brandonpelfrey/chess-max-pieces.py Created Dec 12, 2015

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