N-queens problem: Difference between revisions

Solve the [[WP:Eight_queens_puzzle|eight queens puzzle]].

 

 

* [[Knight's tour]]

 

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

{{trans|FORTRAN}}

MACRO

MEND

NQUEENS CSECT

LOOPN CH R9,L do n=1 to l

BH ELOOPN if n>l then exit loop

STH R0,U-2(R1) u(q+r)=0

B E60 goto e60

LA R9,1(R9) n=n+1

B LOOPN loop do n

LTORG

Z DS H

Y DS H

PG DS CL24 buffer

{{out}}

<pre>

11 2680

12 14200

</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|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|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++}}==

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

 

 

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

class

QUEENS

end

end

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Ruby}}

def queen(n, display \\ true) do

end

if display, do: print(n,row)

1

end

Enum.map(Enum.to_list(0..n-1) -- row, fn x ->

0

end

end

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

IN: queens

 

:: safe? ( board q -- ? )

[let q board nth :> x

x swap

[ board nth ] keep

 

: solution? ( board -- ? )

 

: queens ( n -- l )

 

: .queens ( n -- )

[

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

column three.

 

 

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

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

// Data Structures = Programs."

package main

import "fmt"

var (

i int

x [9]int

)

func try(i int) {

for j := 1; ; j++ {

}

}

func main() {

for i := 1; i <= 8; i++ {

}

}

{{out}}

<pre>

7 2

8 4