N-Queens Problem

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. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3.

Solutions

Backtracking Algorithm
The idea is to place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. In the current column, if we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes then we backtrack and return false.

  • Start in the leftmost column;

  • If all queens are placed, return true;

  • Try all rows in the current column. Do following for every tried row:

    • a) If the queen can be placed safely in this row then mark this [row, column] as part of the solution and recursively check if placing queen here leads to a solution.

    • b) If placing queen in [row, column] leads to a solution then return true.

    • c) If placing queen doesn't lead to a solution then umark this [row, column] (Backtrack) and go to step (a) to try other rows.

  • If all rows have been tried and nothing worked, return false to trigger backtracking.

Implementation

class NQueens:
    def __init__(self, queens_count):
        self.queens_count = queens_count
        self.solutions = []
    def is_safe(self, positions, row, col):
        if positions == []: return True
        for y, x in enumerate(positions):
            if x==row: return False
            if abs(x-row) == abs(y-col): return False
        return True
    def recursive(self, col, positions=[]):
        if col == self.queens_count: 
            self.solutions.append(positions)
            return True
        for row in range(self.queens_count):
            if self.is_safe(positions, row, col):
                self.recursive(col+1, positions+[row])
        return False
    def solve(self):
        self.recursive(0)
        return len(self.solutions)
    def show(self):
        n = self.queens_count
        for idx, s in enumerate(self.solutions):
            chessboard = [['·']*n for i in range(n)]
            for c, r in enumerate(s): chessboard[r][c] = 'Q'
            print(f'Solution NO. {idx+1}:')
            for i in chessboard: print(' '.join(i))