# This program is an extension of the existing program for n+k queens problem available at
# http://www.npluskqueens.info/uploads/2/1/3/5/21355572/npluskqueensasmfund.py
# This program counts the number of fundamental solutions to the n+k queens problem for a rectangular board (defined below):
# Given a positive integer N and a nonnegative integer k, place k pawns and N + k queens on a rectangular chessboard with N rows and M columns (N <= M) so that every pair of queens on the same row, column, or diagonal have at least one pawn between them.
# Program originally written for square boards by:
# Doug Chatham, Dept. of Mathematics, Computer Science, and Physics, Morehead State University, Morehead, Kentucky 40351 (USA)
# October 4, 2014
# Program extended for rectangular boards by:
# Srinath, Department of Mathematics and Computer Science, Sri Sathya Sai Institute of Higher Learning, Puttaparthi, Andhra Pradesh 515134, INDIA.
# December 25, 2019
# email: srinathms@sssihl.edu.in
# This program extends 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 and tested in Python 3.8.1. 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 horizontal axis
return [[b[(Nrow-1)-i][j] for j in range(Ncol)] for i in range(Nrow)]
def Rot90(b): # Rotation by 90 degrees
return [[b[(Ncol-1)-j][i] for j in range(Ncol)] for i in range(Nrow)]
def Rot180(b): # Rotation by 180 degrees
return [[b[(Nrow-1)-i][(Ncol-1)-j] for j in range(Ncol)] for i in range(Nrow)]
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.
if Nrow == Ncol: # A square board which has 8 symmetries (Dihedral group of order 8)
eqclass = (c,Rot180(c),Flip(c),FlipRot180(c),Rot90(c),Rot270(c),FlipRot90(c),FlipRot270(c))
else: # A rectangular (non-square) board which has 4 symmetries (Dihedral group of order 4)
eqclass = (c,Rot180(c),Flip(c),FlipRot180(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(len(eqclass)):
if (eqclass[i] in fundsol):
flag = 1
if not(flag):
fundsol.extend([c])
note = " "
if c == eqclass[1]: # Symmetric with respect to 180 degree rotation
if Nrow == Ncol and c == eqclass[4]: # Symmetric with respect to 90 degree rotation only for square boards
note = 'Doubly centrosymmetric'
dubcentsol.extend([c])
else:
note = 'Centrosymmetric'
centsol.extend([c])
# Procedure for printing solution, if user requested to see individual solutions
if (qu=="Y") or (qu=="y"):
print("Solution ",len(fundsol),":")
Display(c)
print(note)
print(' ', end='\n')
def ClearThisWay(r,colQ,deltx,delty): # If we look in the 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. Precondition: Nrow <= Ncol
if (r == Nrow) 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,Ncol): # Try each column in current row.
if NoQueenAttacks(r,colQ) and r < Nrow:
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,Ncol-1): # Look in all spots to the right of the queen we just placed.
if Nrow != Ncol or LastPieceinColumn(r,colP) == 1: # need piece above to be a queen only if it is a square board.
b[r][colP] = -1 # Place a pawn in (r,colP)
QueensAndPawns(r,colP+1,p-1) # Find all solutions with pawn in (r,colP).
b[r][colP] = 0 # Remove the 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.
def Display(c): # Display the board position described by c.
for i in range(Nrow):
for j in range(Ncol):
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')
#main program
from copy import deepcopy # See http://www.python-course.eu/python3_deep_copy.php
global Nrow,Ncol,b,qu,fundsol,allsol,dubcentsol,centsol
print("Input board size:")
Nrow=input("Number of rows:")
Nrow=int(Nrow)
Ncol=input("Number of columns:")
Ncol=int(Ncol)
# WLG, we assume that the number of rows is less than or equal to the number of columns.
(Nrow,Ncol) = (Ncol,Nrow) if Nrow > Ncol else (Nrow,Ncol) # Swap Nrow and Ncol if Nrow > Ncol
p=input("Number of pawns:")
p=int(p)
qu=input("Show each solution? (Y/N)")
b=[[0 for j in range(Ncol)] for i in range(Nrow)] # 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:")