मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है जहां 0 खाली सेल दर्शाता है और 1 उस सेल पर शतरंज की रानी दर्शाता है। हमें जांचना है कि क्या हम इस बोर्ड को भरकर एक वैध N-क्वीन समाधान प्राप्त कर सकते हैं। N-क्वीन पहेली N x N शतरंज बोर्ड पर N रानियों को रखने के लिए कहती है ताकि कोई दो रानी एक-दूसरे पर हमला न कर सकें।
उदाहरण के लिए, दिए गए प्रारंभिक कॉन्फ़िगरेशन के लिए आउटपुट True होगा क्योंकि एक वैध समाधान मौजूद है।
एल्गोरिदम (बैकट्रैकिंग के साथ स्टैक)
isSafe(board, i, j)फ़ंक्शन परिभाषित करें जो जांचता है कि(i, j)पर रानी रखना सुरक्षित है या नहीं (पंक्ति, कॉलम, दोनों विकर्ण जांचें)- मुख्य विधि से:
r=0, c=0, stack=[]- जब
r < बोर्ड आकार:- यदि पंक्ति
rमें पहले से 1 है, तोr++करें और जारी रखें - अन्यथा, कॉलम
cसे आगे खोजें जहां रानी रखना सुरक्षित हो - यदि मिला, तो रखें, स्टैक में डालें,
c=0, r++ - यदि नहीं मिला, तो बैकट्रैक करें: स्टैक से पॉप करें, उस सेल को 0 करें, अगले कॉलम से पुनः प्रयास करें
- यदि स्टैक खाली है और कोई स्थान नहीं मिला, तो
Falseवापस करें
- यदि पंक्ति
Trueवापस करें
उदाहरण
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))
इनपुट
[[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]]
आउटपुट
True
