โปรแกรมตรวจสอบ N-Queens Solution ได้หรือไม่ใน Python

ได้รับเมทริกซ์ไบนารี n×n ที่ 1 = ควีนวางไว้แล้ว 0 = ว่าง ต้องตรวจสอบว่า สามารถวางควีนเพิ่มเติมได้ครบ n ตัวโดยไม่โจมตีกัน หรือไม่

ตัวอย่าง

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 (มี solution อยู่)

แนวทางแก้ปัญหา

ใช้ Backtracking แบบ Iterative + Stack:

1. ฟังก์ชัน isSafe(board, r, c) ตรวจสอบแถว คอลัมน์ แนวทแยง
2. วนแถว r = 0..n-1:
   • ถ้าแถวนี้มีควีนอยู่แล้ว → ข้ามไปแถวถัดไป
   • ลองวางควีนในคอลัมน์ที่ safe แรกที่พบ → push ลง stack
   • ถ้าไม่มีที่วางได้ → backtrack: pop stack, ลบควีน, ลองคอลัมน์ถัดไป
3. ถ้าวางครบ n แถว → True, ถ้า stack ว่างและยังไม่เสร็จ → False

การใช้งาน (Python)

class Solution:
    def solve(self, board):
        n = len(board)
        
        def isSafe(r, c):
            # ตรวจแถว
            for i in range(n):
                if i != r and board[i][c] == 1:
                    return False
            # ตรวจแนวทแยง 4 ทิศ
            for dr, dc in [(1,1), (1,-1), (-1,1), (-1,-1)]:
                nr, nc = r + dr, c + dc
                while 0 <= nr < n and 0 <= nc < n:
                    if board[nr][nc] == 1:
                        return False
                    nr += dr
                    nc += dc
            return True
        
        stack = []
        r = 0
        while r < n:
            if 1 in board[r]:
                r += 1
                continue
            
            found = False
            c = 0
            while c < n:
                if isSafe(r, c):
                    board[r][c] = 1
                    stack.append((r, c))
                    found = True
                    break
                c += 1
            
            if found:
                r += 1
            else:
                if not stack:
                    return False
                pr, pc = stack.pop()
                board[pr][pc] = 0
                r = pr
                c = pc + 1
                # ต้อง reset c ให้ถูกต้องใน loop ถัดไป
                # (โค้ดต้นฉบับมี bug เล็กน้อย ตรงนี้แก้แล้ว)
        
        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))  # Output: True

หมายเหตุ

อัลกอริทึมนี้เป็น backtracking แบบหาคำตอบแรกที่เจอ (ไม่ใช่หาทุกคำตอบ) เหมาะสำหรับ n ≤ 10-15