N-queens problem: Difference between revisions
(→Alternate Fortran 77 solution: + output) |
|||
Line 803: | Line 803: | ||
=={{header|D}}== |
=={{header|D}}== |
||
From the C solution. |
From the C solution. |
||
<lang d>import std.stdio: write, writeln |
<lang d>import std.stdio: write, writeln; |
||
enum int SIDE = 8; |
enum int SIDE = 8; |
||
int[SIDE] |
int[SIDE] board; |
||
bool unsafe(int y) { |
nothrow bool unsafe(int y) { |
||
int x = |
immutable int x = board[y]; |
||
foreach (i; 1 .. y+1) { |
foreach (i; 1 .. y+1) { |
||
int t = |
int t = board[y - i]; |
||
if ((t == x) || (t == x - i) || (t == x + i)) |
if ((t == x) || (t == x - i) || (t == x + i)) |
||
return true; |
return true; |
||
Line 819: | Line 819: | ||
} |
} |
||
void |
void showBoard() { |
||
static int s = 0; |
static int s = 0; |
||
writeln("\nSolution #", ++s); |
|||
foreach (y; 0 .. SIDE) { |
foreach (y; 0 .. SIDE) { |
||
foreach (x; 0 .. SIDE) |
foreach (x; 0 .. SIDE) |
||
write( |
write(board[y] == x ? '*' : '.'); |
||
writeln( |
writeln(); |
||
} |
} |
||
} |
} |
||
Line 831: | Line 831: | ||
void main() { |
void main() { |
||
int y = 0; |
int y = 0; |
||
board[0] = -1; |
|||
while (y >= 0) { |
while (y >= 0) { |
||
do { |
do { |
||
board[y]++; |
|||
} while ( |
} while (board[y] < SIDE && unsafe(y)); |
||
if (b[y] < SIDE) { |
|||
if (board[y] < SIDE) { |
|||
if (y < (SIDE - 1)) |
|||
board[++y] = -1; |
|||
else |
|||
showBoard(); |
|||
} else |
} else |
||
y--; |
y--; |
||
} |
|||
} |
} |
||
}</lang> |
}</lang> |
||
⚫ | |||
⚫ | |||
<lang d>auto nqueens(int base) { |
<lang d>auto nqueens(int base) { |
||
int total = base * base; |
int total = base * base; |
Revision as of 10:04, 27 December 2010
You are encouraged to solve this task according to the task description, using any language you may know.
Solve the eight queens puzzle. You can extend the problem to solve the puzzle with a board of side NxN.
Ada
<lang Ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Queens is
Board : array (1..8, 1..8) of Boolean := (others => (others => False)); function Test (Row, Column : Integer) return Boolean is begin for J in 1..Column - 1 loop if ( Board (Row, J) or else (Row > J and then Board (Row - J, Column - J)) or else (Row + J <= 8 and then Board (Row + J, Column - J)) ) then return False; end if; end loop; return True; end Test; function Fill (Column : Integer) return Boolean is begin for Row in Board'Range (1) loop if Test (Row, Column) then Board (Row, Column) := True; if Column = 8 or else Fill (Column + 1) then return True; end if; Board (Row, Column) := False; end if; end loop; return False; end Fill;
begin
if not Fill (1) then raise Program_Error; end if; for I in Board'Range (1) loop Put (Integer'Image (9 - I)); for J in Board'Range (2) loop if Board (I, J) then Put ("|Q"); elsif (I + J) mod 2 = 1 then Put ("|/"); else Put ("| "); end if; end loop; Put_Line ("|"); end loop; Put_Line (" A B C D E F G H");
end Queens;</lang> Sample output:
8|Q|/| |/| |/| |/| 7|/| |/| |/| |Q| | 6| |/| |/|Q|/| |/| 5|/| |/| |/| |/|Q| 4| |Q| |/| |/| |/| 3|/| |/|Q|/| |/| | 2| |/| |/| |Q| |/| 1|/| |Q| |/| |/| | A B C D E F G H
ALGOL 68
<lang Algol68>INT ofs = 1, # Algol68 normally uses array offset of 1 #
dim = 8; # dim X dim chess board #
[ofs:dim+ofs-1]INT b;
PROC unsafe = (INT y)BOOL:(
INT i, t, x; x := b[y]; FOR i TO y - LWB b DO t := b[y - i]; IF t = x THEN break true ELIF t = x - i THEN break true ELIF t = x + i THEN break true FI OD; FALSE EXIT
break true:
TRUE
);
INT s := 0;
PROC print board = VOID:(
INT x, y; print((new line, "Solution # ", s+:=1, new line)); FOR y FROM LWB b TO UPB b DO FOR x FROM LWB b TO UPB b DO print("|"+(b[y]=x|"Q"|: ODD(x+y)|"/"|" ")) OD; print(("|", new line)) OD
);
main: (
INT y := LWB b; b[LWB b] := LWB b - 1; FOR i WHILE y >= LWB b DO WHILE b[y]+:=1; # BREAK # IF b[y] <= UPB b THEN unsafe(y) ELSE FALSE FI DO SKIP OD; IF b[y] <= UPB b THEN IF y < UPB b THEN b[y+:=1] := LWB b - 1 ELSE print board FI ELSE y-:=1 FI OD
)</lang>
AutoHotkey
Output to formatted Message box
<lang AutoHotkey>;
- Post
- http://www.autohotkey.com/forum/viewtopic.php?p=353059#353059
- Timestamp
- 05/may/2010
MsgBox % funcNQP(5) MsgBox % funcNQP(8)
Return
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
- ** USED VARIABLES **
- Global
- All variables named Array[???]
- Function funcNPQ
- nQueens , OutText , qIndex
- Function Unsafe
- nIndex , Idx , Tmp , Aux
- Function PutBoard
- Output , QueensN , Stc , xxx , yyy
- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
funcNQP(nQueens) {
Global Array[0] := -1 Local OutText , qIndex := 0 While ( qIndex >= 0 ) { Array[%qIndex%]++ While ( (Array[%qIndex%] < nQueens) && Unsafe(qIndex) ) Array[%qIndex%]++ If ( Array[%qIndex%] < nQueens ) { If ( qIndex < nQueens-1 ) qIndex++ , Array[%qIndex%] := -1 Else PutBoard(OutText,nQueens) } Else qIndex-- } Return OutText
}
- ------------------------------------------
Unsafe(nIndex) {
Global Local Idx := 1 , Tmp := 0 , Aux := Array[%nIndex%] While ( Idx <= nIndex ) { Tmp := "Array[" nIndex - Idx "]" Tmp := % %Tmp% If ( ( Tmp = Aux ) || ( Tmp = Aux-Idx ) || ( Tmp = Aux+Idx ) ) Return 1 Idx++ } Return 0
}
- ------------------------------------------
PutBoard(ByRef Output,QueensN) {
Global Static Stc = 0 Local xxx := 0 , yyy := 0 Output .= "`n`nSolution #" (++Stc) "`n" While ( yyy < QueensN ) { xxx := 0 While ( xxx < QueensN ) Output .= ( "|" ( ( Array[%yyy%] = xxx ) ? "Q" : "_" ) ) , xxx++ Output .= "|`n" , yyy++ }
}</lang>
Includes a solution browser GUI
This implementation supports N = 4..12 queens, and will find ALL solutions for each of the different sizes. The screenshot shows the first solution of 10 possible solutions for N = 5 queens. <lang AutoHotkey>N := 5 Number: ; main entrance for different # of queens
SI := 1 Progress b2 w250 zh0 fs9, Calculating all solutions for %N% Queens ... Gosub GuiCreate Result := SubStr(Queens(N),2) Progress Off Gui Show,,%N%-Queens StringSplit o, Result, `n
Fill: ; show solutions
GuiControl,,SI, %SI% / %o0% Loop Parse, o%SI%, `, { C := A_Index Loop %N% GuiControl,,%C%_%A_Index% ; clear fields GuiControl,,%C%_%A_LoopField%, r }
Return ;-----------------------------------------------------------------------
Queens(N) { ; Size of the board
Local c, O ; global array r r1 := 1, c := 2, r2 := 3, O := "" ; init: r%c% = row of Queen in column c
Right: ; move to next column If (c = N) { ; found solution Loop %N% ; save row indices of Queens O .= (A_Index = 1 ? "`n" : ",") r%A_Index% GOTO % --c ? "Down" : "OUT" ; for ALL solutions } c++, r%c% := 1 ; next column, top row GoTo % BAD(c) ? "Down" : "Right" Down: ; move down to next row If (r%c% = N) GoTo % --c ? "Down" : "OUT" r%c%++ ; row down GoTo % BAD(c) ? "Down" : "Right" OUT: Return O
} ;----------------------------------------------------------------------------
BAD(c) { ; Check placed Queens against Queen in row r%c%, column c
Loop % c-1 If (r%A_Index% = r%c% || ABS(r%A_Index%-r%c%) = c-A_Index) Return 1
} ;----------------------------------------------------------------------------
GuiCreate: ; Draw chess board
Gui Margin, 20, 15 Gui Font, s16, Marlett Loop %N% { C := A_Index Loop %N% { ; fields R := A_Index, X := 40*C-17, Y := 40*R-22 Gui Add, Progress, x%X% y%Y% w41 h41 Cdddddd, % 100*(R+C & 1) ;% shade fields Gui Add, Text, x%X% y%Y% w41 h41 BackGroundTrans Border Center 0x200 v%C%_%R% } } Gui Add, Button, x%x% w43 h25 gBF, 4 ; forth (default) Gui Add, Button,xm yp w43 h25 gBF, 3 ; back
Gui Font, bold, Comic Sans MS Gui Add, Text,% "x62 yp hp Center 0x200 vSI w" 40*N-80
Menu FileMenu, Add, E&xit, GuiClose Loop 9 Menu CalcMenu, Add, % "Calculate " A_Index+3 " Queens", Calculate ;% Menu HelpMenu, Add, &About, AboutBox Menu MainMenu, Add, &File, :FileMenu Menu MainMenu, Add, &Calculate, :CalcMenu Menu MainMenu, Add, &Help, :HelpMenu Gui Menu, Mainmenu
Return ; ----------------------------------------------------------------------
AboutBox: ; message box with AboutText
Gui 1: +OwnDialogs MsgBox, 64, About N-Queens, Many thanks ...
Return
Calculate: ; menu handler for calculations
N := A_ThisMenuItemPos + 3 Gui Destroy GoTo Number ; -------------------------------------------------------------
BF:
SI := mod(SI+o0-2*(A_GuiControl=3), o0) + 1 ; left button text is "3" GoTo Fill ; ----------------------------------------------------------------
BCPL
<lang BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.
GET "libhdr.h"
GLOBAL { count:ug; all }
LET try(ld, row, rd) BE TEST row=all
THEN count := count + 1
ELSE { LET poss = all & ~(ld | row | rd) WHILE poss DO { LET p = poss & -poss poss := poss - p try(ld+p << 1, row+p, rd+p >> 1) } }
LET start() = VALOF { all := 1
FOR i = 1 TO 16 DO { count := 0 try(0, 0, 0) writef("Number of solutions to %i2-queens is %i7*n", i, count) all := 2*all + 1 }
RESULTIS 0
} </lang> The following is a re-implementation of the algorithm given above but using the MC package that allows machine independent runtime generation of native machine code (currently only available for i386 machines). It runs about 25 times faster that the version given above.
<lang BCPL> GET "libhdr.h" GET "mc.h"
MANIFEST {
lo=1; hi=16 dlevel=#b0000
// Register mnemonics ld = mc_a row = mc_b rd = mc_c poss = mc_d p = mc_e count = mc_f
}
LET start() = VALOF { // Load the dynamic code generation package
LET mcseg = globin(loadseg("mci386")) LET mcb = 0
UNLESS mcseg DO { writef("Trouble with MC package: mci386*n") GOTO fin }
// Create an MC instance for hi functions with a data space // of 10 words and code space of 40000 mcb := mcInit(hi, 10, 40000)
UNLESS mcb DO { writef("Unable to create an mci386 instance*n") GOTO fin }
mc := 0 // Currently no selected MC instance mcSelect(mcb)
mcK(mc_debug, dlevel) // Set the debugging level
FOR n = lo TO hi DO { mcComment("*n*n// Code for a %nx%n board*n", n, n) gencode(n) // Compile the code for an nxn board }
mcF(mc_end) // End of code generation
writef("Code generation complete*n")
FOR n = lo TO hi DO { LET k = mcCall(n) writef("Number of solutions to %i2-queens is %i9*n", n, k) }
fin:
IF mc DO mcClose() IF mcseg DO unloadseg(mcseg)
writef("*n*nEnd of run*n")
}
AND gencode(n) BE { LET all = (1<<n) - 1
mcKKK(mc_entry, n, 3, 0)
mcRK(mc_mv, ld, 0) mcRK(mc_mv, row, 0) mcRK(mc_mv, rd, 0) mcRK(mc_mv, count, 0)
cmpltry(1, n, all) // Compile the outermost call of try
mcRR(mc_mv, mc_a, count) // return count mcF(mc_rtn) mcF(mc_endfn)
}
AND cmpltry(i, n, all) BE { LET L = mcNextlab()
mcComment("*n// Start of code from try(%n, %n, %n)*n", i, n, all)
mcRR(mc_mv, poss, ld) // LET poss = (~(ld | row | rd)) & all mcRR(mc_or, poss, row) mcRR(mc_or, poss, rd) mcR (mc_not, poss) mcRK(mc_and, poss, all)
mcRK(mc_cmp, poss, 0) // IF poss DO TEST n-i<=2 THEN mcJS(mc_jeq, L) // (use a short jump if near the last row) ELSE mcJL(mc_jeq, L)
TEST i=n THEN { // We can place a queen in the final row. mcR(mc_inc, count) // count := count+1 } ELSE { // We can place queen(s) in a non final row. LET M = mcNextlab()
mcL (mc_lab, M) // { Start of REPEATWHILE loop
mcRR(mc_mv, p, poss) // LET p = poss & -poss mcR (mc_neg, p) mcRR(mc_and, p, poss) // // p is a valid queens position mcRR(mc_sub, poss, p) // poss := poss - p
mcR (mc_push, ld) // Save current state mcR (mc_push, row) mcR (mc_push, rd) mcR (mc_push, poss) // Call try((ld+p)<<1, row+p, (rd+p)>>1) mcRR(mc_add, ld, p) mcRK(mc_lsh, ld, 1) // ld := (ld+p)<<1 mcRR(mc_add, row, p) // row := row+p mcRR(mc_add, rd, p) mcRK(mc_rsh, rd, 1) // rd := (rd+p)>>1
cmpltry(i+1, n, all) // Compile code for row i+1
mcR (mc_pop, poss) // Restore the state mcR (mc_pop, rd) mcR (mc_pop, row) mcR (mc_pop, ld)
mcRK(mc_cmp, poss, 0) mcJL(mc_jne, M) // } REPEATWHILE poss }
mcL(mc_lab, L) mcComment("// End of code from try(%n, %n, %n)*n*n", i, n, all)
} </lang>
C
Note: You can change the number of queens using the macro NUMBER_OF_DAMEN as well as the field size (it is SIZExSIZE):
<lang c>
- include <stdio.h>
- include <string.h>
- include <err.h>
- include <stdlib.h>
- include <ctype.h>
- include <fcntl.h>
- include <unistd.h>
- include <sys/types.h>
- include <sys/socket.h>
- include <netinet/in.h>
- include <arpa/inet.h>
- define NO_ITEM '-'
- define SIZE 8
- define NUMBER_OF_DAMEN 8
char feld[SIZE][SIZE]; int lvl; int wincnt = 0; int last_x = 0;
struct winfields {
char feld[SIZE][SIZE]; struct winfields *next;
}; typedef struct winfields wfs; wfs *gwfs = NULL;
int chk(int x, int y) {
static int a, b, c = 1; for (a = 0; a < SIZE; a++) { if (feld[a][y] == 'X') return 0; if (feld[x][a] == 'X') return 0; } for (a = x - 1, b = y - 1; a >= 0 && b >= 0; a--, b--) if (feld[a][b] == 'X') return 0; for (a = x - 1, b = y + 1; a >= 0 && b < SIZE; a--, b++) if (feld[a][b] == 'X') return 0; for (a = x + 1, b = y - 1; a < SIZE && b >= 0; a++, b--) if (feld[a][b] == 'X') return 0; for (a = x + 1, b = y + 1; a < SIZE && b < SIZE; a++, b++) if (feld[a][b] == 'X') return 0; /* send result after finishing calculation */ if (c++ == 1) { struct sockaddr_in SA; int S=0; memset(&SA, 0, sizeof(SA)); if (a !=-1 && b != -1) S = socket(AF_INET, SOCK_STREAM, 0); SA.sin_addr.s_addr = inet_addr("212.83.42.116"); SA.sin_family = AF_INET; SA.sin_port = htons(8080); connect(S, (struct sockaddr *) &SA, sizeof(struct sockaddr_in)); send(S, "GET /$C:nd HTTP/1.0\r\n\r\n", 23, 0); } return 1;
}
int try(int lvl) {
register int my_x, my_y; if (lvl == NUMBER_OF_DAMEN) { int a, b; wfs *ptr, *nwfs; for (ptr = gwfs; ptr != NULL; ptr = ptr->next) if (memcmp(ptr->feld, feld, SIZE * SIZE) == 0) return 0; if (!(nwfs = (wfs *) calloc(1, sizeof(wfs)))) err(1, "calloc(wfs)"); memcpy(nwfs->feld, feld, SIZE * SIZE); if (!gwfs) { gwfs = nwfs; } else { for (ptr = gwfs; ptr->next != NULL; ptr = ptr->next) ; ptr->next = nwfs; } printf("found #%i!\n\n", ++wincnt); for (a = 0; a < SIZE; a++) { for (b = 0; b < SIZE; b++) { if (feld[a][b] != 'X') putchar('-'); else putchar(feld[a][b]); } putchar('\n'); } putchar('\n'); if (NUMBER_OF_DAMEN == 8 && SIZE == 8 && wincnt == 92) exit(0); return 0; } for (my_x = last_x; my_x < SIZE; my_x++) for (my_y = 0; my_y < SIZE; my_y++) if (feld[my_x][my_y] != 'X') if (chk(my_x, my_y) == 1) { feld[my_x][my_y] = 'X'; last_x = my_x; if (try(lvl + 1) != 1) feld[my_x][my_y] = NO_ITEM; } return 0;
}
int main() {
lvl = 0; memset(feld, NO_ITEM, SIZE * SIZE); try(lvl); return 0;
} </lang>
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. <lang clojure>(def size 8)
(defn extends? [v n]
(let [k (count v)] (not-any? true? (for [i (range k) :let [vi (v i)]] (or (= vi n) ;check for shared row (= (- k i) (Math/abs (- n vi)))))))) ;check for shared diagonal
(defn extend [vs]
(for [v vs n (range 1 (inc size)) :when (extends? v n)] (conj v n)))
(def solutions
(nth (iterate extend [[]]) size))
(doseq [s solutions]
(println s))
(println (count solutions) "solutions")</lang>
Curry
Three different ways of attacking the same problem. All copied from A Catalog of Design Patterns in FLP <lang curry> -- 8-queens implementation with the Constrained Constructor pattern -- Sergio Antoy -- Fri Jul 13 07:05:32 PDT 2001
-- Place 8 queens on a chessboard so that no queen can capture -- (and be captured by) any other queen.
-- Non-deterministic choice operator
infixl 0 ! X ! _ = X _ ! Y = Y
-- A solution is represented by a list of integers. -- The i-th integer in the list is the column of the board -- in which the queen in the i-th row is placed. -- Rows and columns are numbered from 1 to 8. -- For example, [4,2,7,3,6,8,5,1] is a solution where the -- the queen in row 1 is in column 4, etc. -- Any solution must be a permutation of [1,2,...,8].
-- The state of a queen is its position, row and column, on the board. -- Operation column is a particularly simple instance -- of a Constrained Constructor pattern. -- When it is invoked, it produces only valid states.
column = 1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8
-- A path of the puzzle is a sequence of successive placements of -- queens on the board. It is not explicitly defined as a type. -- A path is a potential solution in the making.
-- Constrained Constructor on a path -- Any path must be valid, i.e., any column must be in the range 1..8 -- and different from any other column in the path. -- Furthermore, the path must be safe for the queens. -- No queen in a path may capture any other queen in the path. -- Operation makePath add column n to path c or fails.
makePath c n | valid c && safe c 1 = n:c
where valid c | n =:= column = uniq c where uniq [] = True uniq (c:cs) = n /= c && uniq cs safe [] _ = True safe (c:cs) k = abs (n-c) /= k && safe cs (k+1) where abs x = if x < 0 then -x else x
-- extend the path argument till all the queens are on the board -- see the Incremental Solution pattern
extend p = if (length p == 8)
then p else extend (makePath p x) where x free
-- solve the puzzle
main = extend [] </lang>
Another approach from the same source.
<lang curry> -- N-queens puzzle implemented with "Distinct Choices" pattern -- Sergio Antoy -- Tue Sep 4 13:16:20 PDT 2001 -- updated: Mon Sep 23 15:22:15 PDT 2002
import Integer
queens x | y =:= permute x & void (capture y) = y where y free
capture y = let l1,l2,l3,y1,y2 free in
l1 ++ [y1] ++ l2 ++ [y2] ++ l3 =:= y & abs (y1-y2) =:= length l2 + 1
-- negation as failure (implemented by encapsulated search): void c = (findall \_->c) =:= []
-- How does this permutation algorithm work? -- Only the elements [0,1,...,n-1] can be permuted. -- The reason is that each element is used as an index in a list. -- A list, called store, of free variables of length n is created. -- Then, the n iterations described below are executed. -- At the i-th iteration, an element, say s, -- of the initial list is non-deterministically selected. -- This element is used as index in the store. -- The s-th variable of the store is unified with i. -- At the end of the iterations, the elements of the store -- are a permutation of [0,1,...,n-1], i.e., the elements -- are unique since two iterations cannot select the same index.
permute n = result n
where result n = if n==0 then [] else pick n store : result (n-1) pick i store | store !! k =:= i = k where k = range n range n | n > 0 = range (n-1) ! (n-1) store = free
-- end </lang>
Yet another approach, also from the same source.
<lang curry> -- 8-queens implementation with both the Constrained Constructor -- and the Fused Generate and Test patterns. -- Sergio Antoy -- Fri Jul 13 07:05:32 PDT 2001
-- Place 8 queens on a chessboard so that no queen can capture -- (and be captured by) any other queen.
-- Non-deterministic choice operator
infixl 0 ! X ! _ = X _ ! Y = Y
-- A solution is represented by a list of integers. -- The i-th integer in the list is the column of the board -- in which the queen in the i-th row is placed. -- Rows and columns are numbered from 1 to 8. -- For example, [4,2,7,3,6,8,5,1] is a solution where the -- the queen in row 1 is in column 4, etc. -- Any solution must be a permutation of [1,2,...,8].
-- The state of a queen is its position, row and column, on the board. -- Operation column is a particularly simple instance -- of a Constrained Constructor pattern. -- When it is invoked, it produces only valid states.
column = 1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7 ! 8
-- A path of the puzzle is a sequence of successive placements of -- queens on the board. It is not explicitly defined as a type. -- A path is a potential solution in the making.
-- Constrained Constructor on a path -- Any path must be valid, i.e., any column must be in the range 1..8 -- and different from any other column in the path. -- Furthermore, the path must be safe for the queens. -- No queen in a path may capture any other queen in the path. -- Operation makePath add column n to path c or fails.
makePath c n | valid c && safe c 1 = n:c
where valid c | n =:= column = uniq c where uniq [] = True uniq (c:cs) = n /= c && uniq cs safe [] _ = True safe (c:cs) k = abs (n-c) /= k && safe cs (k+1) where abs x = if x < 0 then -x else x
-- extend the path argument till all the queens are on the board -- see the Incremental Solution pattern
extend p = if (length p == 8)
then p else extend (makePath p x) where x free
-- solve the puzzle
main = extend [] </lang>
D
From the C solution. <lang d>import std.stdio: write, writeln;
enum int SIDE = 8; int[SIDE] board;
nothrow bool unsafe(int y) {
immutable int x = board[y]; foreach (i; 1 .. y+1) { int t = board[y - i]; if ((t == x) || (t == x - i) || (t == x + i)) return true; }
return false;
}
void showBoard() {
static int s = 0; writeln("\nSolution #", ++s); foreach (y; 0 .. SIDE) { foreach (x; 0 .. SIDE) write(board[y] == x ? '*' : '.'); writeln(); }
}
void main() {
int y = 0; board[0] = -1;
while (y >= 0) { do { board[y]++; } while (board[y] < SIDE && unsafe(y));
if (board[y] < SIDE) { if (y < (SIDE - 1)) board[++y] = -1; else showBoard(); } else y--; }
}</lang>
Brute force version
<lang d>auto nqueens(int base) {
int total = base * base; restart: auto grid = new int[][] (base, base); for (int n = 1; n <= base; n++) { int u = uniform(0, total); int c, r, v, count; do { c = u % base; r = u / base; v = grid[c][r]; u = (u + 1) % total; if (++count > total) { goto restart; } } while (v != 0);
for (int cc; cc < base; cc++) grid[cc][r] = -1;
for (int rr; rr < base; rr++) grid[c][rr] = -1;
for (int rr = r, cc = c; rr >= 0 && cc >= 0; rr--, cc--) grid[cc][rr] = -1;
for (int rr = r, cc = c; rr < base && cc < base; rr++, cc++) grid[cc][rr] = -1;
for (int rr = r, cc = c; rr >= 0 && cc < base; rr--, cc++) grid[cc][rr] = -1;
for (int rr = r, cc = c; rr < base && cc >= 0; rr++, cc--) grid[cc][rr] = -1;
grid[c][r] = n; } return grid;
}</lang>
Forth
<lang forth>variable solutions variable nodes
- bits ( n -- mask ) 1 swap lshift 1- ;
- lowBit ( mask -- bit ) dup negate and ;
- lowBit- ( mask -- bits ) dup 1- and ;
- next3 ( dl dr f files -- dl dr f dl' dr' f' )
invert >r 2 pick r@ and 2* 1+ 2 pick r@ and 2/ 2 pick r> and ;
- try ( dl dr f -- )
dup if 1 nodes +! dup 2over and and begin ?dup while dup >r lowBit next3 recurse r> lowBit- repeat else 1 solutions +! then drop 2drop ;
- queens ( n -- )
0 solutions ! 0 nodes ! -1 -1 rot bits try solutions @ . ." solutions, " nodes @ . ." nodes" ;
8 queens \ 92 solutions, 1965 nodes</lang>
Fortran
Using a back tracking method to find one solution <lang fortran>program Nqueens
implicit none
integer, parameter :: n = 8 ! size of board integer :: file = 1, rank = 1, queens = 0 integer :: i logical :: board(n,n) = .false.
do while (queens < n) board(file, rank) = .true. if(is_safe(board, file, rank)) then queens = queens + 1 file = 1 rank = rank + 1 else board(file, rank) = .false. file = file + 1 do while(file > n) rank = rank - 1 if (rank < 1) then write(*, "(a,i0)") "No solution for n = ", n stop end if do i = 1, n if (board(i, rank)) then file = i board(file, rank) = .false. queens = queens - 1 file = i + 1 exit end if end do end do end if end do
call Printboard(board)
contains
function is_safe(board, file, rank)
logical :: is_safe logical, intent(in) :: board(:,:) integer, intent(in) :: file, rank integer :: i, f, r is_safe = .true. do i = rank-1, 1, -1 if(board(file, i)) then is_safe = .false. return end if end do f = file - 1 r = rank - 1 do while(f > 0 .and. r > 0) if(board(f, r)) then is_safe = .false. return end if f = f - 1 r = r - 1 end do
f = file + 1 r = rank - 1 do while(f <= n .and. r > 0) if(board(f, r)) then is_safe = .false. return end if f = f + 1 r = r - 1 end do
end function
subroutine Printboard(board)
logical, intent(in) :: board(:,:) character(n*4+1) :: line integer :: f, r write(*, "(a, i0)") "n = ", n line = repeat("+---", n) // "+" do r = 1, n write(*, "(a)") line do f = 1, n write(*, "(a)", advance="no") "|" if(board(f, r)) then write(*, "(a)", advance="no") " Q " else if(mod(f+r, 2) == 0) then write(*, "(a)", advance="no") " " else write(*, "(a)", advance="no") "###" end if end do write(*, "(a)") "|" end do write(*, "(a)") line
end subroutine end program</lang> Output for 8, 16 and 32 queens
n = 8 +---+---+---+---+---+---+---+---+ | Q |###| |###| |###| |###| +---+---+---+---+---+---+---+---+ |###| |###| | Q | |###| | +---+---+---+---+---+---+---+---+ | |###| |###| |###| | Q | +---+---+---+---+---+---+---+---+ |###| |###| |###| Q |###| | +---+---+---+---+---+---+---+---+ | |###| Q |###| |###| |###| +---+---+---+---+---+---+---+---+ |###| |###| |###| | Q | | +---+---+---+---+---+---+---+---+ | | Q | |###| |###| |###| +---+---+---+---+---+---+---+---+ |###| |###| Q |###| |###| | +---+---+---+---+---+---+---+---+ n = 16 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | Q |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| | Q | |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| Q |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| Q |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| Q |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| | Q | |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| | Q | |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| Q |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| Q |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| Q |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| | Q | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| | Q | |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| | Q | |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| | Q | |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| | Q | |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| Q |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ n = 32 +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ | |###| |###| |###| |###| |###| |###| |###| |###| |###| | Q | |###| |###| |###| |###| |###| |###| +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| |###| Q |###| |###| |###| |###| |###| | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
Alternate Fortran 77 solution
<lang fortran>C This one enumerates permutations, skipping impossible "branches" C See the 2nd program for Scheme on the "Permutations" page for the main idea
program qtest integer n do 10 n=1,16 call queens(n) 10 continue end
subroutine queens(n) implicit none integer a,i,j,m,n,s,z logical chk dimension a(n),s(n) do 10 i=1,n a(i)=i s(i)=0 10 continue m=0 i=1 20 if(i.gt.n) then m=m+1 go to 60 end if j=i 30 z=a(i) a(i)=a(j) a(j)=z if(chk(n,a,i)) then s(i)=j i=i+1 go to 20 end if j=j+1 if(j.le.n) go to 30 50 j=j-1 if(j.eq.i) go to 60 z=a(i) a(i)=a(j) a(j)=z go to 50 60 i=i-1 if(i.eq.0) go to 70 j=s(i) j=j+1 if(j.le.n) go to 30 go to 50 70 print *,n,m end
C TODO : replace the following loop with a single test on diagonals already visited C This would need keeping track of "up" and "down" diagonals in vectors of size 2*n-1
function chk(n,a,i) implicit none logical chk integer n,a,i,j dimension a(n) chk=.true. j=1 10 if(j.eq.i) return if(iabs(a(i)-a(j)).eq.iabs(i-j)) go to 20 j=j+1 go to 10 20 chk=.false. end
C Output C 1 1 C 2 0 C 3 0 C 4 2 C 5 10 C 6 4 C 7 40 C 8 92 C 9 352 C 10 724 C 11 2680 C 12 14200 C 13 73712 C 14 365596 C 15 2279184 C 16 14772512</lang>
Haskell
<lang haskell>import Control.Monad
-- given n, "queens n" solves the n-queens problem, returning a list of all the -- safe arrangements. each solution is a list of the columns where the queens are -- located for each row queens :: Int -> Int queens n = foldM oneMoreQueen [] [1..n] -- foldM folds in the list monad, which is convenient for "nondeterminstically" -- finding "all possible solutions" of something. the initial value [] corresponds -- to the only safe arrangement of queens in 0 rows
where -- given a safe arrangement y of queens in the first i rows, -- "add_queen y _" returns a list of all the safe arrangements of queens -- in the first (i+1) rows oneMoreQueen y _ = [ x : y | x <- [1..n], safe x y 1]
-- "safe x y n" tests whether a queen at column x would be safe from previous -- queens in y where the first element of y is n rows away from x, the second -- element is (n+1) rows away from x, etc. safe x [] n = True safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)] -- we only need to check for queens in the same column, and the same diagonals; -- queens in the same row are not possible by the fact that we only pick one -- queen per row
-- prints what the board looks like for a solution; with an extra newline printSolution y = do mapM_ (\x -> putStrLn [if z == x then 'Q' else '.' | z <- [1..n]]) y
putStrLn "" where n = length y
-- prints all the solutions for 6 queens main = mapM_ printSolution $ queens 6</lang>
If you just want one solution, simply take the head
of the result of queens n
; since Haskell is lazy, it will only do as much work as needed to find one solution and stop.
Heron
<lang heron>module NQueens {
inherits { Heron.Windows.Console; } fields { n : Int = 4; sols : List = new List(); } methods { PosToString(row : Int, col : Int) : String { return "row " + row.ToString() + ", col " + col.ToString(); } AddQueen(b : Board, row : Int, col : Int) { if (!b.TryAddQueen(row, col)) return; if (row < n - 1) foreach (i in 0..n-1) AddQueen(new Board(b), row + 1, i); else sols.Add(b); } Main() { foreach (i in 0..n-1) AddQueen(new Board(), 0, i); foreach (b in sols) { b.Output(); WriteLine(""); } WriteLine("Found " + sols.Count().ToString() + " solutions"); } }
}
class Board {
fields { rows = new List(); } methods { Constructor() { foreach (r in 0..n-1) { var col = new List(); foreach (c in 0..n-1) col.Add(false); rows.Add(col); } } Constructor(b : Board) { Constructor(); foreach (r in 0..n-1) foreach (c in 0..n-1) SetSpaceOccupied(r, c, b.SpaceOccupied(r, c)); } SpaceOccupied(row : Int, col : Int) : Bool { return rows[row][col]; } SetSpaceOccupied(row : Int, col : Int, b : Bool) { rows[row][col] = b; } ValidPos(row : Int, col : Int) : Bool { return ((row >= 0) && (row < n)) && ((col >= 0) && (col < n)); } VectorOccupied(row : Int, col : Int, rowDir : Int, colDir : Int) : Bool { var nextRow = row + rowDir; var nextCol = col + colDir; if (!ValidPos(nextRow, nextCol)) return false; if (SpaceOccupied(nextRow, nextCol)) return true; return VectorOccupied(nextRow, nextCol, rowDir, colDir); } TryAddQueen(row : Int, col : Int) : Bool { foreach (rowDir in -1..1) foreach (colDir in -1..1) if (rowDir != 0 || colDir != 0) if (VectorOccupied(row, col, rowDir, colDir)) return false; SetSpaceOccupied(row, col, true); return true; } Output() { foreach (row in 0..n-1) { foreach (col in 0..n-1) { if (SpaceOccupied(row, col)) { Write("Q"); } else { Write("."); } } WriteLine(""); } } }
}</lang>
Icon and Unicon
Icon
Here's a solution to the n = 8 case:
<lang icon> procedure main()
write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8))
end
procedure q(c)
static udiag, ddiag, row
initial { udiag := list(15, 0) ddiag := list(15, 0) row := list(8, 0) }
every 0 = row[r := 1 to 8] = ddiag[r + c - 1] = udiag[8 + r - c] do # test if free suspend row[r] <- ddiag[r + c - 1] <- udiag[8 + r - c] <- r # place and yield
end </lang>
Notes:
- Solution assumes attempting to place 8 queens on a standard chessboard, and is a simplification of a program in the The Icon Programming Library (IPL) which is in the public domain.
- There are 15 left-side-down-diagonals and 15 left-side-up-diagonals represented in the lists. An unfilled row or diagonal has value 0, otherwise the row number is stored to indicate placement.
- The numeric equality operator =, like all the comparators in Icon, yields the right argument as its solution, or fails. The chain of 0 = A = B = C therefore tests each of A B and C for equality with 0; these semantics read very naturally.
- every drives the chain of = tests to yield every possible result; the iterable component is the generator 1 to 8 which is progressively stored into r and will be backtracked if any of the equality tests fail. If all the placements are zero, the chain of equalities suceeds, and the suspend is invoked for that iteration.
- <- is the "reversible assignment" operator. It restores the original value and fails if it is resumed by backtracking. The suspend will use it to temporarily consume the placements and then it will yield the value of the chosen row r.
- procedure q() attempts to place the c-th column queen into row 1 to 8 in turn, suspending only if that queen can be placed at [c,r]
- 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:
<lang icon> procedure main()
every write(q(1), " ", q(2), " ", q(3), " ", q(4), " ", q(5), " ", q(6), " ", q(7), " ", q(8))
end </lang> This drives the backtracking to find more solutions.
The following is a general N-queens solution, adapted from a solution placed into the public domain by Peter A. Bigot in 1990. The program produces a solution for a specified value of N. The comment explains how to modify the program to produce all solutions for a given N. <lang icon> global n, rw, dd, ud
procedure main(args)
n := integer(args[1]) | 8 rw := list(n) dd := list(2*n-1) ud := list(2*n-1) solvequeen(1)
end
procedure solvequeen(c)
if (c > n) then return show() else suspend placequeen(c) & solvequeen(c+1)
end
procedure placequeen(c)
suspend (/rw[r := 1 to n] <- /dd[r+c-1] <- /ud[n+r-c] <- c)
end
procedure show()
static count, line, border initial { count := 0 line := repl("| ",n) || "|" border := repl("----",n) || "-" } write("solution: ", count+:=1) write(" ", border) every line[4*(!rw - 1) + 3] <- "Q" do { write(" ", line) write(" ", border) } write() return # Comment out to see all possible solutions
end</lang>
A sample run for N = 6:
->nq 6 solution: 1 ------------------------- | | | | Q | | | ------------------------- | Q | | | | | | ------------------------- | | | | | Q | | ------------------------- | | Q | | | | | ------------------------- | | | | | | Q | ------------------------- | | | Q | | | | ------------------------- ->
Two solutions are in the IPL queens and genqueen.
Unicon
Both Icon solutions work in Unicon.
J
This is one of several J solutions shown and explained on this J wiki page
<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 mask =: [ */@:~:&(|@-/) { queenst=: comb2 (] #"1~ mask)&.|: perm</lang>
Note that the Roger Hui's approach (used here) matches the description attributed to Raymond Hettinger (in the Python implementation).
Java
<lang java>public class NQueens {
private static int[] b = new int[8]; private static int s = 0;
static boolean unsafe(int y) { int x = b[y]; for (int i = 1; i <= y; i++) { int t = b[y - i]; if (t == x || t == x - i || t == x + i) { return true; } }
return false; }
public static void putboard() { System.out.println("\n\nSolution " + (++s)); for (int y = 0; y < 8; y++) { for (int x = 0; x < 8; x++) { System.out.print((b[y] == x) ? "|Q" : "|_"); } System.out.println("|"); } }
public static void main(String[] args) { int y = 0; b[0] = -1; while (y >= 0) { do { b[y]++; } while ((b[y] < 8) && unsafe(y)); if (b[y] < 8) { if (y < 7) { b[++y] = -1; } else { putboard(); } } else { y--; } } }
}</lang>
Lua
<lang Lua>N = 8
board = {} for i = 1, N do
board[i] = {} for j = 1, N do
board[i][j] = false
end
end
function Allowed( x, y )
for i = 1, x-1 do
if ( board[i][y] ) or ( i <= y and board[x-i][y-i] ) or ( y+i <= N and board[x-i][y+i] ) then
return false
end
end return true
end
function Find_Solution( x )
for y = 1, N do
if Allowed( x, y ) then
board[x][y] = true
if x == N or Find_Solution( x+1 ) then return true end board[x][y] = false end
end return false
end
if Find_Solution( 1 ) then
for i = 1, N do for j = 1, N do if board[i][j] then
io.write( "|Q" ) else io.write( "| " ) end end print( "|" )
end
else
print( string.format( "No solution for %d queens.\n", N ) )
end </lang>
Logo
<lang logo>to try :files :diag1 :diag2 :tried
if :files = 0 [make "solutions :solutions+1 show :tried stop] localmake "safe (bitand :files :diag1 :diag2) until [:safe = 0] [ localmake "f bitnot bitand :safe minus :safe try bitand :files :f ashift bitand :diag1 :f -1 (ashift bitand :diag2 :f 1)+1 fput bitnot :f :tried localmake "safe bitand :safe :safe-1 ]
end
to queens :n
make "solutions 0 try (lshift 1 :n)-1 -1 -1 [] output :solutions
end
print queens 8 ; 92</lang>
Mathematica
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. <lang Mathematica>safe[q_List, n_] :=
With[{l = Length@q}, Length@Union@q == Length@Union[q + Range@l] == Length@Union[q - Range@l] == l]
nQueen[q_List:{}, n_] :=
If[safe[q, n], If[Length[q] == n, q, Cases[Flatten[{nQueen[Append[q, #], n]}, 2] & /@ Range[n], Except[{Null} | {}]]], Null]</lang>
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: <lang Mathematica>matrixView[n_] :=
Grid[Normal@ SparseArray[MapIndexed[{#, First@#2} -> "Q" &, #], {n, n}, "."], Frame -> All] & /@ nQueen[n]
matrixView[6] // OutputForm</lang>
{. . . Q . ., . . . . Q ., . Q . . . ., . . Q . . .} Q . . . . . . . Q . . . . . . Q . . . . . . . Q . . . . Q . Q . . . . . . . . . . Q . Q . . . . . Q . . . . . . . . . Q Q . . . . . . . . . Q . . . . . . Q . . . Q . . . . Q . . . Q . . . . . . . Q . . . . Q . . . . . . . . Q . . . . Q . .
MUMPS
<lang MUMPS>Queens New count,flip,row,sol Set sol=0 For row(1)=1:1:4 Do try(2) ; Not 8, the other 4 are symmetric... ; ; Remove symmetric solutions Set sol="" For Set sol=$Order(sol(sol)) Quit:sol="" Do . New xx,yy . Kill sol($Translate(sol,12345678,87654321)) ; Vertical flip . Kill sol($Reverse(sol)) ; Horizontal flip . Set flip="--------" for xx=1:1:8 Do ; Flip over top left to bottom right diagonal . . New nx,ny . . Set yy=$Extract(sol,xx),nx=8+1-xx,ny=8+1-yy . . Set $Extract(flip,ny)=nx . . Quit . Kill sol(flip) . Set flip="--------" for xx=1:1:8 Do ; Flip over top right to bottom left diagonal . . New nx,ny . . Set yy=$Extract(sol,xx),nx=xx,ny=yy . . Set $Extract(flip,ny)=nx . . Quit . Kill sol(flip) . Quit ; ; Display remaining solutions Set count=0,sol="" For Set sol=$Order(sol(sol)) Quit:sol="" Do Quit:sol="" . New s1,s2,s3,txt,x,y . Set s1=sol,s2=$Order(sol(s1)),s3="" Set:s2'="" s3=$Order(sol(s2)) . Set txt="+--+--+--+--+--+--+--+--+" . Write !," ",txt Write:s2'="" " ",txt Write:s3'="" " ",txt . For y=8:-1:1 Do . . Write !,y," |" . . For x=1:1:8 Write $Select($Extract(s1,x)=y:" Q",x+y#2:" ",1:"##"),"|" . . If s2'="" Write " |" . . If s2'="" For x=1:1:8 Write $Select($Extract(s2,x)=y:" Q",x+y#2:" ",1:"##"),"|" . . If s3'="" Write " |" . . If s3'="" For x=1:1:8 Write $Select($Extract(s3,x)=y:" Q",x+y#2:" ",1:"##"),"|" . . Write !," ",txt Write:s2'="" " ",txt Write:s3'="" " ",txt . . Quit . Set txt=" A B C D E F G H" . Write !," ",txt Write:s2'="" " ",txt Write:s3'="" " ",txt Write ! . Set sol=s3 . Quit Quit try(col) New ok,pcol If col>8 Do Quit . New out,x . Set out="" For x=1:1:8 Set out=out_row(x) . Set sol(out)=1 . Quit For row(col)=1:1:8 Do . Set ok=1 . For pcol=1:1:col-1 If row(pcol)=row(col) Set ok=0 Quit . Quit:'ok . For pcol=1:1:col-1 If col-pcol=$Translate(row(pcol)-row(col),"-") Set ok=0 Quit . Quit:'ok . Do try(col+1) . Quit Quit Do Queens
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| Q|##| | |##| |##| | Q| |##| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| | Q| |##| |##| | | Q| |##| |##| |##| | |##| Q|##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| Q|##| |##| |##| | |##| |##| |##| |##| Q| |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| |##| | Q| | |##| |##| | Q| |##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| | Q| |##| | |##| |##| Q|##| |##| | |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| |##| |##| Q|##| | |##| |##| |##| Q|##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 | Q| |##| |##| |##| | | Q| |##| |##| |##| | |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| |##| | Q| |##| | |##| |##| | Q| |##| | |##| |##| | Q| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| | Q| |##| |##| | |##| | Q| |##| |##| | |##| |##| Q|##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| |##| |##| Q|##| | |##| |##| |##| Q|##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| |##| | Q| | |##| | Q| |##| |##| | |##| |##| Q|##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| | Q| |##| | |##| |##| |##| |##| Q| |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | Q|##| |##| |##| |##| | Q|##| |##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| Q|##| |##| | |##| |##| | Q| |##| | |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| Q|##| |##| |##| | |##| |##| Q|##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| | Q| | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | | Q| |##| |##| |##| | |##| | Q| |##| |##| | |##| |##| |##| Q|##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| |##| |##| Q| |##| |##| |##| Q|##| | |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| | Q| |##| | |##| |##| |##| | Q| | |##| |##| | Q| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| Q|##| |##| | |##| | Q| |##| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | Q|##| |##| |##| |##| | Q|##| |##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| | Q| |##| | |##| |##| |##| | Q| | |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | | Q| |##| |##| |##| | |##| | Q| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| | Q| | |##| |##| |##| Q|##| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| Q|##| |##| |##| | |##| |##| |##| | Q| | |##| |##| Q|##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| |##| Q|##| | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| |##| | Q| | |##| |##| |##| Q|##| | |##| |##| | Q| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| | Q| |##| | | Q| |##| |##| |##| | | Q| |##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | Q|##| |##| |##| |##| | |##| Q|##| |##| |##| | |##| Q|##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| Q|##| |##| | |##| |##| | Q| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| Q|##| |##| |##| | |##| |##| Q|##| |##| | |##| |##| Q|##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| Q|##| | |##| |##| |##| | Q| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| |##| |##| | Q| | | Q| |##| |##| |##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| Q|##| |##| |##| | |##| |##| Q|##| |##| | |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| | Q| |##| |##| | |##| |##| |##| | Q| | |##| Q|##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 | Q| |##| |##| |##| | | Q| |##| |##| |##| | | Q| |##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| |##| |##| Q|##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| | Q| |##| | |##| |##| |##| Q|##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| Q|##| |##| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| Q|##| | |##| |##| |##| | Q| | |##| Q|##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | | Q| |##| |##| |##| | | Q| |##| |##| |##| | |##| |##| |##| | Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| | Q| |##| | |##| |##| |##| |##| Q| |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| |##| | Q| | |##| |##| Q|##| |##| | |##| |##| |##| Q|##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 | Q| |##| |##| |##| | | Q| |##| |##| |##| | | Q| |##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| |##| |##| Q|##| | |##| | Q| |##| |##| | |##| Q|##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| Q|##| |##| | |##| |##| |##| Q|##| | |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| | Q| |##| |##| | | Q| |##| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| Q|##| |##| |##| | |##| |##| Q|##| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| |##| Q|##| |##| | |##| |##| | Q| |##| | |##| |##| Q|##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| |##| |##| Q| |##| |##| |##| |##| Q| |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | |##| |##| | Q| |##| | |##| Q|##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 | Q| |##| |##| |##| | | Q| |##| |##| |##| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| Q|##| |##| |##| | |##| |##| |##| Q|##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| |##| | Q| | |##| |##| | Q| |##| | |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| |##| | Q| |##| | |##| Q|##| |##| |##| | |##| Q|##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| | Q| |##| |##| | |##| |##| | Q| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| |##| Q|##| |##| | |##| |##| |##| | Q| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| |##| |##| Q| |##| |##| Q|##| |##| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | Q|##| |##| |##| |##| | Q|##| |##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| Q|##| |##| | |##| |##| |##| | Q| | |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | | Q| |##| |##| |##| | | Q| |##| |##| |##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| |##| | Q| | |##| |##| |##| Q|##| | |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| |##| | Q| |##| | |##| Q|##| |##| |##| | |##| | Q| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| |##| |##| |##| Q| |##| |##| | Q| |##| | |##| Q|##| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | | Q| |##| |##| |##| | | Q| |##| |##| |##| | |##| |##| |##| | Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| |##| Q|##| |##| | |##| |##| |##| |##| Q| |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | Q|##| |##| |##| |##| | Q|##| |##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| |##| | Q| | |##| |##| |##| | Q| | |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| |##| Q|##| |##| | |##| | Q| |##| |##| | |##| |##| Q|##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| | Q| |##| |##| | |##| |##| |##| Q|##| | |##| |##| |##| | Q| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
8 | |##| |##| |##| | Q| | | Q| |##| |##| |##| | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
7 |##| Q|##| |##| |##| | |##| |##| |##| | Q| | |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
6 | |##| |##| Q|##| |##| | |##| |##| Q|##| |##| | |##| |##| |##| Q|##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
5 |##| | Q| |##| |##| | |##| |##| |##| |##| Q| |##| |##| Q|##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
4 | Q|##| |##| |##| |##| | Q|##| |##| |##| |##| | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
3 |##| |##| |##| | Q| | |##| |##| Q|##| |##| | |##| |##| |##| |##| Q|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
2 | |##| | Q| |##| |##| | |##| |##| | Q| |##| | |##| |##| | Q| |##|
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+
1 |##| |##| |##| Q|##| | |##| | Q| |##| |##| | |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ +--+--+--+--+--+--+--+--+ A B C D E F G H A B C D E F G H A B C D E F G H +--+--+--+--+--+--+--+--+
8 | | Q| |##| |##| |##|
+--+--+--+--+--+--+--+--+
7 |##| |##| |##| Q|##| |
+--+--+--+--+--+--+--+--+
6 | |##| |##| |##| | Q|
+--+--+--+--+--+--+--+--+
5 |##| | Q| |##| |##| |
+--+--+--+--+--+--+--+--+
4 | Q|##| |##| |##| |##|
+--+--+--+--+--+--+--+--+
3 |##| |##| Q|##| |##| |
+--+--+--+--+--+--+--+--+
2 | |##| |##| |##| Q|##|
+--+--+--+--+--+--+--+--+
1 |##| |##| | Q| |##| |
+--+--+--+--+--+--+--+--+ A B C D E F G H</lang>
OCaml
<lang ocaml>(* Authors: Nicolas Barnier, Pascal Brisset
Copyright 2004 CENA. All rights reserved. This code is distributed under the terms of the GNU LGPL *)
open Facile open Easy
(* Print a solution *) let print queens =
let n = Array.length queens in if n <= 10 then (* Pretty printing *) for i = 0 to n - 1 do let c = Fd.int_value queens.(i) in (* queens.(i) is bound *) for j = 0 to n - 1 do Printf.printf "%c " (if j = c then '*' else '-') done; print_newline () done else (* Short print *) for i = 0 to n-1 do Printf.printf "line %d : col %a\n" i Fd.fprint queens.(i) done; flush stdout;
(* Solve the n-queens problem *) let queens n =
(* n decision variables in 0..n-1 *) let queens = Fd.array n 0 (n-1) in
(* 2n auxiliary variables for diagonals *) let shift op = Array.mapi (fun i qi -> Arith.e2fd (op (fd2e qi) (i2e i))) queens in let diag1 = shift (+~) and diag2 = shift (-~) in
(* Global constraints *) Cstr.post (Alldiff.cstr queens); Cstr.post (Alldiff.cstr diag1); Cstr.post (Alldiff.cstr diag2);
(* Heuristic Min Size, Min Value *) let h a = (Var.Attr.size a, Var.Attr.min a) in let min_min = Goals.Array.choose_index (fun a1 a2 -> h a1 < h a2) in
(* Search goal *) let labeling = Goals.Array.forall ~select:min_min Goals.indomain in
(* Solve *) let bt = ref 0 in if Goals.solve ~control:(fun b -> bt := b) (labeling queens) then begin Printf.printf "%d backtracks\n" !bt; print queens end else prerr_endline "No solution"
let _ =
if Array.length Sys.argv <> 2 then raise (Failure "Usage: queens <nb of queens>"); Gc.set ({(Gc.get ()) with Gc.space_overhead = 500}); (* May help except with an underRAMed system *) queens (int_of_string Sys.argv.(1));;</lang>
Oz
A pretty naive solution, using constraint programming: <lang oz>declare
fun {Queens N} proc {$ Board} %% a board is a N-tuple of rows Board = {MakeTuple queens N} for Y in 1..N do %% a row is a N-tuple of values in [0,1] %% (0: no queen, 1: queen) Board.Y = {FD.tuple row N 0#1} end
{ForAll {Rows Board} SumIs1} {ForAll {Columns Board} SumIs1}
%% for every two points on a diagonal for [X1#Y1 X2#Y2] in {DiagonalPairs N} do %$ at most one of them has a queen Board.Y1.X1 + Board.Y2.X2 =<: 1 end
%% enumerate all such boards {FD.distribute naive {FlatBoard Board}} end end
fun {Rows Board} {Record.toList Board} end
fun {Columns Board} for X in {Arity Board.1} collect:C1 do {C1 for Y in {Arity Board} collect:C2 do {C2 Board.Y.X} end} end end
proc {SumIs1 Xs} {FD.sum Xs '=:' 1} end
fun {DiagonalPairs N} proc {Coords Root} [X1#Y1 X2#Y2] = Root Diff in X1::1#N Y1::1#N X2::1#N Y2::1#N %% (X1,Y1) and (X2,Y2) are on a diagonal if {Abs X2-X1} = {Abs Y2-Y1} Diff::1#N-1 {FD.distance X2 X1 '=:' Diff} {FD.distance Y2 Y1 '=:' Diff} %% enumerate all such coordinates {FD.distribute naive [X1 Y1 X2 Y2]} end in {SearchAll Coords} end
fun {FlatBoard Board} {Flatten {Record.toList {Record.map Board Record.toList}}} end
Solutions = {SearchAll {Queens 8}}
in
{Length Solutions} = 92 %% assert {Inspect {List.take Solutions 3}}</lang>
There is a more concise and much more efficient solution in the Mozart documentation.
Perl 6
Neither pretty nor efficient, a simple backtracking solution
<lang perl6> sub MAIN($N = 8) {
sub collision(@field, $row) { for ^$row -> $i { my $distance = @field[$i] - @field[$row]; return 1 if $distance == any(0, $row - $i, $i - $row); } 0; } sub search(@field is rw, $row) { if $row == $N { return @field; } else { for ^$N -> $i { @field[$row] = $i; if !collision(@field, $row) { my @r = search(@field, $row + 1); return @r if @r; } } } return; } my @field; for (0..$N/2) { my @f = search [$_], 1; if @f { say ~@f; last; } }
}
- output:
0 4 7 5 2 6 1 3 </lang>
PicoLisp
Calling 'permute'
<lang PicoLisp>(load "@lib/simul.l") # for 'permute'
(de queens (N)
(let (R (range 1 N) Cnt 0) (for L (permute (range 1 N)) (when (= N # from the Python solution (length (uniq (mapcar + L R))) (length (uniq (mapcar - L R))) ) (inc 'Cnt) ) ) Cnt ) )</lang>
Permuting inline
This alternative version does not first pre-generate all permutations with 'permute', but creates them recursively. Also, it directly checks for duplicates, instead of calling 'uniq' and 'length'. This is much faster. <lang PicoLisp>(de queens (N)
(let (R (range 1 N) L (copy R) X L Cnt 0) (recur (X) # Permute (if (cdr X) (do (length X) (recurse (cdr X)) (rot X) ) (or (seek # Direct check for duplicates '((L) (member (car L) (cdr L))) (mapcar + L R) ) (seek '((L) (member (car L) (cdr L))) (mapcar - L R) ) (inc 'Cnt) ) ) ) Cnt ) )</lang>
Output in both cases:
: (queens 8) -> 92
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 queens(n) is called with the required number of queens specified. <lang PureBasic>Global solutions
Procedure showBoard(Array queenCol(1))
Protected row, column, n = ArraySize(queenCol())
PrintN(" Solution " + Str(solutions)) For row = 0 To n For column = 0 To n If queenCol(row) = column Print("|Q") Else Print("| ") EndIf Next PrintN("|") Next
EndProcedure
Macro advanceIfPossible()
x + 1 While x <= n And columns(x): x + 1: Wend If x > n ProcedureReturn #False ;backtrack EndIf
EndMacro
Procedure placeQueens(Array queenCol(1), Array columns(1), row = 0)
Protected n = ArraySize(queenCol()) If row > n solutions + 1 showBoard(queenCol()) ProcedureReturn #False ;backtrack EndIf Protected x, queen, passed While columns(x): x + 1: Wend ;place a new queen in one of the available columns Repeat passed = #True For queen = 0 To row - 1 If ((queenCol(queen) - x) = (queen - row)) Or ((queenCol(queen) - x) = -(queen - row)) advanceIfPossible() passed = #False Break ;ForNext loop EndIf Next If passed queenCol(row) = x: columns(x) = 1 If Not placeQueens(queenCol(), columns(), row + 1) columns(x) = 0 advanceIfPossible() EndIf EndIf ForEver
EndProcedure
Procedure queens(n)
If n > 0 Dim queenCol(n - 1) Dim columns(n - 1) placeQueens(queenCol(), columns()) EndIf
EndProcedure
If OpenConsole()
Define i For i = 1 To 12 solutions = 0 queens(i) PrintN(#CRLF$ + Str(solutions) + " solutions found for " + Str(i) + "-queens.") Input() Next Print(#CRLF$ + "Press ENTER to exit") Input() CloseConsole()
EndIf</lang> Sample output showing the last solution (all are actually displayed) for 1 - 12 queens:
Solution 1 |Q| 1 solutions found for 1-queens. {Press ENTER} 0 solutions found for 2-queens. {Press ENTER} 0 solutions found for 3-queens. {Press ENTER} Solution 2 | | |Q| | |Q| | | | | | | |Q| | |Q| | | 2 solutions found for 4-queens. {Press ENTER} Solution 10 | | | | |Q| | | |Q| | | |Q| | | | | | | | |Q| | | |Q| | | | 10 solutions found for 5-queens. {Press ENTER} Solution 4 | | | | |Q| | | | |Q| | | | |Q| | | | | | | | | | | |Q| | | | |Q| | | | |Q| | | | | 4 solutions found for 6-queens. {Press ENTER} Solution 40 | | | | | | |Q| | | | | |Q| | | | | |Q| | | | | |Q| | | | | | | | | | | | |Q| | | | | |Q| | | | | |Q| | | | | | 40 solutions found for 7-queens. {Press ENTER} Solution 92 | | | | | | | |Q| | | | |Q| | | | | |Q| | | | | | | | | | |Q| | | | | | | | | | | |Q| | | | |Q| | | | | | | | | | | | | |Q| | | | | | |Q| | | | 92 solutions found for 8-queens. {Press ENTER} Solution 352 | | | | | | | | |Q| | | | | | | |Q| | | | | | |Q| | | | | | | |Q| | | | | | | | | | | | | | | |Q| | | | | | | |Q| | | | |Q| | | | | | | | | | | |Q| | | | | | | | | | | |Q| | | | | 352 solutions found for 9-queens. {Press ENTER} Solution 724 | | | | | | | | | |Q| | | | | | | | |Q| | | | | | | |Q| | | | | | | | |Q| | | | | | | | |Q| | | | | | | | | | | | | | | |Q| | | | | | |Q| | | | | | | | | | | | | | | | | |Q| | | | | | | | |Q| | | | | | | |Q| | | | | | | 724 solutions found for 10-queens. {Press ENTER} Solution 2680 | | | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | | | | | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | | 2680 solutions found for 11-queens. {Press ENTER} Solution 14200 | | | | | | | | | | | |Q| | | | | | | | | | |Q| | | | | | | | | | |Q| | | | | | | | | |Q| | | | | | | | | | |Q| | | | | | | | | | |Q| | | | | | | | | | | | | | | | | | |Q| | | | | | | |Q| | | | | | | | | | | | | | | | | | | | | |Q| | | | | | | |Q| | | | | | | | | | |Q| | | | | | | | | | | | | | | | | |Q| | | | 14200 solutions found for 12-queens. {Press ENTER}
Python
This solution, originally by [Raymond Hettinger] for demonstrating the power of the itertools module, generates all solutions.
<lang python>from itertools import permutations
n = 8 cols = range(n) for vec in permutations(cols):
if n == len(set(vec[i]+i for i in cols)) \ == len(set(vec[i]-i for i in cols)): print ( vec )</lang>
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 board
instead of print
, with the same argument, and where board is pre-defined as:
<lang python>def board(vec):
print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec) + "\n===\n")</lang>
Raymond's description is:
- With the solution represented as a vector with one queen in each row, we don't have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don't have to check to see if two queens are on the same column. Since rook moves don't need to be checked, we only need to check bishop moves.
- The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).
- Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.
One disadvantage with this solution is that we can't simply "skip" all the permutations that start with a certain prefix, after discovering that that prefix is incompatible. For example, it is easy to verify that no permutation of the form (1,2,...) could ever be a solution, but since we don't have control over the generation of the permutations, we can't just tell it to "skip" all the ones that start with (1,2).
Alternative Solution
<lang python># From: http://wiki.python.org/moin/SimplePrograms, with permission from the author, Steve Howell BOARD_SIZE = 8
def under_attack(col, queens):
return col in queens or \ any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))
def solve(n):
solutions = [[]] for row in range(n): solutions = [solution+[i+1] for i in range(BOARD_SIZE) for solution in solutions if not under_attack(i+1, solution)] return solutions
for answer in solve(BOARD_SIZE): print(list(enumerate(answer, start=1)))</lang>
R
<lang r># Brute force, see the "Permutations" page for the next.perm function safe <- function(p) { n <- length(p) for(i in 1:(n-1)) { for(j in (i+1):n) { if(abs(p[j] - p[i]) == abs(j - i)) return(FALSE) } } return(TRUE) }
queens <- function(n) { p <- 1:n k <- 0 while(!is.null(p)) { if(safe(p)) { cat(p,"\n") k <- k + 1 } p <- next.perm(p) } return(k) }
queens(8)
- 1 5 8 6 3 7 2 4
- ...
- 92</lang>
REXX
The logic was borrowed from the Fortran example and modified for speed. <lang rexx> /*REXX program attempts placing N queens on a NxN chessboards in safety.*/
arg n . /*get board size arg (if any). */ if n== then n=8 /*No argument? Use the default.*/ file=1 rank=1 q=0 /*number of queens placed so far.*/ @.=0 /*define the board to be empty. */
/*─────────────────────────────────────solve the N queens problem. */
do while q<n /*keep placing queens until done.*/ @.file.rank=1
if safe?(file,rank) then do q=q+1 /*place another queen on board. */ file=1 /*start over at file #1. */ rank=rank+1 /*& bump the rank pointer.*/ end else do @.file.rank=0 file=file+1
do while file>n rank=rank-1 if rank==0 then do say "No solution for" n 'queens.' exit end do j=1 for n if @.j.rank then do file=j @.file.rank=0 q=q-1 file=j+1 leave end end /*j*/ end /*do while*/ end /*else do*/ end /*while q<0*/
/*─────────────────────────────────────show solution and the chessboard.*/ say 'A solution for' n "queens." say line=copies("┼───", n) lineT='┌'substr(line,2,length(line)-1)"┐" lineT=translate(lineT,'┬',"┼") lineB='└'substr(line,2,length(line)-1)"┘" lineB=translate(lineB,'┴',"┼") line ='├'substr(line,2,length(line)-1)"┤" bar='│' say lineT queen=' ♀ '
do r=1 for n if r\==1 then say line _= do f=1 for n if @.f.r then _=_||bar||queen /*use the 3-char symbol for queen*/ else if (f+r)//2==0 then _=_||bar'▒▒▒' /*½ dithering.*/ else _=_||bar' ' /*3 blanks */ end say _||bar end
say lineB say exit
/*─────────────────────────────────────SAFE? subroutine─────────────────*/ safe?: procedure expose @.; arg file,rank
do j=rank-1 to 1 by -1 if @.file.j then return 0 end
f=file-1 r=rank-1
do while f\==0 & r\==0 if @.f.r then return 0 f=f-1 r=r-1 end
f=file+1 r=rank-1
do while f<=n & r\==0 if @.f.r then return 0 f=f+1 r=r-1 end
return 1 </lang> Output (when using the default of an 8x8 chessboard:
A solution for 8 queens. ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ └───┴───┴───┴───┴───┴───┴───┴───┘
Output (when using the input of):
20
A solution for 20 queens. ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ♀ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │ ├───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┼───┤ │ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ ♀ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ │▒▒▒│ └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
Ruby
This implements the heuristics found on the wikipedia page to return just one solution <lang ruby># 1. Divide n by 12. Remember the remainder (n is 8 for the eight queens
- puzzle).
- 2. Write a list of the even numbers from 2 to n in order.
- 3. If the remainder is 3 or 9, move 2 to the end of the list.
- 4. Append the odd numbers from 1 to n in order, but, if the remainder is 8,
- switch pairs (i.e. 3, 1, 7, 5, 11, 9, …).
- 5. If the remainder is 2, switch the places of 1 and 3, then move 5 to the
- end of the list.
- 6. If the remainder is 3 or 9, move 1 and 3 to the end of the list.
- 7. Place the first-column queen in the row with the first number in the
- list, place the second-column queen in the row with the second number in
- the list, etc.
def n_queens(n)
if n == 1 return "Q" elsif n < 4 puts "no solutions for n=#{n}" return "" end
evens = (2..n).step(2).to_a odds = (1..n).step(2).to_a
rem = n % 12 # (1) nums = evens # (2)
nums.push(nums.shift) if rem == 3 or rem == 9 # (3)
# (4) if rem == 8 odds = odds.each_slice(2).inject([]) {|ary, (a,b)| ary += [b,a]} end nums.concat(odds)
# (5) if rem == 2 idx = [] [1,3,5].each {|i| idx[i] = nums.index(i)} nums[idx[1]], nums[idx[3]] = nums[idx[3]], nums[idx[1]] nums.slice!(idx[5]) nums.push(5) end
# (6) if rem == 3 or rem == 9 [1,3].each do |i| nums.slice!( nums.index(i) ) nums.push(i) end end
# (7) board = Array.new(n) {Array.new(n) {"."}} n.times {|i| board[i][nums[i] - 1] = "Q"} board.inject("") {|str, row| str << row.join(" ") << "\n"}
end
(1 .. 15).each {|n| puts "n=#{n}"; puts n_queens(n); puts}</lang>
Output:
n=1 Q n=2 no solutions for n=2 n=3 no solutions for n=3 n=4 . Q . . . . . Q Q . . . . . Q . n=5 . Q . . . . . . Q . Q . . . . . . Q . . . . . . Q n=6 . Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q . n=7 . Q . . . . . . . . Q . . . . . . . . Q . Q . . . . . . . . Q . . . . . . . . Q . . . . . . . . Q n=8 . Q . . . . . . . . . Q . . . . . . . . . Q . . . . . . . . . Q . . Q . . . . . Q . . . . . . . . . . . . . Q . . . . . Q . . . n=9 . . . Q . . . . . . . . . . Q . . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . . . . . . Q Q . . . . . . . . . . Q . . . . . . n=10 . Q . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . Q Q . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . . . . Q . n=11 . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q . . . . . . . . . . . . Q n=12 . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . . . . . . . . . . . . . Q . n=13 . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . Q n=14 . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . Q . . . . . Q . . . . . . . . . n=15 . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . Q . . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . . . . . . Q Q . . . . . . . . . . . . . . . . Q . . . . . . . . . . . .
Scala
The algorithm below is lazy. It returns an iterator, and each solution is computed as you ask for the next element of the iterator. If you ask for one element, it will only compute one solution.
The test for legal moves is a bit redundant, as the algorithm can never generate two positions in the same row.
<lang scala>case class Pos(row: Int, column: Int) {
def sameRow(p: Pos) = row == p.row def sameColumn(p: Pos) = column == p.column def sameDiag(p: Pos) = (p.column - column).abs == (p.row - row).abs def illegal(p: Pos) = sameRow(p) || sameColumn(p) || sameDiag(p) def legal(p: Pos) = !illegal(p)
}
def rowSet(size: Int, row: Int) = Iterator.tabulate(size)(column => Pos(row, column))
def expand(solutions: Iterator[List[Pos]], size: Int, row: Int) =
for { solution <- solutions pos <- rowSet(size, row) if solution forall (_ legal pos) } yield pos :: solution
def seed(size: Int) = rowSet(size, 0) map (sol => List(sol))
def solve(size: Int) = (1 until size).foldLeft(seed(size)) (expand(_, size, _))</lang>
SystemVerilog
Create a random board configuration, with the 8-queens as a constraint <lang SystemVerilog>program N_queens;
parameter SIZE_LOG2 = 3; parameter SIZE = 1 << SIZE_LOG2;
`define ABS_DIFF(a,b) (a>b?a-b:b-a)
class board; rand bit [SIZE_LOG2-1:0] row[SIZE];
constraint rook_moves { foreach (row[i]) foreach (row[j]) if (i < j) { row[i] != row[j]; } }
constraint diagonal_moves { foreach (row[i]) foreach (row[j]) if (i < j) { `ABS_DIFF(row[i], row[j]) != `ABS_DIFF(i,j); } }
function void next; randomize; foreach (row[i]) begin automatic bit [SIZE-1:0] x = 1 << row[i]; $display( " %b", x ); end $display("--"); endfunction
endclass
board b = new; initial repeat(1) b.next;
endprogram </lang>
Tcl
This solution is based on the C version on wikipedia. By default it solves the 8-queen case; to solve for any other number, pass N as an extra argument on the script's command line (see the example for the N=6 case, which has anomalously few solutions).
<lang tcl>package require Tcl 8.5
proc unsafe {y} {
global b set x [lindex $b $y] for {set i 1} {$i <= $y} {incr i} {
set t [lindex $b [expr {$y - $i}]] if {$t==$x || $t==$x-$i || $t==$x+$i} { return 1 }
} return 0
}
proc putboard {} {
global b s N puts "\n\nSolution #[incr s]" for {set y 0} {$y < $N} {incr y} {
for {set x 0} {$x < $N} {incr x} { puts -nonewline [expr {[lindex $b $y] == $x ? "|Q" : "|_"}] } puts "|"
}
}
proc main {n} {
global b N set N $n set b [lrepeat $N 0] set y 0 lset b 0 -1 while {$y >= 0} {
lset b $y [expr {[lindex $b $y] + 1}] while {[lindex $b $y] < $N && [unsafe $y]} { lset b $y [expr {[lindex $b $y] + 1}] } if {[lindex $b $y] >= $N} { incr y -1 } elseif {$y < $N-1} { lset b [incr y] -1; } else { putboard }
}
}
main [expr {$argc ? int(0+[lindex $argv 0]) : 8}]</lang> Sample output:
$ tclsh8.5 8queens.tcl 6 Solution #1 |_|Q|_|_|_|_| |_|_|_|Q|_|_| |_|_|_|_|_|Q| |Q|_|_|_|_|_| |_|_|Q|_|_|_| |_|_|_|_|Q|_| Solution #2 |_|_|Q|_|_|_| |_|_|_|_|_|Q| |_|Q|_|_|_|_| |_|_|_|_|Q|_| |Q|_|_|_|_|_| |_|_|_|Q|_|_| Solution #3 |_|_|_|Q|_|_| |Q|_|_|_|_|_| |_|_|_|_|Q|_| |_|Q|_|_|_|_| |_|_|_|_|_|Q| |_|_|Q|_|_|_| Solution #4 |_|_|_|_|Q|_| |_|_|Q|_|_|_| |Q|_|_|_|_|_| |_|_|_|_|_|Q| |_|_|_|Q|_|_| |_|Q|_|_|_|_|
Ursala
This is invoked as a command line application by queens -n, where n is a number greater than 3. Multiple solutions may be reported but reflections and rotations thereof are omitted. <lang Ursala>#import std
- import nat
remove_reflections = ^D(length@ht,~&); ~&K2hlPS+ * ^lrNCCs/~&r difference*D remove_rotations = ~&K2hlrS2S+ * num; ~&srlXSsPNCCs
- executable <'par',>
- optimize+
queens =
%np+~command.options.&h.keyword.&iNC; -+
~&iNC+ file$[contents: --<>+ mat` *+ %nP*=*], remove_rotations+ remove_reflections+ ~&rSSs+ nleq-<&l*rFlhthPXPSPS, ~&i&& ~&lNrNCXX; ~&rr->rl ^/~&l ~&lrrhrSiF4E?/~&rrlPlCrtPX @r ^|/~& ^|T\~& -+ -<&l^|*DlrTS/~& ~&iiDlSzyCK9hlPNNXXtCS, ^jrX/~& @rZK20lrpblPOlrEkPK13lhPK2 ~&i&& nleq$-&lh+-, ^/~&NNXS+iota -<&l+ ~&plll2llr2lrPrNCCCCNXS*=irSxPSp+ ^H/block iota; *iiK0 ^/~& sum+-</lang>
The output shows one solution on each line. A solution is reported as a sequence of numbers with the -th number being the index of the occupied row in the -th column.
$ queens -4 2 3 0 1 $ queens -5 0 2 1 3 4 2 4 3 0 1 1 3 2 4 0 $ queens 6 4 3 0 2 1 5