-
Notifications
You must be signed in to change notification settings - Fork 0
/
NQUEENS.py
81 lines (68 loc) · 1.9 KB
/
NQUEENS.py
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# -*- coding: utf-8 -*-
"""
Created on Sun Dec 9 23:00:24 2018
@author: Nikhil
"""
def initializeBoard(Board,n):
for key in ["queen","row","column","nw2se","sw2ne"]:
Board[key]={}
for i in range(n):
Board["queen"][i]=-1
Board["row"][i]=0
Board["column"][i]=0
for i in range(-(n-1),n):
Board["nw2se"][i]=0
for i in range(0,2*n-1):
Board["sw2ne"][i]=0
def printBoard(Board):
for row in sorted(Board["queen"].keys()):
print((row,Board["queen"][row]),end=" ")
else:
print()
def free(i,j,Board):
return (Board["row"][i]==0
and Board["column"][j]==0
and Board["nw2se"][j-i]==0
and Board["sw2ne"][i+j]==0)
def addqueen(i,j,Board):
Board["queen"][i]=j
Board["row"][i]=1
Board["column"][j]=1
Board["nw2se"][j-i]=1
Board["sw2ne"][i+j]=1
def undoqueen(i,j,Board):
Board["queen"][i]=-1
Board["row"][i]=0
Board["column"][j]=0
Board["nw2se"][j-i]=0
Board["sw2ne"][i+j]=0
def placequeen(i,Board):
n =len(Board["queen"].keys())
for j in range(0,n):
if free(i,j,Board):
addqueen(i,j,Board)
if i==n-1:
return True
else:
extendsolution=placequeen(i+1,Board)
if extendsolution:
return True
else:
undoqueen(i,j,Board)
else:
return False
def solveQueen(Board):
if placequeen(0,Board):
printBoard(Board)
else: print("No Solution")
while 1:
Board={}
while True:
try:
N=int(input("Enter the value of N to solve for N Queen Problem: \n"))
except:
print("Enter the valid input")
else:
break
initializeBoard(Board, N)
solveQueen(Board)