N-queens problem: Difference between revisions
Content added Content deleted
(Added Quackery.) |
|||
Line 12,516: | Line 12,516: | ||
9 -> 352 |
9 -> 352 |
||
10 -> 724</pre> |
10 -> 724</pre> |
||
=={{header|Quackery}}== |
|||
<code>perms</code> is defined at [[Permutations#Quackery]]. The solution used determines the order of the n-Queen solutions found. The output illustrated here is from the <code>perms</code> solution titled "An Uncommon Ordering". |
|||
The method used here stems from the following observations. |
|||
* Queens can attach with rook (castle) moves or bishop moves. |
|||
* The solutions to the N-rooks problem correspond to the permutations of the numbers 0 to N-1 in a zero-indexed list. |
|||
* Two queens are attacking one another with bishop moves to the left (from the appropriate point of view) if the sum of the x-coordinate and the y-coordinate for each of the queens is the same. |
|||
* A bishop move to the right is the mirror image of a bishop move to the left. |
|||
<syntaxhighlight lang="Quackery"> [ false 0 rot |
|||
witheach |
|||
[ i + bit |
|||
2dup & iff |
|||
[ drop dip not |
|||
conclude ] |
|||
done |
|||
| ] |
|||
drop ] is l-bishop ( [ --> b ) |
|||
[ reverse l-bishop ] is r-bishop ( [ --> b ) |
|||
[ [] swap perms |
|||
witheach |
|||
[ dup l-bishop iff |
|||
drop done |
|||
dup r-bishop iff |
|||
drop done |
|||
nested join ] ] is queens ( n --> [ ) |
|||
8 queens |
|||
dup size echo say " solutions." |
|||
cr cr |
|||
witheach |
|||
[ echo |
|||
i^ 1+ 4 mod iff sp else cr ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>92 solutions. |
|||
[ 4 1 5 0 6 3 7 2 ] [ 5 2 4 6 0 3 1 7 ] [ 5 3 6 0 2 4 1 7 ] [ 2 5 1 6 4 0 7 3 ] |
|||
[ 5 2 0 6 4 7 1 3 ] [ 5 1 6 0 2 4 7 3 ] [ 5 3 6 0 7 1 4 2 ] [ 2 5 1 6 0 3 7 4 ] |
|||
[ 5 2 6 1 3 7 0 4 ] [ 5 2 6 3 0 7 1 4 ] [ 1 5 0 6 3 7 2 4 ] [ 5 1 6 0 3 7 4 2 ] |
|||
[ 5 2 6 1 7 4 0 3 ] [ 4 6 1 5 2 0 3 7 ] [ 4 6 1 5 2 0 7 3 ] [ 3 6 4 2 0 5 7 1 ] |
|||
[ 3 6 4 1 5 0 2 7 ] [ 6 4 2 0 5 7 1 3 ] [ 3 1 6 2 5 7 0 4 ] [ 3 1 6 2 5 7 4 0 ] |
|||
[ 0 6 3 5 7 1 4 2 ] [ 6 1 5 2 0 3 7 4 ] [ 1 6 2 5 7 4 0 3 ] [ 6 2 0 5 7 4 1 3 ] |
|||
[ 4 1 3 6 2 7 5 0 ] [ 2 4 6 0 3 1 7 5 ] [ 4 6 3 0 2 7 5 1 ] [ 4 6 1 3 7 0 2 5 ] |
|||
[ 1 4 6 3 0 7 5 2 ] [ 4 6 0 3 1 7 5 2 ] [ 4 2 0 6 1 7 5 3 ] [ 1 4 6 0 2 7 5 3 ] |
|||
[ 4 6 0 2 7 5 3 1 ] [ 3 1 6 4 0 7 5 2 ] [ 6 3 1 4 7 0 2 5 ] [ 2 0 6 4 7 1 3 5 ] |
|||
[ 1 6 4 7 0 3 5 2 ] [ 0 6 4 7 1 3 5 2 ] [ 3 6 2 7 1 4 0 5 ] [ 3 6 0 7 4 1 5 2 ] |
|||
[ 6 1 3 0 7 4 2 5 ] [ 2 6 1 7 4 0 3 5 ] [ 6 2 7 1 4 0 5 3 ] [ 6 3 1 7 5 0 2 4 ] |
|||
[ 2 6 1 7 5 3 0 4 ] [ 6 0 2 7 5 3 1 4 ] [ 4 1 3 5 7 2 0 6 ] [ 4 0 3 5 7 1 6 2 ] |
|||
[ 4 2 0 5 7 1 3 6 ] [ 3 5 0 4 1 7 2 6 ] [ 5 3 0 4 7 1 6 2 ] [ 5 2 4 7 0 3 1 6 ] |
|||
[ 2 5 1 4 7 0 6 3 ] [ 5 0 4 1 7 2 6 3 ] [ 2 5 3 1 7 4 6 0 ] [ 2 5 3 0 7 4 6 1 ] |
|||
[ 5 3 1 7 4 6 0 2 ] [ 5 2 0 7 4 1 3 6 ] [ 2 5 7 0 4 6 1 3 ] [ 1 3 5 7 2 0 6 4 ] |
|||
[ 3 5 7 2 0 6 4 1 ] [ 3 5 7 1 6 0 2 4 ] [ 2 5 7 1 3 0 6 4 ] [ 2 5 7 0 3 6 4 1 ] |
|||
[ 5 2 0 7 3 1 6 4 ] [ 1 5 7 2 0 3 6 4 ] [ 5 7 1 3 0 6 4 2 ] [ 0 5 7 2 6 3 1 4 ] |
|||
[ 3 1 4 7 5 0 2 6 ] [ 3 0 4 7 5 2 6 1 ] [ 4 7 3 0 2 5 1 6 ] [ 2 4 1 7 5 3 6 0 ] |
|||
[ 0 4 7 5 2 6 1 3 ] [ 4 0 7 5 2 6 1 3 ] [ 3 1 7 5 0 2 4 6 ] [ 7 2 0 5 1 4 6 3 ] |
|||
[ 1 7 5 0 2 4 6 3 ] [ 3 7 0 2 5 1 6 4 ] [ 7 3 0 2 5 1 6 4 ] [ 3 0 4 7 1 6 2 5 ] |
|||
[ 2 4 7 3 0 6 1 5 ] [ 4 2 7 3 6 0 5 1 ] [ 4 1 7 0 3 6 2 5 ] [ 4 0 7 3 1 6 2 5 ] |
|||
[ 4 7 3 0 6 1 5 2 ] [ 2 4 1 7 0 6 3 5 ] [ 3 7 4 2 0 6 1 5 ] [ 3 1 7 4 6 0 2 5 ] |
|||
[ 3 7 0 4 6 1 5 2 ] [ 7 1 4 2 0 6 3 5 ] [ 7 1 3 0 6 4 2 5 ] [ 2 7 3 6 0 5 1 4 ]</pre> |
|||
=={{header|QBasic}}== |
=={{header|QBasic}}== |