Chương trình kiểm tra xem chúng ta có thể nhận được giải pháp N nữ hoàng hay không bằng Python

Giả sử chúng ta có một ma trận nhị phân trong đó 0 đại diện cho ô trống và 1 đại diện cho quân cờ tại ô đó. Chúng tôi phải kiểm tra xem chúng tôi có thể điền vào bảng này và nhận được một giải pháp nqueen hợp lệ hay không. Như chúng ta đã biết, câu đố n nữ hoàng yêu cầu đặt n quân hậu trên một bàn cờ n × n sao cho không có hai quân hậu nào có thể tấn công nhau.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, như một giải pháp là -

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm isSafe (). Điều này sẽ diễn ra, tôi, j

• đối với r trong phạm vi 0 đến kích thước của bảng, thực hiện

  • nếu r không giống với i và board [r, j] giống với 1 thì

    • trả về Sai

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

• trong khi r

  • nếu bảng [r, c] giống 1 thì

    • trả về Sai

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

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

• trong khi r =0, thực hiện

  • nếu bảng [r, c] giống 1 thì

    • trả về Sai

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

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

• while r> =0 and c

  • nếu bảng [r, c] giống 1 thì

    • trả về Sai

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

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

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

  • nếu bảng [r, c] giống 1 thì

    • trả về Sai

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

• trả về True

• Từ phương thức chính, hãy làm như sau -

• r:=0, c:=0

• stack:=một ngăn xếp mới

• trong khi r

  • nếu 1 trong bảng [r], thì

    • r:=r + 1

    • chuyển sang lần lặp tiếp theo

  • nếu không,

    • tìm thấy:=Sai

    • trong khi c

      • nếu isSafe (board, r, c) là true thì

        • bảng [r, c]:=1

        • chèn [r, c] vào ngăn xếp

        • tìm thấy:=True

        • đi ra từ vòng lặp

      • c:=c + 1

    • nếu tìm thấy là đúng, thì

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

    • nếu không,

      • nếu ngăn xếp trống, thì

        • trả về Sai

      • m:=xóa phần tử trên cùng khỏi ngăn xếp

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

      • bảng [r, c - 1]:=0

• trả về True

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

True