N-queens problem: Difference between revisions
m
→Python: Backtracking on permutations: Restored the original look
m (removed BASIC header, hoisted BBC BASIC and Applesoft BASIC) |
m (→Python: Backtracking on permutations: Restored the original look) |
||
| (24 intermediate revisions by 4 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 11,238 ⟶ 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,706 ⟶ 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,715 ⟶ 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,882 ⟶ 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,891 ⟶ 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,910 ⟶ 15,036:
pub struct NQueens {
iterator: Box<Iterator<dyn Item=NQueensSolution>>
}
Line 14,958 ⟶ 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}}==
| |||