Write a program getPositions in Python that takes as input a list L representing

Question

Write a program getPositions in Python that takes as input a list L representing a partial solution to the n-Queens problem and a positive integer n representing the dimension of the n×n chessboard. The input list contains the positions of the Queens currently placed on the board (or is empty if no Queens have been placed). You should use the same list representation as you use in Task 3 of Workshop 6, that is, the entry L[i] gives the row position of the Queen in column i. You may assume that the partial solution gives the positions of the Queens in the first i columns and that the other columns are empty. Your program should return a list containing possible row positions for a Queen to be placed in the next column on the board. (The index of the next column can be obtained by the length of L.)

For example: If your list is [5,3] and n = 6, your program should return the list [0,1], that is, a Queen could be placed at row 0 column 2, or row 1 column 2, of the board.

Some further examples: If your list is empty and n = 5, your program should return the list [0,1,2,3,4]. If your list is [3,1] and n = 4, your program should return an empty list.

Explanation / Answer

import copy
def t_input():
while True: #input the size of the chess board n*n
try:
size_chess = int(input("Enter the size of the chessboard? n = "))
if size_chess <= 3:
print("Enter a number such that size of chess board>=4")
continue
return size_chess
except ValueError:
print("Enter a valid number... try again")

def board(size_chess):
g_board = [0]*size_chess #Returns an n by n chess square board
for i in range(size_chess):
g_board[i] = [0]*size_chess
return g_board

def solutions(sol, size_chess):
for s in sol: #Prints all the solutions
for r in s:
print(r)
print()
  
def safe(g_board, r, c, size_chess): #Check the position of the queen in board[x][y] to be placed is safe or not
#check row on left side
for j in range(c):
if g_board[r][j] == 1:
return False
i, j = r, c
while i >= 0 and j >= 0:
if g_board[i][j] == 1:
return False
i-=1
j-=1
  
k, l = r,c
while k < size_chess and l >= 0:
if g_board[k][l] == 1:
return False
k+=1
l-=1
return True
def find(gboard, c, size_chess):
#backtracking for finding all solutions
if c >= size_chess:
return
  
for x in range(size_chess):
if safe(g_board, x, c, size_chess):
g_board[x][c] = 1
if c == size_chess-1:
add_sol(g_board)
g_board[x][c] = 0
return
find(g_board, c+1, size_chess)
#backtrack
g_board[x][c] = 0

def add_sol(g_board):
#Saves in the global variable from board state
global sol
sav_board = copy.deepcopy(g_board)
sol.append(sav_board)

size_chess = t_input()

g_board = board(size_chess)

sol = []

find(g_board, 0, size_chess)

solutions(sol, size_chess)

print("solutions = {}".format(len(sol)))

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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