N-queens problem: Difference between revisions
Content added Content deleted
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: | Line 5,521: | ||
8 queens \ 92 solutions, 1965 nodes</syntaxhighlight> |
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}}== |
=={{header|Fortran}}== |