โปรแกรมตรวจสอบว่าบอร์ดเป็นโซลูชัน N queens ที่ถูกต้องหรือไม่ใน python

สมมติว่าเรามีเมทริกซ์ n x n แทนกระดานหมากรุก มีบาง 1 และ 0 โดยที่ 1 แทนราชินีและ 0 แทนเซลล์ว่าง เราต้องตรวจสอบว่ากระดานเป็นคำตอบที่ถูกต้องสำหรับปริศนา N-Queen หรือไม่ อย่างที่เราทราบดีว่ากระดานเป็นวิธีแก้ปัญหาของ N-queen ที่ถูกต้อง โดยที่ไม่มีราชินีสองตัวโจมตีกันและกัน

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• n :=จำนวนแถวของเมทริกซ์
• แถว :=ชุดใหม่ cols :=ชุดใหม่ diags :=ชุดใหม่ rev_diags :=ชุดใหม่
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • สำหรับ j ในช่วง 0 ถึง n ทำ
    • ถ้าเมทริกซ์[i, j] เป็น 1 แล้ว
      • แทรก i ลงในแถว
      • แทรก j ลงใน cols
      • แทรก (i - j) ลงในไดอะแกรม
      • แทรก (i + j) ลงใน rev_diags
• คืนค่า จริง เมื่อขนาดของแถว ขนาดของ cols ขนาดของ diags ขนาดของ rev_diags เท่ากับ n มิฉะนั้น เท็จ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

คลาสโซลูชัน:def แก้(ตัวเอง, เมทริกซ์):n =len(เมทริกซ์) แถว =set() cols =set() diags =set() rev_diags =set() สำหรับฉันในช่วง (n):สำหรับ j ในช่วง (n):ถ้า matrix[i][j]:rows.add(i) cols.add(j) diags.add(i - j) rev_diags.add(i + j) ส่งคืน len (แถว) ==len(cols) ==len(diags) ==len(rev_diags) ==nob =สารละลาย()เมทริกซ์ =[ [0, 0, 0, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [1, 0, 0, 0, 0]]พิมพ์(ob.solve(เมทริกซ์))

อินพุต

ผลลัพธ์

จริง