# Program to count the number of fundamental solutions to the n+k queens problem for input (small) values of n and k
# Doug Chatham, Dept. of Mathematics, Computer Science, and Physics, Morehead State University, Morehead, Kentucky 40351 (USA)
# October 4, 2014
# This program implements the "ASM" algorithm described in "Centrosymmetric Solutions to Chessboard Separation Problems"
# (Chatham, Doyle, Jeffers, Kosters, Skaggs, and Ward, Bulletin of the Institute of Combinatorics and its Applications, volume 65, May 2012)
# -- except that this program does not output a solution obtainable by rotating and/or reflecting a previously found solution.
# This program is written in Python 3.3. It is not intended to be optimal.
# For more information on the "n+k queens problem", visit http://npluskqueens.info.
########################################
# The next seven functions take a solution b and find all equivalent solutions, where two solutions are equivalent if one can be obtained
# by rotating and/or reflecting the other.
def Flip(b): # Reflecting across vertical line
return [[b[(N-1)-i][j] for j in range(N)] for i in range(N)]
def Rot90(b): # Rotation 90 degrees to the right
return [[b[(N-1)-j][i] for j in range(N)] for i in range(N)]
def Rot180(b):
return Rot90(Rot90(b))
def Rot270(b):
return Rot180(Rot90(b))
def FlipRot90(b):
return Flip(Rot90(b))
def FlipRot180(b):
return Flip(Rot180(b))
def FlipRot270(b):
return Flip(Rot270(b))
########################################
def OutputAndProcess(b):
global fundsol, allsol
c = deepcopy(b) # b is the current solution. Need an actual "deep" copy that doesn't change when we find a new b. See http://www.python-course.eu/python3_deep_copy.php
eqclass = (c,Rot90(c),Rot180(c),Rot270(c),Flip(c),FlipRot90(c),FlipRot180(c),FlipRot270(c))
allsol.extend([c])
flag = 0 # flag will indicate whether we've printed a member of the equivalence class of c
for i in range(8):
if (eqclass[i] in fundsol):
flag = 1
if not(flag):
fundsol.extend([c])
note = " "
if c == eqclass[2]: # Symmetric with respect to 180 degree rotation
if c == eqclass[1]: #Symmetric with respect to 90 degree rotation
note = 'Doubly centrosymmetric'
dubcentsol.extend([c])
else:
note = 'Centrosymmetric'
centsol.extend([c])
# Below is our procedure for printing solution, if user requested to see individual solutions
if (qu=="Y") or (qu=="y"):
print("Solution ",len(fundsol),":")
for i in range(N):
for j in range(N):
if c[i][j] == 1: # 1 indicates a queen in row i and column j
print('Q', end=' ')
if c[i][j] == 0: # 0 indicates empty space in row i and column j
print('*', end=' ')
if c[i][j] == -1: # -1 indicates a pawn in row i and column j
print('P', end=' ')
print(' ', end='\n')
print(note)
print(' ', end='\n')
def ClearThisWay(r,colQ,deltx,delty): # If we look in direction indicated by (deltx, delty), are there any queens between current position (r, colQ) and either a pawn or the board's edge, whichever comes first?
x = r + deltx
y = colQ + delty
while (x>=0) and (y>=0) and (x=0):
if b[i][colP]!=0:
return b[i][colP] # We've found the last piece currently in column.
i = i-1
return 0 # Column empty
def QueensAndPawns(r,c,p): # Start from position (r,c) with p pawns. This procedure is displayed in Figure 6 of the above-mentioned "Centrosymmetric Solutions to Chessboard Separation Problems"
if (r == N) and (p == 0): # then we are past the last row and have no more pieces to place. We have a solution.
OutputAndProcess(b)
else:
for colQ in range(c,N): # Try each column in current row.
if NoQueenAttacks(r,colQ):
b[r][colQ]=1 # Place queen in (r,colQ).
if p>0: # then we have pawns left to place.
for colP in range(colQ+1,N-1): # Look in all spots to the right of the queen we just placed
if LastPieceinColumn(colP) == 1: # In a solution, in rows with pawns, the pawns and queeens alternate. So, to place a pawn in (r,colP), need piece above to be a queen.
b[r][colP] = -1
QueensAndPawns(r,colP+1,p-1) # Find all solutions with pawn in (r,colP).
b[r][colP] = 0 # Remove pawn and continue looking down the row.
QueensAndPawns(r+1,0,p) # Either no more pawns or no more places for pawns in current row, so go to next row and find all other solutions with queen at (r, colQ).
b[r][colQ] = 0 # Have found all solutions with queen at (r,colQ), so remove it and look for solutions with (r,colQ) empty.
#main program
from copy import deepcopy # See http://www.python-course.eu/python3_deep_copy.php
global N,b,qu,fundsol,allsol,dubcentsol,centsol
N=input("Board size:")
N=int(N)
p=input("Number of pawns:")
p=int(p)
qu=input("Show each solution? (Y/N)")
b=[[0 for i in range(N)] for j in range(N)] # b is an array holding the solution currently under construction
fundsol=[] # list of fundamental solutions
allsol=[] # list of all solutions
dubcentsol=[] # list of all doubly centrosymmetric fundamental solutions
centsol=[] # list of all centrosymmetric fundamental solutions
QueensAndPawns(0,0,p)
print("Distinct solutions:",len(allsol))
print("Fundamental solutions:",len(fundsol))
print("Centrosymmetric fundamental solutions:", len(centsol))
print("Doubly centrosymmetric fundamental solutions:", len(dubcentsol))
print(" ")
qu=input("Hit Enter to end program:")