Teaching Kids Programming – Backtracking Algorithm to Solve N-Queen Problem

Teaching Kids Programming: Videos on Data Structures and Algorithms

8-queens

Given NxN chess board, you are asked to place N queens so that they are not attacking each other horizontally, vertically and diagonally. If the requirment is only not being attacked by other queens vertically and horizontally but it is ok to have other queens in four diagonal directions, we can compute the number of placement solution is N! (factorial).

We can place N queens in N columns. For first queen, we have N places to put, and for second column, we have N-1, for the third column, we have N-2 etc. The total solutions are N*(N-1)*(N-2)*…1 which is N! (factorial).

Backtracking Algorithm to Solve N Queen Problem

The strategy is to try placing current queen, then try placing next queen until we have done placing N queens. To check if a queen can be placed, we need to check if the current proposed position (row number) has conflicts with existing queens – which we need to check if the row has appeared before and also if it will attack existing queens diagonally.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def can_place(cur, x):
    for i, y in enumerate(cur):
        if y == x or len(cur) - i == abs(x - y):
            return False
    return True
 
def dfs(cur, n):
    if len(cur) == n:
        return 1
    ans = 0
    for row in range(n):
        if can_place(cur, row):
            # placing next queen
            ans += dfs(cur + [row], n)
    return ans
 
def queen(n):
    return dfs([], n)
    
# 92 solutions for 8x8 queen problem
print(queen(8))

def can_place(cur, x):
    for i, y in enumerate(cur):
        if y == x or len(cur) - i == abs(x - y):
            return False
    return True

def dfs(cur, n):
    if len(cur) == n:
        return 1
    ans = 0
    for row in range(n):
        if can_place(cur, row):
            # placing next queen
            ans += dfs(cur + [row], n)
    return ans

def queen(n):
    return dfs([], n)
    
# 92 solutions for 8x8 queen problem
print(queen(8))

Depth First Search Algorithm to compute the N Queen Problem with Set

We can use the set to store the number of existing solutions, with left and right for two diagonals:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def totalNQueens(self, n: int) -> int:
        def dfs(queens, left, right):
            rows = len(queens)
            if n == rows:
                return 1
            ans = 0
            for col in range(n):
                if col not in queens and rows-col not in left and rows+col not in right:
                    ans += dfs(queens + [col], left | {rows- col}, right | {rows + col})
            return ans
        return dfs([], set(), set())           

class Solution:
    def totalNQueens(self, n: int) -> int:
        def dfs(queens, left, right):
            rows = len(queens)
            if n == rows:
                return 1
            ans = 0
            for col in range(n):
                if col not in queens and rows-col not in left and rows+col not in right:
                    ans += dfs(queens + [col], left | {rows- col}, right | {rows + col})
            return ans
        return dfs([], set(), set())           

See other implementations of N-Queen Problems:

• Algorithm to Valid N Queens
• Teaching Kids Programming – Backtracking Algorithm to Solve N-Queen Problem
• Using Recursive Backtracking Algorithm to Solve Classic N Queen Problem
• Find the Queens That Can Attack the King
• N Queen Problem in Back Tracing, Bit-logics
• Coding Exercise – N Queen Problem – C++ – Bit Logics – Shortest and Fastest Solution – Online Judge
• N Queen Problem in Back Tracing, Bit-logics

–EOF (The Ultimate Computing & Technology Blog) —