I've started solving the 8 queens problem with backtracking in Python. Everything is nice & fine. It even printed out the first answer. However, it stuck itself on its first backtracking try.
The task sounded in that way:
Implement a Python function that solves the 8 queens puzzle. The 8 queen puzzle consists of placing 8 queens on a chess board, so that, none of the queens could capture any other. Note that queens can move orthogonally or diagonally in any direction.
You should implement a function solve() that when called, it prints the first solution of the puzzle and then it awaits for input. Once the user presses ‘enter’, the next solution is printed, and so on.
- Your program should be able to find all the solutions for the puzzle and each solution only once. '
- It should be easy to modify your program, so that, it works for different board sizes. Hints:
- In any row, there is exactly one queen. Hence, all you need to compute is the column in which each of the 8 queens can be placed.
- You should implement a recursive function solve(n) that finds a place for nth+1 the queen and then calls itself recursively for the n+1 queen (unless all the queens have been placed). It should systematically explore all the possibilities using backtracking.
- You are allowed (and encouraged) to define extra functions (other than solve() ) to improve the quality of your code if necessary.
import numpy as np
grid = np.zeros((8, 8), dtype = int)
def possible(y, n):
global solved
global grid
for i in range(0, 8):
if grid[y][i] == n:
return False
try:
for item in solved[str(y)]:
if grid[y].all() == item.all():
return False
except KeyError:
return True
return True
max_y = 7
max_x = 7
def print_grid():
global grid
for line in grid:
for square in line:
if square == 0:
print(".", end = " ")
else :
print("Q", end = " ")
print()
solved = {}
def prefilled_solved():
global solved
for i in range(0, len(grid[0])):
solved[f"{str(i)}"] = []
def solve(y=0):
global grid
global solved
while y < 8:
for x in range(0, 8):
if grid[y][x] == 0:
if possible(x, 1):
grid[y][x] = 1
solved[f"{str(y)}"].append(grid[y])
y += 1
solve(y)
#y -= 1 or y = 0 or y -=2
# backtracking - bad choice
# grid[y][x] = 0
print_grid()
print(grid)
return
input("More?")
if __name__ == '__main__':
prefilled_solved()
solve()
I've followed the @mkam advice, Now I've got the random constellation of Queen but I've got rid of recursion altogether.
```import numpy as np
grid = np.zeros((8, 8), dtype = int)
from random import randint, shuffle, choice
from itertools import permutations
constellations_drawn = []
def print_grid():
global grid
for line in grid:
for square in line:
if square == 0:
print(".", end = " ")
else :
print("Q", end = " ")
print()
solved = []
def prefilled_solved():
global solved
new_board = ['1', '2', '3', '4', '5', '6', '7', '8']
new_board_i = ''.join(new_board)
solved = permutations(new_board_i, 8)
def solve(y=0):
global grid
global solved
global constellations_drawn
list_solved = list(solved)
len_solved = len(list_solved)
board_drawn = list_solved[randint(0, len_solved-1)]
board_drawn_str = ''.join(board_drawn)
while board_drawn_str in constellations_drawn:
board_drawn = list_solved[randint(0, len_solved - 1)]
new_board_list = [int(item) for item in board_drawn]
for i, x in enumerate(new_board_list):
if grid[i-1][x-1] == 0:
grid[i-1][x-1] = 1
#y += 1
#solve(y)
#y -= 1 or y = 0 or y -=2
# backtracking - bad choice
# grid[y][x] = 0
constellations_drawn.append(board_drawn_str)
print_grid()
print(grid)
return
input("More?")
if __name__ == '__main__':
prefilled_solved()
solve()
I've merged the code of @mkam and mine. And it works. I still use numpy ndarray.
import numpy as np
from numpy.core._multiarray_umath import ndarray
def print_grid(solutions_found, board) -> None:
line: ndarray
len_board = len(board)
grid: ndarray = np.zeros((len_board, len_board), dtype=int)
for i, number in enumerate(board):
grid[i - 1][number - 1] = 1
for line in grid:
for square in line:
if square == 0:
print(".", end=" ")
else:
print("Q", end=" ")
print()
print(f'Solution - {solutions_found}')
def solve(boardsize, board=[], solutions_found=0):
if len(board) == boardsize:
solutions_found += 1
print_grid(solutions_found, board)
else:
for q in [col for col in range(1, boardsize + 1) if col not in board]:
if is_safe(q, board):
solutions_found = solve(boardsize, board + [q], solutions_found)
return solutions_found
def is_safe(q, board, x=1):
if not board:
return True
if board[-1] in [q + x, q - x]:
return False
return is_safe(q, board[:-1], x + 1)
if __name__ == '__main__':
solve(8)
This is an example of how the 8-Queens problem can be solved recursively, using a simple list to represent the board. A list such as [8, 4, 1, 3, 6, 2, 7, 5] represents the 8 rows of a chessboard from top to bottom, with a Q in the 8th column of the top row, the 4th column of the 7th row, the 1st column of the 6th row ... and the 5th column of the bottom row.
A solution is built starting with an empty board [] by placing a Q in the next row in a column position where it cannot be taken. Possible positions are columns which have not already been taken earlier (this is the for loop in function solve). For each of these possible column positions, function issafe checks whether the position is safe from being taken diagonally by the Qs already on the board. If the position is safe, the solution board is extended by another row and the solution recurses until the board is filled (len(board) == boardsize), at which point the solution count is incremented and the board is displayed.
Note that the function solve works for any size of square chessboard - the desired size is passed as a parameter to solve, and the function returns the total number of solutions found.
Hope this helps explain how the 8-Queens problem can be solved recursively WITHOUT numpy.
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[], solutions_found=0):
if len(board) == boardsize:
solutions_found += 1
display(solutions_found, board)
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
solutions_found = solve(boardsize, board + [q], solutions_found)
return solutions_found
if __name__ == '__main__':
solutions = solve(8)
print(f'{solutions} solutions found')
You mention using yield - this is also possible, and will transform solve into a generator, producing one solution at a time. Your program can then use a for loop to receive each solution in turn and process it as required. The following yield solution works with Python v.3.3 onwards because it uses yield from:
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[]):
if len(board) == boardsize:
yield board
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
yield from solve(boardsize, board + [q])
if __name__ == '__main__':
for solutionnumber, solution in enumerate(solve(8)):
display(solutionnumber+1, solution)
If the recursive function issafe appears confusing, here is a non-recursive version:
def issafe(q, board):
x = len(board)
for col in board:
if col in [q+x,q-x]: return False
x -= 1
return True