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

PythonServer Side ProgrammingProgramming

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

 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

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

 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

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
Published on 22-Dec-2020 11:01:14
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.2403203845024109, "perplexity": 2418.273843805591}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-21/segments/1620243990584.33/warc/CC-MAIN-20210513080742-20210513110742-00118.warc.gz"}