Question
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
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.
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.
Code so far: (Please write in Python)
class EightQueens (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)
# check if no queen captures another def isValid (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): rowDiff = abs (row - i) colDiff = abs (col - j) if (rowDiff == colDiff) and (self.board[i][j] == 'Q'): return False return True
def recursiveSolve (self, col): if (col == self.n): return True else: for i in range (self.n): if (self.isValid (i, col)): self.board[i][col] = 'Q' if (self.recursiveSolve (col + 1)): return True self.board[i][col] = '*' return False
# solve the problem def solve (self): for i in range (self.n): if (self.recursiveSolve (i)): self.printBoard ()
# print the board def printBoard (self): for i in range (self.n): for j in range (self.n): print (self.board[i][j], end = ' ' ) print ()
def main(): # create object queens = EightQueens (8) queens.solve()
main()
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started