Question

The Eight Queens Problem is a fairly old problem that has been well discussed and researched. The first published reference to this problem was in a German Chess magazine in 1848 by Max Bezzel. In 1850, Franz Nauck published all 92 solutions of the problem for an 8x8 board. S. Gunther in 1874 suggested a method for finding solutions by using determinants and J.W.L. Glaisher extended this method. E. Dijkstra published a detailed description of the solution of the problem as a depth-first backtracking algorithm.

The original statement of the problem ran as follows - how can we place eight queens on a regular chess board such that no queen can capture another. It turns out there is no unique solution but 92 possible solutions of which only 12 are distinct. The 12 distinct solutions can generate all other solutions through reflections and / or rotations. Here is a table that gives the size of the board, all possible solutions, and all distinct solutions.

Size	All Solutions	Distinct Solutions
1	1	1
2	0	0
3	0	0
4	2	1
5	10	2
6	4	1
7	40	6
8	92	12

Prompt the user to enter the size of the board. The size of the board must be a number between 1 and 8 inclusive. Keep prompting the user to enter a number in that range, if he does not get it right. For the size of the board that the user specified generate and print all possible solutions for that size. Keep a count of the number of solutions and your last line should print the total number. Here is a possible scenario:

Enter the size of board: 4

* Q * *
* * * Q
Q * * *
* * Q *

* * Q *
Q * * *
* * * Q
* Q * *

There are 2 solutions for a 4 x 4 board.

This is what I have so far, but it only prints one possible solution for the size of the board:

class Queens (object):

# initialize the board

def __init__ (self, n = 8):

self.board = []

self.n = n

for i in range (self.n):

row = []

for j in range (self.n):

row.append ('*')

self.board.append (row)

# print the board

def print_board (self):

for i in range (self.n):

for j in range (self.n):

print (self.board[i][j], end = ' ')

print ()

# check if no queen captures another

def is_valid (self, row, col):

for i in range (self.n):

if (self.board[row][i] == 'Q' or self.board[i][col] == 'Q'):

return False

for i in range (self.n):

for j in range (self.n):

row_diff = abs (row - i)

col_diff = abs (col - j)

if (row_diff == col_diff) and (self.board[i][j] == 'Q'):

return False

return True

# do a recursive backtracking solution

def recursive_solve (self, col):

if (col == self.n):

return True

else:

for i in range (self.n):

if (self.is_valid(i, col)):

self.board[i][col] = 'Q'

if (self.recursive_solve (col + 1)):

return True

self.board[i][col] = '*'

return False

# if the problem has a solution print the board

def solve (self):

for i in range (self.n):

if (self.recursive_solve(i)):

self.print_board()

def main():

# create a regular chess board

game = Queens (8)

# place the queens on the board

game.solve()

main()

Answer 1

Code implemented in python:

Note: Comments are written for code explanation

Filename: Queens.py

Code:

#global counter variable to count the number of possible solutions for n queens
counter = 0
#initialize the class of Queens
class Queens (object):
# initialize the board
def __init__ (self, n = 8):
self.board = []
self.n = n
for i in range (self.n):
row = []
for j in range (self.n):
row.append ('*')
self.board.append (row)

# print the board
def print_board (self):
for i in range (self.n):
for j in range (self.n):
print (self.board[i][j], end = ' ')
print ()
print()

# check if no queen captures another
def is_valid (self, row, col):
for i in range (self.n):
if (self.board[row][i] == 'Q' or self.board[i][col] == 'Q'):
return False
for i in range (self.n):
for j in range (self.n):
row_diff = abs (row - i)
col_diff = abs (col - j)
if (row_diff == col_diff) and (self.board[i][j] == 'Q'):
return False
return True

# do a recursive backtracking solution
def recursive_solve (self, col):
global counter
if (col == self.n):
#this uses the helper function to see how many queens are present
num = self.count_Queen()
if num == self.n:
  
self.print_board()
counter += 1
return True
else:
solvable = False
for i in range (self.n):
if (self.is_valid(i, col)):
self.board[i][col] = 'Q'
solvable = self.recursive_solve(col + 1) or solvable
self.board[i][col] = '*'
return

# if the problem has a solution print the board
def solve (self):
for i in range (self.n):
self.recursive_solve(i)

#this counts the numer of queens present in the solution and returns a sum
def count_Queen(self):
qsum = 0
for i in range(self.n):
qsum += self.board[i].count('Q')
return qsum
  
  
def main():
try:
  
# create a regular chess board
n = eval(input("Enter size of board: "))
print()
while n <= 0 or n > 8:
n = eval(input("Enter size of board: "))
print()
  
game = Queens (n)

# place the queens on the board
game.solve()
  
print("There are " , counter ,"solutions for a ", str(n) , "x" , str(n ), "board.")
  
#exception handling for user input
except ValueError:
print("Invalid Input.")
  
except SyntaxError:
print("invalid Input.")
except TypeError:
print("Invalid end.")
main()

Working Code Output Screenshot:

If you like my answer, hit thumbs up . Thank you.