N-queens problem: Difference between revisions
6502 Assembly and Zero Page stub
(6502 Assembly and Zero Page stub) |
|||
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">
| |||