Question

Write and Compile a python script to solve the 4-queens problem using Forward Checking algorithm . The code should allow for random starting, and for placed starting. Random Starting means randomly place a queen position on the chessboard. Placed Starting means asked for the user input to place a queen position on the chessboard. Display the iterations until the final solution

"The 4-Queens Problem[1] consists in placing four queens on a 4 x 4 chessboard so that no two queens can capture each other. That is, no two queens are allowed to be placed on the same row, the same column or the same diagonal."

Display the output of the python Script

Answer 1

#python Code Backtracking

import math
ways = 0

def solveBoard(board, row, rowmask,
                           ldmask, rdmask):

   n = len(board)
  

   all_rows_filled = (1 << n) - 1
  

   if (rowmask == all_rows_filled):
       global ways
       ways = ways + 1
       print("=====================")
       print("Queen placement - " + (str)(ways))
       print("=====================")
       printBoard(board)
      

   # placement of iteration for row index
   safe = all_rows_filled & (~(rowmask |
                               ldmask | rdmask))
  
   while (safe > 0):
  
  
       p = safe & (-safe)
       col = (int)(math.log(p)/math.log(2))
       board[row][col] = 'Q'
      
       solveBoard(board, row+1, rowmask|p,
                       (ldmask|p) << 1, (rdmask|p) >> 1)
      
  
       safe = safe & (safe-1)
      
       # Backtracking
       board[row][col] = ' '

# Program to print board
def printBoard(board):
   for row in board:
       print("|" + "|".join(row) + "|")

# Driver Code     
def main():

   n = 4; # board size
   board = []
  
   for i in range (n):
       row = []
       for j in range (n):
           row.append(' ')
       board.append(row)

   rowmask = 0
   ldmask = 0
   rdmask = 0
   row = 0
  
   # Function Call
   solveBoard(board, row, rowmask, ldmask, rdmask)
  
   # creates a new line
   print()
   print("Number of ways to place " + (str)(n) +
                       " queens : " + (str)(ways))
  
if __name__== "__main__":
   main()