modifizierte Königinnen

Question

Zur Formulierung einer modifizierten N Königinnen.

Im Gegensatz zum ursprünglichen Queens-Problem gibt es nur eine Regel: Alle N Queens müssen zuerst zeilenweise platziert werden .

Ziel ist es, die kleinste Ganzzahl auszuwählen $p$ so dass $p^2 \geq N$.

Ich denke an diesen booleschen Ausdruck für x_i_j , der darstellt$i$-te Reihe und $j$-te Spalte:

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

Ist der Ausdruck richtig dargestellt? Oder es wird 'oder' anstelle von '&' geben. Jeder Hinweis / jede Hilfe wird geschätzt.

Answer 1

Ihr Ausdruck scheint nicht korrekt zu sein. Die Art und Weise, wie Sie ihn geschrieben haben, wird nur dann als boolesch wahr bewertet, wenn sich an jeder Position auf der Position eine Königin befindet $p \times p$Tafel. Was Sie stattdessen wollen, ist, einen Ort der letzten Königin zu identifizieren, damit$N$ Königinnen werden platziert, sagen, es wird auf Position sein $i,j$ (Wir müssen haben $(i-1)p+j=N$). Dann wollen wir alle$x_{a,b}$ mit $a \leq i$ oder $a=i$ und $b \leq j$zu wahr bewerten. Der Rest der Positionen wird also keine Königin haben$x_{a,b}$sollte dort als falsch auswerten. Wenn Sie es in eine kleine Matrix schreiben, möchten Sie

\ begin {array} {c | cc} & 1 & 2 & \ Punkte & j & j + 1 & \ Punkte & p \\ \ hline 1 & wahr & wahr & \ Punkte & wahr & wahr & \ Punkte & wahr \\ 2 & wahr & wahr & \ Punkte & wahr & wahr & \ Punkte & wahr & wahr & wahr & wahr & wahr & wahr & wahr & wahr & wahr & wahr & wahr & wahr Punkte & wahr & falsch & \ Punkte & falsch \\ i + 1 & falsch & falsch & \ Punkte & falsch & falsch & \ Punkte & falsch \\ \ v Punkte \\ p & falsch & falsch & \ Punkte & falsch & falsch & \ Punkte & falsch \ Ende {Array}

Verbinden Sie diese nun einfach mit der logischen und verwenden Sie die logische Negation, wenn die Variable als falsch ausgewertet werden muss, und Sie sollten ungefähr Folgendes erhalten:

$$ 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}. $$