N-Queens Problem

In this problem, there exists an $n$ x $n$ chessboard, containing $n$ queens. The goal of the problem is to place these queens such that no two queens can attack each other.

Decision Version: NP-Complete §

Given an $n\times n$ chessboard, is it possible to arrange $n$ queens such that no two queens can attack each other

Note the n-queens problem does not have an optimisation version.

#computer-science/algorithm/design/brute-force Approach §

First, let us start by using n=8 i.e. solving the 8-queens problem.

1. Arrange 8 queens in 64 possible positions. There are 64 possible places, so we need to choose 8 to place the queens there. This can be done in $nCr=64C8=\frac{64!}{8!\ast 56!}=4,426,165,368$ ways.
2. Arrangements of 1 queen per row. If we restrict to one queen per row, each queen has 8 possible places, so the total number of arrangements is $8^8=16,777,216$.
3. Permutations of 8 queens, 1 queen per row. By using permutations, we no longer have double-ups in the same rows. Then the total number would be $8!=40320$

#computer-science/algorithm/design/backtracking Approach §

1. Choose a possible queen combination
2. Check if this position is possible
3. If not, backtrack

def n_queens(n):
    board = [[0 for i in range(n)] for j in range(n)]   #Create an nxn board with 0s
    backtrack(0,board,n)    #Runs backtrack from row 0
    for i in board: print(i)
 
def backtrack(row,board,n):
    if row == n:    #Base case, all queens placed
        return True
    for col in range(n):
            if safe_move(row,col,board,n):  #If a queen can be placed here
                board[row][col] = 'Q'
                if backtrack(row+1,board,n):
                     return True
                board[row][col] = 0
    return False
            
def safe_move(row,col,board,n):
    for i in range(n):
        if i != col and board[row][i] == 'Q':
            return False
    for j in range(n):
        if j != row and board[j][col] == 'Q':
            return False
    # Some magic shit i copied from GeeksForGeeks
    for i, j in zip(range(row, -1, -1),
                    range(col, -1, -1)):
        if board[i][j] == 'Q':
            return False
    for i, j in zip(range(row, n, 1),
                    range(col, -1, -1)):
        if board[i][j] == 'Q':
            return False
    return True
 
n_queens(4)