ราชินีดัดแปลง

Question

สำหรับการกำหนด N queens ที่แก้ไขแล้ว

ซึ่งแตกต่างจากปัญหาควีนส์เดิมมีเพียงหนึ่ง rule- ทั้งหมดราชินี N จะต้องวางอยู่แถวฉลาดแรก

เป้าหมายคือการเลือกจำนวนเต็มที่น้อยที่สุด $p$ ดังนั้น $p^2 \geq N$.

ฉันคิดว่านิพจน์บูลีนสำหรับx_i_jซึ่งแสดงถึง$i$แถวที่ - และ $j$คอลัมน์ที่ -:

x_1_1 & x_1_2 & ...x_1_p &
x_2_1 & x_2_2 & ...x_2_p &
... &
... &
x_p_1 & x_p_2 & ...x_p_p

นิพจน์แสดงอย่างถูกต้องหรือไม่? หรือจะมี "หรือ" แทน "&" เบาะแส / ความช่วยเหลือใด ๆ จะได้รับการชื่นชม

Answer 1

การแสดงออกของคุณดูเหมือนจะไม่ถูกต้องวิธีที่คุณเขียนมันจะประเมินว่าเป็นบูลีนจริงก็ต่อเมื่อมีราชินีอยู่ทุกตำแหน่งบน $p \times p$คณะกรรมการ. สิ่งที่คุณต้องการแทนคือการระบุตำแหน่งของราชินีองค์สุดท้ายเพื่อที่$N$ ราชินีถูกวางไว้บอกว่าจะอยู่ในตำแหน่ง $i,j$ (เราต้องมี $(i-1)p+j=N$). แล้วเราต้องการทั้งหมด$x_{a,b}$ ด้วย $a \leq i$ หรือ $a=i$ และ $b \leq j$เพื่อประเมินเป็นจริง ตำแหน่งที่เหลือจะไม่มีราชินีดังนั้น$x_{a,b}$ควรประเมินเป็นเท็จที่นั่น ถ้าคุณเขียนในเมทริกซ์เล็กน้อยคุณต้องการ

\ start {array} {c | cc} & 1 & 2 & \ dots & j & j + 1 & \ dots & p \\ \ hline 1 & true & true & \ dots & true & true & \ dots & true \\ 2 & true & true & \ dots & true & true & \ dots & true \\ \ vdots \\ i-1 & true & true & true & true & dots & true จุด & จริง & เท็จ & \ จุด & เท็จ \\ i + 1 & เท็จ & เท็จ & \ จุด & เท็จ & เท็จ & \ จุด & เท็จ \\ \ vdots \\ p & เท็จ & เท็จ & \ จุด & เท็จ & เท็จ & \ จุด & เท็จ \ end {array}

ตอนนี้เพียงแค่เชื่อมต่อสิ่งเหล่านี้ด้วยตรรกะและใช้การลบเชิงตรรกะที่ตัวแปรต้องประเมินเป็นเท็จและคุณควรได้รับสิ่งนี้:

$$ x_{1,1} \land x_{1,2} \land \dots \land x_{1,p}\\ \land x_{2,1} \land x_{2,2} \land \dots \land x_{2,p}\\ \vdots\\ \land x_{i,1} \land x_{i,2} \land \dots \land x_{i,j} \land \lnot x_{i,j+1} \land \dots \land \lnot x_{i,p}\\ \vdots\\ \land \lnot x_{p,1} \land \lnot x_{p,2} \land \dots \land \lnot x_{p,p}. $$