How can we place eight queens on a regular chess board such that no queen can ca

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 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

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()

Explanation / Answer

# 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()

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.