Backtracking Algorithm to Solve N Queens Puzzle (Partially Filled)

The n queens puzzle asks to place n queens on an n×n chessboard so that no two queens are attacking each other.

Given a partially filled two-dimensional integer matrix where 1 represents a queen and 0 represents an empty cell, return whether this configuration of the board can solve the puzzle.

Constraints
1 ≤ n ≤ 15
Example 1
Input

1 2 3 4 5 6 7

matrix = [     [1, 0, 0, 0, 0],     [0, 0, 0, 0, 0],     [0, 0, 0, 0, 1],     [0, 0, 0, 0, 0],     [0, 0, 0, 1, 0] ]

matrix = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0]
]

Output
True
Explanation
One solution is:

1 2 3 4 5

[1, 0, 0, 0, 0] [0, 0, 1, 0, 0] [0, 0, 0, 0, 1] [0, 1, 0, 0, 0] [0, 0, 0, 1, 0]

[1, 0, 0, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 1]
[0, 1, 0, 0, 0]
[0, 0, 0, 1, 0]

Backtracking Algorithm (Depth First Search) to Solve Partially Prefilled N Queen

Given partially prefilled board, we need to find out the index for the 1’s. If there are more than 1 one, it is impossible to fulfill/solve the N queen puzzle.

If the current row is allocated a queen, we simply try to put it during the Backtracking search, otherwise, we try every possible i.e. N places.

The following is the Depth First Search aka Back tracking algorithm to solve the partially pre-filled N queen puzzle.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
    def solve(self, matrix):
        if not matrix:
            return True
        n = len(matrix)
        data = []
        for i in range(n):
            x = matrix[i].count(1)
            if x > 1:
                return False
            if x == 1:
                data.append(matrix[i].index(1))
            else:
                data.append(-1)
        def check(cur, i):
            for j in range(len(cur)):
                if abs(i - cur[j]) == len(cur) - j or i == cur[j]:
                    return False
            return True
        def dfs(cur):
            if len(cur) == n:
                return True
            x = data[len(cur)]
            sols = []
            if x == -1:
                sols = list(range(n))
            else:
                sols.append(x)
            for i in sols:
                if check(cur, i) and dfs(cur + [i]):
                    return True                        
            return False
        return dfs([])

class Solution:
    def solve(self, matrix):
        if not matrix:
            return True
        n = len(matrix)
        data = []
        for i in range(n):
            x = matrix[i].count(1)
            if x > 1:
                return False
            if x == 1:
                data.append(matrix[i].index(1))
            else:
                data.append(-1)
        def check(cur, i):
            for j in range(len(cur)):
                if abs(i - cur[j]) == len(cur) - j or i == cur[j]:
                    return False
            return True
        def dfs(cur):
            if len(cur) == n:
                return True
            x = data[len(cur)]
            sols = []
            if x == -1:
                sols = list(range(n))
            else:
                sols.append(x)
            for i in sols:
                if check(cur, i) and dfs(cur + [i]):
                    return True                        
            return False
        return dfs([])

–EOF (The Ultimate Computing & Technology Blog) —