# 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<Nrow) and (y<Ncol):
        if b[x][y]==-1: # A pawn. Current position is not under attack from this direction.
            return 1
        if b[x][y]==1: # A queen which attacks current position
            return 0
        x = x + deltx
        y = y + delty
    return 1

def NoQueenAttacks(r,colQ): # Does any queen attack the current position (r,colQ)?
    return (ClearThisWay(r,colQ,-1,0) and ClearThisWay(r,colQ,0,-1) and ClearThisWay(r, colQ, -1,-1) and ClearThisWay(r,colQ,-1,1))
# With the program's way of traversing the board, don't need to check other directions.
    
def LastPieceinColumn(r,colP): # Determine if the last piece, if any, in the column is a queen or pawn.
    i = r-1
    while (i>=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:")