N-queens problem: Difference between revisions
Convert <lang> elements to <syntaxhighlight>
m (→{{header|Tailspin}}: typed array indexing) |
(Convert <lang> elements to <syntaxhighlight>) |
||
Line 26:
{{trans|Nim}}
<
F underAttack(col, queens)
Line 57:
print(‘ ’, end' ‘’)
print(Char(code' ‘a’.code + row)‘’col, end' ‘’)
print(end' I L.index % 4 == 3 {"\n"} E ‘ ’)</
{{out}}
Line 92:
Translated from the Fortran 77 solution.<br>
For maximum compatibility, this program uses only the basic instruction set (S/360).
<
MACRO
&LAB XDECO ®,&TARGET
Line 233:
U DC (4*LL-2)H'0' stack
REGS make sure to include copybook jcl
END NQUEENS</
{{out}}
<pre>
Line 253:
=={{header|ABAP}}==
<
TYPES: BEGIN OF gty_matrix,
1 TYPE c,
Line 539:
SKIP 1.
ENDFORM. " SHOW_MATRIX
</syntaxhighlight>
=={{header|Ada}}==
<
procedure Queens is
Line 591:
end loop;
Put_Line (" A B C D E F G H");
end Queens;</
{{out}}
<pre>
Line 610:
This one only counts solutions, though it's easy to do something else with each one (instead of the <code>M := M + 1;</code> line).
<
use Ada.Text_IO;
Line 658:
Put_Line (Long_Integer'Image (Queens (N)));
end loop;
end CountQueens;</
=={{header|ALGOL 68}}==
Line 668:
{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8.8d.fc9.i386]}}
<
dim = 8; # dim X dim chess board #
[ofs:dim+ofs-1]INT b;
Line 718:
FI
OD
)</
=={{header|APL}}==
{{works with|Dyalog APL}}
More or less copied from the "DFS" lesson on tryapl.org .
<
⍝Solution
accm←{⍺,((⍴⍵)=⍴⊃⍺)↑⊂⍵}
Line 735:
⍝Example
printqueens 6
</syntaxhighlight>
{{out}}
<pre>
Line 769:
=={{header|AppleScript}}==
<
property Grid_Size : 8
Line 932:
return newRows
end Reflect</
=={{header|Arc}}==
This program prints out all possible solutions:
<
(if (< len.queens n)
(let row (if queens (+ 1 queens.0.0) 0)
Line 955:
(def diagonal-match (curr other)
(is (abs (- curr.0 other.0))
(abs (- curr.1 other.1))))</
{{out}}
The output is one solution per line, each solution in the form `((row col) (row col) (row col) ...)`:
Line 964:
=={{header|Arturo}}==
<
queens: function [n, i, a, b, c][
Line 995:
]
print ""
]</
{{out}}
Line 1,029:
=={{header|AWK}}==
Inspired by Raymond Hettinger's Python solution, but builds the vector incrementally.
<
#!/usr/bin/gawk -f
# Solve the Eight Queens Puzzle
Line 1,103:
</syntaxhighlight>
{{out}}
<pre>
Line 1,118:
=={{header|ATS}}==
<
(* ****** ****** *)
//
Line 1,199:
(* end of [queens.dats] *)
</syntaxhighlight>
=={{header|AutoHotkey}}==
=== Output to formatted Message box ===
{{trans|C}}
<
; Post: http://www.autohotkey.com/forum/viewtopic.php?p=353059#353059
; Timestamp: 05/may/2010
Line 1,283:
Output .= "|`n" , yyy++
}
}</
=== Includes a solution browser GUI ===
This implementation supports N = 4..12 queens, and will find ALL solutions
Line 1,289:
The screenshot shows the first solution of 10 possible solutions for N = 5 queens.
<
Number: ; main entrance for different # of queens
SI := 1
Line 1,378:
GuiClose:
ExitApp</
[[image:N-Queens_SolutionBrowserGUI.png]]
Line 1,387:
[[Image:queens9_bbc.gif|right]]
[[Image:queens10_bbc.gif|right]]
<
Cell% = 32
VDU 23,22,Size%*Cell%;Size%*Cell%;Cell%,Cell%,16,128+8,5
Line 1,447:
ENDWHILE
UNTIL i% = 0
= m%</
=={{header|BCPL}}==
<
GET "libhdr.h"
Line 1,480:
RESULTIS 0
}
</syntaxhighlight>
The following is a re-implementation of the algorithm given above but
using the MC package that allows machine independent runtime generation
Line 1,486:
It runs about 25 times faster that the version given above.
<
GET "libhdr.h"
GET "mc.h"
Line 1,621:
i, n, all)
}
</syntaxhighlight>
=={{header|Befunge}}==
Line 1,627:
This algorithm works with any board size from 4 upwards.
<
"| Q"$$$>:01p:2%!00g0>>^<<!:-1\<1>00p::2%-:40p2/50p2*1+
!77**48*+31p\:1\g,::2\g:,\3\g,,^g>0g++40g%40g\-\40g\`*-
2g05\**!!%6g04-g052!:`\g05::-1/2<^4*2%g05\+*+1*!!%6g04-</
{{out}}
Line 1,655:
=={{header|Bracmat}}==
<
= board M L x y S R row line
. :?board
Line 1,715:
| out$(found !solutions solutions)
)
);</
{{out}} (tail):
<pre>
Line 1,760:
=={{header|C}}==
C99, compiled with <code>gcc -std=c99 -Wall</code>. Take one commandline argument: size of board, or default to 8. Shows the board layout for each solution.<
#include <stdlib.h>
Line 1,790:
int hist[n];
solve(n, 0, hist);
}</
Similiar to above, but using bits to save board configurations and quite a bit faster:<
#include <stdlib.h>
#include <stdint.h>
Line 1,829:
printf("\nSolutions: %d\n", count);
return 0;
}</
Take that and unwrap the recursion, plus some heavy optimizations, and we have a very fast and very unreadable solution:
<
#include <stdlib.h>
Line 1,921:
printf("\nSolutions: %d\n", count);
return 0;
}</
A slightly cleaned up version of the code above where some optimizations were redundant. This version is also further optimized, and runs about 15% faster than the one above on modern compilers:
<
#define MAXN 31
Line 1,994:
printf("Number of solution for %d is %d\n",n,nqueens(n));
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
Line 2,007:
{{works with|C sharp|C#|7}}
<!-- By Martin Freedman, 13/02/2018 -->
<
using static System.Linq.Enumerable;
using static System.Console;
Line 2,049:
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; }
}
}</
Output
<pre>8-queens has 92 solutions
Line 2,057:
===Hettinger Algorithm===
Compare this to the Hettinger solution used in the first Python answer. The logic is similar but the diagonal calculation is different and more expensive computationally (Both suffer from being unable to eliminate permutation prefixes that are invalid e.g. 0 1 ...)
<
using System.Collections.Generic;
using static System.Linq.Enumerable;
Line 2,095:
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; }
}
}</
=== Amb solution===
This uses the second version of the [https://rosettacode.org/wiki/Amb#C.23 Amb C# class] in the Amb challenge. Really that is not McCarthy's Amb (Ambiguous function) and here it is used just as a simple general interface by lambdas to a standalone backtrack algorithm. Due to the specification of the Amb challenge, this, ironically (given the notion of ambiguous functions), only produces one solution not 92. It is trivial to update Amb (might be better called a backtracker rather than Amb too) but here it is just used to show how easy it is to go from a generate and prune Linq solution to a backtrack solution. The Linq filters becoming "amb" requirements.
{{works with|C sharp|C#|7.1}}
<!-- By Martin Freedman, 9/02/2018 -->
<
using static System.Console;
Line 2,128:
}
}
}</
=={{header|C++}}==
<
// uses C++11 threads to parallelize the computation; also uses backtracking
// Outputs all solutions for any table size
Line 2,234:
return 0;
}
</syntaxhighlight>
{{out}}Output for N = 4:
<pre> a b c d
Line 2,248:
3 #
4 # </pre>
<
// A straight-forward brute-force C++ version with formatted output,
// eschewing obfuscation and C-isms, producing ALL solutions, which
Line 2,506:
std::cout << queens( N ) << "\n";
}
</syntaxhighlight>
{{out}} for N=4:
<pre>
Line 2,527:
=== Alternate version ===
Windows-only
<
#include <windows.h>
#include <iostream>
Line 2,628:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
{{out}}
<pre>
Line 2,657:
Version using Heuristics - explained here: [http://en.wikipedia.org/wiki/8_queens_puzzle#Solution_construction Solution_construction]
<
#include <windows.h>
#include <iostream>
Line 2,746:
}
//--------------------------------------------------------------------------------------------------
</syntaxhighlight>
=={{header|Clojure}}==
This produces all solutions by essentially a backtracking algorithm. The heart is the ''extends?'' function, which takes a partial solution for the first ''k<size'' columns and sees if the solution can be extended by adding a queen at row ''n'' of column ''k+1''. The ''extend'' function takes a list of all partial solutions for ''k'' columns and produces a list of all partial solutions for ''k+1'' columns. The final list ''solutions'' is calculated by starting with the list of 0-column solutions (obviously this is the list ''[ [] ]'', and iterates ''extend'' for ''size'' times.
<
(defn extends? [v n]
Line 2,772:
(println s))
(println (count solutions) "solutions")</
===Short Version===
<
(:require [clojure.math.combinatorics :as combo]
(defn queens [n]
(filter (fn [x] (every? #(apply distinct? (map-indexed % x)) [+ -]))
(combo/permutations (range 1 (inc n))))) </
===Backtracking as Tree processing===
Each state of the board can be represented as a sequence of the row coordinate for a queen, the column being the index in the sequence (coordinates starting at 0). Each state can have 'children' states if it is legal (no conflict) and has less than n queens. A child state is the result of adding a new queen on the next column, there are as many children states as rows as we are trying all of them. A depth first traversal of this virtual tree of states gives us the solutions when we filter out the illegal states and the incomplete states. The sequence of states is lazy so we could read only one result and not have to compute the other states.
<
(defn n-queens [n]
(let[children #(map (partial conj %) (range n))
Line 2,793:
no-conflict?)
children []))))
</
=={{header|CLU}}==
{{trans|C}}
<
rep = null
own hist: array[int] := array[int]$[]
Line 2,855:
stream$putl(po, "No. " || int$unparse(count) || "\n-------\n" || s)
end
end start_up</
{{out}}
<pre style='height:50ex'>No. 1
Line 3,870:
=={{header|CoffeeScript}}==
<
# Unlike traditional N-Queens solutions that use recursion, this
# program attempts to more closely model the "human" algorithm.
Line 3,982:
nqueens(8)
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(if (zerop n)
(list nil)
Line 4,003:
(defun print-queens (n)
(mapc #'print-solution (queens n)))</
=== Alternate solution ===
Translation of Fortran 77
<
(let ((a (make-array n))
(s (make-array n))
Line 4,046:
> (loop for n from 1 to 14 collect (cons n (queens1 n)))
((1 . 1) (2 . 0) (3 . 0) (4 . 2) (5 . 10) (6 . 4) (7 . 40) (8 . 92) (9 . 352)
(10 . 724) (11 . 2680) (12 . 14200) (13 . 73712) (14 . 365596))</
As in Fortran, the iterative function above is equivalent to the recursive function below:
<
(let ((a (make-array n))
(u (make-array (+ n n -1) :initial-element t))
Line 4,070:
(rotatef (aref a i) (aref a k))))))))
(sub 0))
m))</
=={{header|Curry}}==
Three different ways of attacking the same problem. All copied from [http://web.cecs.pdx.edu/~antoy/flp/patterns/ A Catalog of Design Patterns in FLP]
<
-- 8-queens implementation with the Constrained Constructor pattern
-- Sergio Antoy
Line 4,133:
main = extend []
</syntaxhighlight>
Another approach from the same source.
<
-- N-queens puzzle implemented with "Distinct Choices" pattern
-- Sergio Antoy
Line 4,172:
store = free
-- end
</syntaxhighlight>
Yet another approach, also from the same source.
<
-- 8-queens implementation with both the Constrained Constructor
-- and the Fused Generate and Test patterns.
Line 4,236:
main = extend []
</syntaxhighlight>
Mainly [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi?queens webpakcs], uses constraint-solver.
<
import Findall
Line 4,256:
-- oneSolution = unpack $ queens 8
-- allSolutions = findall $ queens 8</
=={{header|D}}==
===Short Version===
This high-level version uses the second solution of the Permutations task.
<
import std.stdio, std.algorithm, std.range, permutations2;
Line 4,269:
n.iota.map!(i => p[i] - i).array.sort().uniq.count == n)
.count.writeln;
}</
{{out}}
<pre>92</pre>
Line 4,276:
This version shows all the solutions.
{{trans|C}}
<
__gshared int[side] board;
Line 4,319:
y--;
}
}</
{{out}}
<pre>
Line 4,356:
===Fast Version===
{{trans|C}}
<
in {
assert(nn > 0 && nn <= 27,
Line 4,445:
immutable uint side = (args.length >= 2) ? args[1].to!uint : 8;
writefln("N-queens(%d) = %d solutions.", side, side.nQueens);
}</
{{out}}
<pre>N-queens(8) = 92 solutions.</pre>
Line 4,454:
=={{header|Dart}}==
<
Return true if queen placement q[n] does not conflict with
other queens q[0] through q[n-1]
Line 4,518:
void main() {
enumerate(4);
}</
{{out}}
<pre>* Q * *
Line 4,533:
{{libheader| System.SysUtils}}
{{Trans|Go}}
<
program N_queens_problem;
Line 4,597:
writeln(i, ' ', x[i]);
readln;
end.</
=={{header|Draco}}==
{{trans|C}}
<
word count;
Line 4,638:
count := 0;
solve(hist, 0)
corp</
{{out}}
<pre>No. 1
Line 4,712:
.
.
print n_sol & " solutions"</
{{out}}
<pre>Solution 1
Line 4,728:
=={{header|EchoLisp}}==
<
;; square num is i + j*N
(define-syntax-rule (sq i j) (+ i (* j N)))
Line 4,786:
(define (task up-to-n)
(for ((i up-to-n)) (writeln i ' ♕ (q-count i) 'solutions)))
</syntaxhighlight>
{{out}}
<pre>
Line 4,807:
=={{header|Eiffel}}==
<
class
QUEENS
Line 4,876:
end
end
</syntaxhighlight>
{{out}}
<pre>
Line 4,912:
=={{header|Elixir}}==
{{trans|Ruby}}
<
def queen(n, display \\ true) do
solve(n, [], [], [], display)
Line 4,949:
Enum.each(7..12, fn n ->
IO.puts " #{n} Queen : #{RC.queen(n, false)}" # no display
end)</
{{out}}
Line 5,086:
=={{header|Erlang}}==
Instead of spawning a new process to search for each possible solution I backtrack.
<
-module( n_queens ).
Line 5,170:
Board = solve( N ),
display( Board ).
</syntaxhighlight>
{{out}}
<pre>
Line 5,191:
===Alternative Version===
<
%%%For 8X8 chessboard with N queens.
-module(queens).
Line 5,206:
(Row /= Column + N) andalso (Row /= Column - N) andalso
safe(Row, Columns, (N+1)).
</syntaxhighlight>
=={{header|ERRE}}==
Line 5,294:
END IF
END PROGRAM
</syntaxhighlight>
Note: The program prints solutions one per line. This version works well for the PC and the C-64. For PC only you can omit the % integer-type specificator with a <code>!$INTEGER</code> pragma directive.
=={{header|F Sharp}}==
<
let rec iterate f value = seq {
yield value
Line 5,341:
printNumberOfSolutions()
</syntaxhighlight>
The output:
Line 5,367:
10 724
11 2680
</syntaxhighlight>
=={{header|Factor}}==
{{works with|Factor|0.98}}
<
IN: queens
Line 5,397:
[
[ 1 + "%d " printf ] each nl
] each ;</
=={{header|Forth}}==
<
variable nodes
Line 5,428:
solutions @ . ." solutions, " nodes @ . ." nodes" ;
8 queens \ 92 solutions, 1965 nodes</
=={{header|Fortran}}==
Line 5,434:
Using a back tracking method to find one solution
<
implicit none
Line 5,534:
write(*, "(a)") line
end subroutine
end program</
{{out}} for 8, 16 and 32 queens
<pre style="height:40ex;overflow:scroll">n = 8
Line 5,658:
===Alternate Fortran 77 solution===
<
C See the 2nd program for Scheme on the "Permutations" page for the
C main idea.
Line 5,730:
C 17 95815104
C 18 666090624
</syntaxhighlight>
<
!functions. The same algorithm is much easier to follow in Fortran 90, using the RECURSIVE keyword.
!Like previously, the program only counts solutions. It's pretty straightforward to adapt it to print
Line 5,784:
print *, n, m
end do
end program</
===Alternate Fortran 95 solution with OpenMP===
Line 5,797:
With some versions of GCC the function OMP_GET_WTIME is not known, which seems to be a bug. Then it's enough to comment out the two calls, and the program won't display timings.
<
use omp_lib
implicit none
Line 5,921:
go to 60
end function
end program</
===Fortran 2008 in a Lisp-like fashion===
Line 5,928:
Part of the intent here is to show that Fortran can do quite a few things people would not think it could, if it is given adequate library support.
<
use, intrinsic :: iso_fortran_env, only: output_unit
Line 6,207:
end subroutine check_garbage
end program example__n_queens</
{{out}}$ ./example__n_queens 1 2 3 4
<pre style="height:40ex;overflow:scroll">
Line 6,245:
=={{header|FreeBASIC}}==
Get slower for N > 14
<
' compile with: fbc -s console
Dim Shared As ULong count, c()
Line 6,300:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 1 3 5 2 4
Line 6,331:
=== Alternate version : recursive ===
<
u() As Integer, v() As Integer, ByRef m As LongInt)
Line 6,371:
aux(n, 1, a(), u(), v(), m)
Print m
End If</
=== Alternate version : iterative ===
<
Dim m As LongInt = 0
Line 6,417:
u(p) = 1 : v(q) = 1
Goto L3
End If</
=={{header|Frink}}==
This example uses Frink's built-in <CODE>array.permute[]</CODE> method to generate possible permutations of the board efficiently.
<
{
for q = 0 to length[board] - 1
Line 6,432:
for b = array[1 to 8].permute[]
if solution[b]
println[b]</
=={{header|Fōrmulæ}}==
Line 6,446:
Translation of Fortran 77. See also alternate Python implementation. One function to return the number of solutions, another to return the list of permutations.
<
local a, up, down, m, sub;
a := [1 .. n];
Line 6,523:
[ 0, 0, 0, 0, 0, 0, 1, 0 ],
[ 0, 1, 0, 0, 0, 0, 0, 0 ],
[ 0, 0, 0, 1, 0, 0, 0, 0 ] ]</
=={{header|Go}}==
===Niklaus Wirth algorithm (Wikipedia)===
<
// WP page. Well, it happened to be the example program the day I completed
// the task. It seems from the WP history that there has been some churn
Line 6,587:
}
}
}</
{{out}}
Line 6,602:
=== Refactored Niklaus Wirth algorithm (clearer/Go friendly solution) ===
<
* N-Queens Problem
*
Line 6,725:
trycol(0)
printresults()
}</
{{out}}
<pre>
Line 6,746:
[[N-queens_problem/dlx_go|dlx packge]].
<
import (
Line 6,881:
}
return nil
}</
{{out}}
<pre>
Line 6,915:
===Distinct Solutions===
This solver starts with the N! distinct solutions to the N-Rooks problem and then keeps only the candidates in which all Queens are mutually diagonal-safe.
<
def k = [a.size(), b.size()].min()
def i = (0..<k).find { a[it] != b[it] }
Line 6,938:
// each permutation is an N-Rooks solution
orderedPermutations((0..<n)).findAll (diagonalSafe)
}</
===Unique Solutions===
Unique solutions are equivalence classes of distinct solutions, factoring out all reflections and rotations of a given solution. See the [[WP:Eight_queens_puzzle|Wikipedia page]] for more details.
<
public static final diag = { list ->
final n = list.size()
Line 6,992:
}
qus
}</
===Test and Results===
This script tests both distinct and unique solution lists.
<
def qds = queensDistinctSolutions(n)
def qus = queensUniqueSolutions(qds)
Line 7,003:
else { println "first:${qus[0]}"; println "last:${qus[-1]}" }
println()
}</
Interpreting the Results:
Line 7,073:
=={{header|Haskell}}==
<
import Data.List
Line 7,102:
-- prints all the solutions for 6 queens
main = mapM_ printSolution $ queens 6</
If you just want one solution, simply take the <code>head</code> of the result of <code>queens n</code>; since Haskell is lazy, it will only do as much work as needed to find one solution and stop.
===Alternative version===
<
import Data.List ((\\))
Line 7,117:
where
f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs]
q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]</
===Using permutations===
This version uses permutations to generate unique horizontal and vertical position for each queen. Thus, we only need to check diagonals. However, it is less efficient than the previous version because it does not prune out prefixes that are found to be unsuitable.
<
-- checks if queens are on the same diagonal
Line 7,132:
-- 8 is for "8 queens"
main = print $ generate 8</
===In terms of foldr===
A back-tracking variant using the Prelude's plain '''foldr''':
{{Trans|JavaScript}}
<
--------------------- N QUEENS PROBLEM -------------------
Line 7,190:
main :: IO ()
main = (putStrLn . unlines) $ showSolutions 10 7</
{{Out}}
<pre>......♛ ......♛ ......♛ ......♛ .....♛. .....♛. .....♛. .....♛. .....♛. .....♛.
Line 7,225:
===Breadth-first search and Depth-first search===
<
import System.Environment
Line 7,287:
let n = read narg :: Int
print (bfs n [emptySt])
print (head $ dfs n emptySt)</
{{Out}}
Line 7,294:
=={{header|Heron}}==
<
inherits {
Heron.Windows.Console;
Line 7,388:
}
}
}</
=={{header|Icon}} and {{header|Unicon}}==
Here's a solution to the <tt>n = 8</tt> case:
<
write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8))
end
Line 7,407:
every 0 = row[r := 1 to 8] = ddiag[r + c - 1] = udiag[8 + r - c] do # test if free
suspend row[r] <- ddiag[r + c - 1] <- udiag[8 + r - c] <- r # place and yield
end</
Notes:
Line 7,418:
* As the calls to q() are evaluated in main, each one will suspend a possible row, thereby allowing the next q(n) in main to be evaluated. If any of the q() fails to yield a row for the nth queen (or runs out of solutions) the previous, suspended calls to q() are backtracked progressively. If the final q(8) yields a row, the write() will be called with the row positions of each queen. Note that even the final q(8) will be suspended along with the other 7 calls to q(). Unless the write() is driven to produce more solutions (see next point) the suspended procedures will be closed at the "end of statement" ie after the write has "succeeded".
* If you want to derive all possible solutions, main() can be embellished with the '''every''' keyword:
<
procedure main()
every write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8))
end
</syntaxhighlight>
This drives the backtracking to find more solutions.
Line 7,430:
The comment explains how to modify the program to produce <i>all</i>
solutions for a given <tt>N</tt>.
<
procedure main(args)
Line 7,464:
write()
return # Comment out to see all possible solutions
end</
A sample run for <tt>N = 6</tt>:
Line 7,488:
=={{header|IS-BASIC}}==
<
110 TEXT 80
120 DO
Line 7,525:
450 LET T(I)=1
460 NEXT
470 END DEF</
=={{header|J}}==
Line 7,531:
This is one of several J solutions shown and explained on this [[J:Essays/N%20Queens%20Problem|J wiki page]]
<
comb2 =: (, #: I.@,@(</)&i.)~ NB. all size 2 combinations of integers 0 to y
mask =: [ */@:~:&(|@-/) {
queenst=: comb2 (] #"1~ mask)&.|: perm</
Note that the Roger Hui's approach (used here) matches the description attributed to Raymond Hettinger (in the Python implementation). (Both were posted years ago: 1981 for Hui's version which was used here, and 2009 for Hettinger's.) However they do use different diagonal queen clash elimination approaches -see [http://rosettacode.org/wiki/N-queens_problem#Roger_Hui_.281981.29_Algorithm C# Roger Hui Algorithm] for a comparison of the two approaches.
Line 7,540:
Example use:
<
92 8</
92 distinct solutions for an 8 by 8 board.
<
0 4 7 5 2 6 1 3</
One of the solutions. Position indicates row number, the integer indicates column number (0..7) for each queen -- though of course you could just as validly think of that the other way around.
=={{header|Java}}==
<
private static int[] b = new int[8];
Line 7,598:
}
}
}</
=={{header|Javascript}}==
===ES5===
Algorithm uses recursive Backtracking. Checks for correct position on subfields, whichs saves a lot position checks. Needs 15.720 position checks for a 8x8 field.
<
if (rows <= 0) {
return [[]];
Line 7,635:
}
console.log(queenPuzzle(8,8));</
===ES6===
Translating the ES5 version, and adding a function to display columns of solutions.
<
"use strict";
Line 7,767:
// MAIN ---
return main();
})();</
{{Out}}
<pre>....... ....... ....... ....... ♛...... ♛...... ♛...... ♛...... ♛...... ♛......
Line 7,806:
This section presents a function for finding a single solution using
the formulae for explicit solutions at [[WP:Eight_queens_puzzle|Eight Queens Puzzle]].
<
def q: "♛";
def init(k): reduce range(0;k) as $i ([]; . + ["."]);
Line 7,830:
(""; reduce $row[] as $x (.; . + $x) + "\n");
single_solution_queens(8) | pp</
{{out}}
$ jq -M -n -r -f n-queens-single-solution.jq
<
.....♛..
.......♛
Line 7,840:
♛.......
..♛.....
....♛...</
====Generate-and-test counter====
{{ works with|jq|1.4}}
'''Part 1: Generic functions'''
<
def permutations(n):
# Given a single array, generate a stream by inserting n at different positions:
Line 7,856:
end;
def count(g): reduce g as $i (0; .+1);</
'''Part 2: n-queens'''
<
def sums:
. as $board
Line 7,874:
count( permutations(n) | select(allowable) );
</syntaxhighlight>
'''Example''':
<syntaxhighlight lang
{{out}}
92
Line 7,882:
=={{header|Julia}}==
<
# EightQueensPuzzle
Line 7,949:
println()
end
</
<pre>
n = 1
Line 8,022:
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<
var count = 0
Line 8,051:
println()
}
}</
{{out}}
Line 8,112:
=={{header|Liberty BASIC}}==
Program uses permutation generator (stores all permutations) and solves tasks 4x4 to 9x9. It prints all the solutions.
<syntaxhighlight lang=lb>
'N queens
'>10 would not work due to way permutations used
Line 8,198:
End Function
</syntaxhighlight>
=={{header|Locomotive Basic}}==
Line 8,204:
Uses the heuristic from the Wikipedia article to get one solution.
<
20 while n<4:input "How many queens (N>=4)";n:wend
30 dim q(n),e(n),o(n)
Line 8,255:
500 for i=1 to n
510 if o(i)=1 or o(i)=3 then o(i)=-1 else if o(i)=0 then o(i)=1:o(i+1)=3:return
520 next</
[[File:Queens Puzzle, Locomotive Basic.png]]
Line 8,261:
=={{header|Logo}}==
<
if :files = 0 [make "solutions :solutions+1 show :tried stop]
localmake "safe (bitand :files :diag1 :diag2)
Line 8,277:
end
print queens 8 ; 92</
=={{header|Lua}}==
<
-- We'll use nil to indicate no queen is present.
Line 8,314:
else
print(string.format("No solution for %d queens.\n", N))
end</
=={{header|M2000 Interpreter}}==
{{trans|VBA}}
<
Module N_queens {
Const l = 15 'number of queens
Line 8,377:
}
N_queens
</syntaxhighlight>
=={{header|m4}}==
Line 8,383:
It finds one solution of the Eight Queens problem.
<
The following macro find one solution to the eight-queens problem:
Line 8,476:
divert`'dnl
dnl
solve_eight_queens</
{{out}}
Line 8,501:
{{trans|Python}}
<
local a,u,v,m,aux;
a:=[$1..n];
Line 8,534:
end:
for a in queens(8) do printf("%a\n",a) od;</
{{out}}
Line 8,548:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
This code recurses through the possibilities, using the "safe" method to check if the current set is allowed. The recursive method has the advantage that finding all possibilities is about as hard (code-wise, not computation-wise) as finding just one.
<
With[{l = Length@q},
Length@Union@q == Length@Union[q + Range@l] ==
Line 8,556:
If[Length[q] == n, {q},
Cases[nQueen[Append[q, #], n] & /@ Range[n],
Except[{Null} | {}], {2}]], Null]</
This returns a list of valid permutations by giving the queen's column number for each row. It can be displayed in a list of chess-board tables like this:
<
Grid[Normal@
SparseArray[MapIndexed[{#, First@#2} -> "Q" &, #], {n, n}, "."],
Frame -> All] & /@ nQueen[n]
matrixView[6] // OutputForm</
{{out}}
<pre>{. . . Q . ., . . . . Q ., . Q . . . ., . . Q . . .}
Line 8,580:
This solution uses Permutations and subsets, also prints out a board representation.
<
Do[per[[q]]=Partition[Riffle[Reverse[Range[n]],per[[q]]],2],{q,1,Length[per]}];(* Riffled in the reverse of [range n] partitioned into pairs*)
Do[w=Subsets[per[[t]],{2}];(* This is a full subset of the previous set of pairs taken 2 at a time *)
Line 8,587:
If[tot==0,g=Grid[Table[" ",{n},{n}],Alignment->Center,Frame->All,Spacings->{1.2,1}];(* If no clashing diagonals setup an array and print the permutation and the grid*)
Do[g[[1,per[[t,w,1]],per[[t,w,2]]]]="Q",{w,1,n}];
Print[cnt," ",per[[t]]," ",g];cnt++],{t,1,Length[per]}]</
Alternative Solution using Linear Programming:
<
dispSol[sol_] := sol /. {1 -> "Q" , 0 -> "-"} // Grid
Line 8,636:
solveNqueens[8] // dispSol
</syntaxhighlight>
<pre>- - - - Q - - -
- Q - - - - - -
Line 8,648:
=={{header|MATLAB}}==
This solution is inspired by Raymond Hettinger's permutations based solution which was made in Python: https://code.activestate.com/recipes/576647/
<
solutions=[[]];
v = 1:n;
Line 8,672:
end
s
end</
{{out}}
<pre>
Line 8,688:
=={{header|Maxima}}==
<
queens(n) := block([a, i, j, m, p, q, r, s, u, v, w, y, z],
Line 8,705:
[1, 6, 8, 3, 7, 4, 2, 5],
...]] */
length(%); /* 92 */</
=={{header|MiniZinc}}==
<
array [1..n] of var 1..n: q; % queen in column i is in row q[i]
Line 8,721:
satisfy;
output [ if fix(q[j]) == i then "Q" else "." endif ++
if j == n then "\n" else "" endif | i,j in 1..n]</
This solution appears in the official MiniZinc tutorial documentation, and is generalized.
Line 8,727:
=={{header|Modula-2}}==
{{trans|C}}
<
FROM InOut IMPORT Write, WriteCard, WriteString, WriteLn;
Line 8,782:
count := 0;
Solve(N, 0);
END NQueens.</
{{out}}
Line 9,799:
=={{header|MUMPS}}==
<
Set sol=0
For row(1)=1:1:4 Do try(2) ; Not 8, the other 4 are symmetric...
Line 9,858:
Quit
Do Queens
</syntaxhighlight>
<div style="overflow:scroll; height:400px;">
<
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##|
Line 10,068:
1 |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+
A B C D E F G H</
=={{header|Nim}}==
<
proc underAttack(col: int; queens: seq[int]): bool =
Line 10,099:
if row > 0: stdout.write ' '
stdout.write chr(ord('a') + row), col
stdout.write if i mod 4 == 3: "\n" else: " "</
{{out}}
Line 10,131:
{{trans|Java}}
<
class NQueens {
b : static : Int[];
Line 10,188:
}
}
</syntaxhighlight>
=={{header|OCaml}}==
{{libheader|FaCiLe}}
<
Copyright 2004 CENA. All rights reserved.
This code is distributed under the terms of the GNU LGPL *)
Line 10,251:
then raise (Failure "Usage: queens <nb of queens>");
Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *)
queens (int_of_string Sys.argv.(1));;</
===A stand-alone OCaml solution===
<
let show board =
Line 10,284:
else 8 in
solutions n</
{{out}}
<pre>$ ocaml queens.ml 6
Line 10,318:
=={{header|Oz}}==
A pretty naive solution, using constraint programming:
<
fun {Queens N}
proc {$ Board}
Line 10,385:
in
{Length Solutions} = 92 %% assert
{Inspect {List.take Solutions 3}}</
There is a more concise and much more efficient [http://www.mozart-oz.org/documentation/fdt/node25.html#section.scripts.queens solution] in the Mozart documentation.
=={{header|Pascal}}==
<
const l=16;
Line 10,470:
14 365596
15 2279184
16 14772512 }</
===Alternative===
Line 10,488:
Solution found</pre>
<
{$IFDEF FPC}
{$MODE DELPHI}
Line 10,599:
end;
WriteLn('Fertig');
end.</
{{out}}
<pre>
Line 10,623:
=={{header|PDP-11 Assembly}}==
<
; "eight queens problem" benchmark test
Line 10,738:
scr: ;display RAM
</syntaxhighlight>
=={{header|Perl}}==
<
sub try_column {
Line 10,780:
#print for @solutions; # un-comment to see all solutions
print "total " . @solutions . " solutions\n";</
{{out}}
<pre>total 14200 solutions</pre>
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">--
Line 10,841:
<span style="color: #000000;">n_queens</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">,</span><span style="color: #000000;">N</span><span style="color: #0000FF;"><</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 10,874:
=={{header|PHP}}==
<
<html>
<head>
Line 11,052:
</body>
</html>
</syntaxhighlight>
<h2>Solution with recursion</h2>
<
<html>
<body>
Line 11,130:
</body>
</html>
</syntaxhighlight>
=={{header|Picat}}==
===0/1 encoding a N x N matrix===
Using constraint modelling using an 0/1 encoding of an N x N matrix. It is the probably the fastest approach when using SAT and MIP solvers.
<
% import mip.
Line 11,157:
sum([Q[I,J] : I in 1..N]) #= 1
end,
solve([inout],Q).</
===Constraint programming===
This is the "standard" model using constraint programming (in contract to the SAT 0/1 approach). Instead of an NxN matrix, this encoding uses a single list representing the columns. The three <code>all_different/1</code> then ensures that the rows, and the two diagonals are distinct.
<
queens(N, Q) =>
Line 11,169:
all_different([$Q[I]-I : I in 1..N]),
all_different([$Q[I]+I : I in 1..N]),
solve([ff],Q).</
==="Naive" approach===
This approach might be called "naive" (in the constraint programming context) since it doesn't use the (general) faster <code>all_different/1</code> constraint.
<
Q = new_list(N),
Q :: 1..N,
Line 11,181:
Q[I] - I #!= Q[J] - J
end,
solve([ff], Q).</
Line 11,222:
=={{header|PicoLisp}}==
===Calling 'permute'===
<
(de queens (N)
Line 11,232:
(length (uniq (mapcar - L R))) )
(inc 'Cnt) ) )
Cnt ) )</
===Permuting inline===
This alternative version does not first pre-generate all permutations with
'permute', but creates them recursively. Also, it directly checks for
duplicates, instead of calling 'uniq' and 'length'. This is much faster.
<
(let (R (range 1 N) L (copy R) X L Cnt 0)
(recur (X) # Permute
Line 11,252:
(mapcar - L R) )
(inc 'Cnt) ) ) )
Cnt ) )</
{{out}} for both cases:
<pre>: (queens 8)
Line 11,259:
=={{header|PL/I}}==
This code compiles with PL/I compilers ranging from the ancient IBM MVT PL/I F compiler of the 1960s, the IBM PL/I Optimizing compiler, thru the IBM PL/I compiler for MVS and VM, to the z/OS Enterprise PL/I v4.60 compiler;spanning 50 years of PL/I compilers. It only outputs the number of solutions found for a given N instead of printing out each individual chess board solution to avoid filling up spool space for large values of N. It's trivial to add a print-out of the individual solutions.
<
NQUEENS: PROC OPTIONS (MAIN);
DCL A(35) BIN FIXED(31) EXTERNAL;
Line 11,337:
END QUEEN;
END NQUEENS; </
=={{header|PowerBASIC}}==
=== Recursive version ===
{{trans|Stata}}
<
#DIM ALL
Line 11,387:
PRINT m
END IF
END FUNCTION</
=== Iterative version ===
{{trans|Stata}}
<
#DIM ALL
Line 11,437:
GOTO 3
END IF
END FUNCTION</
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<
function PlaceQueen ( [ref]$Board, $Row, $N )
{
Line 11,501:
}
}
</syntaxhighlight>
<
Get-NQueensBoard 8
''
Line 11,510:
''
Get-NQueensBoard 14
</syntaxhighlight>
{{out}}
<pre>
Line 11,547:
=={{header|Processing}}==
{{trans|Java}}
<
int n = 8;
int[] b = new int[n];
Line 11,618:
b[0] = -1;
}
</syntaxhighlight>
==={{header|Processing Python mode}}===
Line 11,625:
This solution, originally by Raymond Hettinger for demonstrating the power of the itertools module, generates all solutions.
<
n = 8
Line 11,653:
global i
i = (i + 1) % len(solutions)
</syntaxhighlight>
=={{header|Prolog}}==
Line 11,659:
Solution #1:
<
solution([X/Y|Others]) :-
Line 11,679:
member(Item,Rest).
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).</
Solution #2:
<
permutation([1,2,3,4,5,6,7,8], Queens),
safe(Queens).
Line 11,709:
Y-Y1=\=Xdist,
Dist1 is Xdist + 1,
noattack(Y,Ylist,Dist1).</
Solution #3:
<
sol(Ylist,[1,2,3,4,5,6,7,8],
[1,2,3,4,5,6,7,8],
Line 11,731:
del(Item,[First|List],[First|List1]) :-
del(Item,List,List1).</
[http://ideone.com/Y6olN Output]:
Line 11,739:
===Alternative version===
Uses non-ISO predicates between/3 and select/3 (available in SWI Prolog and GNU Prolog).
<
Line 11,754:
main :- findall(Qs, (queens(8,Qs), write(Qs), nl), _), halt.</
[http://ideone.com/3bbIx0 Runs in: time: 0.02 memory: 68352]
Line 11,760:
Uses backtracking- a highly efficient mechanism in Prolog to find all solutions.
{{works with|SWI Prolog|version 6.2.6 by Jan Wielemaker, University of Amsterdam}}
<
% q(Row) represents a queen, allocated one per row. No rows ever clash.
% The columns are chosen iteratively from available columns held in a
Line 11,782:
length(Boards, Len), writef('%w solutions:\n', [Len]), % Output solutions
member(R,Boards), reverse(R,Board), writef(' - %w\n', [Board]), fail.
queens.</
{{out}}
<pre>?- queens.
Line 11,799:
===Short version===
SWI-Prolog 7.2.3
<
maplist(plus, X, N, Z1), maplist(plus, X, Z2, N), is_set(Z1), is_set(Z2).
queens(N, Qs) :-
numlist(1, N, P), findall(Q, (permutation(P, Q), not_diagonal(Q, P)), Qs).</
{{out}}
<pre>
Line 11,812:
===SWISH Prolog version===
<
% John Devou: 26-Nov-2021
% Short solution to use on https://swish.swi-prolog.org/.
Line 11,823:
not((member((U,V),Qs), (V =:= C; R-U =:= abs(C-V)))).
q(N,X):- q(N,N,_,X).
</syntaxhighlight>
===CLP(FD): Constraint Logic Programming over Finite Domains Version===
Line 11,846:
</ul>
<br/>
<
% DOC: http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html
Line 11,918:
main :-
print_nqueens_all(8).
</syntaxhighlight>
{{out}}
<pre>
Line 11,946:
From the Pure (programming language) Wikipedia page
<
n-queens.pure
Tectonics:
Line 11,964:
compiling || (puts("queens 4: " + str(queens 4)) $$
puts("Solutions to queens 7: " + str(#queens 7)));</
{{out}}
Line 11,982:
=={{header|PureBasic}}==
A recursive approach is taken. A queen is placed in an unused column for each new row. An array keeps track if a queen has already been placed in a given column so that no duplicate columns result. That handles the Rook attacks. Bishop attacks are handled by checking the diagonal alignments of each new placement against the previously placed queens and if an attack is possible the solution backtracks. The solutions are kept track of in a global variable and the routine <tt>queens(n)</tt> is called with the required number of queens specified.
<
Procedure showBoard(Array queenCol(1))
Line 12,061:
Input()
CloseConsole()
EndIf</
Sample output showing the last solution (all are actually displayed) for 1 - 12 queens:
<pre style="height:40ex;overflow:scroll"> Solution 1
Line 12,184:
This solution, originally by [http://code.activestate.com/recipes/576647/ Raymond Hettinger] for demonstrating the power of the itertools module, generates all solutions. On a regular 8x8 board only 40,320 possible queen positions are examined.
<
n = 8
Line 12,191:
if n == len(set(vec[i]+i for i in cols)) \
== len(set(vec[i]-i for i in cols)):
print ( vec )</
The output is presented in vector form (each number represents the column position of a queen on consecutive rows).
The vector can be pretty printed by substituting a call to <code>board</code> instead of <code>print</code>, with the same argument, and where board is pre-defined as:
<
print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec) + "\n===\n")</
Raymond's description is:
Line 12,211:
On a regular 8x8 board only 15,720 possible queen positions are examined.
{{works with|Python|2.6, 3.x}}
<
BOARD_SIZE = 8
Line 12,227:
return solutions
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</
===Python: Simple Backtracking Solution===
Line 12,233:
to a generator expression) produces a backtracking solution. On a regular 8x8 board only 15,720 possible queen positions are examined.
{{works with|Python|2.6, 3.x}}
<
def under_attack(col, queens):
Line 12,251:
answers = solve(BOARD_SIZE)
first_answer = next(answers)
print(list(enumerate(first_answer, start=1)))</
===Python: Simple Backtracking Solution (Niklaus Wirth Algorithm)===
The following program is a translation of Niklaus Wirth's solution into the Python programming language, but does without the index arithmetic used in the original and uses simple lists instead, which means that the array ''x'' for recording the solution can be omitted. A generator replaces the procedure (see [https://www.inf.ethz.ch/personal/wirth/AD.pdf Algorithms and Data Structures], pages 114 to 118). On a regular 8x8 board only 15,720 possible queen positions are examined.
<
if i < n:
for j in range(n):
Line 12,264:
for solution in queens(8, 0, [], [], []):
print(solution)</
The algorithm can be slightly improved by using sets instead of lists (cf. backtracking on permutations). But this makes the algorithm a bit harder to read, since the list x has to be added to record the solution. On a regular 8x8 board only 5,508 possible queen positions are examined. However, since these two solutions are intended for educational purposes, they are neither resource-friendly nor optimized for speed. The next program (backtracking on permutations) shows a much faster solution that also uses less space on the stack.
<
if a: # a is not empty
for j in a:
Line 12,275:
for solution in queens([], 0, set(range(8)), set(), set()):
print(solution)</
===Python: backtracking on permutations===
Line 12,284:
The solutions are returned as a generator, using the "yield from" functionality of Python 3.3, described in [https://www.python.org/dev/peps/pep-0380/ PEP-380].
<
a = list(range(n))
up = [True]*(2*n - 1)
Line 12,306:
#Count solutions for n=8:
sum(1 for p in queens(8))
92</
The preceding function does not enumerate solutions in lexicographic order, see [[Permutations#Recursive implementation]] for an explanation. The following does, but is almost 50% slower, because the exchange is always made (otherwise the loop to shift the array a by one place would not work). On a regular 8x8 board only 5,508 possible queen positions are examined.
Line 12,312:
However, it may be interesting to look at the first solution in lexicographic order: for growing n, and apart from a +1 offset, it gets closer and closer to the sequence [http://oeis.org/A065188 A065188] at OEIS. The first n for which the first solutions differ is n=26.
<
a = list(range(n))
up = [True]*(2*n - 1)
Line 12,342:
#Compare to A065188
#1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, ...</
===Python: fold/reduce===
Expressed in terms of nested folds, allowing for graphic display of results, and listing the number of solutions found for boards of various sizes. On a regular 8x8 board only 15,720 possible queen positions are examined.
{{Works with|Python|3.7}}
<
from functools import reduce
Line 12,492:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>10 solutions for a 5 * 5 board:
Line 12,518:
{{works with|QBasic}}
{{trans|QB64}}
<
CLS
COLOR 15
Line 12,562:
continue1:
NEXT icol
END SUB</
=={{header|QB64}}==
<
DIM SHARED QUEENS AS INTEGER
PRINT "# of queens:";: INPUT QUEENS
Line 12,606:
NEXT icol
END SUB
</syntaxhighlight>
=={{header|R}}==
Line 12,614:
This solution uses recursive backtracking.
<
a <- seq(n)
u <- rep(T, 2 * n - 1)
Line 12,641:
aux(1)
m
}</
Show the first solution found for size 8 as a permutation matrix.
<
a <- queens(8)
as(a[, 1], "pMatrix")</
{{out}}
Line 12,664:
Count solutions for board size 4 to 12.
<
{{out}}
Line 12,674:
Backtracking algorithm; returns one solution
<
#lang racket
Line 12,705:
(nqueens 8)
; => (list (Q 3 7) (Q 1 6) (Q 6 5) (Q 2 4) (Q 5 3) (Q 7 2) (Q 4 1) (Q 0 0))
</syntaxhighlight>
Show result with "How to Design Programs" GUI.
<
(require htdp/show-queen)
Line 12,719:
(show-nqueens 8)
</syntaxhighlight>
[[image:Racket-nqueens.png]]
Line 12,731:
Computes all solutions.
<
#lang racket
Line 12,777:
'() qss-so-far)))
(lazy-filter valid? all-possible-solutions))
</syntaxhighlight>
Taking the first solution does not compute the other solutions:
<
(car (nqueens 8))
;; => (list (Q 7 3) (Q 6 1) (Q 5 6) (Q 4 2) (Q 3 5) (Q 2 7) (Q 1 4) (Q 0 0))
</syntaxhighlight>
Computing all solutions is also possible:
<
(define (force-and-print qs)
(define forced (force qs))
Line 12,806:
;(list (Q 7 3) (Q 6 6) (Q 5 4) (Q 4 1) (Q 3 5) (Q 2 0) (Q 1 2) (Q 0 7))
;(list (Q 7 4) (Q 6 6) (Q 5 1) (Q 4 5) (Q 3 2) (Q 2 0) (Q 1 3) (Q 0 7))
</syntaxhighlight>
Logic borrowed from the Ruby example
<
#lang racket
(define (remove x lst)
Line 12,866:
(define (print-queens n)
(for ([x (queens n)]) (displayln (string-join x))))
</syntaxhighlight>
=={{header|Raku}}==
Line 12,873:
Neither pretty nor efficient, a simple backtracking solution
<
sub collision(@field, $row) {
for ^$row -> $i {
Line 12,896:
}
}
}</
{{out}}
<pre>[0 4 7 5 2 6 1 3]</pre>
Line 12,902:
=={{header|Rascal}}==
<
public set[list[int]] Nqueens(int n){
Line 12,911:
result += vector;}
return result;
}</
=={{header|REXX}}==
Line 12,920:
About half of the REXX code involves presentation (and colorization achieved through dithering) of the chessboard and queens.
<
parse arg N . /*obtain optional argument from the CL.*/
if N=='' | N=="," then N= 8 /*Not specified: Then use the default.*/
Line 12,969:
say pad _ || bar /*show a single rank of the board.*/
end /*rank*/ /*80 cols can view a 19x19 board.*/
say pad translate('╚'g"╝", '╩', "╬"); return /*display the last rank (of board)*/</
{{out|output|text= when using the default of an '''8'''<small>x</small>'''8''' chessboard:}}
<pre>
Line 13,040:
=={{header|Ring}}==
<
// Bert Mariani 2020-07-17
Line 13,089:
//================================
</syntaxhighlight>
Output:
<pre>
Line 13,112:
=={{header|Ring}}==
<
load "stdlib.ring"
load "guilib.ring"
Line 13,801:
###============================================================
</syntaxhighlight>
[https://www.mediafire.com/file/53bxu7kpuc4tlx5/Images.zip/file Necessary images]
=={{header|Ruby}}==
This implements the heuristics found on the wikipedia page to return just one solution
<
# puzzle).
# 2. Write a list of the even numbers from 2 to n in order.
Line 13,862:
end
(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}</
{{out}}
Line 14,016:
===Alternate solution===
If there is not specification, it outputs all solutions.
<
attr_reader :count
Line 14,054:
puts @frame
end
end</
'''Example:'''
<
puzzle = Queen.new(n)
puts " #{n} Queen : #{puzzle.count}"
Line 14,065:
puzzle = Queen.new(n, false) # do not display
puts " #{n} Queen : #{puzzle.count}"
end</
{{out}}
Line 14,201:
=={{header|Run BASIC}}==
<
input "How many queens (N>=4)";n
if n < 4 then
Line 14,312:
end if
end if
next</
<pre>abcdefgh
* 8
Line 14,324:
=={{header|Rust}}==
<
fn try(mut board: &mut [[bool; N]; N], row: usize, mut count: &mut i64) {
Line 14,356:
try (&mut board, 0, &mut count);
println!("Found {} solutions", count)
}</
===Using Iterators===
Solution to the puzzle using an iterator that yields the 92 solutions for 8 queens.
<
use std::iter::IntoIterator;
Line 14,436:
str
}
}</
=={{header|SAS}}==
<
data queens;
array a{8} p1-p8;
Line 14,496:
put n m;
keep p1-p8;
run;</
=={{header|Scala}}==
Line 14,504:
Lazily generates permutations with an <code>Iterator</code>.
<
object NQueens {
Line 14,554:
}
}
</syntaxhighlight>
<pre>
Line 14,585:
This is a simple breadth-first technique to retrieve all solutions.
<
(import (scheme base)
(scheme write)
Line 14,660:
(pretty-print (n-queens 5) 5)
(pretty-print (n-queens 8) 8)
</syntaxhighlight>
{{out}}
Line 14,875:
string(Board_size)+"x"+string(Board_size)+" board.");
//Time elapsed
disp("Time: "+string(toc())+"s.");</
{{out}}
Line 14,884:
=={{header|Seed7}}==
<
var array integer: board is 8 times 0;
Line 14,934:
end if;
end while;
end func;</
=={{header|Sidef}}==
{{trans|Raku}}
<
func collision(field, row) {
Line 14,968:
for n in (1..15) {
say "#{'%2d' % n}: #{N_queens_solution(n) || 'No solution'}"
}</
{{out}}
<pre>
Line 14,989:
=={{header|SNOBOL4}}==
<
* N queens problem
* Set N to the desired number. The program prints out all solution boards.
Line 15,013:
PRTLOOP B LEN(NP1) . OUTPUT = :S(PRTLOOP)F(RETURN)
END
</syntaxhighlight>
=={{header|Sparkling}}==
This is somewhat a transliteration of the "shortened" C++ code above.
<
pos.foreach(function (_, i) {
stdout.printf(" %c", 'a' + i);
Line 15,071:
};
stdout.printf("%d solutions\n", n_queens(range(8), 0));</
=={{header|SQL}}==
Line 15,077:
This implementation, which solves the problem for n=8, makes use of Common Table Expressions and has been tested with SQLite (>=3.8.3) and Postgres (please note the related comment in the code). It might be compatible with other SQL dialects as well. A gist with the SQL file and a Python script that runs it using SQLite is available on Github: https://gist.github.com/adewes/5e5397b693eb50e67f07
<
WITH RECURSIVE
positions(i) as (
Line 15,108:
SELECT board,n_queens FROM solutions WHERE n_queens = 8;
</syntaxhighlight>
=={{header|SQL PL}}==
{{works with|Db2 LUW}} version 9.7 or higher.
With SQL PL:
<
-- A column of a matrix.
CREATE TYPE INTEGER_ARRAY AS INTEGER ARRAY[]@
Line 15,392:
</syntaxhighlight>
Output:
<pre>
Line 15,431:
=={{header|Standard ML}}==
This implementation uses failure continuations for backtracking.
<
(*
* val threat : (int * int) -> (int * int) -> bool
Line 15,471:
(* NONE *)
queens(2);
</syntaxhighlight>
=={{header|Stata}}==
Line 15,477:
Adapted from the Fortran 77 program, to illustrate the '''[http://www.stata.com/help.cgi?m2_goto goto]''' statement in Stata.
<
real matrix queens(real scalar n) {
real scalar i, j, k, p, q
Line 15,534:
rows(a)
92
end</
It's also possible to save the solutions to a Stata dataset:
<
mata: a=queens(8)
getmata (a*)=a
save queens, replace</
=== Recursive version ===
Line 15,547:
The recursive solution is adapted from one of the Python programs.
<
real matrix queens_rec(real scalar n) {
real rowvector a, u, v
Line 15,583:
}
}
end</
The iterative and the recursive programs are equivalent:
<
1</
=={{header|Swift}}==
Port of the optimized C code above
<
let maxn = 31
Line 15,650:
}
</syntaxhighlight>
=={{header|SystemVerilog}}==
Create a random board configuration, with the 8-queens as a constraint
<
parameter SIZE_LOG2 = 3;
Line 15,691:
endprogram
</syntaxhighlight>
=={{header|Tailspin}}==
A functional-ish solution utilising tailspin's data flows
<
templates queens
def n: $;
Line 15,727:
'For 3 queens there are $:[3 -> queens] -> $::length; solutions
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 15,736:
A solution using state to find one solution if any exist
<
templates queens
def n: $;
Line 15,785:
'A solution to the 3 queens problem is $:3 -> queens;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 15,797:
{{works with|Tcl|8.5}}
<
proc unsafe {y} {
Line 15,843:
}
main [expr {$argc ? int(0+[lindex $argv 0]) : 8}]</
{{out}}
<pre>$ tclsh8.5 8queens.tcl 6
Line 15,886:
The total number of solutions for 8 queens is displayed at the end of the run. The code could be adapted to display a selected solution or multiple solutions. This code runs anywhere you can get bash to run.
<
# variable declaration
Line 15,963:
work
out
depose</
=={{header|Ursala}}==
Line 15,969:
n is a number greater than 3. Multiple solutions may be reported
but reflections and rotations thereof are omitted.
<
#import nat
Line 15,986:
-<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS,
^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-,
^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-</
The output shows one solution on each line.
A solution is reported as a sequence of <math>n</math> numbers
Line 16,004:
=={{header|VBA}}==
{{trans|BBC BASIC}}
<
Sub n_queens()
Const l = 15 'number of queens
Line 16,061:
Debug.Print n, m 'number of queens, number of solutions
Next n
End Sub 'n_queens</
{{out}}
<pre>
Line 16,084:
{{trans|BBC BASIC}}
To have the solutions printed (raw format) uncomment the ad hoc statement.
<
const l=15
dim a(),s(),u(): redim a(l),s(l),u(4*l-2)
Line 16,129:
Loop Until i=0
wscript.echo n &":"& m
next 'n</
{{out}}
<pre>
Line 16,152:
{{works with|Visual Basic|VB6 Standard}}
{{trans|BBC BASIC}}
<
Sub n_queens()
Const l = 15 'number of queens
Line 16,209:
Debug.Print n, m 'number of queens, number of solutions
Next n
End Sub 'n_queens</
{{out}}
<pre>
Line 16,231:
=={{header|Visual Basic .NET}}==
{{trans|BBC BASIC}}
<
Module Mod_n_queens
Sub n_queens()
Line 16,291:
Next n
End Sub 'n_queens
End Module</
{{out}}
<pre>
Line 16,312:
=={{header|Wart}}==
<
prn "step: " queens # show progress
if (len.queens = n)
Line 16,335:
def (diagonal_match curr other)
(= (abs (curr.0 - other.0))
(abs (curr.1 - other.1)))</
=={{header|Wren}}==
{{trans|Kotlin}}
Very slow for the larger boards.
<
var c = []
var f = []
Line 16,377:
if (count > 0) System.print(" First is %(f)")
System.print()
}</
{{out}}
Line 16,439:
Copied from http://www.cs.bu.edu/~hwxi/Xanadu/Examples/
<
int abs(i: int) {
if (i >= 0) return i; else return -i;
Line 16,508:
int main () {
return queen (8);
}</
=={{header|XPL0}}==
[[File:NQueensXPL0.GIF|right]]
<
int R, C; \row and column of board
char B(N,N); \board
Line 16,568:
C:= 0; \start at left column
Try;
]</
=={{header|XSLT}}==
Line 16,580:
83162574
84136275
</syntaxhighlight>
You can view the results directly in your browser (Chrome/FF/IE/Opera/Safari) here: [[http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens.xsl.xml]]
Line 16,599:
Here is stylesheet 8-queens.xsl.xml which produces the (simple) output by having itself as input: [[http://stamm-wilbrandt.de/en/xsl-list/n-queens/8-queens.xsl.xml]]
<
<!-- 8-queens.xsl disguised as XML file for the browsers -->
Line 16,726:
</xsl:stylesheet>
</syntaxhighlight>
=={{header|Yabasic}}==
<
DOCU Place N Queens on an NxN chess board
DOCU such that they don't threaten each other.
Line 16,793:
wend
end sub
</syntaxhighlight>
=={{header|Zig}}==
Outputs all 92 solutions.
<
const std = @import("std");
const stdout = std.io.getStdOut().outStream();
Line 16,838:
}
}
</syntaxhighlight>
{{Out}}
<pre>
Line 16,851:
=={{header|zkl}}==
Modified from a Haskell version (if I remember correctly)
<
{ r,c:=q; (r==x or c==y or r+c==x+y or r-c==x-y) }
fcn isSafe(r,c,qs) // queen safe at (r,c)?, qs=( (r,c),(r,c)..) solution so far
Line 16,860:
if (row == N) return(qs);
return(qs.apply(self.fcn.fp(N,row+1)).flatten());
}</
<
println(queens.len()," solution(s):");
queens.apply2(Console.println);</
{{out}}
<pre>
|