N queens Task
"I am currently a Software Engineering student at ALX. I'm passionate about technology and enjoy conducting research to find answers on my own. I have a natural inclination to ask 'WHY' more often than 'HOW'.
"While working on projects at ALX, I have acquired a wealth of interesting and diverse knowledge about software engineering and computer science in general. Therefore, I needed a place to store and save all this information, allowing me to refer back to it whenever I forget."
Eight queens puzzle
The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column, or diagonal. There are 92 solutions. The problem was first posed in the mid-19th century. In the modern era, it is often used as an example problem for various computer programming techniques.
The eight queens puzzle is a special case of the more general n queens problem of placing n non-attacking queens on an n×n chessboard. Solutions exist for all natural numbers n with the exception of n = 2 and n = 3. Although the exact number of solutions is only known for n ≤ 27, the asymptotic growth rate of the number of solutions is approximately (0.143 n)n.
In this task, we going to be leveraging backtracking
Backtracking is a general algorithmic technique used in programming to find solutions to combinatorial problems, such as finding a feasible arrangement of elements or a valid configuration. It is commonly applied in problems that involve searching through a large search space or trying out different possibilities until a solution is found.
The backtracking algorithm starts with an initial partial solution and systematically explores all possible extensions of the solution, one step at a time. At each step, the algorithm tries out a choice and moves forward, and if it reaches a point where the current choice cannot lead to a valid solution, it backtracks and tries a different choice. This process continues until either a valid solution is found or all possible choices have been exhausted.
The key idea behind backtracking is to efficiently explore the search space by eliminating branches that cannot lead to a valid solution. By backtracking, the algorithm avoids unnecessary computation and optimizes the search process.
Backtracking is often implemented using recursion, where the recursive function represents each step of the algorithm and the call stack maintains the state of the exploration. When the algorithm reaches a point of backtracking, it returns from the current recursive call and proceeds with the next possible choice.
Here's a simplified example of a backtracking algorithm to find all possible permutations of a set of elements:
function backtrack(permutation, choices):
if choices is empty:
print permutation
else:
for each choice in choices:
add choice to permutation
remove choice from choices
backtrack(permutation, choices)
remove choice from permutation
add choice back to choices
In this example, the backtrack function takes a partial permutation and a set of available choices. If the set of choices is empty, it means a complete permutation has been generated, and it is printed as a solution. Otherwise, for each choice, it is added to the current permutation, and the algorithm proceeds recursively. After the recursive call, the choice is removed from the permutation and added back to the set of choices to explore other possibilities.
Backtracking can be a powerful technique for solving complex problems, but it can also be computationally expensive if the search space is large. Therefore, it is crucial to design efficient pruning strategies and explore optimization techniques to improve the performance of backtracking algorithms.
This solution, solves the nqueens puzzle but gives the output in dots(.) and 'Q's, This makes it easier to understand what is going on and the logic behind it.
def nqueens(n):
if n < 4:
print("number must be >= 4")
sys.exit(1)
res = []
board = [["."] * n for i in range(n)]
cols = set()
posdiag = set()
negdiag = set()
def backtrack(row):
if row == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for col in range(n):
if col in cols or row + col in posdiag or row - col in negdiag:
continue
cols.add(col)
posdiag.add(row + col)
negdiag.add(row - col)
board[row][col] = "Q"
backtrack(row + 1)
cols.remove(col)
posdiag.remove(row + col)
negdiag.remove(row - col)
board[row][col] = "."
backtrack(0)
return res
if __name__ == "__main__":
if len(sys.argv) != 2:
print("Usage: nqueens N")
sys.exit(1)
try:
n = int(sys.argv[1])
except ValueError:
print("value must be an integer")
sys.exit(1)
solution = nqueens(n)
for sol in solution:
print(sol)
output:
['.Q..', '...Q', 'Q...', '..Q.']
['..Q.', 'Q...', '...Q', '.Q..']
This gives the output by specifying the rows and columns(position) of each Queen:
import sys
def nqueens(n):
if n < 4:
print("number must be >= 4")
sys.exit(1)
res = []
board = [["."] * n for _ in range(n)]
cols = set()
posdiag = set()
negdiag = set()
def backtrack(row):
if row == n:
queens = []
for r in range(n):
for c in range(n):
if board[r][c] == "Q":
queens.append([r, c])
res.append(queens)
return
for col in range(n):
if col in cols or row + col in posdiag or row - col in negdiag:
continue
cols.add(col)
posdiag.add(row + col)
negdiag.add(row - col)
board[row][col] = "Q"
backtrack(row + 1)
cols.remove(col)
posdiag.remove(row + col)
negdiag.remove(row - col)
board[row][col] = "."
backtrack(0)
return res
if __name__ == "__main__":
if len(sys.argv) != 2:
print("Usage: nqueens N")
sys.exit(1)
try:
num = int(sys.argv[1])
except ValueError:
print("Value must be an integer")
sys.exit(1)
solution = nqueens(num)
for sol in solution:
print(sol)
The Algorithm:
The algorithm is quite simple, but took me two days to get around it(I'm a slow learner👦)
The rule of the game is to place the queens so that no two queens threaten each other, you should know a little about chess to understand the logic.
The queens can cover any number of blocks both vertically, horizontally, and diagonally(positive and negative diagonals)We are going to maintain the columns of the previous Queens we have already placed.
We don't have to maintain the rows, because any time we place a Queen, we would be moving to the next row anyway.
But we need to maintain the two diagonals, so we know if the Queen/Queens previously placed is not in any way a threat to the new queen.
Now you might be wondering how to know/check the diagonals, so there is a bit of a pattern when it comes to diagonals(positive and negative) the difference between their rows and cols is always a constant. eg for the center negative diagonal, the diff is always 0. other diagonals can be -1 or 1, -2 or 2 etc.
So along every diagonal, the computation row - col, will always stay constant for the negative diagonal, and row + col will always stay a constant for the positive diagonal.
Output:
root@f0a915964a9b:/# python3 nqueens.py 4
[[0, 1], [1, 3], [2, 0], [3, 2]]
[[0, 2], [1, 0], [2, 3], [3, 1]]
Positive Diagonal(growing upwards)
Negative Diagonal(growing downwards)
If you were wondering just like I was why the first placement of queen for nqueens 4 didn't start at [0, 0] but started at [0, 1]. Here's why in drawing
MORE ON THE OUTPUT:
Let me explain the matrix arrangement and the meaning of each number in the context of the N-queens problem.
In the N-queens problem, the chessboard is represented as an N×N matrix. Each cell in the matrix represents a position on the chessboard. The value in each cell indicates whether a queen is placed at that position.
When printing the solutions, the program represents the positions of the queens as [row, col] coordinates. The row value corresponds to the row index in the matrix, and the col value corresponds to the column index in the matrix.
For example, let's consider the solution [[0, 1], [1, 3], [2, 0], [3, 2]] for the 4-queens problem. The matrix representation of this solution would look like this:
. Q . .
. . . Q
Q . . .
. . Q .
In the above representation, each Q represents the position of a queen on the chessboard. The . represents an empty cell.
Let's break down the [row, col] coordinates in the solution:
[0, 1]means a queen is placed in the first row (row=0) and the second column (col=1).[1, 3]means a queen is placed in the second row (row=1) and the fourth column (col=3).[2, 0]means a queen is placed in the third row (row=2) and the first column (col=0).[3, 2]means a queen is placed in the fourth row (row=3) and the third column (col=2).
The program generates all possible valid solutions and prints them in a similar format, with each solution represented as a list of [row, col] coordinates.
Another way to implement the nqueens task(3 eg):
import sys
def solve_nqueens(n):
if n < 4:
print("N must be at least 4")
sys.exit(1)
# Initialize the board with -1 values
board = [-1] * n
solutions = []
def is_safe(row, col):
for i in range(row):
if board[i] == col or board[i] - i == col - row or \
board[i] + i == col + row:
return False
return True
def add_solution():
solution = []
for i in range(n):
solution.append([i, board[i]])
solutions.append(solution)
def place_queen(row):
if row == n:
add_solution()
return
for col in range(n):
if is_safe(row, col):
board[row] = col
place_queen(row + 1)
place_queen(0)
return solutions
# Main program
if len(sys.argv) != 2:
print("Usage: nqueens N")
sys.exit(1)
try:
N = int(sys.argv[1])
except ValueError:
print("N must be a number")
sys.exit(1)
solutions = solve_nqueens(N)
for solution in solutions:
print(solution)
In the given code, backtracking is implemented in the place_queen function.
The place_queen function is a recursive function that tries to place the queens on the board row by row. It takes a parameter row which represents the current row being processed.
Here's how backtracking is applied in the place_queen function:
Base Case: If
rowis equal ton, it means all the queens have been successfully placed on the board. In this case, the function calls theadd_solutionfunction to add the current valid solution to the list of solutions. Then, it returns to continue exploring other possibilities.Recursive Case: If the base case is not met, the function enters a loop that iterates over each column in the current row (
colvariable). It checks if it's safe to place a queen at the current position by calling theis_safefunction.If it's safe to place a queen at the current position, the function sets the value of
board[row]tocoland makes a recursive call toplace_queen(row + 1)to proceed to the next row.If it's not safe to place a queen at the current position, the function backtracks by not making a recursive call and continues to the next iteration of the loop, trying the next column.
By using backtracking, the place_queen function explores different possibilities of queen placements on the board and backtracks whenever a placement leads to an unsafe configuration. This allows it to find all valid solutions to the N queens puzzle.
Now how does it know where the previous queens are placed so to avoid two queens threatening each other
The place_queen function keeps track of the positions of previously placed queens using the board list. The index of the list represents the row number, and the value at that index represents the column number where a queen is placed.
When the function checks if it's safe to place a queen at a specific position (is_safe function), it iterates over the rows that have been processed so far (from 0 to row - 1). For each row, it compares the column value (board[i]) with the current column (col) and checks if they are the same (queens in the same column) or if their differences (board[i] - i and col - row) or sums (board[i] + i and col + row) are the same (queens in diagonal positions).
If any of these conditions are met, it means that the current position is not safe for placing a queen, and the function returns False. This prevents two queens from threatening each other in the same column or along diagonals.
By iterating over the rows and comparing the positions of previously placed queens, the function ensures that each new queen is placed in a position that is not threatened by any other queens on the board.
Now how does it remove the previous queens to try out new positions when backtracking
In the given code, the backtracking mechanism is implemented implicitly through the recursive nature of the place_queen function. When backtracking occurs, the function does not explicitly remove the previously placed queens. Instead, it revisits earlier recursive calls with different possibilities for queen placements.
Here's how the backtracking process works:
Initially, the
place_queenfunction is called withrowparameter set to 0, indicating that we are starting from the first row.Within the function, it iterates over the columns in the current row (
colvariable) and checks if it's safe to place a queen at that position.If it's safe, the function updates the
boardwith the new queen position by settingboard[row] = coland makes a recursive call toplace_queen(row + 1)to proceed to the next row.If it's not safe to place a queen at the current position, the function continues to the next iteration of the loop, trying the next column. This skips the recursive call and triggers backtracking implicitly.
Backtracking occurs when the function reaches the base case (when
rowis equal ton), and a valid solution has been found. At this point, the function calls theadd_solutionfunction to add the current valid solution to the list of solutions. Then, it returns from the current recursive call to the previous level, continuing the loop from the next iteration to explore other possibilities.Backtracking continues to happen until all possible placements for queens have been explored in the earlier recursive calls. Each time the function returns from a recursive call, it goes back to the previous row and continues from where it left off, trying different positions for the queen in that row.
By revisiting earlier recursive calls and exploring different possibilities, the function effectively tries out new positions for queens while implicitly "removing" previously placed queens as it backtracks to explore other options.
A simple backtracking algorithm
Here's a simple implementation of a backtracking algorithm in Python to find all possible permutations of the characters 'A', 'B', and 'C':
def permute(nums):
result = []
backtrack(nums, [], result)
return result
def backtrack(nums, path, result):
if not nums:
result.append(path)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], path + [nums[i]], result)
# Test the algorithm
input_nums = ['A', 'B', 'C']
permutations = permute(input_nums)
for permutation in permutations:
print(permutation)
When you run this code, it will output all possible permutations of the characters 'A', 'B', and 'C'. Each permutation will be printed on a separate line.
root@f0a915964a9b:/# python3 backtrack.py
['A', 'B', 'C']
['A', 'C', 'B']
['B', 'A', 'C']
['B', 'C', 'A']
['C', 'A', 'B']
['C', 'B', 'A']
Please note that this implementation assumes that there are no duplicate characters in the input list. If there are duplicate characters, you may need to modify the algorithm to handle them correctly.
Finding it difficult figuring the backtrack stuff, I added print statement to help you figure out whats going on in each recursion
def permute(nums):
result = []
backtrack(nums, [], result)
return result
def backtrack(nums, path, result):
print("Backtrack called with nums =", nums, "path =", path, "result =", result)
if not nums:
result.append(path)
print("Permutation found:", path)
return
for i in range(len(nums)):
backtrack(nums[:i] + nums[i+1:], path + [nums[i]], result)
# Test the algorithm
input_nums = ['A', 'B', 'C']
permutations = permute(input_nums)
for permutation in permutations:
print(permutation)
Output:
root@f0a915964a9b:/# python3 del1.py
Backtrack called with nums = ['A', 'B', 'C'] path = [] result = []
Backtrack called with nums = ['B', 'C'] path = ['A'] result = []
Backtrack called with nums = ['C'] path = ['A', 'B'] result = []
Backtrack called with nums = [] path = ['A', 'B', 'C'] result = []
Permutation found: ['A', 'B', 'C']
Backtrack called with nums = ['B'] path = ['A', 'C'] result = [['A', 'B', 'C']]
Backtrack called with nums = [] path = ['A', 'C', 'B'] result = [['A', 'B', 'C']]
Permutation found: ['A', 'C', 'B']
Backtrack called with nums = ['A', 'C'] path = ['B'] result = [['A', 'B', 'C'], ['A', 'C', 'B']]
Backtrack called with nums = ['C'] path = ['B', 'A'] result = [['A', 'B', 'C'], ['A', 'C', 'B']]
Backtrack called with nums = [] path = ['B', 'A', 'C'] result = [['A', 'B', 'C'], ['A', 'C', 'B']]
Permutation found: ['B', 'A', 'C']
Backtrack called with nums = ['A'] path = ['B', 'C'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C']]
Backtrack called with nums = [] path = ['B', 'C', 'A'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C']]
Permutation found: ['B', 'C', 'A']
Backtrack called with nums = ['A', 'B'] path = ['C'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A']]
Backtrack called with nums = ['B'] path = ['C', 'A'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A']]
Backtrack called with nums = [] path = ['C', 'A', 'B'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A']]
Permutation found: ['C', 'A', 'B']
Backtrack called with nums = ['A'] path = ['C', 'B'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B']]
Backtrack called with nums = [] path = ['C', 'B', 'A'] result = [['A', 'B', 'C'], ['A', 'C', 'B'], ['B', 'A', 'C'], ['B', 'C', 'A'], ['C', 'A', 'B']]
Permutation found: ['C', 'B', 'A']
['A', 'B', 'C']
['A', 'C', 'B']
['B', 'A', 'C']
['B', 'C', 'A']
['C', 'A', 'B']
['C', 'B', 'A']
I used the ABC example because printing each step for the nqueens puzzle could be cumbersome.
