Program to check whether we can get N queens solution or not in Python

Suppose we have a binary matrix where 0 is representing empty cell and 1 is representing a chess queen at that cell. We have to check whether we can fill this board and get a valid nqueen solution or not. As we know the n queens puzzle asks to place n queens on an n × n chessboard so that no two chess queens can attack each other.

So, if the input is like

then the output will be True, as one solution is like −

To solve this, we will follow these steps −

• Define a function isSafe() . This will take board, i, j

• for r in range 0 to size of board, do

  • if r is not same as i and board[r, j] is same as 1, then

    • return False

• r := i + 1, c := j + 1

• while r < row size of board and c < column size of board, do

  • if board[r, c] is same as 1, then

    • return False

  • r := r + 1, c := c + 1

• r:= i + 1, c := j - 1

• while r < row size of board and c >= 0, do

  • if board[r, c] is same as 1, then

    • return False

  • r := r + 1, c := c - 1

• r := i - 1, c := j + 1

• while r >= 0 and c < column size of board, do

  • if board[r, c] is same as 1, then

    • return False

  • r := r - 1, c := c + 1

• r := i - 1, c := j - 1

• while r >= 0 and c >= 0, do

  • if board[r, c] is same as 1, then

    • return False

  • r := r - 1, c := c - 1

• return True

• From the main method do the following −

• r := 0, c := 0

• stack := a new stack

• while r < row size of board, do

  • if 1 is in board[r], then

    • r := r + 1

    • go for next iteration

  • otherwise,

    • found := False

    • while c < column size of board, do

      • if isSafe(board, r, c) is true, then

        • board[r, c] := 1

        • insert [r, c] into stack

        • found := True

        • come out from the loop

      • c := c + 1

    • if found is true, then

      • c := 0, r := r + 1

    • otherwise,

      • if stack is empty, then

        • return False

      • m := delete top element from stack

      • r := m[0], c := m[1] + 1

      • board[r, c - 1] := 0

• return True

Example 

Let us see the following implementation to get better understanding −

 Live Demo

class Solution:    def solve(self, board):       def isSafe(board, i, j):          for r in range(len(board)):             if r != i and board[r][j] == 1:                return False          r, c = i + 1, j + 1          while r < len(board) and c < len(board[0]):             if board[r][c] == 1:                return False             r += 1             c += 1          r, c = i + 1, j - 1          while r < len(board) and c >= 0:             if board[r][c] == 1:                return False             r += 1             c -= 1          r, c = i - 1, j + 1          while r >= 0 and c < len(board[0]):             if board[r][c] == 1:                return False             r -= 1             c += 1          r, c = i - 1, j - 1          while r >= 0 and c >= 0:             if board[r][c] == 1:                return False             r -= 1             c -= 1          return True       r = c = 0       stack = []       while r < len(board):          if 1 in board[r]:             r += 1             continue          else:             found = False             while c < len(board[0]):                if isSafe(board, r, c):                   board[r][c] = 1                   stack.append([r, c])                   found = True                   break                c += 1             if found:                c = 0                r += 1             else:                if not stack:                   return False                m = stack.pop()                r, c = m[0], m[1] + 1                board[r][c - 1] = 0       return True ob = Solution() 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] ] print(ob.solve(matrix))

Input

[ [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