## Eight queens problem, backtracking, Python3

- Problem:

Given an 8×8 board, your job is to place 8 queens on the board such that none of them can attack each other (If you are not familiar with chess, then google it first). The problem can be more general, given a n x n (n > 3) board, place n queens on the board such that there is no way a queen can attack the others. There are 92 solutions to this problem.

- Solutions

The way to solve this problem is already described in the title. Here’s let solve it step by step. First let’s try some thoughts on a small board to see if we can apply the approach which we are about to come up with on small board to a wider one.

To develop an algorithm for this problem, we can first study a smaller instance of the problem by using just four queens and a 4 * 4 board. How would you go about solving this smaller problem? You may attempt to randomly place the queens on the board until you find a solution that may work for this smaller case. But when attempting to solve the original eight-queens problem, this approach may lead to chaos.

Consider a more organized approach to solving this problem.

Since no two queens can occupy the same column, we can proceed one column at a time and attempt to position a queen in each column.We start by placing a queen in the upper-left square or position (0, 0) using the 2-D array notation:

With this move, we now eliminate all squares horizontally, vertically, and diagonally from this position for the placement of additional queens since these positions are guarded by the queen we just placed.

With the first queen placed in the first column, we now move to the second column. The first open position in this column where a queen can be placed without being attacked by the first queen we placed is at position (2,1). We can place a queen in this position and mark those squares that this queen guards, removing yet more positions for the placement of additional queens.

We are now ready to position a queen in the third column. But you may notice there are no open positions in the third column. Thus, the placement of the first two queens will not result in a valid solution. At this point, you may be tempted to remove all of the existing queens and start over. But that would be a drastic move.

But there are no more open squares in the second column to try, so we must back up even further, returning to the first column. When returning to a column, the first step is always to pick up the queen previously placed in that column.

After picking up the queen in the first column, we place it in the next position (1, 0) within that column.

We can now repeat the process and attempt to find open positions in each of the remaining columns. These final steps, which are illustrated here, results in a solution to the four-queens problem.

Having found a solution for the four-queens problem, we can use the same approach to solve the eight-queens problem. The only difference between the two is that there is likely to be more backtracking required to find a solution. In addition, while the four-queens problem has two solutions, the eight-queens problem has 92 solutions.

The original problem definition only considered finding a solution for a normal 8 * 8 chessboard. A more general problem, however, is known as the n-queens problem, which allows for the placement of n queens on a board of size n*n where n > 3. The same backtracking technique described earlier can be used with the n-queens problem, although finding a solution to larger-sized boards can be quite time consuming.

**The possible data structures for representing the actual board.**

The most obvious choice is a 2-D array of size n * n. The elements of the array can contain boolean values with True indicating the placement of the queens. To determine if a given square is unguarded, loops can be used to iterate over all of the squares to which a queen can move from that position. If a queen is found in any of the squares searched during the loop iterations, then we know the square is currently guarded by at least one queen. The placement and removal of the queens is also quite easy to implement using the 2-D array structure.

As an alternative, we can actually use a 1-D array consisting of n elements. Each element of the 1-D array corresponds to one column on the board. The elements of the 1-D array will contain row indices indicating the positions of the queens on the board.

Since only one queen can be placed within a given column, we need only keep track of the row containing the queen in the column. When determining if a square is unguarded, we can iterate through the row and column indices for the preceding columns on the board from which the given square can be attacked by a queen. Instead of searching for a True value within the elements of a 2-D array, we need only determine if the elements of the 1-D array contain one of the row indices being examined.

When searching horizontally backward, we examine the elements of the 1-D array looking for an index equal to that of the current row. If one is found, then there is a queen already positioned on the current row as is the case in the above example. If a queen was not found on the current row, then we would have to search diagonally to the upper left and to the lower left. We only search in this two directions because we place the queen from left to right, column by column. In these two cases, we search the squares indicated by the arrows and examine the row indices of each and compare them to the entries in the 1-D array. If any of the indices match, then a queen is currently guarding the position and it is not a legal move.

Code using backtracking to solve n-queens problem.

from board import Board def solve_n_queens(board, col, ways): # check if n-queens has been placed on the board # base case if board.num_queens() == board.size(): ways.append([x for x in board._board]) return False else: for row in range(board.size()): if board.unguarded(row, col): # place a queen in that square board.place_queen(row, col) # continue placing queens in the following columns if solve_n_queens(board, col+1, ways): # we are finished if a solution was found return True else: # no solution was found with the queen in this square # so it has to be removed from the board # and try the next row in this col if board._board[0] == 1: print(board._board) board.remove_queen(row, col) # If the loop terminates no queen can be placed within this column return False if __name__ == '__main__': for col in range(0, 1): ways = [] board = Board(8) res = solve_n_queens(board, col, ways) print(*ways, sep='\n') print(len(ways))

The board

from array import Array class Board: def __init__(self, size): self._size = size self._board = Array(size) def size(self): return self._size def num_queens(self): return len([x for x in self._board if x is not None]) def place_queen(self, row, col): self._board[col] = row def remove_queen(self, row, col): self._board[col] = None def unguarded(self, row, col): # first check if this row is guarded if row in self._board: return False # check up left diagonal up_left_row = row - 1 up_left_col = col - 1 while self._in_bound(up_left_row, up_left_col): if self._board[up_left_col] is not None and \ self._board[up_left_col] == up_left_row: return False up_left_row -= 1 up_left_col -= 1 # check lower left diagonal low_left_row = row + 1 low_left_col = col - 1 while self._in_bound(low_left_row, low_left_col): if self._board[low_left_col] is not None and \ self._board[low_left_col] == low_left_row: return False low_left_row += 1 low_left_col -= 1 return True def _in_bound(self, row, col): return row >= 0 and row < self.size() and \ col >= 0 and col < self.size()

And the Array that’s used to construct Board

import ctypes class Array: def __init__(self, size): assert size > 0, "Array size must be > 0" self._size = size PyArrayType = ctypes.py_object * size self._elements = PyArrayType() self.clear(None) def __len__(self): return self._size def __getitem__(self, index): assert index >= 0 and index < len(self), "Array subcript out of range" return self._elements[index] def __setitem__(self, index, value): assert index >= 0 and index < len(self), "Array subcript out of range" self._elements[index] = value def clear(self, value): for i in range(len(self)): self._elements[i] = value def __iter__(self): return _ArrayIterator(self._elements) def __str__(self): str_template = "" for item in self: str_template += " %4s " str_template = str_template.strip() return "[" + str_template % tuple(self) + "]" def __contains__(self, val): for i in self: if i is not None and i == val: return True return False

## Reply