N-queens problem: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: typed array indexing) |
(Convert <lang> elements to <syntaxhighlight>) |
||
Line 26: | Line 26: | ||
{{trans|Nim}} |
{{trans|Nim}} |
||
< |
<syntaxhighlight lang=11l>-V BoardSize = 8 |
||
F underAttack(col, queens) |
F underAttack(col, queens) |
||
Line 57: | Line 57: | ||
print(‘ ’, end' ‘’) |
print(‘ ’, end' ‘’) |
||
print(Char(code' ‘a’.code + row)‘’col, end' ‘’) |
print(Char(code' ‘a’.code + row)‘’col, end' ‘’) |
||
print(end' I L.index % 4 == 3 {"\n"} E ‘ ’)</ |
print(end' I L.index % 4 == 3 {"\n"} E ‘ ’)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 92: | Line 92: | ||
Translated from the Fortran 77 solution.<br> |
Translated from the Fortran 77 solution.<br> |
||
For maximum compatibility, this program uses only the basic instruction set (S/360). |
For maximum compatibility, this program uses only the basic instruction set (S/360). |
||
< |
<syntaxhighlight lang=360asm>* N-QUEENS PROBLEM 04/09/2015 |
||
MACRO |
MACRO |
||
&LAB XDECO ®,&TARGET |
&LAB XDECO ®,&TARGET |
||
Line 233: | Line 233: | ||
U DC (4*LL-2)H'0' stack |
U DC (4*LL-2)H'0' stack |
||
REGS make sure to include copybook jcl |
REGS make sure to include copybook jcl |
||
END NQUEENS</ |
END NQUEENS</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 253: | Line 253: | ||
=={{header|ABAP}}== |
=={{header|ABAP}}== |
||
< |
<syntaxhighlight lang=ABAP> |
||
TYPES: BEGIN OF gty_matrix, |
TYPES: BEGIN OF gty_matrix, |
||
1 TYPE c, |
1 TYPE c, |
||
Line 539: | Line 539: | ||
SKIP 1. |
SKIP 1. |
||
ENDFORM. " SHOW_MATRIX |
ENDFORM. " SHOW_MATRIX |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
< |
<syntaxhighlight lang=Ada>with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Queens is |
procedure Queens is |
||
Line 591: | Line 591: | ||
end loop; |
end loop; |
||
Put_Line (" A B C D E F G H"); |
Put_Line (" A B C D E F G H"); |
||
end Queens;</ |
end Queens;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 610: | 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). |
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). |
||
< |
<syntaxhighlight lang=ada>with Ada.Text_IO; |
||
use Ada.Text_IO; |
use Ada.Text_IO; |
||
Line 658: | Line 658: | ||
Put_Line (Long_Integer'Image (Queens (N))); |
Put_Line (Long_Integer'Image (Queens (N))); |
||
end loop; |
end loop; |
||
end CountQueens;</ |
end CountQueens;</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 668: | 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]}} |
{{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]}} |
||
< |
<syntaxhighlight lang=Algol68>INT ofs = 1, # Algol68 normally uses array offset of 1 # |
||
dim = 8; # dim X dim chess board # |
dim = 8; # dim X dim chess board # |
||
[ofs:dim+ofs-1]INT b; |
[ofs:dim+ofs-1]INT b; |
||
Line 718: | Line 718: | ||
FI |
FI |
||
OD |
OD |
||
)</ |
)</syntaxhighlight> |
||
=={{header|APL}}== |
=={{header|APL}}== |
||
{{works with|Dyalog APL}} |
{{works with|Dyalog APL}} |
||
More or less copied from the "DFS" lesson on tryapl.org . |
More or less copied from the "DFS" lesson on tryapl.org . |
||
< |
<syntaxhighlight lang=APL> |
||
⍝Solution |
⍝Solution |
||
accm←{⍺,((⍴⍵)=⍴⊃⍺)↑⊂⍵} |
accm←{⍺,((⍴⍵)=⍴⊃⍺)↑⊂⍵} |
||
Line 735: | Line 735: | ||
⍝Example |
⍝Example |
||
printqueens 6 |
printqueens 6 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 769: | Line 769: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
< |
<syntaxhighlight lang=applescript>-- Finds all possible solutions and the unique patterns. |
||
property Grid_Size : 8 |
property Grid_Size : 8 |
||
Line 932: | Line 932: | ||
return newRows |
return newRows |
||
end Reflect</ |
end Reflect</syntaxhighlight> |
||
=={{header|Arc}}== |
=={{header|Arc}}== |
||
This program prints out all possible solutions: |
This program prints out all possible solutions: |
||
< |
<syntaxhighlight lang=Lisp>(def nqueens (n (o queens)) |
||
(if (< len.queens n) |
(if (< len.queens n) |
||
(let row (if queens (+ 1 queens.0.0) 0) |
(let row (if queens (+ 1 queens.0.0) 0) |
||
Line 955: | Line 955: | ||
(def diagonal-match (curr other) |
(def diagonal-match (curr other) |
||
(is (abs (- curr.0 other.0)) |
(is (abs (- curr.0 other.0)) |
||
(abs (- curr.1 other.1))))</ |
(abs (- curr.1 other.1))))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
The output is one solution per line, each solution in the form `((row col) (row col) (row col) ...)`: |
The output is one solution per line, each solution in the form `((row col) (row col) (row col) ...)`: |
||
Line 964: | Line 964: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang=arturo>result: new [] |
||
queens: function [n, i, a, b, c][ |
queens: function [n, i, a, b, c][ |
||
Line 995: | Line 995: | ||
] |
] |
||
print "" |
print "" |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,029: | Line 1,029: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
Inspired by Raymond Hettinger's Python solution, but builds the vector incrementally. |
Inspired by Raymond Hettinger's Python solution, but builds the vector incrementally. |
||
< |
<syntaxhighlight lang=awk> |
||
#!/usr/bin/gawk -f |
#!/usr/bin/gawk -f |
||
# Solve the Eight Queens Puzzle |
# Solve the Eight Queens Puzzle |
||
Line 1,103: | Line 1,103: | ||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,118: | Line 1,118: | ||
=={{header|ATS}}== |
=={{header|ATS}}== |
||
< |
<syntaxhighlight lang=ATS> |
||
(* ****** ****** *) |
(* ****** ****** *) |
||
// |
// |
||
Line 1,199: | Line 1,199: | ||
(* end of [queens.dats] *) |
(* end of [queens.dats] *) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
=== Output to formatted Message box === |
=== Output to formatted Message box === |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=AutoHotkey>; |
||
; Post: http://www.autohotkey.com/forum/viewtopic.php?p=353059#353059 |
; Post: http://www.autohotkey.com/forum/viewtopic.php?p=353059#353059 |
||
; Timestamp: 05/may/2010 |
; Timestamp: 05/may/2010 |
||
Line 1,283: | Line 1,283: | ||
Output .= "|`n" , yyy++ |
Output .= "|`n" , yyy++ |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=== Includes a solution browser GUI === |
=== Includes a solution browser GUI === |
||
This implementation supports N = 4..12 queens, and will find ALL solutions |
This implementation supports N = 4..12 queens, and will find ALL solutions |
||
Line 1,289: | Line 1,289: | ||
The screenshot shows the first solution of 10 possible solutions for N = 5 queens. |
The screenshot shows the first solution of 10 possible solutions for N = 5 queens. |
||
< |
<syntaxhighlight lang=AutoHotkey>N := 5 |
||
Number: ; main entrance for different # of queens |
Number: ; main entrance for different # of queens |
||
SI := 1 |
SI := 1 |
||
Line 1,378: | Line 1,378: | ||
GuiClose: |
GuiClose: |
||
ExitApp</ |
ExitApp</syntaxhighlight> |
||
[[image:N-Queens_SolutionBrowserGUI.png]] |
[[image:N-Queens_SolutionBrowserGUI.png]] |
||
Line 1,387: | Line 1,387: | ||
[[Image:queens9_bbc.gif|right]] |
[[Image:queens9_bbc.gif|right]] |
||
[[Image:queens10_bbc.gif|right]] |
[[Image:queens10_bbc.gif|right]] |
||
< |
<syntaxhighlight lang=bbcbasic> Size% = 8 |
||
Cell% = 32 |
Cell% = 32 |
||
VDU 23,22,Size%*Cell%;Size%*Cell%;Cell%,Cell%,16,128+8,5 |
VDU 23,22,Size%*Cell%;Size%*Cell%;Cell%,Cell%,16,128+8,5 |
||
Line 1,447: | Line 1,447: | ||
ENDWHILE |
ENDWHILE |
||
UNTIL i% = 0 |
UNTIL i% = 0 |
||
= m%</ |
= m%</syntaxhighlight> |
||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<syntaxhighlight lang=BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10. |
||
GET "libhdr.h" |
GET "libhdr.h" |
||
Line 1,480: | Line 1,480: | ||
RESULTIS 0 |
RESULTIS 0 |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
The following is a re-implementation of the algorithm given above but |
The following is a re-implementation of the algorithm given above but |
||
using the MC package that allows machine independent runtime generation |
using the MC package that allows machine independent runtime generation |
||
Line 1,486: | Line 1,486: | ||
It runs about 25 times faster that the version given above. |
It runs about 25 times faster that the version given above. |
||
< |
<syntaxhighlight lang=BCPL> |
||
GET "libhdr.h" |
GET "libhdr.h" |
||
GET "mc.h" |
GET "mc.h" |
||
Line 1,621: | Line 1,621: | ||
i, n, all) |
i, n, all) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
Line 1,627: | Line 1,627: | ||
This algorithm works with any board size from 4 upwards. |
This algorithm works with any board size from 4 upwards. |
||
< |
<syntaxhighlight lang=befunge><+--XX@_v#!:-1,+55,g\1$_:00g2%-0vv:,+55<&,,,,,,"Size: " |
||
"| Q"$$$>:01p:2%!00g0>>^<<!:-1\<1>00p::2%-:40p2/50p2*1+ |
"| 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\`*- |
!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-</ |
2g05\**!!%6g04-g052!:`\g05::-1/2<^4*2%g05\+*+1*!!%6g04-</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,655: | Line 1,655: | ||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
< |
<syntaxhighlight lang=bracmat>( ( printBoard |
||
= board M L x y S R row line |
= board M L x y S R row line |
||
. :?board |
. :?board |
||
Line 1,715: | Line 1,715: | ||
| out$(found !solutions solutions) |
| out$(found !solutions solutions) |
||
) |
) |
||
);</ |
);</syntaxhighlight> |
||
{{out}} (tail): |
{{out}} (tail): |
||
<pre> |
<pre> |
||
Line 1,760: | Line 1,760: | ||
=={{header|C}}== |
=={{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.< |
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.<syntaxhighlight lang=C>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 1,790: | Line 1,790: | ||
int hist[n]; |
int hist[n]; |
||
solve(n, 0, hist); |
solve(n, 0, hist); |
||
}</ |
}</syntaxhighlight> |
||
Similiar to above, but using bits to save board configurations and quite a bit faster:< |
Similiar to above, but using bits to save board configurations and quite a bit faster:<syntaxhighlight lang=c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdint.h> |
#include <stdint.h> |
||
Line 1,829: | Line 1,829: | ||
printf("\nSolutions: %d\n", count); |
printf("\nSolutions: %d\n", count); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Take that and unwrap the recursion, plus some heavy optimizations, and we have a very fast and very unreadable solution: |
Take that and unwrap the recursion, plus some heavy optimizations, and we have a very fast and very unreadable solution: |
||
< |
<syntaxhighlight lang=c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 1,921: | Line 1,921: | ||
printf("\nSolutions: %d\n", count); |
printf("\nSolutions: %d\n", count); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang=c>#include <stdio.h> |
||
#define MAXN 31 |
#define MAXN 31 |
||
Line 1,994: | Line 1,994: | ||
printf("Number of solution for %d is %d\n",n,nqueens(n)); |
printf("Number of solution for %d is %d\n",n,nqueens(n)); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
Line 2,007: | Line 2,007: | ||
{{works with|C sharp|C#|7}} |
{{works with|C sharp|C#|7}} |
||
<!-- By Martin Freedman, 13/02/2018 --> |
<!-- By Martin Freedman, 13/02/2018 --> |
||
< |
<syntaxhighlight lang=csharp>using System.Collections.Generic; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
using static System.Console; |
using static System.Console; |
||
Line 2,049: | Line 2,049: | ||
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; } |
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output |
Output |
||
<pre>8-queens has 92 solutions |
<pre>8-queens has 92 solutions |
||
Line 2,057: | Line 2,057: | ||
===Hettinger Algorithm=== |
===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 ...) |
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 ...) |
||
< |
<syntaxhighlight lang=csharp> |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
using static System.Linq.Enumerable; |
using static System.Linq.Enumerable; |
||
Line 2,095: | Line 2,095: | ||
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; } |
public static IEnumerable<T> ToSingleton<T>(this T item) { yield return item; } |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=== Amb solution=== |
=== 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. |
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}} |
{{works with|C sharp|C#|7.1}} |
||
<!-- By Martin Freedman, 9/02/2018 --> |
<!-- By Martin Freedman, 9/02/2018 --> |
||
< |
<syntaxhighlight lang=csharp>using static System.Linq.Enumerable; |
||
using static System.Console; |
using static System.Console; |
||
Line 2,128: | Line 2,128: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang=cpp>// Much shorter than the version below; |
||
// uses C++11 threads to parallelize the computation; also uses backtracking |
// uses C++11 threads to parallelize the computation; also uses backtracking |
||
// Outputs all solutions for any table size |
// Outputs all solutions for any table size |
||
Line 2,234: | Line 2,234: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}Output for N = 4: |
{{out}}Output for N = 4: |
||
<pre> a b c d |
<pre> a b c d |
||
Line 2,248: | Line 2,248: | ||
3 # |
3 # |
||
4 # </pre> |
4 # </pre> |
||
< |
<syntaxhighlight lang=cpp> |
||
// A straight-forward brute-force C++ version with formatted output, |
// A straight-forward brute-force C++ version with formatted output, |
||
// eschewing obfuscation and C-isms, producing ALL solutions, which |
// eschewing obfuscation and C-isms, producing ALL solutions, which |
||
Line 2,506: | Line 2,506: | ||
std::cout << queens( N ) << "\n"; |
std::cout << queens( N ) << "\n"; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} for N=4: |
{{out}} for N=4: |
||
<pre> |
<pre> |
||
Line 2,527: | Line 2,527: | ||
=== Alternate version === |
=== Alternate version === |
||
Windows-only |
Windows-only |
||
< |
<syntaxhighlight lang=cpp> |
||
#include <windows.h> |
#include <windows.h> |
||
#include <iostream> |
#include <iostream> |
||
Line 2,628: | Line 2,628: | ||
} |
} |
||
//-------------------------------------------------------------------------------------------------- |
//-------------------------------------------------------------------------------------------------- |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,657: | Line 2,657: | ||
Version using Heuristics - explained here: [http://en.wikipedia.org/wiki/8_queens_puzzle#Solution_construction Solution_construction] |
Version using Heuristics - explained here: [http://en.wikipedia.org/wiki/8_queens_puzzle#Solution_construction Solution_construction] |
||
< |
<syntaxhighlight lang=cpp> |
||
#include <windows.h> |
#include <windows.h> |
||
#include <iostream> |
#include <iostream> |
||
Line 2,746: | Line 2,746: | ||
} |
} |
||
//-------------------------------------------------------------------------------------------------- |
//-------------------------------------------------------------------------------------------------- |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Clojure}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=clojure>(def size 8) |
||
(defn extends? [v n] |
(defn extends? [v n] |
||
Line 2,772: | Line 2,772: | ||
(println s)) |
(println s)) |
||
(println (count solutions) "solutions")</ |
(println (count solutions) "solutions")</syntaxhighlight> |
||
===Short Version=== |
===Short Version=== |
||
< |
<syntaxhighlight lang=clojure>(ns queens |
||
(:require [clojure.math.combinatorics :as combo] |
(:require [clojure.math.combinatorics :as combo] |
||
(defn queens [n] |
(defn queens [n] |
||
(filter (fn [x] (every? #(apply distinct? (map-indexed % x)) [+ -])) |
(filter (fn [x] (every? #(apply distinct? (map-indexed % x)) [+ -])) |
||
(combo/permutations (range 1 (inc n))))) </ |
(combo/permutations (range 1 (inc n))))) </syntaxhighlight> |
||
===Backtracking as Tree processing=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=clojure> |
||
(defn n-queens [n] |
(defn n-queens [n] |
||
(let[children #(map (partial conj %) (range n)) |
(let[children #(map (partial conj %) (range n)) |
||
Line 2,793: | Line 2,793: | ||
no-conflict?) |
no-conflict?) |
||
children [])))) |
children [])))) |
||
</ |
</syntaxhighlight> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=clu>n_queens = cluster is solve |
||
rep = null |
rep = null |
||
own hist: array[int] := array[int]$[] |
own hist: array[int] := array[int]$[] |
||
Line 2,855: | Line 2,855: | ||
stream$putl(po, "No. " || int$unparse(count) || "\n-------\n" || s) |
stream$putl(po, "No. " || int$unparse(count) || "\n-------\n" || s) |
||
end |
end |
||
end start_up</ |
end start_up</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre style='height:50ex'>No. 1 |
<pre style='height:50ex'>No. 1 |
||
Line 3,870: | Line 3,870: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang=coffeescript> |
||
# Unlike traditional N-Queens solutions that use recursion, this |
# Unlike traditional N-Queens solutions that use recursion, this |
||
# program attempts to more closely model the "human" algorithm. |
# program attempts to more closely model the "human" algorithm. |
||
Line 3,982: | Line 3,982: | ||
nqueens(8) |
nqueens(8) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<syntaxhighlight lang=lisp>(defun queens (n &optional (m n)) |
||
(if (zerop n) |
(if (zerop n) |
||
(list nil) |
(list nil) |
||
Line 4,003: | Line 4,003: | ||
(defun print-queens (n) |
(defun print-queens (n) |
||
(mapc #'print-solution (queens n)))</ |
(mapc #'print-solution (queens n)))</syntaxhighlight> |
||
=== Alternate solution === |
=== Alternate solution === |
||
Translation of Fortran 77 |
Translation of Fortran 77 |
||
< |
<syntaxhighlight lang=lisp>(defun queens1 (n) |
||
(let ((a (make-array n)) |
(let ((a (make-array n)) |
||
(s (make-array n)) |
(s (make-array n)) |
||
Line 4,046: | Line 4,046: | ||
> (loop for n from 1 to 14 collect (cons n (queens1 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) |
((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))</ |
(10 . 724) (11 . 2680) (12 . 14200) (13 . 73712) (14 . 365596))</syntaxhighlight> |
||
As in Fortran, the iterative function above is equivalent to the recursive function below: |
As in Fortran, the iterative function above is equivalent to the recursive function below: |
||
< |
<syntaxhighlight lang=lisp>(defun queens2 (n) |
||
(let ((a (make-array n)) |
(let ((a (make-array n)) |
||
(u (make-array (+ n n -1) :initial-element t)) |
(u (make-array (+ n n -1) :initial-element t)) |
||
Line 4,070: | Line 4,070: | ||
(rotatef (aref a i) (aref a k)))))))) |
(rotatef (aref a i) (aref a k)))))))) |
||
(sub 0)) |
(sub 0)) |
||
m))</ |
m))</syntaxhighlight> |
||
=={{header|Curry}}== |
=={{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] |
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] |
||
< |
<syntaxhighlight lang=curry> |
||
-- 8-queens implementation with the Constrained Constructor pattern |
-- 8-queens implementation with the Constrained Constructor pattern |
||
-- Sergio Antoy |
-- Sergio Antoy |
||
Line 4,133: | Line 4,133: | ||
main = extend [] |
main = extend [] |
||
</syntaxhighlight> |
|||
</lang> |
|||
Another approach from the same source. |
Another approach from the same source. |
||
< |
<syntaxhighlight lang=curry> |
||
-- N-queens puzzle implemented with "Distinct Choices" pattern |
-- N-queens puzzle implemented with "Distinct Choices" pattern |
||
-- Sergio Antoy |
-- Sergio Antoy |
||
Line 4,172: | Line 4,172: | ||
store = free |
store = free |
||
-- end |
-- end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Yet another approach, also from the same source. |
Yet another approach, also from the same source. |
||
< |
<syntaxhighlight lang=curry> |
||
-- 8-queens implementation with both the Constrained Constructor |
-- 8-queens implementation with both the Constrained Constructor |
||
-- and the Fused Generate and Test patterns. |
-- and the Fused Generate and Test patterns. |
||
Line 4,236: | Line 4,236: | ||
main = extend [] |
main = extend [] |
||
</syntaxhighlight> |
|||
</lang> |
|||
Mainly [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi?queens webpakcs], uses constraint-solver. |
Mainly [http://www-ps.informatik.uni-kiel.de/~pakcs/webpakcs/main.cgi?queens webpakcs], uses constraint-solver. |
||
< |
<syntaxhighlight lang=curry>import CLPFD |
||
import Findall |
import Findall |
||
Line 4,256: | Line 4,256: | ||
-- oneSolution = unpack $ queens 8 |
-- oneSolution = unpack $ queens 8 |
||
-- allSolutions = findall $ queens 8</ |
-- allSolutions = findall $ queens 8</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
===Short Version=== |
===Short Version=== |
||
This high-level version uses the second solution of the Permutations task. |
This high-level version uses the second solution of the Permutations task. |
||
< |
<syntaxhighlight lang=d>void main() { |
||
import std.stdio, std.algorithm, std.range, permutations2; |
import std.stdio, std.algorithm, std.range, permutations2; |
||
Line 4,269: | Line 4,269: | ||
n.iota.map!(i => p[i] - i).array.sort().uniq.count == n) |
n.iota.map!(i => p[i] - i).array.sort().uniq.count == n) |
||
.count.writeln; |
.count.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>92</pre> |
<pre>92</pre> |
||
Line 4,276: | Line 4,276: | ||
This version shows all the solutions. |
This version shows all the solutions. |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=d>enum side = 8; |
||
__gshared int[side] board; |
__gshared int[side] board; |
||
Line 4,319: | Line 4,319: | ||
y--; |
y--; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,356: | Line 4,356: | ||
===Fast Version=== |
===Fast Version=== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=d>ulong nQueens(in uint nn) pure nothrow @nogc @safe |
||
in { |
in { |
||
assert(nn > 0 && nn <= 27, |
assert(nn > 0 && nn <= 27, |
||
Line 4,445: | Line 4,445: | ||
immutable uint side = (args.length >= 2) ? args[1].to!uint : 8; |
immutable uint side = (args.length >= 2) ? args[1].to!uint : 8; |
||
writefln("N-queens(%d) = %d solutions.", side, side.nQueens); |
writefln("N-queens(%d) = %d solutions.", side, side.nQueens); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>N-queens(8) = 92 solutions.</pre> |
<pre>N-queens(8) = 92 solutions.</pre> |
||
Line 4,454: | Line 4,454: | ||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
< |
<syntaxhighlight lang=dart>/** |
||
Return true if queen placement q[n] does not conflict with |
Return true if queen placement q[n] does not conflict with |
||
other queens q[0] through q[n-1] |
other queens q[0] through q[n-1] |
||
Line 4,518: | Line 4,518: | ||
void main() { |
void main() { |
||
enumerate(4); |
enumerate(4); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>* Q * * |
<pre>* Q * * |
||
Line 4,533: | Line 4,533: | ||
{{libheader| System.SysUtils}} |
{{libheader| System.SysUtils}} |
||
{{Trans|Go}} |
{{Trans|Go}} |
||
< |
<syntaxhighlight lang=Delphi> |
||
program N_queens_problem; |
program N_queens_problem; |
||
Line 4,597: | Line 4,597: | ||
writeln(i, ' ', x[i]); |
writeln(i, ' ', x[i]); |
||
readln; |
readln; |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|Draco}}== |
=={{header|Draco}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=draco>byte SIZE = 8; |
||
word count; |
word count; |
||
Line 4,638: | Line 4,638: | ||
count := 0; |
count := 0; |
||
solve(hist, 0) |
solve(hist, 0) |
||
corp</ |
corp</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>No. 1 |
<pre>No. 1 |
||
Line 4,712: | Line 4,712: | ||
. |
. |
||
. |
. |
||
print n_sol & " solutions"</ |
print n_sol & " solutions"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Solution 1 |
<pre>Solution 1 |
||
Line 4,728: | Line 4,728: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
< |
<syntaxhighlight lang=scheme> |
||
;; square num is i + j*N |
;; square num is i + j*N |
||
(define-syntax-rule (sq i j) (+ i (* j N))) |
(define-syntax-rule (sq i j) (+ i (* j N))) |
||
Line 4,786: | Line 4,786: | ||
(define (task up-to-n) |
(define (task up-to-n) |
||
(for ((i up-to-n)) (writeln i ' ♕ (q-count i) 'solutions))) |
(for ((i up-to-n)) (writeln i ' ♕ (q-count i) 'solutions))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,807: | Line 4,807: | ||
=={{header|Eiffel}}== |
=={{header|Eiffel}}== |
||
< |
<syntaxhighlight lang=Eiffel> |
||
class |
class |
||
QUEENS |
QUEENS |
||
Line 4,876: | Line 4,876: | ||
end |
end |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,912: | Line 4,912: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang=elixir>defmodule RC do |
||
def queen(n, display \\ true) do |
def queen(n, display \\ true) do |
||
solve(n, [], [], [], display) |
solve(n, [], [], [], display) |
||
Line 4,949: | Line 4,949: | ||
Enum.each(7..12, fn n -> |
Enum.each(7..12, fn n -> |
||
IO.puts " #{n} Queen : #{RC.queen(n, false)}" # no display |
IO.puts " #{n} Queen : #{RC.queen(n, false)}" # no display |
||
end)</ |
end)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,086: | Line 5,086: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Instead of spawning a new process to search for each possible solution I backtrack. |
Instead of spawning a new process to search for each possible solution I backtrack. |
||
< |
<syntaxhighlight lang=Erlang> |
||
-module( n_queens ). |
-module( n_queens ). |
||
Line 5,170: | Line 5,170: | ||
Board = solve( N ), |
Board = solve( N ), |
||
display( Board ). |
display( Board ). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 5,191: | Line 5,191: | ||
===Alternative Version=== |
===Alternative Version=== |
||
< |
<syntaxhighlight lang=Erlang> |
||
%%%For 8X8 chessboard with N queens. |
%%%For 8X8 chessboard with N queens. |
||
-module(queens). |
-module(queens). |
||
Line 5,206: | Line 5,206: | ||
(Row /= Column + N) andalso (Row /= Column - N) andalso |
(Row /= Column + N) andalso (Row /= Column - N) andalso |
||
safe(Row, Columns, (N+1)). |
safe(Row, Columns, (N+1)). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
Line 5,294: | Line 5,294: | ||
END IF |
END IF |
||
END PROGRAM |
END PROGRAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
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. |
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}}== |
=={{header|F Sharp}}== |
||
< |
<syntaxhighlight lang=fsharp> |
||
let rec iterate f value = seq { |
let rec iterate f value = seq { |
||
yield value |
yield value |
||
Line 5,341: | Line 5,341: | ||
printNumberOfSolutions() |
printNumberOfSolutions() |
||
</syntaxhighlight> |
|||
</lang> |
|||
The output: |
The output: |
||
Line 5,367: | Line 5,367: | ||
10 724 |
10 724 |
||
11 2680 |
11 2680 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
< |
<syntaxhighlight lang=factor>USING: kernel sequences math math.combinatorics formatting io locals ; |
||
IN: queens |
IN: queens |
||
Line 5,397: | Line 5,397: | ||
[ |
[ |
||
[ 1 + "%d " printf ] each nl |
[ 1 + "%d " printf ] each nl |
||
] each ;</ |
] each ;</syntaxhighlight> |
||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang=forth>variable solutions |
||
variable nodes |
variable nodes |
||
Line 5,428: | Line 5,428: | ||
solutions @ . ." solutions, " nodes @ . ." nodes" ; |
solutions @ . ." solutions, " nodes @ . ." nodes" ; |
||
8 queens \ 92 solutions, 1965 nodes</ |
8 queens \ 92 solutions, 1965 nodes</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
Line 5,434: | Line 5,434: | ||
Using a back tracking method to find one solution |
Using a back tracking method to find one solution |
||
< |
<syntaxhighlight lang=fortran>program Nqueens |
||
implicit none |
implicit none |
||
Line 5,534: | Line 5,534: | ||
write(*, "(a)") line |
write(*, "(a)") line |
||
end subroutine |
end subroutine |
||
end program</ |
end program</syntaxhighlight> |
||
{{out}} for 8, 16 and 32 queens |
{{out}} for 8, 16 and 32 queens |
||
<pre style="height:40ex;overflow:scroll">n = 8 |
<pre style="height:40ex;overflow:scroll">n = 8 |
||
Line 5,658: | Line 5,658: | ||
===Alternate Fortran 77 solution=== |
===Alternate Fortran 77 solution=== |
||
< |
<syntaxhighlight lang=fortran>C This one implements depth-first backtracking. |
||
C See the 2nd program for Scheme on the "Permutations" page for the |
C See the 2nd program for Scheme on the "Permutations" page for the |
||
C main idea. |
C main idea. |
||
Line 5,730: | Line 5,730: | ||
C 17 95815104 |
C 17 95815104 |
||
C 18 666090624 |
C 18 666090624 |
||
</syntaxhighlight> |
|||
</lang> |
|||
< |
<syntaxhighlight lang=fortran>!The preceding program implements recursion using arrays, since Fortran 77 does not allow recursive |
||
!functions. The same algorithm is much easier to follow in Fortran 90, using the RECURSIVE keyword. |
!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 |
!Like previously, the program only counts solutions. It's pretty straightforward to adapt it to print |
||
Line 5,784: | Line 5,784: | ||
print *, n, m |
print *, n, m |
||
end do |
end do |
||
end program</ |
end program</syntaxhighlight> |
||
===Alternate Fortran 95 solution with OpenMP=== |
===Alternate Fortran 95 solution with OpenMP=== |
||
Line 5,797: | 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. |
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. |
||
< |
<syntaxhighlight lang=fortran>program queens |
||
use omp_lib |
use omp_lib |
||
implicit none |
implicit none |
||
Line 5,921: | Line 5,921: | ||
go to 60 |
go to 60 |
||
end function |
end function |
||
end program</ |
end program</syntaxhighlight> |
||
===Fortran 2008 in a Lisp-like fashion=== |
===Fortran 2008 in a Lisp-like fashion=== |
||
Line 5,928: | 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. |
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. |
||
< |
<syntaxhighlight lang=fortran>program example__n_queens |
||
use, intrinsic :: iso_fortran_env, only: output_unit |
use, intrinsic :: iso_fortran_env, only: output_unit |
||
Line 6,207: | Line 6,207: | ||
end subroutine check_garbage |
end subroutine check_garbage |
||
end program example__n_queens</ |
end program example__n_queens</syntaxhighlight> |
||
{{out}}$ ./example__n_queens 1 2 3 4 |
{{out}}$ ./example__n_queens 1 2 3 4 |
||
<pre style="height:40ex;overflow:scroll"> |
<pre style="height:40ex;overflow:scroll"> |
||
Line 6,245: | Line 6,245: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
Get slower for N > 14 |
Get slower for N > 14 |
||
< |
<syntaxhighlight lang=freebasic>' version 13-04-2017 |
||
' compile with: fbc -s console |
' compile with: fbc -s console |
||
Dim Shared As ULong count, c() |
Dim Shared As ULong count, c() |
||
Line 6,300: | Line 6,300: | ||
Print : Print "hit any key to end program" |
Print : Print "hit any key to end program" |
||
Sleep |
Sleep |
||
End</ |
End</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 3 5 2 4 |
<pre> 1 3 5 2 4 |
||
Line 6,331: | Line 6,331: | ||
=== Alternate version : recursive === |
=== Alternate version : recursive === |
||
< |
<syntaxhighlight lang=freebasic>Sub aux(n As Integer, i As Integer, a() As Integer, _ |
||
u() As Integer, v() As Integer, ByRef m As LongInt) |
u() As Integer, v() As Integer, ByRef m As LongInt) |
||
Line 6,371: | Line 6,371: | ||
aux(n, 1, a(), u(), v(), m) |
aux(n, 1, a(), u(), v(), m) |
||
Print m |
Print m |
||
End If</ |
End If</syntaxhighlight> |
||
=== Alternate version : iterative === |
=== Alternate version : iterative === |
||
< |
<syntaxhighlight lang=freebasic>Dim As Integer n, i, j, k, p, q |
||
Dim m As LongInt = 0 |
Dim m As LongInt = 0 |
||
Line 6,417: | Line 6,417: | ||
u(p) = 1 : v(q) = 1 |
u(p) = 1 : v(q) = 1 |
||
Goto L3 |
Goto L3 |
||
End If</ |
End If</syntaxhighlight> |
||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
This example uses Frink's built-in <CODE>array.permute[]</CODE> method to generate possible permutations of the board efficiently. |
This example uses Frink's built-in <CODE>array.permute[]</CODE> method to generate possible permutations of the board efficiently. |
||
< |
<syntaxhighlight lang=Frink>solution[board] := |
||
{ |
{ |
||
for q = 0 to length[board] - 1 |
for q = 0 to length[board] - 1 |
||
Line 6,432: | Line 6,432: | ||
for b = array[1 to 8].permute[] |
for b = array[1 to 8].permute[] |
||
if solution[b] |
if solution[b] |
||
println[b]</ |
println[b]</syntaxhighlight> |
||
=={{header|Fōrmulæ}}== |
=={{header|Fōrmulæ}}== |
||
Line 6,446: | 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. |
Translation of Fortran 77. See also alternate Python implementation. One function to return the number of solutions, another to return the list of permutations. |
||
< |
<syntaxhighlight lang=gap>NrQueens := function(n) |
||
local a, up, down, m, sub; |
local a, up, down, m, sub; |
||
a := [1 .. n]; |
a := [1 .. n]; |
||
Line 6,523: | Line 6,523: | ||
[ 0, 0, 0, 0, 0, 0, 1, 0 ], |
[ 0, 0, 0, 0, 0, 0, 1, 0 ], |
||
[ 0, 1, 0, 0, 0, 0, 0, 0 ], |
[ 0, 1, 0, 0, 0, 0, 0, 0 ], |
||
[ 0, 0, 0, 1, 0, 0, 0, 0 ] ]</ |
[ 0, 0, 0, 1, 0, 0, 0, 0 ] ]</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Niklaus Wirth algorithm (Wikipedia)=== |
===Niklaus Wirth algorithm (Wikipedia)=== |
||
< |
<syntaxhighlight lang=go>// A fairly literal translation of the example program on the referenced |
||
// WP page. Well, it happened to be the example program the day I completed |
// 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 |
// the task. It seems from the WP history that there has been some churn |
||
Line 6,587: | Line 6,587: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,602: | Line 6,602: | ||
=== Refactored Niklaus Wirth algorithm (clearer/Go friendly solution) === |
=== Refactored Niklaus Wirth algorithm (clearer/Go friendly solution) === |
||
< |
<syntaxhighlight lang=go>/* |
||
* N-Queens Problem |
* N-Queens Problem |
||
* |
* |
||
Line 6,725: | Line 6,725: | ||
trycol(0) |
trycol(0) |
||
printresults() |
printresults() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,746: | Line 6,746: | ||
[[N-queens_problem/dlx_go|dlx packge]]. |
[[N-queens_problem/dlx_go|dlx packge]]. |
||
< |
<syntaxhighlight lang=Go>package main |
||
import ( |
import ( |
||
Line 6,881: | Line 6,881: | ||
} |
} |
||
return nil |
return nil |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,915: | Line 6,915: | ||
===Distinct Solutions=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=groovy>def listOrder = { a, b -> |
||
def k = [a.size(), b.size()].min() |
def k = [a.size(), b.size()].min() |
||
def i = (0..<k).find { a[it] != b[it] } |
def i = (0..<k).find { a[it] != b[it] } |
||
Line 6,938: | Line 6,938: | ||
// each permutation is an N-Rooks solution |
// each permutation is an N-Rooks solution |
||
orderedPermutations((0..<n)).findAll (diagonalSafe) |
orderedPermutations((0..<n)).findAll (diagonalSafe) |
||
}</ |
}</syntaxhighlight> |
||
===Unique Solutions=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=groovy>class Reflect { |
||
public static final diag = { list -> |
public static final diag = { list -> |
||
final n = list.size() |
final n = list.size() |
||
Line 6,992: | Line 6,992: | ||
} |
} |
||
qus |
qus |
||
}</ |
}</syntaxhighlight> |
||
===Test and Results=== |
===Test and Results=== |
||
This script tests both distinct and unique solution lists. |
This script tests both distinct and unique solution lists. |
||
< |
<syntaxhighlight lang=groovy>(1..9).each { n -> |
||
def qds = queensDistinctSolutions(n) |
def qds = queensDistinctSolutions(n) |
||
def qus = queensUniqueSolutions(qds) |
def qus = queensUniqueSolutions(qds) |
||
Line 7,003: | Line 7,003: | ||
else { println "first:${qus[0]}"; println "last:${qus[-1]}" } |
else { println "first:${qus[0]}"; println "last:${qus[-1]}" } |
||
println() |
println() |
||
}</ |
}</syntaxhighlight> |
||
Interpreting the Results: |
Interpreting the Results: |
||
Line 7,073: | Line 7,073: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang=haskell>import Control.Monad |
||
import Data.List |
import Data.List |
||
Line 7,102: | Line 7,102: | ||
-- prints all the solutions for 6 queens |
-- prints all the solutions for 6 queens |
||
main = mapM_ printSolution $ queens 6</ |
main = mapM_ printSolution $ queens 6</syntaxhighlight> |
||
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. |
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=== |
===Alternative version=== |
||
< |
<syntaxhighlight lang=haskell>import Control.Monad (foldM) |
||
import Data.List ((\\)) |
import Data.List ((\\)) |
||
Line 7,117: | Line 7,117: | ||
where |
where |
||
f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs] |
f qs _ = [q:qs | q <- [1..n] \\ qs, q `notDiag` qs] |
||
q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]</ |
q `notDiag` qs = and [abs (q - qi) /= i | (qi,i) <- qs `zip` [1..]]</syntaxhighlight> |
||
===Using permutations=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=haskell>import Data.List (nub, permutations) |
||
-- checks if queens are on the same diagonal |
-- checks if queens are on the same diagonal |
||
Line 7,132: | Line 7,132: | ||
-- 8 is for "8 queens" |
-- 8 is for "8 queens" |
||
main = print $ generate 8</ |
main = print $ generate 8</syntaxhighlight> |
||
===In terms of foldr=== |
===In terms of foldr=== |
||
A back-tracking variant using the Prelude's plain '''foldr''': |
A back-tracking variant using the Prelude's plain '''foldr''': |
||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
< |
<syntaxhighlight lang=haskell>import Data.List (intercalate, transpose) |
||
--------------------- N QUEENS PROBLEM ------------------- |
--------------------- N QUEENS PROBLEM ------------------- |
||
Line 7,190: | Line 7,190: | ||
main :: IO () |
main :: IO () |
||
main = (putStrLn . unlines) $ showSolutions 10 7</ |
main = (putStrLn . unlines) $ showSolutions 10 7</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>......♛ ......♛ ......♛ ......♛ .....♛. .....♛. .....♛. .....♛. .....♛. .....♛. |
<pre>......♛ ......♛ ......♛ ......♛ .....♛. .....♛. .....♛. .....♛. .....♛. .....♛. |
||
Line 7,225: | Line 7,225: | ||
===Breadth-first search and Depth-first search=== |
===Breadth-first search and Depth-first search=== |
||
< |
<syntaxhighlight lang=haskell>import Control.Monad |
||
import System.Environment |
import System.Environment |
||
Line 7,287: | Line 7,287: | ||
let n = read narg :: Int |
let n = read narg :: Int |
||
print (bfs n [emptySt]) |
print (bfs n [emptySt]) |
||
print (head $ dfs n emptySt)</ |
print (head $ dfs n emptySt)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 7,294: | Line 7,294: | ||
=={{header|Heron}}== |
=={{header|Heron}}== |
||
< |
<syntaxhighlight lang=heron>module NQueens { |
||
inherits { |
inherits { |
||
Heron.Windows.Console; |
Heron.Windows.Console; |
||
Line 7,388: | Line 7,388: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
Here's a solution to the <tt>n = 8</tt> case: |
Here's a solution to the <tt>n = 8</tt> case: |
||
< |
<syntaxhighlight lang=icon>procedure main() |
||
write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8)) |
write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8)) |
||
end |
end |
||
Line 7,407: | Line 7,407: | ||
every 0 = row[r := 1 to 8] = ddiag[r + c - 1] = udiag[8 + r - c] do # test if free |
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 |
suspend row[r] <- ddiag[r + c - 1] <- udiag[8 + r - c] <- r # place and yield |
||
end</ |
end</syntaxhighlight> |
||
Notes: |
Notes: |
||
Line 7,418: | 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". |
* 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: |
* If you want to derive all possible solutions, main() can be embellished with the '''every''' keyword: |
||
< |
<syntaxhighlight lang=icon> |
||
procedure main() |
procedure main() |
||
every write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8)) |
every write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8)) |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
This drives the backtracking to find more solutions. |
This drives the backtracking to find more solutions. |
||
Line 7,430: | Line 7,430: | ||
The comment explains how to modify the program to produce <i>all</i> |
The comment explains how to modify the program to produce <i>all</i> |
||
solutions for a given <tt>N</tt>. |
solutions for a given <tt>N</tt>. |
||
< |
<syntaxhighlight lang=icon>global n, rw, dd, ud |
||
procedure main(args) |
procedure main(args) |
||
Line 7,464: | Line 7,464: | ||
write() |
write() |
||
return # Comment out to see all possible solutions |
return # Comment out to see all possible solutions |
||
end</ |
end</syntaxhighlight> |
||
A sample run for <tt>N = 6</tt>: |
A sample run for <tt>N = 6</tt>: |
||
Line 7,488: | Line 7,488: | ||
=={{header|IS-BASIC}}== |
=={{header|IS-BASIC}}== |
||
< |
<syntaxhighlight lang=IS-BASIC>100 PROGRAM "NQueens.bas" |
||
110 TEXT 80 |
110 TEXT 80 |
||
120 DO |
120 DO |
||
Line 7,525: | Line 7,525: | ||
450 LET T(I)=1 |
450 LET T(I)=1 |
||
460 NEXT |
460 NEXT |
||
470 END DEF</ |
470 END DEF</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
Line 7,531: | Line 7,531: | ||
This is one of several J solutions shown and explained on this [[J:Essays/N%20Queens%20Problem|J wiki page]] |
This is one of several J solutions shown and explained on this [[J:Essays/N%20Queens%20Problem|J wiki page]] |
||
< |
<syntaxhighlight lang=j>perm =: ! A.&i. ] NB. all permutations of integers 0 to y |
||
comb2 =: (, #: I.@,@(</)&i.)~ NB. all size 2 combinations of integers 0 to y |
comb2 =: (, #: I.@,@(</)&i.)~ NB. all size 2 combinations of integers 0 to y |
||
mask =: [ */@:~:&(|@-/) { |
mask =: [ */@:~:&(|@-/) { |
||
queenst=: comb2 (] #"1~ mask)&.|: perm</ |
queenst=: comb2 (] #"1~ mask)&.|: perm</syntaxhighlight> |
||
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. |
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: | Line 7,540: | ||
Example use: |
Example use: |
||
< |
<syntaxhighlight lang=j> $queenst 8 |
||
92 8</ |
92 8</syntaxhighlight> |
||
92 distinct solutions for an 8 by 8 board. |
92 distinct solutions for an 8 by 8 board. |
||
< |
<syntaxhighlight lang=j> {.queenst 8 |
||
0 4 7 5 2 6 1 3</ |
0 4 7 5 2 6 1 3</syntaxhighlight> |
||
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. |
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}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang=java>public class NQueens { |
||
private static int[] b = new int[8]; |
private static int[] b = new int[8]; |
||
Line 7,598: | Line 7,598: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Javascript}}== |
=={{header|Javascript}}== |
||
===ES5=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=javascript>function queenPuzzle(rows, columns) { |
||
if (rows <= 0) { |
if (rows <= 0) { |
||
return [[]]; |
return [[]]; |
||
Line 7,635: | Line 7,635: | ||
} |
} |
||
console.log(queenPuzzle(8,8));</ |
console.log(queenPuzzle(8,8));</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
Translating the ES5 version, and adding a function to display columns of solutions. |
Translating the ES5 version, and adding a function to display columns of solutions. |
||
< |
<syntaxhighlight lang=JavaScript>(() => { |
||
"use strict"; |
"use strict"; |
||
Line 7,767: | Line 7,767: | ||
// MAIN --- |
// MAIN --- |
||
return main(); |
return main(); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>....... ....... ....... ....... ♛...... ♛...... ♛...... ♛...... ♛...... ♛...... |
<pre>....... ....... ....... ....... ♛...... ♛...... ♛...... ♛...... ♛...... ♛...... |
||
Line 7,806: | Line 7,806: | ||
This section presents a function for finding a single solution using |
This section presents a function for finding a single solution using |
||
the formulae for explicit solutions at [[WP:Eight_queens_puzzle|Eight Queens Puzzle]]. |
the formulae for explicit solutions at [[WP:Eight_queens_puzzle|Eight Queens Puzzle]]. |
||
< |
<syntaxhighlight lang=jq>def single_solution_queens(n): |
||
def q: "♛"; |
def q: "♛"; |
||
def init(k): reduce range(0;k) as $i ([]; . + ["."]); |
def init(k): reduce range(0;k) as $i ([]; . + ["."]); |
||
Line 7,830: | Line 7,830: | ||
(""; reduce $row[] as $x (.; . + $x) + "\n"); |
(""; reduce $row[] as $x (.; . + $x) + "\n"); |
||
single_solution_queens(8) | pp</ |
single_solution_queens(8) | pp</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
$ jq -M -n -r -f n-queens-single-solution.jq |
$ jq -M -n -r -f n-queens-single-solution.jq |
||
< |
<syntaxhighlight lang=sh>...♛.... |
||
.....♛.. |
.....♛.. |
||
.......♛ |
.......♛ |
||
Line 7,840: | Line 7,840: | ||
♛....... |
♛....... |
||
..♛..... |
..♛..... |
||
....♛...</ |
....♛...</syntaxhighlight> |
||
====Generate-and-test counter==== |
====Generate-and-test counter==== |
||
{{ works with|jq|1.4}} |
{{ works with|jq|1.4}} |
||
'''Part 1: Generic functions''' |
'''Part 1: Generic functions''' |
||
< |
<syntaxhighlight lang=jq># permutations of 0 .. (n-1) |
||
def permutations(n): |
def permutations(n): |
||
# Given a single array, generate a stream by inserting n at different positions: |
# Given a single array, generate a stream by inserting n at different positions: |
||
Line 7,856: | Line 7,856: | ||
end; |
end; |
||
def count(g): reduce g as $i (0; .+1);</ |
def count(g): reduce g as $i (0; .+1);</syntaxhighlight> |
||
'''Part 2: n-queens''' |
'''Part 2: n-queens''' |
||
< |
<syntaxhighlight lang=jq>def queens(n): |
||
def sums: |
def sums: |
||
. as $board |
. as $board |
||
Line 7,874: | Line 7,874: | ||
count( permutations(n) | select(allowable) ); |
count( permutations(n) | select(allowable) ); |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Example''': |
'''Example''': |
||
<lang |
<syntaxhighlight lang=jq>queens(8)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
92 |
92 |
||
Line 7,882: | Line 7,882: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang=ruby>""" |
||
# EightQueensPuzzle |
# EightQueensPuzzle |
||
Line 7,949: | Line 7,949: | ||
println() |
println() |
||
end |
end |
||
</ |
</syntaxhighlight> {{out}} |
||
<pre> |
<pre> |
||
n = 1 |
n = 1 |
||
Line 8,022: | Line 8,022: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<syntaxhighlight lang=scala>// version 1.1.3 |
||
var count = 0 |
var count = 0 |
||
Line 8,051: | Line 8,051: | ||
println() |
println() |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,112: | Line 8,112: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
Program uses permutation generator (stores all permutations) and solves tasks 4x4 to 9x9. It prints all the solutions. |
Program uses permutation generator (stores all permutations) and solves tasks 4x4 to 9x9. It prints all the solutions. |
||
<syntaxhighlight lang=lb> |
|||
<lang lb> |
|||
'N queens |
'N queens |
||
'>10 would not work due to way permutations used |
'>10 would not work due to way permutations used |
||
Line 8,198: | Line 8,198: | ||
End Function |
End Function |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Locomotive Basic}}== |
=={{header|Locomotive Basic}}== |
||
Line 8,204: | Line 8,204: | ||
Uses the heuristic from the Wikipedia article to get one solution. |
Uses the heuristic from the Wikipedia article to get one solution. |
||
< |
<syntaxhighlight lang=locobasic>10 mode 1:defint a-z |
||
20 while n<4:input "How many queens (N>=4)";n:wend |
20 while n<4:input "How many queens (N>=4)";n:wend |
||
30 dim q(n),e(n),o(n) |
30 dim q(n),e(n),o(n) |
||
Line 8,255: | Line 8,255: | ||
500 for i=1 to 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 |
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</ |
520 next</syntaxhighlight> |
||
[[File:Queens Puzzle, Locomotive Basic.png]] |
[[File:Queens Puzzle, Locomotive Basic.png]] |
||
Line 8,261: | Line 8,261: | ||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang=logo>to try :files :diag1 :diag2 :tried |
||
if :files = 0 [make "solutions :solutions+1 show :tried stop] |
if :files = 0 [make "solutions :solutions+1 show :tried stop] |
||
localmake "safe (bitand :files :diag1 :diag2) |
localmake "safe (bitand :files :diag1 :diag2) |
||
Line 8,277: | Line 8,277: | ||
end |
end |
||
print queens 8 ; 92</ |
print queens 8 ; 92</syntaxhighlight> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang=Lua>N = 8 |
||
-- We'll use nil to indicate no queen is present. |
-- We'll use nil to indicate no queen is present. |
||
Line 8,314: | Line 8,314: | ||
else |
else |
||
print(string.format("No solution for %d queens.\n", N)) |
print(string.format("No solution for %d queens.\n", N)) |
||
end</ |
end</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
{{trans|VBA}} |
{{trans|VBA}} |
||
< |
<syntaxhighlight lang=M2000 Interpreter> |
||
Module N_queens { |
Module N_queens { |
||
Const l = 15 'number of queens |
Const l = 15 'number of queens |
||
Line 8,377: | Line 8,377: | ||
} |
} |
||
N_queens |
N_queens |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|m4}}== |
=={{header|m4}}== |
||
Line 8,383: | Line 8,383: | ||
It finds one solution of the Eight Queens problem. |
It finds one solution of the Eight Queens problem. |
||
< |
<syntaxhighlight lang=m4>divert(-1) |
||
The following macro find one solution to the eight-queens problem: |
The following macro find one solution to the eight-queens problem: |
||
Line 8,476: | Line 8,476: | ||
divert`'dnl |
divert`'dnl |
||
dnl |
dnl |
||
solve_eight_queens</ |
solve_eight_queens</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,501: | Line 8,501: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang=maple>queens:=proc(n) |
||
local a,u,v,m,aux; |
local a,u,v,m,aux; |
||
a:=[$1..n]; |
a:=[$1..n]; |
||
Line 8,534: | Line 8,534: | ||
end: |
end: |
||
for a in queens(8) do printf("%a\n",a) od;</ |
for a in queens(8) do printf("%a\n",a) od;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 8,548: | Line 8,548: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=Mathematica>safe[q_List, n_] := |
||
With[{l = Length@q}, |
With[{l = Length@q}, |
||
Length@Union@q == Length@Union[q + Range@l] == |
Length@Union@q == Length@Union[q + Range@l] == |
||
Line 8,556: | Line 8,556: | ||
If[Length[q] == n, {q}, |
If[Length[q] == n, {q}, |
||
Cases[nQueen[Append[q, #], n] & /@ Range[n], |
Cases[nQueen[Append[q, #], n] & /@ Range[n], |
||
Except[{Null} | {}], {2}]], Null]</ |
Except[{Null} | {}], {2}]], Null]</syntaxhighlight> |
||
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: |
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: |
||
< |
<syntaxhighlight lang=Mathematica>matrixView[n_] := |
||
Grid[Normal@ |
Grid[Normal@ |
||
SparseArray[MapIndexed[{#, First@#2} -> "Q" &, #], {n, n}, "."], |
SparseArray[MapIndexed[{#, First@#2} -> "Q" &, #], {n, n}, "."], |
||
Frame -> All] & /@ nQueen[n] |
Frame -> All] & /@ nQueen[n] |
||
matrixView[6] // OutputForm</ |
matrixView[6] // OutputForm</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{. . . Q . ., . . . . Q ., . Q . . . ., . . Q . . .} |
<pre>{. . . Q . ., . . . . Q ., . Q . . . ., . . Q . . .} |
||
Line 8,580: | Line 8,580: | ||
This solution uses Permutations and subsets, also prints out a board representation. |
This solution uses Permutations and subsets, also prints out a board representation. |
||
< |
<syntaxhighlight lang=Mathematica>n=8;cnt=1;per=Permutations[Range[n],{n}];(* All Permutations of length n *) |
||
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[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 *) |
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: | 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*) |
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}]; |
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]}]</ |
Print[cnt," ",per[[t]]," ",g];cnt++],{t,1,Length[per]}]</syntaxhighlight> |
||
Alternative Solution using Linear Programming: |
Alternative Solution using Linear Programming: |
||
< |
<syntaxhighlight lang=Mathematica> |
||
dispSol[sol_] := sol /. {1 -> "Q" , 0 -> "-"} // Grid |
dispSol[sol_] := sol /. {1 -> "Q" , 0 -> "-"} // Grid |
||
Line 8,636: | Line 8,636: | ||
solveNqueens[8] // dispSol |
solveNqueens[8] // dispSol |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre>- - - - Q - - - |
<pre>- - - - Q - - - |
||
- Q - - - - - - |
- Q - - - - - - |
||
Line 8,648: | Line 8,648: | ||
=={{header|MATLAB}}== |
=={{header|MATLAB}}== |
||
This solution is inspired by Raymond Hettinger's permutations based solution which was made in Python: https://code.activestate.com/recipes/576647/ |
This solution is inspired by Raymond Hettinger's permutations based solution which was made in Python: https://code.activestate.com/recipes/576647/ |
||
< |
<syntaxhighlight lang=MATLAB>n=8; |
||
solutions=[[]]; |
solutions=[[]]; |
||
v = 1:n; |
v = 1:n; |
||
Line 8,672: | Line 8,672: | ||
end |
end |
||
s |
s |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 8,688: | Line 8,688: | ||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang=maxima>/* translation of Fortran 77, return solutions as permutations */ |
||
queens(n) := block([a, i, j, m, p, q, r, s, u, v, w, y, z], |
queens(n) := block([a, i, j, m, p, q, r, s, u, v, w, y, z], |
||
Line 8,705: | Line 8,705: | ||
[1, 6, 8, 3, 7, 4, 2, 5], |
[1, 6, 8, 3, 7, 4, 2, 5], |
||
...]] */ |
...]] */ |
||
length(%); /* 92 */</ |
length(%); /* 92 */</syntaxhighlight> |
||
=={{header|MiniZinc}}== |
=={{header|MiniZinc}}== |
||
< |
<syntaxhighlight lang=minizinc>int: n; |
||
array [1..n] of var 1..n: q; % queen in column i is in row q[i] |
array [1..n] of var 1..n: q; % queen in column i is in row q[i] |
||
Line 8,721: | Line 8,721: | ||
satisfy; |
satisfy; |
||
output [ if fix(q[j]) == i then "Q" else "." endif ++ |
output [ if fix(q[j]) == i then "Q" else "." endif ++ |
||
if j == n then "\n" else "" endif | i,j in 1..n]</ |
if j == n then "\n" else "" endif | i,j in 1..n]</syntaxhighlight> |
||
This solution appears in the official MiniZinc tutorial documentation, and is generalized. |
This solution appears in the official MiniZinc tutorial documentation, and is generalized. |
||
Line 8,727: | Line 8,727: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang=modula2>MODULE NQueens; |
||
FROM InOut IMPORT Write, WriteCard, WriteString, WriteLn; |
FROM InOut IMPORT Write, WriteCard, WriteString, WriteLn; |
||
Line 8,782: | Line 8,782: | ||
count := 0; |
count := 0; |
||
Solve(N, 0); |
Solve(N, 0); |
||
END NQueens.</ |
END NQueens.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 9,799: | Line 9,799: | ||
=={{header|MUMPS}}== |
=={{header|MUMPS}}== |
||
< |
<syntaxhighlight lang=MUMPS>Queens New count,flip,row,sol |
||
Set sol=0 |
Set sol=0 |
||
For row(1)=1:1:4 Do try(2) ; Not 8, the other 4 are symmetric... |
For row(1)=1:1:4 Do try(2) ; Not 8, the other 4 are symmetric... |
||
Line 9,858: | Line 9,858: | ||
Quit |
Quit |
||
Do Queens |
Do Queens |
||
</syntaxhighlight> |
|||
</lang> |
|||
<div style="overflow:scroll; height:400px;"> |
<div style="overflow:scroll; height:400px;"> |
||
< |
<syntaxhighlight lang=MUMPS> |
||
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ |
||
8 | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##| |
8 | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##| |
||
Line 10,068: | Line 10,068: | ||
1 |##| |##| | Q| |##| | |
1 |##| |##| | Q| |##| | |
||
+--+--+--+--+--+--+--+--+ |
+--+--+--+--+--+--+--+--+ |
||
A B C D E F G H</ |
A B C D E F G H</syntaxhighlight></div> |
||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang=nim>const BoardSize = 8 |
||
proc underAttack(col: int; queens: seq[int]): bool = |
proc underAttack(col: int; queens: seq[int]): bool = |
||
Line 10,099: | Line 10,099: | ||
if row > 0: stdout.write ' ' |
if row > 0: stdout.write ' ' |
||
stdout.write chr(ord('a') + row), col |
stdout.write chr(ord('a') + row), col |
||
stdout.write if i mod 4 == 3: "\n" else: " "</ |
stdout.write if i mod 4 == 3: "\n" else: " "</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 10,131: | Line 10,131: | ||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang=objeck>bundle Default { |
||
class NQueens { |
class NQueens { |
||
b : static : Int[]; |
b : static : Int[]; |
||
Line 10,188: | Line 10,188: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
{{libheader|FaCiLe}} |
{{libheader|FaCiLe}} |
||
< |
<syntaxhighlight lang=ocaml>(* Authors: Nicolas Barnier, Pascal Brisset |
||
Copyright 2004 CENA. All rights reserved. |
Copyright 2004 CENA. All rights reserved. |
||
This code is distributed under the terms of the GNU LGPL *) |
This code is distributed under the terms of the GNU LGPL *) |
||
Line 10,251: | Line 10,251: | ||
then raise (Failure "Usage: queens <nb of queens>"); |
then raise (Failure "Usage: queens <nb of queens>"); |
||
Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *) |
Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *) |
||
queens (int_of_string Sys.argv.(1));;</ |
queens (int_of_string Sys.argv.(1));;</syntaxhighlight> |
||
===A stand-alone OCaml solution=== |
===A stand-alone OCaml solution=== |
||
< |
<syntaxhighlight lang=ocaml>let solutions n = |
||
let show board = |
let show board = |
||
Line 10,284: | Line 10,284: | ||
else 8 in |
else 8 in |
||
solutions n</ |
solutions n</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>$ ocaml queens.ml 6 |
<pre>$ ocaml queens.ml 6 |
||
Line 10,318: | Line 10,318: | ||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
A pretty naive solution, using constraint programming: |
A pretty naive solution, using constraint programming: |
||
< |
<syntaxhighlight lang=oz>declare |
||
fun {Queens N} |
fun {Queens N} |
||
proc {$ Board} |
proc {$ Board} |
||
Line 10,385: | Line 10,385: | ||
in |
in |
||
{Length Solutions} = 92 %% assert |
{Length Solutions} = 92 %% assert |
||
{Inspect {List.take Solutions 3}}</ |
{Inspect {List.take Solutions 3}}</syntaxhighlight> |
||
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. |
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}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang=pascal>program queens; |
||
const l=16; |
const l=16; |
||
Line 10,470: | Line 10,470: | ||
14 365596 |
14 365596 |
||
15 2279184 |
15 2279184 |
||
16 14772512 }</ |
16 14772512 }</syntaxhighlight> |
||
===Alternative=== |
===Alternative=== |
||
Line 10,488: | Line 10,488: | ||
Solution found</pre> |
Solution found</pre> |
||
< |
<syntaxhighlight lang=pascal>program NQueens; |
||
{$IFDEF FPC} |
{$IFDEF FPC} |
||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
Line 10,599: | Line 10,599: | ||
end; |
end; |
||
WriteLn('Fertig'); |
WriteLn('Fertig'); |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 10,623: | Line 10,623: | ||
=={{header|PDP-11 Assembly}}== |
=={{header|PDP-11 Assembly}}== |
||
< |
<syntaxhighlight lang=PDP-11 Assembly> |
||
; "eight queens problem" benchmark test |
; "eight queens problem" benchmark test |
||
Line 10,738: | Line 10,738: | ||
scr: ;display RAM |
scr: ;display RAM |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang=perl>my ($board_size, @occupied, @past, @solutions); |
||
sub try_column { |
sub try_column { |
||
Line 10,780: | Line 10,780: | ||
#print for @solutions; # un-comment to see all solutions |
#print for @solutions; # un-comment to see all solutions |
||
print "total " . @solutions . " solutions\n";</ |
print "total " . @solutions . " solutions\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>total 14200 solutions</pre> |
<pre>total 14200 solutions</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang=Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #000080;font-style:italic;">-- |
<span style="color: #000080;font-style:italic;">-- |
||
Line 10,841: | 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: #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> |
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 10,874: | Line 10,874: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang=PHP> |
||
<html> |
<html> |
||
<head> |
<head> |
||
Line 11,052: | Line 11,052: | ||
</body> |
</body> |
||
</html> |
</html> |
||
</syntaxhighlight> |
|||
</lang> |
|||
<h2>Solution with recursion</h2> |
<h2>Solution with recursion</h2> |
||
< |
<syntaxhighlight lang=PHP> |
||
<html> |
<html> |
||
<body> |
<body> |
||
Line 11,130: | Line 11,130: | ||
</body> |
</body> |
||
</html> |
</html> |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
===0/1 encoding a N x N matrix=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=Picat>import sat. |
||
% import mip. |
% import mip. |
||
Line 11,157: | Line 11,157: | ||
sum([Q[I,J] : I in 1..N]) #= 1 |
sum([Q[I,J] : I in 1..N]) #= 1 |
||
end, |
end, |
||
solve([inout],Q).</ |
solve([inout],Q).</syntaxhighlight> |
||
===Constraint programming=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=Picat>import cp. |
||
queens(N, Q) => |
queens(N, Q) => |
||
Line 11,169: | Line 11,169: | ||
all_different([$Q[I]-I : I in 1..N]), |
all_different([$Q[I]-I : I in 1..N]), |
||
all_different([$Q[I]+I : I in 1..N]), |
all_different([$Q[I]+I : I in 1..N]), |
||
solve([ff],Q).</ |
solve([ff],Q).</syntaxhighlight> |
||
==="Naive" approach=== |
==="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. |
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. |
||
< |
<syntaxhighlight lang=Picat>queens_naive(N, Q) => |
||
Q = new_list(N), |
Q = new_list(N), |
||
Q :: 1..N, |
Q :: 1..N, |
||
Line 11,181: | Line 11,181: | ||
Q[I] - I #!= Q[J] - J |
Q[I] - I #!= Q[J] - J |
||
end, |
end, |
||
solve([ff], Q).</ |
solve([ff], Q).</syntaxhighlight> |
||
Line 11,222: | Line 11,222: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
===Calling 'permute'=== |
===Calling 'permute'=== |
||
< |
<syntaxhighlight lang=PicoLisp>(load "@lib/simul.l") # for 'permute' |
||
(de queens (N) |
(de queens (N) |
||
Line 11,232: | Line 11,232: | ||
(length (uniq (mapcar - L R))) ) |
(length (uniq (mapcar - L R))) ) |
||
(inc 'Cnt) ) ) |
(inc 'Cnt) ) ) |
||
Cnt ) )</ |
Cnt ) )</syntaxhighlight> |
||
===Permuting inline=== |
===Permuting inline=== |
||
This alternative version does not first pre-generate all permutations with |
This alternative version does not first pre-generate all permutations with |
||
'permute', but creates them recursively. Also, it directly checks for |
'permute', but creates them recursively. Also, it directly checks for |
||
duplicates, instead of calling 'uniq' and 'length'. This is much faster. |
duplicates, instead of calling 'uniq' and 'length'. This is much faster. |
||
< |
<syntaxhighlight lang=PicoLisp>(de queens (N) |
||
(let (R (range 1 N) L (copy R) X L Cnt 0) |
(let (R (range 1 N) L (copy R) X L Cnt 0) |
||
(recur (X) # Permute |
(recur (X) # Permute |
||
Line 11,252: | Line 11,252: | ||
(mapcar - L R) ) |
(mapcar - L R) ) |
||
(inc 'Cnt) ) ) ) |
(inc 'Cnt) ) ) ) |
||
Cnt ) )</ |
Cnt ) )</syntaxhighlight> |
||
{{out}} for both cases: |
{{out}} for both cases: |
||
<pre>: (queens 8) |
<pre>: (queens 8) |
||
Line 11,259: | Line 11,259: | ||
=={{header|PL/I}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=pli> |
||
NQUEENS: PROC OPTIONS (MAIN); |
NQUEENS: PROC OPTIONS (MAIN); |
||
DCL A(35) BIN FIXED(31) EXTERNAL; |
DCL A(35) BIN FIXED(31) EXTERNAL; |
||
Line 11,337: | Line 11,337: | ||
END QUEEN; |
END QUEEN; |
||
END NQUEENS; </ |
END NQUEENS; </syntaxhighlight> |
||
=={{header|PowerBASIC}}== |
=={{header|PowerBASIC}}== |
||
=== Recursive version === |
=== Recursive version === |
||
{{trans|Stata}} |
{{trans|Stata}} |
||
< |
<syntaxhighlight lang=powerbasic>#COMPILE EXE |
||
#DIM ALL |
#DIM ALL |
||
Line 11,387: | Line 11,387: | ||
PRINT m |
PRINT m |
||
END IF |
END IF |
||
END FUNCTION</ |
END FUNCTION</syntaxhighlight> |
||
=== Iterative version === |
=== Iterative version === |
||
{{trans|Stata}} |
{{trans|Stata}} |
||
< |
<syntaxhighlight lang=powerbasic>#COMPILE EXE |
||
#DIM ALL |
#DIM ALL |
||
Line 11,437: | Line 11,437: | ||
GOTO 3 |
GOTO 3 |
||
END IF |
END IF |
||
END FUNCTION</ |
END FUNCTION</syntaxhighlight> |
||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
{{works with|PowerShell|2}} |
{{works with|PowerShell|2}} |
||
< |
<syntaxhighlight lang=PowerShell> |
||
function PlaceQueen ( [ref]$Board, $Row, $N ) |
function PlaceQueen ( [ref]$Board, $Row, $N ) |
||
{ |
{ |
||
Line 11,501: | Line 11,501: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
< |
<syntaxhighlight lang=PowerShell> |
||
Get-NQueensBoard 8 |
Get-NQueensBoard 8 |
||
'' |
'' |
||
Line 11,510: | Line 11,510: | ||
'' |
'' |
||
Get-NQueensBoard 14 |
Get-NQueensBoard 14 |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 11,547: | Line 11,547: | ||
=={{header|Processing}}== |
=={{header|Processing}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang=java> |
||
int n = 8; |
int n = 8; |
||
int[] b = new int[n]; |
int[] b = new int[n]; |
||
Line 11,618: | Line 11,618: | ||
b[0] = -1; |
b[0] = -1; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
==={{header|Processing Python mode}}=== |
==={{header|Processing Python mode}}=== |
||
Line 11,625: | Line 11,625: | ||
This solution, originally by Raymond Hettinger for demonstrating the power of the itertools module, generates all solutions. |
This solution, originally by Raymond Hettinger for demonstrating the power of the itertools module, generates all solutions. |
||
< |
<syntaxhighlight lang=python>from itertools import permutations, product |
||
n = 8 |
n = 8 |
||
Line 11,653: | Line 11,653: | ||
global i |
global i |
||
i = (i + 1) % len(solutions) |
i = (i + 1) % len(solutions) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
Line 11,659: | Line 11,659: | ||
Solution #1: |
Solution #1: |
||
< |
<syntaxhighlight lang=Prolog>solution([]). |
||
solution([X/Y|Others]) :- |
solution([X/Y|Others]) :- |
||
Line 11,679: | Line 11,679: | ||
member(Item,Rest). |
member(Item,Rest). |
||
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).</ |
template([1/Y1,2/Y2,3/Y3,4/Y4,5/Y5,6/Y6,7/Y7,8/Y8]).</syntaxhighlight> |
||
Solution #2: |
Solution #2: |
||
< |
<syntaxhighlight lang=Prolog>solution(Queens) :- |
||
permutation([1,2,3,4,5,6,7,8], Queens), |
permutation([1,2,3,4,5,6,7,8], Queens), |
||
safe(Queens). |
safe(Queens). |
||
Line 11,709: | Line 11,709: | ||
Y-Y1=\=Xdist, |
Y-Y1=\=Xdist, |
||
Dist1 is Xdist + 1, |
Dist1 is Xdist + 1, |
||
noattack(Y,Ylist,Dist1).</ |
noattack(Y,Ylist,Dist1).</syntaxhighlight> |
||
Solution #3: |
Solution #3: |
||
< |
<syntaxhighlight lang=Prolog>solution(Ylist) :- |
||
sol(Ylist,[1,2,3,4,5,6,7,8], |
sol(Ylist,[1,2,3,4,5,6,7,8], |
||
[1,2,3,4,5,6,7,8], |
[1,2,3,4,5,6,7,8], |
||
Line 11,731: | Line 11,731: | ||
del(Item,[First|List],[First|List1]) :- |
del(Item,[First|List],[First|List1]) :- |
||
del(Item,List,List1).</ |
del(Item,List,List1).</syntaxhighlight> |
||
[http://ideone.com/Y6olN Output]: |
[http://ideone.com/Y6olN Output]: |
||
Line 11,739: | Line 11,739: | ||
===Alternative version=== |
===Alternative version=== |
||
Uses non-ISO predicates between/3 and select/3 (available in SWI Prolog and GNU Prolog). |
Uses non-ISO predicates between/3 and select/3 (available in SWI Prolog and GNU Prolog). |
||
< |
<syntaxhighlight lang=prolog>:- initialization(main). |
||
Line 11,754: | Line 11,754: | ||
main :- findall(Qs, (queens(8,Qs), write(Qs), nl), _), halt.</ |
main :- findall(Qs, (queens(8,Qs), write(Qs), nl), _), halt.</syntaxhighlight> |
||
[http://ideone.com/3bbIx0 Runs in: time: 0.02 memory: 68352] |
[http://ideone.com/3bbIx0 Runs in: time: 0.02 memory: 68352] |
||
Line 11,760: | Line 11,760: | ||
Uses backtracking- a highly efficient mechanism in Prolog to find all solutions. |
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}} |
{{works with|SWI Prolog|version 6.2.6 by Jan Wielemaker, University of Amsterdam}} |
||
< |
<syntaxhighlight lang=prolog>% 8 queens problem. |
||
% q(Row) represents a queen, allocated one per row. No rows ever clash. |
% q(Row) represents a queen, allocated one per row. No rows ever clash. |
||
% The columns are chosen iteratively from available columns held in a |
% The columns are chosen iteratively from available columns held in a |
||
Line 11,782: | Line 11,782: | ||
length(Boards, Len), writef('%w solutions:\n', [Len]), % Output solutions |
length(Boards, Len), writef('%w solutions:\n', [Len]), % Output solutions |
||
member(R,Boards), reverse(R,Board), writef(' - %w\n', [Board]), fail. |
member(R,Boards), reverse(R,Board), writef(' - %w\n', [Board]), fail. |
||
queens.</ |
queens.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>?- queens. |
<pre>?- queens. |
||
Line 11,799: | Line 11,799: | ||
===Short version=== |
===Short version=== |
||
SWI-Prolog 7.2.3 |
SWI-Prolog 7.2.3 |
||
< |
<syntaxhighlight lang=Prolog>not_diagonal(X, N) :- |
||
maplist(plus, X, N, Z1), maplist(plus, X, Z2, N), is_set(Z1), is_set(Z2). |
maplist(plus, X, N, Z1), maplist(plus, X, Z2, N), is_set(Z1), is_set(Z2). |
||
queens(N, Qs) :- |
queens(N, Qs) :- |
||
numlist(1, N, P), findall(Q, (permutation(P, Q), not_diagonal(Q, P)), Qs).</ |
numlist(1, N, P), findall(Q, (permutation(P, Q), not_diagonal(Q, P)), Qs).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 11,812: | Line 11,812: | ||
===SWISH Prolog version=== |
===SWISH Prolog version=== |
||
< |
<syntaxhighlight lang=Prolog> |
||
% John Devou: 26-Nov-2021 |
% John Devou: 26-Nov-2021 |
||
% Short solution to use on https://swish.swi-prolog.org/. |
% Short solution to use on https://swish.swi-prolog.org/. |
||
Line 11,823: | Line 11,823: | ||
not((member((U,V),Qs), (V =:= C; R-U =:= abs(C-V)))). |
not((member((U,V),Qs), (V =:= C; R-U =:= abs(C-V)))). |
||
q(N,X):- q(N,N,_,X). |
q(N,X):- q(N,N,_,X). |
||
</syntaxhighlight> |
|||
</lang> |
|||
===CLP(FD): Constraint Logic Programming over Finite Domains Version=== |
===CLP(FD): Constraint Logic Programming over Finite Domains Version=== |
||
Line 11,846: | Line 11,846: | ||
</ul> |
</ul> |
||
<br/> |
<br/> |
||
< |
<syntaxhighlight lang=Prolog>:- use_module(library(clpfd)). |
||
% DOC: http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html |
% DOC: http://www.pathwayslms.com/swipltuts/clpfd/clpfd.html |
||
Line 11,918: | Line 11,918: | ||
main :- |
main :- |
||
print_nqueens_all(8). |
print_nqueens_all(8). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 11,946: | Line 11,946: | ||
From the Pure (programming language) Wikipedia page |
From the Pure (programming language) Wikipedia page |
||
< |
<syntaxhighlight lang=pure>/* |
||
n-queens.pure |
n-queens.pure |
||
Tectonics: |
Tectonics: |
||
Line 11,964: | Line 11,964: | ||
compiling || (puts("queens 4: " + str(queens 4)) $$ |
compiling || (puts("queens 4: " + str(queens 4)) $$ |
||
puts("Solutions to queens 7: " + str(#queens 7)));</ |
puts("Solutions to queens 7: " + str(#queens 7)));</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 11,982: | Line 11,982: | ||
=={{header|PureBasic}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang=PureBasic>Global solutions |
||
Procedure showBoard(Array queenCol(1)) |
Procedure showBoard(Array queenCol(1)) |
||
Line 12,061: | Line 12,061: | ||
Input() |
Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
Sample output showing the last solution (all are actually displayed) for 1 - 12 queens: |
Sample output showing the last solution (all are actually displayed) for 1 - 12 queens: |
||
<pre style="height:40ex;overflow:scroll"> Solution 1 |
<pre style="height:40ex;overflow:scroll"> Solution 1 |
||
Line 12,184: | 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. |
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. |
||
< |
<syntaxhighlight lang=python>from itertools import permutations |
||
n = 8 |
n = 8 |
||
Line 12,191: | Line 12,191: | ||
if n == len(set(vec[i]+i for i in cols)) \ |
if n == len(set(vec[i]+i for i in cols)) \ |
||
== len(set(vec[i]-i for i in cols)): |
== len(set(vec[i]-i for i in cols)): |
||
print ( vec )</ |
print ( vec )</syntaxhighlight> |
||
The output is presented in vector form (each number represents the column position of a queen on consecutive rows). |
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: |
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: |
||
< |
<syntaxhighlight lang=python>def board(vec): |
||
print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec) + "\n===\n")</ |
print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec) + "\n===\n")</syntaxhighlight> |
||
Raymond's description is: |
Raymond's description is: |
||
Line 12,211: | Line 12,211: | ||
On a regular 8x8 board only 15,720 possible queen positions are examined. |
On a regular 8x8 board only 15,720 possible queen positions are examined. |
||
{{works with|Python|2.6, 3.x}} |
{{works with|Python|2.6, 3.x}} |
||
< |
<syntaxhighlight lang=python># From: http://wiki.python.org/moin/SimplePrograms, with permission from the author, Steve Howell |
||
BOARD_SIZE = 8 |
BOARD_SIZE = 8 |
||
Line 12,227: | Line 12,227: | ||
return solutions |
return solutions |
||
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</ |
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</syntaxhighlight> |
||
===Python: Simple Backtracking Solution=== |
===Python: Simple Backtracking Solution=== |
||
Line 12,233: | Line 12,233: | ||
to a generator expression) produces a backtracking solution. On a regular 8x8 board only 15,720 possible queen positions are examined. |
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}} |
{{works with|Python|2.6, 3.x}} |
||
< |
<syntaxhighlight lang=python>BOARD_SIZE = 8 |
||
def under_attack(col, queens): |
def under_attack(col, queens): |
||
Line 12,251: | Line 12,251: | ||
answers = solve(BOARD_SIZE) |
answers = solve(BOARD_SIZE) |
||
first_answer = next(answers) |
first_answer = next(answers) |
||
print(list(enumerate(first_answer, start=1)))</ |
print(list(enumerate(first_answer, start=1)))</syntaxhighlight> |
||
===Python: Simple Backtracking Solution (Niklaus Wirth Algorithm)=== |
===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. |
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. |
||
< |
<syntaxhighlight lang=python>def queens(n, i, a, b, c): |
||
if i < n: |
if i < n: |
||
for j in range(n): |
for j in range(n): |
||
Line 12,264: | Line 12,264: | ||
for solution in queens(8, 0, [], [], []): |
for solution in queens(8, 0, [], [], []): |
||
print(solution)</ |
print(solution)</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang=python>def queens(x, i, a, b, c): |
||
if a: # a is not empty |
if a: # a is not empty |
||
for j in a: |
for j in a: |
||
Line 12,275: | Line 12,275: | ||
for solution in queens([], 0, set(range(8)), set(), set()): |
for solution in queens([], 0, set(range(8)), set(), set()): |
||
print(solution)</ |
print(solution)</syntaxhighlight> |
||
===Python: backtracking on permutations=== |
===Python: backtracking on permutations=== |
||
Line 12,284: | 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]. |
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]. |
||
< |
<syntaxhighlight lang=python>def queens(n): |
||
a = list(range(n)) |
a = list(range(n)) |
||
up = [True]*(2*n - 1) |
up = [True]*(2*n - 1) |
||
Line 12,306: | Line 12,306: | ||
#Count solutions for n=8: |
#Count solutions for n=8: |
||
sum(1 for p in queens(8)) |
sum(1 for p in queens(8)) |
||
92</ |
92</syntaxhighlight> |
||
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. |
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: | 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. |
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. |
||
< |
<syntaxhighlight lang=python>def queens_lex(n): |
||
a = list(range(n)) |
a = list(range(n)) |
||
up = [True]*(2*n - 1) |
up = [True]*(2*n - 1) |
||
Line 12,342: | Line 12,342: | ||
#Compare to A065188 |
#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, ...</ |
#1, 3, 5, 2, 4, 9, 11, 13, 15, 6, 8, 19, 7, 22, 10, 25, 27, 29, 31, 12, 14, 35, 37, ...</syntaxhighlight> |
||
===Python: fold/reduce=== |
===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. |
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}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang=Python>'''N Queens problem''' |
||
from functools import reduce |
from functools import reduce |
||
Line 12,492: | Line 12,492: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>10 solutions for a 5 * 5 board: |
<pre>10 solutions for a 5 * 5 board: |
||
Line 12,518: | Line 12,518: | ||
{{works with|QBasic}} |
{{works with|QBasic}} |
||
{{trans|QB64}} |
{{trans|QB64}} |
||
< |
<syntaxhighlight lang=QBasic>DIM SHARED queens AS INTEGER |
||
CLS |
CLS |
||
COLOR 15 |
COLOR 15 |
||
Line 12,562: | Line 12,562: | ||
continue1: |
continue1: |
||
NEXT icol |
NEXT icol |
||
END SUB</ |
END SUB</syntaxhighlight> |
||
=={{header|QB64}}== |
=={{header|QB64}}== |
||
< |
<syntaxhighlight lang=QB64> |
||
DIM SHARED QUEENS AS INTEGER |
DIM SHARED QUEENS AS INTEGER |
||
PRINT "# of queens:";: INPUT QUEENS |
PRINT "# of queens:";: INPUT QUEENS |
||
Line 12,606: | Line 12,606: | ||
NEXT icol |
NEXT icol |
||
END SUB |
END SUB |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
Line 12,614: | Line 12,614: | ||
This solution uses recursive backtracking. |
This solution uses recursive backtracking. |
||
< |
<syntaxhighlight lang=r>queens <- function(n) { |
||
a <- seq(n) |
a <- seq(n) |
||
u <- rep(T, 2 * n - 1) |
u <- rep(T, 2 * n - 1) |
||
Line 12,641: | Line 12,641: | ||
aux(1) |
aux(1) |
||
m |
m |
||
}</ |
}</syntaxhighlight> |
||
Show the first solution found for size 8 as a permutation matrix. |
Show the first solution found for size 8 as a permutation matrix. |
||
< |
<syntaxhighlight lang=R>library(Matrix) |
||
a <- queens(8) |
a <- queens(8) |
||
as(a[, 1], "pMatrix")</ |
as(a[, 1], "pMatrix")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 12,664: | Line 12,664: | ||
Count solutions for board size 4 to 12. |
Count solutions for board size 4 to 12. |
||
< |
<syntaxhighlight lang=R>sapply(4:12, function(n) ncol(queens(n)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 12,674: | Line 12,674: | ||
Backtracking algorithm; returns one solution |
Backtracking algorithm; returns one solution |
||
< |
<syntaxhighlight lang=racket> |
||
#lang racket |
#lang racket |
||
Line 12,705: | Line 12,705: | ||
(nqueens 8) |
(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)) |
; => (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> |
|||
</lang> |
|||
Show result with "How to Design Programs" GUI. |
Show result with "How to Design Programs" GUI. |
||
< |
<syntaxhighlight lang=racket> |
||
(require htdp/show-queen) |
(require htdp/show-queen) |
||
Line 12,719: | Line 12,719: | ||
(show-nqueens 8) |
(show-nqueens 8) |
||
</syntaxhighlight> |
|||
</lang> |
|||
[[image:Racket-nqueens.png]] |
[[image:Racket-nqueens.png]] |
||
Line 12,731: | Line 12,731: | ||
Computes all solutions. |
Computes all solutions. |
||
< |
<syntaxhighlight lang=racket> |
||
#lang racket |
#lang racket |
||
Line 12,777: | Line 12,777: | ||
'() qss-so-far))) |
'() qss-so-far))) |
||
(lazy-filter valid? all-possible-solutions)) |
(lazy-filter valid? all-possible-solutions)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Taking the first solution does not compute the other solutions: |
Taking the first solution does not compute the other solutions: |
||
< |
<syntaxhighlight lang=racket> |
||
(car (nqueens 8)) |
(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)) |
;; => (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> |
|||
</lang> |
|||
Computing all solutions is also possible: |
Computing all solutions is also possible: |
||
< |
<syntaxhighlight lang=racket> |
||
(define (force-and-print qs) |
(define (force-and-print qs) |
||
(define forced (force qs)) |
(define forced (force qs)) |
||
Line 12,806: | 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 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)) |
;(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> |
|||
</lang> |
|||
Logic borrowed from the Ruby example |
Logic borrowed from the Ruby example |
||
< |
<syntaxhighlight lang=racket> |
||
#lang racket |
#lang racket |
||
(define (remove x lst) |
(define (remove x lst) |
||
Line 12,866: | Line 12,866: | ||
(define (print-queens n) |
(define (print-queens n) |
||
(for ([x (queens n)]) (displayln (string-join x)))) |
(for ([x (queens n)]) (displayln (string-join x)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 12,873: | Line 12,873: | ||
Neither pretty nor efficient, a simple backtracking solution |
Neither pretty nor efficient, a simple backtracking solution |
||
< |
<syntaxhighlight lang=perl6>sub MAIN(\N = 8) { |
||
sub collision(@field, $row) { |
sub collision(@field, $row) { |
||
for ^$row -> $i { |
for ^$row -> $i { |
||
Line 12,896: | Line 12,896: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[0 4 7 5 2 6 1 3]</pre> |
<pre>[0 4 7 5 2 6 1 3]</pre> |
||
Line 12,902: | Line 12,902: | ||
=={{header|Rascal}}== |
=={{header|Rascal}}== |
||
< |
<syntaxhighlight lang=Rascal>import Prelude; |
||
public set[list[int]] Nqueens(int n){ |
public set[list[int]] Nqueens(int n){ |
||
Line 12,911: | Line 12,911: | ||
result += vector;} |
result += vector;} |
||
return result; |
return result; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 12,920: | Line 12,920: | ||
About half of the REXX code involves presentation (and colorization achieved through dithering) of the chessboard and queens. |
About half of the REXX code involves presentation (and colorization achieved through dithering) of the chessboard and queens. |
||
< |
<syntaxhighlight lang=rexx>/*REXX program places N queens on an NxN chessboard (the eight queens problem). */ |
||
parse arg N . /*obtain optional argument from the CL.*/ |
parse arg N . /*obtain optional argument from the CL.*/ |
||
if N=='' | N=="," then N= 8 /*Not specified: Then use the default.*/ |
if N=='' | N=="," then N= 8 /*Not specified: Then use the default.*/ |
||
Line 12,969: | Line 12,969: | ||
say pad _ || bar /*show a single rank of the board.*/ |
say pad _ || bar /*show a single rank of the board.*/ |
||
end /*rank*/ /*80 cols can view a 19x19 board.*/ |
end /*rank*/ /*80 cols can view a 19x19 board.*/ |
||
say pad translate('╚'g"╝", '╩', "╬"); return /*display the last rank (of board)*/</ |
say pad translate('╚'g"╝", '╩', "╬"); return /*display the last rank (of board)*/</syntaxhighlight> |
||
{{out|output|text= when using the default of an '''8'''<small>x</small>'''8''' chessboard:}} |
{{out|output|text= when using the default of an '''8'''<small>x</small>'''8''' chessboard:}} |
||
<pre> |
<pre> |
||
Line 13,040: | Line 13,040: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang=ring> |
||
// Bert Mariani 2020-07-17 |
// Bert Mariani 2020-07-17 |
||
Line 13,089: | Line 13,089: | ||
//================================ |
//================================ |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 13,112: | Line 13,112: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang=ring> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
load "guilib.ring" |
load "guilib.ring" |
||
Line 13,801: | Line 13,801: | ||
###============================================================ |
###============================================================ |
||
</syntaxhighlight> |
|||
</lang> |
|||
[https://www.mediafire.com/file/53bxu7kpuc4tlx5/Images.zip/file Necessary images] |
[https://www.mediafire.com/file/53bxu7kpuc4tlx5/Images.zip/file Necessary images] |
||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
This implements the heuristics found on the wikipedia page to return just one solution |
This implements the heuristics found on the wikipedia page to return just one solution |
||
< |
<syntaxhighlight lang=ruby># 1. Divide n by 12. Remember the remainder (n is 8 for the eight queens |
||
# puzzle). |
# puzzle). |
||
# 2. Write a list of the even numbers from 2 to n in order. |
# 2. Write a list of the even numbers from 2 to n in order. |
||
Line 13,862: | Line 13,862: | ||
end |
end |
||
(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}</ |
(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 14,016: | Line 14,016: | ||
===Alternate solution=== |
===Alternate solution=== |
||
If there is not specification, it outputs all solutions. |
If there is not specification, it outputs all solutions. |
||
< |
<syntaxhighlight lang=ruby>class Queen |
||
attr_reader :count |
attr_reader :count |
||
Line 14,054: | Line 14,054: | ||
puts @frame |
puts @frame |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
'''Example:''' |
'''Example:''' |
||
< |
<syntaxhighlight lang=ruby>(1..6).each do |n| |
||
puzzle = Queen.new(n) |
puzzle = Queen.new(n) |
||
puts " #{n} Queen : #{puzzle.count}" |
puts " #{n} Queen : #{puzzle.count}" |
||
Line 14,065: | Line 14,065: | ||
puzzle = Queen.new(n, false) # do not display |
puzzle = Queen.new(n, false) # do not display |
||
puts " #{n} Queen : #{puzzle.count}" |
puts " #{n} Queen : #{puzzle.count}" |
||
end</ |
end</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 14,201: | Line 14,201: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
< |
<syntaxhighlight lang=runbasic>[loop] |
||
input "How many queens (N>=4)";n |
input "How many queens (N>=4)";n |
||
if n < 4 then |
if n < 4 then |
||
Line 14,312: | Line 14,312: | ||
end if |
end if |
||
end if |
end if |
||
next</ |
next</syntaxhighlight> |
||
<pre>abcdefgh |
<pre>abcdefgh |
||
* 8 |
* 8 |
||
Line 14,324: | Line 14,324: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang=rust>const N: usize = 8; |
||
fn try(mut board: &mut [[bool; N]; N], row: usize, mut count: &mut i64) { |
fn try(mut board: &mut [[bool; N]; N], row: usize, mut count: &mut i64) { |
||
Line 14,356: | Line 14,356: | ||
try (&mut board, 0, &mut count); |
try (&mut board, 0, &mut count); |
||
println!("Found {} solutions", count) |
println!("Found {} solutions", count) |
||
}</ |
}</syntaxhighlight> |
||
===Using Iterators=== |
===Using Iterators=== |
||
Solution to the puzzle using an iterator that yields the 92 solutions for 8 queens. |
Solution to the puzzle using an iterator that yields the 92 solutions for 8 queens. |
||
< |
<syntaxhighlight lang=rust>use std::collections::LinkedList; |
||
use std::iter::IntoIterator; |
use std::iter::IntoIterator; |
||
Line 14,436: | Line 14,436: | ||
str |
str |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|SAS}}== |
=={{header|SAS}}== |
||
< |
<syntaxhighlight lang=sas>/* Store all 92 permutations in a SAS dataset. Translation of Fortran 77 */ |
||
data queens; |
data queens; |
||
array a{8} p1-p8; |
array a{8} p1-p8; |
||
Line 14,496: | Line 14,496: | ||
put n m; |
put n m; |
||
keep p1-p8; |
keep p1-p8; |
||
run;</ |
run;</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Line 14,504: | Line 14,504: | ||
Lazily generates permutations with an <code>Iterator</code>. |
Lazily generates permutations with an <code>Iterator</code>. |
||
< |
<syntaxhighlight lang=scala> |
||
object NQueens { |
object NQueens { |
||
Line 14,554: | Line 14,554: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
Line 14,585: | Line 14,585: | ||
This is a simple breadth-first technique to retrieve all solutions. |
This is a simple breadth-first technique to retrieve all solutions. |
||
< |
<syntaxhighlight lang=scheme> |
||
(import (scheme base) |
(import (scheme base) |
||
(scheme write) |
(scheme write) |
||
Line 14,660: | Line 14,660: | ||
(pretty-print (n-queens 5) 5) |
(pretty-print (n-queens 5) 5) |
||
(pretty-print (n-queens 8) 8) |
(pretty-print (n-queens 8) 8) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 14,875: | Line 14,875: | ||
string(Board_size)+"x"+string(Board_size)+" board."); |
string(Board_size)+"x"+string(Board_size)+" board."); |
||
//Time elapsed |
//Time elapsed |
||
disp("Time: "+string(toc())+"s.");</ |
disp("Time: "+string(toc())+"s.");</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 14,884: | Line 14,884: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang=seed7>$ include "seed7_05.s7i"; |
||
var array integer: board is 8 times 0; |
var array integer: board is 8 times 0; |
||
Line 14,934: | Line 14,934: | ||
end if; |
end if; |
||
end while; |
end while; |
||
end func;</ |
end func;</syntaxhighlight> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
< |
<syntaxhighlight lang=ruby>func N_queens_solution(N = 8) { |
||
func collision(field, row) { |
func collision(field, row) { |
||
Line 14,968: | Line 14,968: | ||
for n in (1..15) { |
for n in (1..15) { |
||
say "#{'%2d' % n}: #{N_queens_solution(n) || 'No solution'}" |
say "#{'%2d' % n}: #{N_queens_solution(n) || 'No solution'}" |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 14,989: | Line 14,989: | ||
=={{header|SNOBOL4}}== |
=={{header|SNOBOL4}}== |
||
< |
<syntaxhighlight lang=SNOBOL4> |
||
* N queens problem |
* N queens problem |
||
* Set N to the desired number. The program prints out all solution boards. |
* Set N to the desired number. The program prints out all solution boards. |
||
Line 15,013: | Line 15,013: | ||
PRTLOOP B LEN(NP1) . OUTPUT = :S(PRTLOOP)F(RETURN) |
PRTLOOP B LEN(NP1) . OUTPUT = :S(PRTLOOP)F(RETURN) |
||
END |
END |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Sparkling}}== |
=={{header|Sparkling}}== |
||
This is somewhat a transliteration of the "shortened" C++ code above. |
This is somewhat a transliteration of the "shortened" C++ code above. |
||
< |
<syntaxhighlight lang=sparkling>let print_table = function (pos) { |
||
pos.foreach(function (_, i) { |
pos.foreach(function (_, i) { |
||
stdout.printf(" %c", 'a' + i); |
stdout.printf(" %c", 'a' + i); |
||
Line 15,071: | Line 15,071: | ||
}; |
}; |
||
stdout.printf("%d solutions\n", n_queens(range(8), 0));</ |
stdout.printf("%d solutions\n", n_queens(range(8), 0));</syntaxhighlight> |
||
=={{header|SQL}}== |
=={{header|SQL}}== |
||
Line 15,077: | 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 |
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 |
||
< |
<syntaxhighlight lang=SQL> |
||
WITH RECURSIVE |
WITH RECURSIVE |
||
positions(i) as ( |
positions(i) as ( |
||
Line 15,108: | Line 15,108: | ||
SELECT board,n_queens FROM solutions WHERE n_queens = 8; |
SELECT board,n_queens FROM solutions WHERE n_queens = 8; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|SQL PL}}== |
=={{header|SQL PL}}== |
||
{{works with|Db2 LUW}} version 9.7 or higher. |
{{works with|Db2 LUW}} version 9.7 or higher. |
||
With SQL PL: |
With SQL PL: |
||
< |
<syntaxhighlight lang=sql pl> |
||
-- A column of a matrix. |
-- A column of a matrix. |
||
CREATE TYPE INTEGER_ARRAY AS INTEGER ARRAY[]@ |
CREATE TYPE INTEGER_ARRAY AS INTEGER ARRAY[]@ |
||
Line 15,392: | Line 15,392: | ||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 15,431: | Line 15,431: | ||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
This implementation uses failure continuations for backtracking. |
This implementation uses failure continuations for backtracking. |
||
< |
<syntaxhighlight lang=Standard ML> |
||
(* |
(* |
||
* val threat : (int * int) -> (int * int) -> bool |
* val threat : (int * int) -> (int * int) -> bool |
||
Line 15,471: | Line 15,471: | ||
(* NONE *) |
(* NONE *) |
||
queens(2); |
queens(2); |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
Line 15,477: | Line 15,477: | ||
Adapted from the Fortran 77 program, to illustrate the '''[http://www.stata.com/help.cgi?m2_goto goto]''' statement in Stata. |
Adapted from the Fortran 77 program, to illustrate the '''[http://www.stata.com/help.cgi?m2_goto goto]''' statement in Stata. |
||
< |
<syntaxhighlight lang=stata>mata |
||
real matrix queens(real scalar n) { |
real matrix queens(real scalar n) { |
||
real scalar i, j, k, p, q |
real scalar i, j, k, p, q |
||
Line 15,534: | Line 15,534: | ||
rows(a) |
rows(a) |
||
92 |
92 |
||
end</ |
end</syntaxhighlight> |
||
It's also possible to save the solutions to a Stata dataset: |
It's also possible to save the solutions to a Stata dataset: |
||
< |
<syntaxhighlight lang=stata>clear |
||
mata: a=queens(8) |
mata: a=queens(8) |
||
getmata (a*)=a |
getmata (a*)=a |
||
save queens, replace</ |
save queens, replace</syntaxhighlight> |
||
=== Recursive version === |
=== Recursive version === |
||
Line 15,547: | Line 15,547: | ||
The recursive solution is adapted from one of the Python programs. |
The recursive solution is adapted from one of the Python programs. |
||
< |
<syntaxhighlight lang=stata>mata |
||
real matrix queens_rec(real scalar n) { |
real matrix queens_rec(real scalar n) { |
||
real rowvector a, u, v |
real rowvector a, u, v |
||
Line 15,583: | Line 15,583: | ||
} |
} |
||
} |
} |
||
end</ |
end</syntaxhighlight> |
||
The iterative and the recursive programs are equivalent: |
The iterative and the recursive programs are equivalent: |
||
< |
<syntaxhighlight lang=stata>queens(8) == queens_rec(8) |
||
1</ |
1</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
Port of the optimized C code above |
Port of the optimized C code above |
||
< |
<syntaxhighlight lang=Swift> |
||
let maxn = 31 |
let maxn = 31 |
||
Line 15,650: | Line 15,650: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|SystemVerilog}}== |
=={{header|SystemVerilog}}== |
||
Create a random board configuration, with the 8-queens as a constraint |
Create a random board configuration, with the 8-queens as a constraint |
||
< |
<syntaxhighlight lang=SystemVerilog>program N_queens; |
||
parameter SIZE_LOG2 = 3; |
parameter SIZE_LOG2 = 3; |
||
Line 15,691: | Line 15,691: | ||
endprogram |
endprogram |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Tailspin}}== |
=={{header|Tailspin}}== |
||
A functional-ish solution utilising tailspin's data flows |
A functional-ish solution utilising tailspin's data flows |
||
< |
<syntaxhighlight lang=tailspin> |
||
templates queens |
templates queens |
||
def n: $; |
def n: $; |
||
Line 15,727: | Line 15,727: | ||
'For 3 queens there are $:[3 -> queens] -> $::length; solutions |
'For 3 queens there are $:[3 -> queens] -> $::length; solutions |
||
' -> !OUT::write |
' -> !OUT::write |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 15,736: | Line 15,736: | ||
A solution using state to find one solution if any exist |
A solution using state to find one solution if any exist |
||
< |
<syntaxhighlight lang=tailspin> |
||
templates queens |
templates queens |
||
def n: $; |
def n: $; |
||
Line 15,785: | Line 15,785: | ||
'A solution to the 3 queens problem is $:3 -> queens; |
'A solution to the 3 queens problem is $:3 -> queens; |
||
' -> !OUT::write |
' -> !OUT::write |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 15,797: | Line 15,797: | ||
{{works with|Tcl|8.5}} |
{{works with|Tcl|8.5}} |
||
< |
<syntaxhighlight lang=tcl>package require Tcl 8.5 |
||
proc unsafe {y} { |
proc unsafe {y} { |
||
Line 15,843: | Line 15,843: | ||
} |
} |
||
main [expr {$argc ? int(0+[lindex $argv 0]) : 8}]</ |
main [expr {$argc ? int(0+[lindex $argv 0]) : 8}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>$ tclsh8.5 8queens.tcl 6 |
<pre>$ tclsh8.5 8queens.tcl 6 |
||
Line 15,886: | 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. |
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. |
||
< |
<syntaxhighlight lang=bash>#!/bin/bash |
||
# variable declaration |
# variable declaration |
||
Line 15,963: | Line 15,963: | ||
work |
work |
||
out |
out |
||
depose</ |
depose</syntaxhighlight> |
||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
Line 15,969: | Line 15,969: | ||
n is a number greater than 3. Multiple solutions may be reported |
n is a number greater than 3. Multiple solutions may be reported |
||
but reflections and rotations thereof are omitted. |
but reflections and rotations thereof are omitted. |
||
< |
<syntaxhighlight lang=Ursala>#import std |
||
#import nat |
#import nat |
||
Line 15,986: | Line 15,986: | ||
-<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS, |
-<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS, |
||
^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-, |
^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-, |
||
^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-</ |
^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-</syntaxhighlight> |
||
The output shows one solution on each line. |
The output shows one solution on each line. |
||
A solution is reported as a sequence of <math>n</math> numbers |
A solution is reported as a sequence of <math>n</math> numbers |
||
Line 16,004: | Line 16,004: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
< |
<syntaxhighlight lang=vb>'N-queens problem - non recursive & structured - vba - 26/02/2017 |
||
Sub n_queens() |
Sub n_queens() |
||
Const l = 15 'number of queens |
Const l = 15 'number of queens |
||
Line 16,061: | Line 16,061: | ||
Debug.Print n, m 'number of queens, number of solutions |
Debug.Print n, m 'number of queens, number of solutions |
||
Next n |
Next n |
||
End Sub 'n_queens</ |
End Sub 'n_queens</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 16,084: | Line 16,084: | ||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
To have the solutions printed (raw format) uncomment the ad hoc statement. |
To have the solutions printed (raw format) uncomment the ad hoc statement. |
||
< |
<syntaxhighlight lang=vb>'N-queens problem - non recursive & structured - vbs - 24/02/2017 |
||
const l=15 |
const l=15 |
||
dim a(),s(),u(): redim a(l),s(l),u(4*l-2) |
dim a(),s(),u(): redim a(l),s(l),u(4*l-2) |
||
Line 16,129: | Line 16,129: | ||
Loop Until i=0 |
Loop Until i=0 |
||
wscript.echo n &":"& m |
wscript.echo n &":"& m |
||
next 'n</ |
next 'n</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 16,152: | Line 16,152: | ||
{{works with|Visual Basic|VB6 Standard}} |
{{works with|Visual Basic|VB6 Standard}} |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
< |
<syntaxhighlight lang=vb>'N-queens problem - non recursive & structured - vb6 - 25/02/2017 |
||
Sub n_queens() |
Sub n_queens() |
||
Const l = 15 'number of queens |
Const l = 15 'number of queens |
||
Line 16,209: | Line 16,209: | ||
Debug.Print n, m 'number of queens, number of solutions |
Debug.Print n, m 'number of queens, number of solutions |
||
Next n |
Next n |
||
End Sub 'n_queens</ |
End Sub 'n_queens</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 16,231: | Line 16,231: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
< |
<syntaxhighlight lang=vb>'N-queens problem - non recursive & structured - vb.net - 26/02/2017 |
||
Module Mod_n_queens |
Module Mod_n_queens |
||
Sub n_queens() |
Sub n_queens() |
||
Line 16,291: | Line 16,291: | ||
Next n |
Next n |
||
End Sub 'n_queens |
End Sub 'n_queens |
||
End Module</ |
End Module</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 16,312: | Line 16,312: | ||
=={{header|Wart}}== |
=={{header|Wart}}== |
||
< |
<syntaxhighlight lang=Wart>def (nqueens n queens) |
||
prn "step: " queens # show progress |
prn "step: " queens # show progress |
||
if (len.queens = n) |
if (len.queens = n) |
||
Line 16,335: | Line 16,335: | ||
def (diagonal_match curr other) |
def (diagonal_match curr other) |
||
(= (abs (curr.0 - other.0)) |
(= (abs (curr.0 - other.0)) |
||
(abs (curr.1 - other.1)))</ |
(abs (curr.1 - other.1)))</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Kotlin}} |
{{trans|Kotlin}} |
||
Very slow for the larger boards. |
Very slow for the larger boards. |
||
< |
<syntaxhighlight lang=ecmascript>var count = 0 |
||
var c = [] |
var c = [] |
||
var f = [] |
var f = [] |
||
Line 16,377: | Line 16,377: | ||
if (count > 0) System.print(" First is %(f)") |
if (count > 0) System.print(" First is %(f)") |
||
System.print() |
System.print() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 16,439: | Line 16,439: | ||
Copied from http://www.cs.bu.edu/~hwxi/Xanadu/Examples/ |
Copied from http://www.cs.bu.edu/~hwxi/Xanadu/Examples/ |
||
< |
<syntaxhighlight lang=Xanadu> |
||
int abs(i: int) { |
int abs(i: int) { |
||
if (i >= 0) return i; else return -i; |
if (i >= 0) return i; else return -i; |
||
Line 16,508: | Line 16,508: | ||
int main () { |
int main () { |
||
return queen (8); |
return queen (8); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
[[File:NQueensXPL0.GIF|right]] |
[[File:NQueensXPL0.GIF|right]] |
||
< |
<syntaxhighlight lang=XPL0>def N=8; \board size (NxN) |
||
int R, C; \row and column of board |
int R, C; \row and column of board |
||
char B(N,N); \board |
char B(N,N); \board |
||
Line 16,568: | Line 16,568: | ||
C:= 0; \start at left column |
C:= 0; \start at left column |
||
Try; |
Try; |
||
]</ |
]</syntaxhighlight> |
||
=={{header|XSLT}}== |
=={{header|XSLT}}== |
||
Line 16,580: | Line 16,580: | ||
83162574 |
83162574 |
||
84136275 |
84136275 |
||
</syntaxhighlight> |
|||
</lang> |
|||
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]] |
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: | 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]] |
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]] |
||
< |
<syntaxhighlight lang=xml> |
||
<!-- 8-queens.xsl disguised as XML file for the browsers --> |
<!-- 8-queens.xsl disguised as XML file for the browsers --> |
||
Line 16,726: | Line 16,726: | ||
</xsl:stylesheet> |
</xsl:stylesheet> |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
< |
<syntaxhighlight lang=Yabasic>DOCU The N Queens Problem: |
||
DOCU Place N Queens on an NxN chess board |
DOCU Place N Queens on an NxN chess board |
||
DOCU such that they don't threaten each other. |
DOCU such that they don't threaten each other. |
||
Line 16,793: | Line 16,793: | ||
wend |
wend |
||
end sub |
end sub |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Zig}}== |
=={{header|Zig}}== |
||
Outputs all 92 solutions. |
Outputs all 92 solutions. |
||
< |
<syntaxhighlight lang=Zig> |
||
const std = @import("std"); |
const std = @import("std"); |
||
const stdout = std.io.getStdOut().outStream(); |
const stdout = std.io.getStdOut().outStream(); |
||
Line 16,838: | Line 16,838: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre> |
<pre> |
||
Line 16,851: | Line 16,851: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
Modified from a Haskell version (if I remember correctly) |
Modified from a Haskell version (if I remember correctly) |
||
< |
<syntaxhighlight lang=zkl>fcn isAttacked(q, x,y) // ( (r,c), x,y ) : is queen at r,c attacked by q@(x,y)? |
||
{ r,c:=q; (r==x or c==y or r+c==x+y or r-c==x-y) } |
{ 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 |
fcn isSafe(r,c,qs) // queen safe at (r,c)?, qs=( (r,c),(r,c)..) solution so far |
||
Line 16,860: | Line 16,860: | ||
if (row == N) return(qs); |
if (row == N) return(qs); |
||
return(qs.apply(self.fcn.fp(N,row+1)).flatten()); |
return(qs.apply(self.fcn.fp(N,row+1)).flatten()); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang=zkl>queens := queensN(4); |
||
println(queens.len()," solution(s):"); |
println(queens.len()," solution(s):"); |
||
queens.apply2(Console.println);</ |
queens.apply2(Console.println);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |