N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
mNo edit summary |
m (→Python: Backtracking on permutations: Restored the original look) |
||
| (35 intermediate revisions by 11 users not shown) | |||
Line 252:
</pre>
=={{header|6502 Assembly}}==
{{trans|Java}}
A few optimization techniques are used in this implementation. One goal was to get 8-queens to run in under 2 seconds on a 1 MHz computer.
Zero page values are stored where frequent use of the immediate addressing mode can be used as a speed up. This can be seen where a byte is referenced as variablename+1. INC and DEC instructions are used instead of ADC and SBC instructions for the comparison offsets.
The solution count is a 64-bit little endian value stored in memory starting at $0020, or $0D20 if the [[#Zero Page stub|Zero Page stub]] routine is used.
<syntaxhighlight lang="6502asm">n equ 8 ; queens
maximum equ 32 ; only limited by time
place equ $00
count equ maximum+place ; 64 bits (8 bytes)
length equ maximum+8
org $80
start
LDY #n ; n queens on an n x n board
STY greater+1
DEY
STY safe+1
LDX #length
LDA #$00
clear
STA place,X
DEX
BPL clear
next
INX
LDA #$FF
STA place,X
loop
INC place,X
LDA place,X
greater
CMP #n
BCS max
STX index+1
index
LDY #$00 ; index+1
BEQ safe
DEY
STA compare+1
STA add+1 ; compare
STA sub+1 ; compare
issafe
LDA place,Y
compare
CMP #$00 ; compare+1
BEQ loop ; unsafe
INC add+1
add
CMP #$00 ; add+1
BEQ loop ; unsafe
DEC sub+1
sub
CMP #$00 ; sub+1
BEQ loop ; unsafe
DEY
BPL issafe
safe
CPX #n-1
BNE next
INC count ; 64 bits (8 bytes)
BNE loop
INC count+1
BNE loop
INC count+2
BNE loop
INC count+3
BNE loop
INC count+4
BNE loop
INC count+5
BNE loop
INC count+6
BNE loop
INC count+7
BNE loop
BRK
max
DEX
BPL loop
; RTS</syntaxhighlight>
The code was assembled using Merlin32. The code length is 104 bytes not including the final 6 cycle RTS instruction.
<pre> n solutions cycles
1 1 443
2 0 710
3 0 1440
4 2 4359
5 10 17134
6 4 75848
7 40 337161
8 92 1616054
9 352 8044019
10 724 41556729
11 2680 230829955
12 14200 1378660940
13 73712 8684130248
14 365596 58185218171
15 2279184 412358679630
</pre>
==== Zero Page stub ====
The 6502 N-queens problem code resides within the zero page starting at $80 which can make running the program a bit tricky on some platforms. A stub is provided to facilitate running the zero page code. The stub routine turns off interrupts and swaps the zero page memory with an area residing at $D00 to $DFF, runs the zero page code, and swaps memory again. The cycle counts listed above do not include the time to run this stub. With the final RTS instruction included, the 105 byte N-queens zero page code must be in memory starting at $D80.
<syntaxhighlight lang="6502asm"> org $C00
PHP
SEI
JSR swap
JSR $0080
JSR swap
PLP
jmp end
swap
LDX #$00
loop
LDY $D00,X
LDA $00,X
STY $00,X
STA $D00,X
INX
BNE loop
RTS
end
; RTS</syntaxhighlight>
=={{header|ABAP}}==
<syntaxhighlight lang="abap">
Line 933 ⟶ 1,055:
return newRows
end Reflect</syntaxhighlight>
=={{header|Applesoft BASIC}}==
{{trans|Java}}
<syntaxhighlight lang="basic"> 1 READ N,T,M,R(0): FOR Y = 0 TO M STEP 0: FOR L = 0 TO T STEP 0:R(Y) = R(Y) + T:X = R(Y):C = NOT Y: IF NOT C THEN FOR I = T TO Y:A = R(Y - I): IF NOT (A = X OR A = X - I OR A = X + I) THEN NEXT I:C = T
2 L = R(Y) > N OR C: NEXT L:D = - (R(Y) > N): IF NOT D AND Y < N THEN R(Y + T) = M:D = D + T
3 S = S + NOT D:Y = Y + D: NEXT Y: PRINT "THERE " MID$ ("AREIS",4 ^ (S = 1),3)" "S" SOLUTION" MID$ ("S",1,S < > 1)" FOR "N + T" X "N + T: DATA7,1,-1,-1</syntaxhighlight>
{{out}}
<pre>THERE ARE 92 SOLUTIONS FOR 8 X 8
</pre>
=={{header|Arc}}==
Line 4,666 ⟶ 4,797:
<syntaxhighlight lang="easylang">
subr show_sol
print "Solution " & n_sol
print ""
for i = 1 to n
write " "
for j = 1 to n
if j = x[i]
write "Q "
else
write ". "
.
.
print ""
.
subr test
ok = 1
for i = 1 to y - 1
if x[y] = x[i] or abs (x[i] - x[y]) = abs (y - i)
ok = 0
.
.
.
n = 8
Line 4,694 ⟶ 4,825:
x[1] = 1
while y >= 1
if ok = 1 and y + 1 <= n
y += 1
x[y] = 1
else
if ok = 1
n_sol += 1
if n_sol <= 1
.
.
while y >= 1 and x[y] = n
y -= 1
.
.
print n_sol & " solutions"
Line 4,807 ⟶ 4,938:
12 ♕ 14200 solutions
</pre>
=={{header|Ecstasy}}==
<syntaxhighlight lang="Ecstasy">/**
* A solver for the classic 8-queens problem.
*
* @see https://rosettacode.org/wiki/N-queens_problem
*/
module eightQueens {
void run() {
@Inject Console console;
Int count = new Board().solve(b -> console.print($"{b}\n"));
console.print($"{count} solutions found");
}
/**
* `Board` represents a chess board that holds only queens. The board
* is organized as columns 0 ("A") to 7 ("H"), and rows 0 (rank "1")
* to 7 (rank "8").
*/
const Board {
/**
* Construct an empty board.
*/
construct() {}
/**
* Internal: Construct a specifically-populated board.
*/
private construct(Int queens, Int claimed) {
this.queens = queens;
this.claimed = claimed;
}
/**
* Each bit of this 64-bit integer represents a queen.
*/
private Int queens;
/**
* Each bit of this 64-bit integer represents a queen or a threat.
*/
private Int claimed;
/**
* Translate a column and row to a bit-mask, used with the
* [queens] and [claimed] properties. Examples:
* * A1 is (0,0) => 0x0000000000000001
* * H8 is (7,7) => 0x8000000000000000
*/
private Int mask(Int col, Int row) = 1 << (row << 3) + col;
/**
* Determine if the specified square has a queen in it.
*/
Boolean occupied(Int col, Int row) {
return queens & mask(col, row) != 0;
}
/**
* Determine if the specified square is safe from the queens.
*/
Boolean safe(Int col, Int row) {
return claimed & mask(col, row) == 0;
}
/**
* Attempt to place a queen in a specified square.
*
* @return True iff a queen can be safely placed in the square
* @return (conditional) the new Board with the new queen on it
*/
conditional Board placeQueen(Int col, Int row) {
assert 0 <= col < 8 && 0 <= row < 8;
if (!safe(col, row)) {
return False;
}
Int newQueens = queens | mask(col, row);
Int newClaimed = claimed | queens;
// claim all threatened spaces
for (Int i : 0..7) {
newClaimed |= mask(i, row) | mask(col, i);
val diagDownRow = row + i - col;
if (0 <= diagDownRow < 8) {
newClaimed |= mask(i, diagDownRow);
}
val diagUpRow = row - i + col;
if (0 <= diagUpRow < 8) {
newClaimed |= mask(i, diagUpRow);
}
}
return True, new Board(newQueens, newClaimed);
}
/**
* Attempt to find all solutions to the n-queens problem.
*/
Int solve(function void(Board) yield) = solve(yield, 0);
/**
* Internal: Attempt to find all solutions to the n-queens problem,
* starting with the specified column and recursively solving by
* moving to the next column for each potential solution found in
* the specified column.
*/
private Int solve(function void(Board) yield, Int col) {
if (col == 8) {
// there is no column 8; we've found a solution
yield(this);
return 1;
}
Int count = 0;
for (Int rank : 8..1) {
val row = 8-rank;
if (Board afterPlacing := placeQueen(col, row)) {
count += afterPlacing.solve(yield, col + 1);
}
}
return count;
}
@Override String toString() {
val buf = new StringBuffer();
for (Int rank : 8..1) {
buf.append($"{rank} |");
val row = 8-rank;
for (Int col : 0..7) {
buf.add(occupied(col, row) ? 'q' : '_').add('|');
}
buf.add('\n');
}
return buf.append(" A B C D E F G H").toString();
}
}
}</syntaxhighlight>
<b>Output:</b>
<code><pre>
8 |q|_|_|_|_|_|_|_|
7 |_|_|_|_|_|_|q|_|
6 |_|_|_|_|q|_|_|_|
5 |_|_|_|_|_|_|_|q|
4 |_|q|_|_|_|_|_|_|
3 |_|_|_|q|_|_|_|_|
2 |_|_|_|_|_|q|_|_|
1 |_|_|q|_|_|_|_|_|
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
(...)
8 |_|_|q|_|_|_|_|_|
7 |_|_|_|_|_|q|_|_|
6 |_|_|_|q|_|_|_|_|
5 |_|q|_|_|_|_|_|_|
4 |_|_|_|_|_|_|_|q|
3 |_|_|_|_|q|_|_|_|
2 |_|_|_|_|_|_|q|_|
1 |q|_|_|_|_|_|_|_|
A B C D E F G H
92 solutions found
</pre></code>
=={{header|Eiffel}}==
Line 5,521 ⟶ 5,823:
8 queens \ 92 solutions, 1965 nodes</syntaxhighlight>
=== Alternate solution adapted from FD-V02N1.pdf ===
<syntaxhighlight lang="forth">
\ http://www.forth.org/fd/FD-V02N1.pdf
VOCABULARY nqueens ALSO nqueens DEFINITIONS
8 constant queens
\ Nqueen solution from FD-V02N1.pdf
: 1array CREATE 0 DO 1 , LOOP DOES> SWAP CELLS + ;
queens 1array a \ a,b & c: workspaces for solutions
queens 2* 1array b
queens 2* 1array c
queens 1array x \ trial solutions
: safe ( c i -- n )
SWAP
2DUP - queens 1- + c @ >R
2DUP + b @ >R
DROP a @ R> R> * * ;
: mark ( c i -- )
SWAP
2DUP - queens 1- + c 0 swap !
2DUP + b 0 swap !
DROP a 0 swap ! ;
: unmark ( c i -- )
SWAP
2DUP - queens 1- + c 1 swap !
2DUP + b 1 swap !
DROP a 1 swap ! ;
VARIABLE tries
VARIABLE sols
: .cols queens 0 DO I x @ 1+ 5 .r loop ;
: .sol ." Found on try " tries @ 6 .R .cols cr ;
: try
queens 0
DO 1 tries +!
DUP I safe
IF DUP I mark
DUP I SWAP x !
DUP queens 1- < IF DUP 1+ RECURSE ELSE sols ++ .sol THEN
DUP I unmark
THEN
LOOP DROP ;
: go 0 tries ! CR 0 try CR sols @ . ." solutions Found, for n = " queens . ;
go
</syntaxhighlight>
=={{header|Fortran}}==
Line 6,528 ⟶ 6,883:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/N-queens_problem}}
'''Solution'''
The following function:
* Is able to calculate solution for chessboards of any size (but it is slow for big chessboards)
* It does not detect rotated or reflected solutions
This is an example of backtracking:
[[File:Fōrmulæ - N-queens problem 01.png]]
[[File:Fōrmulæ - N-queens problem 02.png]]
[[File:Fōrmulæ - N-queens problem 03.png]]
'''Improvement.''' The following functions calls the previous one, but shows the solution on a more friendly way
[[File:Fōrmulæ - N-queens problem 04.png]]
[[File:Fōrmulæ - N-queens problem 05.png]]
[[File:Fōrmulæ - N-queens problem 06.png]]
=={{header|GAP}}==
Line 8,798 ⟶ 9,172:
...]] */
length(%); /* 92 */</syntaxhighlight>
<syntaxhighlight lang="maxima">
/* Inspired by code from Python */
Queens(N):=block([K,C,P,V,L:[]],
C: makelist(K,K,1,N),
P: permutations(C),
for V in P do (
if is(N=length(unique(makelist(V[K]+K, K, C)))) then (
if is(N=length(unique(makelist(V[K]-K, K, C)))) then (
L: endcons(V, L)
)
)
), L
)$
Queens(8);length(%);</syntaxhighlight>
=={{header|MiniScript}}==
This GUI implementation is for use with [http://miniscript.org/MiniMicro Mini Micro]. It displays a chess board with animation of the possibilities. At the end, after all of the solutions have been calculated, you can scroll through them with the left/right cursor keys.
<syntaxhighlight lang="miniscript">
clear
N = 8
SOLUTIONCOUNT = 0
getTileDisplay = function
gfx.clear
queen = file.loadImage("/sys/pics/gamePieces/blackQueen.png")
gfx.color = color.white
gfx.fillRect 0, 0, 80, 80
gfx.fillRect 160, 0, 80, 80
gfx.color = color.brown
gfx.fillRect 80, 0, 80, 80
gfx.fillRect 240, 0, 80, 80
gfx.drawImage queen, 172, 14
gfx.drawImage queen, 252, 14
tiles = gfx.getImage(0,0, 320, 80)
gfx.clear
display(4).mode = displayMode.tile
td = display(4)
td.cellSize = 640 / N
td.extent = [N, N]
td.overlap = 0
td.tileSet = tiles
td.tileSetTileSize = 80
td.scrollX = -160
td.clear
return td
end function
updateBoard = function(td, arr)
for y in range(0, N - 1)
ix = y % 2
for x in range(0, N - 1)
td.setCell x, y, ix
ix += 1
ix %= 2
end for
end for
y = 0
for x in arr
td.setCell x, y, td.cell(x, y) + 2
y += 1
end for
yield
end function
list.has = function(n)
return self.indexOf(n) != null
end function
queens = function(n, i, a, b, c, td)
solutions = []
updateBoard(td, a)
if i < n then
for j in range(0, n - 1)
if not a.has(j) and not b.has(i + j) and not c.has(i - j) then
solution = queens(n, i + 1, a + [j], b + [i + j], c + [i - j], td)
if solution != null then solutions += solution
end if
end for
else
globals.SOLUTIONCOUNT += 1
text.row = 25
text.print "SOLUTIONS"
text.print globals.SOLUTIONCOUNT
solutions.push(a)
end if
return solutions
end function
td = getTileDisplay
solutions = queens(N, 0, [], [], [], td)
ix = 0
while true
text.row = 25
text.print "SOLUTION # "
text.print (ix + 1) + (" " * 10)
text.print
text.print char(17) + "/" + char(18) + " keys"
updateBoard(td, solutions[ix])
k = key.get
kcode = code(k)
if kcode == 27 then break
ix = ix - (kcode == 17) + (kcode == 18) + solutions.len
ix %= solutions.len
end while
</syntaxhighlight>
=={{header|MiniZinc}}==
Line 10,877 ⟶ 11,360:
=={{header|Phix}}==
<!--
<syntaxhighlight lang="phix">
with javascript_semantics
--
-- demo\rosetta\n_queens.exw
-- =========================
--
sequence co, -- columns occupied
-- (ro is implicit)
fd, -- forward diagonals
bd,
board
atom count
procedure solve(integer row, integer N, integer show)
for col=1 to N do
if not co[col] then
integer fdi = col+row-1,
bdi = row-col+N
if not fd[fdi]
and not bd[bdi] then
board[row][col] = 'Q'
co[col] = true
fd[fdi] = true
bd[bdi] = true
if row=N then
if show then
puts(1,join(board,"\n")&"\n")
end if
else
end if
board[row][col] = '.'
co[col] = false
fd[fdi] = false
bd[bdi] = false
end if
end if
end for
end procedure
procedure n_queens(integer N=8, integer show=1)
co = repeat(false,N)
fd = repeat(false,N*2-1)
bd = repeat(false,N*2-1)
board = repeat(repeat('.',N),N)
count = 0
solve(1,N,show)
printf(1,"%d queens: %d solutions\n",{N,count})
end procedure
for N=1 to iff(platform()=JS?12:14) do
n_queens(N,N<5)
end for
</syntaxhighlight>
{{out}}
<pre>
Line 12,345 ⟶ 12,829:
print(list(enumerate(first_answer, start=1)))</syntaxhighlight>
===Python:
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/
<syntaxhighlight lang="python">def queens(n: int, i: int, a: list, b: list, c: list):
if i < n:
for j in range(n):
Line 12,354 ⟶ 12,838:
else:
yield a
for solution in queens(8, 0, [], [], []):
print(solution)</syntaxhighlight>
The algorithm can be
<syntaxhighlight lang="python">def queens(
if a: # set a is not empty
for j in a:
if i + j not in b and i - j not in c:
yield from queens(i + 1, a - {j})
b.remove(i + j); c.remove(i - j); x.pop()
else:
yield x
b = set(); c = set(); x = []
for solution in queens(0, set(range(8))):
print(solution)</syntaxhighlight>
===Python:
Queens positions on a n x n board are encoded as permutations of [0, 1, ..., n]. The algorithms consists in building a permutation from left to right, by swapping elements of the initial [0, 1, ..., n], recursively calling itself unless the current position is not possible. The test is done by checking only diagonals, since rows/columns have by definition of a permutation, only one queen.
This is initially a translation of the Fortran 77 solution. 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]. On a regular 8x8 board only 5,508 possible queen positions are examined.
<syntaxhighlight lang="python">def queens(n: int):
def sub(i: int):
for k in range(i, n):
j = a[k]
a[i], a[k] = a[k], a[i]
b[i + j] = c[i - j] = False
yield from sub(i + 1)
a[i], a[k] = a[k], a[i]
else:
yield a
a = list(range(n))
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from sub(0)
sum(1 for p in queens(8)) # count solutions
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, restoring the
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: int):
for k in range(i, n):
j = a[k]
a[i], a[k] = a[k], a[i]
if b[i + j]
yield from sub(i + 1)
a = list(range(n))
b = [True] * (2 * n - 1)
c = [True] * (2 * n - 1)
yield from sub(0)
next(queens(31))
next(queens_lex(31))
#Compare to A065188
Line 14,521 ⟶ 15,006:
===Using Iterators===
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;
Line 14,530 ⟶ 15,017:
}
fn permutations<'a, T, I>(collection: I) -> Box<Iterator<dyn Item=LinkedList<T>> + 'a>
where I: 'a + IntoIterator<Item=T> + Clone,
T: 'a + PartialEq + Copy + Clone {
Line 14,549 ⟶ 15,036:
pub struct NQueens {
iterator: Box<Iterator<dyn Item=NQueensSolution>>
}
Line 14,597 ⟶ 15,084:
str
}
}
</syntaxhighlight>
===Permutation with Filtering===
Using Itertools and arrays.
{{trans|D}}
<syntaxhighlight lang="rust">
extern crate itertools;
use itertools::Itertools;
fn main() {
const N: usize = 8;
let permutations = (0..N).permutations(N);
let solution_count = permutations
.filter(|p| {
let mut diag1 = [false; 2 * N - 1];
let mut diag2 = [false; 2 * N - 1];
for (i, &row) in p.iter().enumerate() {
if diag1[row + i] || diag2[N - 1 + row - i] {
return false; // Queens mutual threat
}
diag1[row + i] = true;
diag2[N - 1 + row - i] = true;
}
true // No Queens mutual threat
})
.count();
println!("{}", solution_count);
}
</syntaxhighlight>
=={{header|SAS}}==
Line 16,501 ⟶ 17,027:
{{trans|Kotlin}}
Very slow for the larger boards.
<syntaxhighlight lang="
var c = []
var f = []
| |||