N-queens problem: Difference between revisions

[[File:chess_queen.jpg|400px||right]]

 

You can extend the problem to solve the puzzle with a board of size &nbsp; <big>'''N'''x'''N'''</big>.

 

 

* [[Solve the no connection puzzle]]

<br><br>

 

=={{header|360 Assembly}}==

Translated from the Fortran 77 solution.<br>

For maximum compatibility, this program uses only the basic instruction set (S/360).

MACRO

&LAB XDECO &REG,&TARGET

U DC (4*LL-2)H'0' stack

REGS make sure to include copybook jcl

{{out}}

<pre>

</pre>

 

=={{header|ABAP}}==

TYPES: BEGIN OF gty_matrix,

1 TYPE c,

SKIP 1.

ENDFORM. " SHOW_MATRIX

 

=={{header|Ada}}==

 

procedure Queens is

end loop;

Put_Line (" A B C D E F G H");

{{out}}

<pre>

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;

 

Put_Line (Long_Integer'Image (Queens (N)));

end loop;

 

=={{header|ALGOL 68}}==

 

{{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;

FI

OD

 

=={{header|APL}}==

{{works with|Dyalog APL}}

More or less copied from the "DFS" lesson on tryapl.org .

⍝Solution

accm←{⍺,((⍴⍵)=⍴⊃⍺)↑⊂⍵}

⍝Example

printqueens 6

{{out}}

<pre>

 

=={{header|AppleScript}}==

 

property Grid_Size : 8

return newRows

 

=={{header|Arc}}==

This program prints out all possible solutions:

(if (< len.queens n)

(let row (if queens (+ 1 queens.0.0) 0)

(def diagonal-match (curr other)

(is (abs (- curr.0 other.0))

{{out}}

The output is one solution per line, each solution in the form `((row col) (row col) (row col) ...)`:

((3 2) (2 0) (1 3) (0 1))

((3 1) (2 3) (1 0) (0 2))</pre>

 

=={{header|ATS}}==

(* ****** ****** *)

//

 

(* end of [queens.dats] *)

 

=={{header|AutoHotkey}}==

=== Output to formatted Message box ===

{{trans|C}}

; Post: http://www.autohotkey.com/forum/viewtopic.php?p=353059#353059

; Timestamp: 05/may/2010

Output .= "|`n" , yyy++

}

=== Includes a solution browser GUI ===

This implementation supports N = 4..12 queens, and will find ALL solutions

The screenshot shows the first solution of 10 possible solutions for N = 5 queens.

 

Number: ; main entrance for different # of queens

SI := 1

 

GuiClose:

[[image:N-Queens_SolutionBrowserGUI.png]]

 

[[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

ENDWHILE

UNTIL i% = 0

 

=={{header|BCPL}}==

 

GET "libhdr.h"

RESULTIS 0

}

The following is a re-implementation of the algorithm given above but

using the MC package that allows machine independent runtime generation

It runs about 25 times faster that the version given above.

 

GET "libhdr.h"

GET "mc.h"

i, n, all)

}

 

=={{header|Befunge}}==

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\`*-

 

{{out}}

 

=={{header|Bracmat}}==

= board M L x y S R row line

. :?board

| out$(found !solutions solutions)

)

{{out}} (tail):

<pre>

 

=={{header|C}}==

#include <stdlib.h>

 

int hist[n];

solve(n, 0, hist);

 

#include <stdlib.h>

#include <stdint.h>

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>

 

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

 

printf("Number of solution for %d is %d\n",n,nqueens(n));

}

 

=={{header|C sharp|C#}}==

{{works with|C sharp|C#|7}}

<!-- By Martin Freedman, 13/02/2018 -->

using static System.Linq.Enumerable;

using static System.Console;

public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; }

}

Output

<pre>8-queens has 92 solutions

===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;

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;

 

}

}

 

=={{header|C++}}==

// uses C++11 threads to parallelize the computation; also uses backtracking

// Outputs all solutions for any table size

return 0;

}

{{out}}Output for N = 4:

<pre> a b c d

3 #

4 # </pre>

// A straight-forward brute-force C++ version with formatted output,

// eschewing obfuscation and C-isms, producing ALL solutions, which

std::cout << queens( N ) << "\n";

}

{{out}} for N=4:

<pre>

=== Alternate version ===

Windows-only

#include <windows.h>

#include <iostream>

}

//--------------------------------------------------------------------------------------------------

{{out}}

<pre>

 

Version using Heuristics - explained here: [http://en.wikipedia.org/wiki/8_queens_puzzle#Solution_construction Solution_construction]

#include <windows.h>

#include <iostream>

}

//--------------------------------------------------------------------------------------------------

 

=={{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]

(println s))

 

===Short Version===

(:require [clojure.math.combinatorics :as combo]

 

(defn queens [n]

(filter (fn [x] (every? #(apply distinct? (map-indexed % x)) [+ -]))

 

=={{header|CoffeeScript}}==

# Unlike traditional N-Queens solutions that use recursion, this

# program attempts to more closely model the "human" algorithm.

 

nqueens(8)

 

=={{header|Common Lisp}}==

(if (zerop n)

(list nil)

 

(defun print-queens (n)

 

=== Alternate solution ===

Translation of Fortran 77

(let ((a (make-array n))

(s (make-array n))

> (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)

 

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))

(rotatef (aref a i) (aref a k))))))))

(sub 0))

 

=={{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

 

main = extend []

 

Another approach from the same source.

 

-- N-queens puzzle implemented with "Distinct Choices" pattern

-- Sergio Antoy

store = free

-- end

 

Yet another approach, also from the same source.

 

-- 8-queens implementation with both the Constrained Constructor

-- and the Fused Generate and Test patterns.

 

main = extend []

Mainly [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi?queens webpakcs], uses constraint-solver.

import Findall

 

 

-- oneSolution = unpack $ 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;

 

n.iota.map!(i => p[i] - i).array.sort().uniq.count == n)

.count.writeln;

{{out}}

<pre>92</pre>

This version shows all the solutions.

{{trans|C}}

__gshared int[side] board;

 

y--;

}

{{out}}

<pre>

===Fast Version===

{{trans|C}}

in {

assert(nn > 0 && nn <= 27,

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>

 

=={{header|Dart}}==

Return true if queen placement q[n] does not conflict with

other queens q[0] through q[n-1]

void main() {

enumerate(4);

{{out}}

<pre>* Q * *

* Q * *

</pre>

 

=={{header|EasyLang}}==

 

subr show_sol

.

.

subr test

.

n = 8

len x[] n

.

.

{{out}}

<pre>Solution 1

 

=={{header|EchoLisp}}==

;; square num is i + j*N

(define-syntax-rule (sq i j) (+ i (* j N)))

(define (task up-to-n)

(for ((i up-to-n)) (writeln i ' ♕ (q-count i) 'solutions)))

{{out}}

<pre>

12 ♕ 14200 solutions

</pre>

 

=={{header|Eiffel}}==

class

QUEENS

end

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Ruby}}

def queen(n, display \\ true) do

solve(n, [], [], [], display)

Enum.each(7..12, fn n ->

IO.puts " #{n} Queen : #{RC.queen(n, false)}" # no display

 

{{out}}

11 Queen : 2680

12 Queen : 14200

</pre>

 

=={{header|Erlang}}==

Instead of spawning a new process to search for each possible solution I backtrack.

-module( n_queens ).

 

Board = solve( N ),

display( Board ).

{{out}}

<pre>

. . Q . . . . .

</pre>

 

=={{header|ERRE}}==

!------------------------------------------------

! QUEENS.R : solve queens problem on a NxN board

END IF

END PROGRAM

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

 

printNumberOfSolutions()

 

The output:

 

| | | |X| | | | | |

| |X| | | | | | | |

10 724

11 2680

 

=={{header|Factor}}==

{{works with|Factor|0.98}}

IN: queens

 

[

[ 1 + "%d " printf ] each nl

 

=={{header|Forth}}==

variable nodes

 

solutions @ . ." solutions, " nodes @ . ." nodes" ;

 

 

=={{header|Fortran}}==

 

Using a back tracking method to find one solution

implicit none

 

write(*, "(a)") line

end subroutine

{{out}} for 8, 16 and 32 queens

<pre style="height:40ex;overflow:scroll">n = 8

 

===Alternate Fortran 77 solution===

C See the 2nd program for Scheme on the "Permutations" page for the

C main idea.

C 17 95815104

C 18 666090624

 

!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

print *, n, m

end do

 

===Alternate Fortran 95 solution with OpenMP===

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

integer, parameter :: long = selected_int_kind(17)

integer, parameter :: l = 18

integer :: n, i, j, a(l*l, 2), k, p, q

integer(long) :: s, b(l*l)

real(kind(1d0)) :: t1, t2

do n = 6, l

k = 0

go to 60

end function

 

=={{header|FreeBASIC}}==

Get slower for N > 14

' compile with: fbc -s console

Dim Shared As ULong count, c()

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 1 3 5 2 4

=== Alternate version : recursive ===

 

u() As Integer, v() As Integer, ByRef m As LongInt)

 

aux(n, 1, a(), u(), v(), m)

Print m

 

=== Alternate version : iterative ===

 

Dim m As LongInt = 0

 

u(p) = 1 : v(q) = 1

Goto L3

 

=={{header|Frink}}==

{

for q = 0 to length[board] - 1

if board@q == board@c + (c - q) or board@q == board@c - (c - q)

return false

}

 

for b = array[1 to 8].permute[]

if solution[b]

 

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|GAP}}==

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];

[ 0, 0, 0, 0, 0, 0, 1, 0 ],

[ 0, 1, 0, 0, 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

}

}

 

{{out}}

 

=== Refactored Niklaus Wirth algorithm (clearer/Go friendly solution) ===

* N-Queens Problem

*

trycol(0)

printresults()

{{out}}

<pre>

[[N-queens_problem/dlx_go|dlx packge]].

 

 

import (

}

return nil

{{out}}

<pre>

===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] }

// 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()

}

qus

 

===Test and Results===

This script tests both distinct and unique solution lists.

def qds = queensDistinctSolutions(n)

def qus = queensUniqueSolutions(qds)

else { println "first:${qus[0]}"; println "last:${qus[-1]}" }

println()

 

Interpreting the Results:

 

=={{header|Haskell}}==

import Data.List

 

 

-- prints all the solutions for 6 queens

 

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 ((\\))

 

where

f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs]

 

===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

 

-- 8 is for "8 queens"

 

===In terms of foldr===

A back-tracking variant using the Prelude's plain '''foldr''':

{{Trans|JavaScript}}

 

queenPuzzle :: Int -> Int -> [[Int]]

| nRows <= 0 = [[]]

| otherwise =

 

safe :: Int -> Int -> [Int] -> Bool

safe iRow iCol qs =

(not . or) $

 

-- 10 columns of solutions for the 7*7 board:

showSolutions :: Int -> Int -> [String]

showSolutions nCols nSize =

where

boardLines rows =

 

chunksOf :: Int -> [a] -> [[a]]

 

main :: IO ()

{{Out}}

<pre>......♛ ......♛ ......♛ ......♛ .....♛. .....♛. .....♛. .....♛. .....♛. .....♛.

 

===Breadth-first search and Depth-first search===

import System.Environment

 

let n = read narg :: Int

print (bfs n [emptySt])

 

{{Out}}

 

=={{header|Heron}}==

inherits {

Heron.Windows.Console;

}

}

 

=={{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

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

 

Notes:

* 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

This drives the backtracking to find more solutions.

 

The comment explains how to modify the program to produce <i>all</i>

solutions for a given <tt>N</tt>.

 

procedure main(args)

write()

return # Comment out to see all possible solutions

 

A sample run for <tt>N = 6</tt>:

 

=={{header|IS-BASIC}}==

110 TEXT 80

120 DO

450 LET T(I)=1

460 NEXT

 

=={{header|J}}==

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 =: [ */@:~:&(|@-/) {

 

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.

Example use:

 

 

92 distinct solutions for an 8 by 8 board.

 

 

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];

}

}

 

=={{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 [[]];

}

 

 

===ES6===

Translating the ES5 version, and adding a function to display columns of solutions.

 

 

// queenPuzzle :: Int -> Int -> [[Int]]

[]

] : go(nRows - 1).reduce(

);

return go;

};

// safe : Int -> Int -> [Int] -> Bool

const safe = (iRow, iCol, solution) =>

([sc, sr]) => (iCol === sc) || (

sc + sr === iCol + iRow

) || (sc - sr === iCol - iRow)

 

// Ten columns of solutions to the 7*7 board

 

// main :: IO ()

const main = () =>

console.log(

);

 

 

// showSolutions :: Int -> Int -> String

)

)

 

 

 

// chunksOf :: Int -> [a] -> [[a]]

 

 

 

 

// enumFromTo :: Int -> Int -> [Int]

}, (_, i) => m + i);

 

 

 

 

 

 

 

 

 

=={{header|jq}}==

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 ([]; . + ["."]);

(""; reduce $row[] as $x (.; . + $x) + "\n");

 

{{out}}

$ jq -M -n -r -f n-queens-single-solution.jq

.....♛..

.......♛

♛.......

..♛.....

====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:

end;

 

'''Part 2: n-queens'''

def sums:

. as $board

 

count( permutations(n) | select(allowable) );

'''Example''':

{{out}}

92

=={{header|Julia}}==

 

# EightQueensPuzzle

 

module EightQueensPuzzle

 

 

cols::Int

nodes::Int

"Marks occupancy."

function mark!(b::Board, k::Int, j::Int)

end

 

end

 

 

end

n = 1

elapsed: 0.000001 seconds

 

n = 5

solutions = 10

 

n = 6

solutions = 4

 

n = 7

solutions = 40

 

n = 8

solutions = 92

 

n = 9

solutions = 352

 

n = 10

solutions = 724

 

n = 11

solutions = 2680

 

n = 12

solutions = 14200

 

n = 13

solutions = 73712

 

n = 14

solutions = 365596

 

n = 15

solutions = 2279184

 

n = 16

solutions = 14772512

 

n = 17

solutions = 95815104

 

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

var count = 0

println()

}

 

{{out}}

=={{header|Liberty BASIC}}==

Program uses permutation generator (stores all permutations) and solves tasks 4x4 to 9x9. It prints all the solutions.

'N queens

'>10 would not work due to way permutations used

End Function

 

 

=={{header|Locomotive Basic}}==

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)

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

 

[[File:Queens Puzzle, Locomotive Basic.png]]

 

=={{header|Logo}}==

if :files = 0 [make "solutions :solutions+1 show :tried stop]

localmake "safe (bitand :files :diag1 :diag2)

end

 

 

=={{header|Lua}}==

 

-- We'll use nil to indicate no queen is present.

else

print(string.format("No solution for %d queens.\n", N))

 

=={{header|M2000 Interpreter}}==

{{trans|VBA}}

Module N_queens {

Const l = 15 'number of queens

}

N_queens

 

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] ==

If[Length[q] == n, {q},

Cases[nQueen[Append[q, #], n] & /@ Range[n],

 

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]

{{out}}

<pre>{. . . Q . ., . . . . Q ., . Q . . . ., . . Q . . .}

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 *)

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}];

 

Alternative Solution using Linear Programming:

 

dispSol[sol_] := sol /. {1 -> "Q" , 0 -> "-"} // Grid

 

 

solveNqueens[8] // dispSol

<pre>- - - - Q - - -

- Q - - - - - -

- - - - - - - Q

- - Q - - - - -</pre>

 

=={{header|Maxima}}==

 

queens(n) := block([a, i, j, m, p, q, r, s, u, v, w, y, z],

[1, 6, 8, 3, 7, 4, 2, 5],

...]] */

 

=={{header|MiniZinc}}==

array [1..n] of var 1..n: q; % queen in column i is in row q[i]

 

satisfy;

output [ if fix(q[j]) == i then "Q" else "." endif ++

 

This solution appears in the official MiniZinc tutorial documentation, and is generalized.