N-queens problem: Difference between revisions
This is a solution adapted from Forth Dimensions Volume II Number 1, article titled "Recursion - The Eight Queens Problem by Jerry LeVan. It uses the same technique of Wirth with the left diagonal adjusted since there are no negative indexses
mNo edit summary |
(This is a solution adapted from Forth Dimensions Volume II Number 1, article titled "Recursion - The Eight Queens Problem by Jerry LeVan. It uses the same technique of Wirth with the left diagonal adjusted since there are no negative indexses) |
||
Line 5,521:
8 queens \ 92 solutions, 1965 nodes</syntaxhighlight>
=== Alternate solution adapted from FD-V02N1.pdf ===
<syntaxhighlight lang="forth">
\ http://www.forth.org/fd/FD-V02N1.pdf
VOCABULARY nqueens ALSO nqueens DEFINITIONS
8 constant queens
\ Nqueen solution from FD-V02N1.pdf
: 1array CREATE 0 DO 1 , LOOP DOES> SWAP CELLS + ;
queens 1array a \ a,b & c: workspaces for solutions
queens 2* 1array b
queens 2* 1array c
queens 1array x \ trial solutions
: safe ( c i -- n )
SWAP
2DUP - queens 1- + c @ >R
2DUP + b @ >R
DROP a @ R> R> * * ;
: mark ( c i -- )
SWAP
2DUP - queens 1- + c 0 swap !
2DUP + b 0 swap !
DROP a 0 swap ! ;
: unmark ( c i -- )
SWAP
2DUP - queens 1- + c 1 swap !
2DUP + b 1 swap !
DROP a 1 swap ! ;
VARIABLE tries
VARIABLE sols
: .cols queens 0 DO I x @ 1+ 5 .r loop ;
: .sol ." Found on try " tries @ 6 .R .cols cr ;
: try
queens 0
DO 1 tries +!
DUP I safe
IF DUP I mark
DUP I SWAP x !
DUP queens 1- < IF DUP 1+ RECURSE ELSE sols ++ .sol THEN
DUP I unmark
THEN
LOOP DROP ;
: go 0 tries ! CR 0 try CR sols @ . ." solutions Found, for n = " queens . ;
go
</syntaxhighlight>
=={{header|Fortran}}==
| |||