

Solve the eight queens puzzle.



You can extend the problem to solve the puzzle with a board of size   NxN.

For the number of solutions for small values of   N,   see   OEIS: A000170.



Related tasks

 A* search algorithm
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Knight's tour
 Peaceful chess queen armies
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


 
; "eight queens problem" benchmark test
 
         .radix    16
 
         .loc 0
 
          nop            ;
          mov  #scr,@#E800
          mov  #88C6,@#E802
; clear the display RAM
          mov  #scr,r0
          mov  #1E0,r1
cls:      clr  (r0)+
          sob  r1,cls
; display the initial counter value
          clr  r3
          mov  #scr,r0
          jsr  pc,number
; perform the test
          jsr  pc,queens
; display the counter
          mov  #scr,r0
          jsr  pc,number
finish:   br   finish
 
; display the character R1 at the screen address R0,
; advance the pointer R0 to the next column
putc:     mov  r2,-(sp)
; R1 <- 6 * R1
         asl  r1        ;* 2
         mov  r1,-(sp)
         asl  r1        ;* 4
         add  (sp)+,r1  ;* 6
         add  #chars,r1
         mov  #6,r2
putc1:   movb (r1)+,(r0)
         add  #1E,r0
         sob  r2,putc1
         sub  #B2,r0         ;6 * 1E - 2 = B2
         mov  (sp)+,r2
         rts  pc
 
print1:   jsr  pc,putc
; print a string pointed to by R2 at the screen address R0,
; advance the pointer R0 to the next column,
; the string should be terminated by a negative byte
print:    movb (r2)+,r1
          bpl  print1
          rts  pc
 
; display the word R3 decimal at the screen address R0
number:   mov  sp,r1
          mov  #A0A,-(sp)
          mov  (sp),-(sp)
          mov  (sp),-(sp)
          movb #80,-(r1)
numb1:    clr  r2
          div  #A,r2
          movb r3,-(r1)
          mov  r2,r3
          bne  numb1
          mov  sp,r2
          jsr  pc,print
          add  #6,sp
          rts  pc
 
queens:  mov  #64,r5         ;100
l06:     clr  r3
         clr  r0
l00:     cmp  #8,r0
         beq  l05
         inc  r0
         movb #8,ary(r0)
l01:     inc  r3
         mov  r0,r1
l02:     dec  r1
         beq  l00
         movb ary(r0),r2
         movb ary(r1),r4
         sub  r2,r4
         beq  l04
         bcc  l03
         neg  r4
l03:     add  r1,r4
         sub  r0,r4
         bne  l02
l04:     decb ary(r0)
         bne  l01
         sob  r0,l04
l05:     sob  r5,l06
         mov  r3,cnt
         rts  pc
 
; characters, width = 8 pixels, height = 6 pixels
chars:  .byte     3C, 46, 4A, 52, 62, 3C   ;digit '0'
        .byte     18, 28, 8,  8,  8,  3E   ;digit '1'
        .byte     3C, 42, 2,  3C, 40, 7E   ;digit '2'
        .byte     3C, 42, C,  2,  42, 3C   ;digit '3'
        .byte     8,  18, 28, 48, 7E, 8    ;digit '4'
        .byte     7E, 40, 7C, 2,  42, 3C   ;digit '5'
        .byte     3C, 40, 7C, 42, 42, 3C   ;digit '6'
        .byte     7E, 2,  4,  8,  10, 10   ;digit '7'
        .byte     3C, 42, 3C, 42, 42, 3C   ;digit '8'
        .byte     3C, 42, 42, 3E, 2,  3C   ;digit '9'
        .byte     0,  0,  0,  0,  0,  0    ;space
 
        .even
 
cnt:    .blkw     1
ary:    .blkb     9
 
        .loc 200
 
scr:                                        ;display RAM
 