N-queens problem - solution in nasm

[fmartins]

I'm learning assembly and just finished coding the n-queens problem in nasm.

The n-queens problems consists of placing n queens on a nxn chessboard so that no two queens are in the same row, column or diagonal (so that no queen could take another). For years, this is the first program I write in any new language I learn.

If there is interest in the code, I can post it here.

[Evenbit]

Yes. Please post the code. I would like to see it.

Nathan.

[fmartins]

Here is the code:

; queens.asm
;
; The n queens problem, in nasm.
; Solves the n-queens problem by a depth-first tree search.
; Board symmetries are not considered.
;
; Output format:
; Solutions are printed as a sequence of n integers. Each integer
; gives the position of a queen in a column. For example, for n=8,
; the output line
;       1 5 8 6 3 7 2 4
; means that queens are placed (using standard chess notation) on
; squares a1, b5, c8, d6, e3, f7, g2 and h4.
;
; Notes:
; The code assumes that n is at most 20. To increase this limit, change
; the value specified for the constant NMAX and rebuild. The code is
; naive, so don't expect fast results for even moderately large n.
;
; To assemble/link in windows under Cygwin:
; nasm -o queens.o -f win32 queens.asm
; gcc -o queens queens.o
;
; Not tested in other platforms. If you test the code in other
; platforms, or have comments or suggestions, please contact the
; author.
;
; Author: L. Felipe Martins
; [e-mail]

section .data
NMAX        equ 20              ; Maximum board size
board       times NMAX dd 0     ; The board
nsols       dd 0                ; Number of solutions

; Formats for input and output
promptn     db 'Enter number of queens (an integer): ',0
fmtintr     db '%d', 0
fmtintw     db '%d ', 0
promptyn    db 'Print all solutions (y or n)? ', 0
fmtstr      db '%s', 0
msgerryn    db 'Error: invalid input', 10, 0
msgerrint   db 'Error: invalid integer', 10, 0
fmtnsol     db 'Number of solutions: %u', 10, 0
fmtnl       db 10, 0

section .bss
n       resd 1                      ; Board size
bprt    resd 1                      ; Indicator for printing solutions
buffer  resb 128

section .text
        global _main
        extern _printf, _scanf
    
_main:
        enter 0, 0
        push    promptn             ; Prompt for n and read it
        call    _printf
        add     esp, 4
        push    n
        push    fmtintr
        call    _scanf
        add     esp, 8
        cmp     dword [n], 0        ; Check n for correct range
        jle     invalid_n
        cmp     dword [n], NMAX
        jle     get_yn
invalid_n:
        push    msgerrint
        call    _printf
        add     esp, 4
        mov     eax, 1
        jmp     finish        
get_yn:
        push    promptyn            ; Prompt for y/n and read it
        call    _printf
        add     esp, 4
        push    buffer
        push    fmtstr
        call    _scanf
        add     esp, 8

        mov     dword [bprt],1      ; Set bprt according to y/n
        mov     al, [buffer]
        cmp     al, 'y'
        jz      start_search
        cmp     al, 'Y'
        jz      start_search
        cmp     al, 'n'
        jz      set_bprt_0
        cmp     al, 'N'
        jz      set_bprt_0
        push    msgerryn            ; Invalid input for y/n
        call    _printf
        add     esp, 4
        mov     eax, 1
        jmp     finish
set_bprt_0:
        mov     dword [bprt], 0

        ; Search for solutions starts here
        ; ebx points to the column where a new queen
        ; is being placed
start_search:               
        mov     ebx, 0
cont_search:
        mov     eax,[4*ebx+board]   ; Increment row     
        inc     eax
        cmp     eax, dword [n]      ; Check if row <= n
        jle     check_board
        dec     ebx                 ; Return to previous column
        cmp     ebx, 0              ; If ebx < 0, search is finished
        jnge    near search_finished
        jmp     cont_search

check_board:
        mov     [4*ebx+board],eax   ; Check if last queen does
        cmp     ebx, 0              ; not attack other queens
        je      accept_board
        mov     ecx, ebx
        mov     edx, [4*ecx + board]
        mov     esi, board
        cld
test_loop:
        lodsd
        sub     eax, edx            ; Check if queens are in same row
        jz      cont_search
        cmp     eax, 0
        jg      eax_positive
        neg     eax
eax_positive:
        sub     eax, ecx            ; Check if queens are in same diagonal
        jz      cont_search
        loop    test_loop

accept_board:
        inc     ebx                 ; Go to next column
        cmp     ebx, [n]            ; If ebx==n, found a solution
        jz      found_solution
        mov     dword[4*ebx+board],0
        jmp     cont_search

found_solution:
        inc     dword [nsols]       ; Increment solution count
        dec     ebx                 ; Continue search in last column
        cmp     dword [bprt], 0     ; Check if solution should be printed
        jz      cont_search

        mov     ecx, [n]            ; Print solution
        mov     esi, board
print_loop:
        push    ecx
        lodsd
        push    eax
        push    fmtintw
        call    _printf
        add     esp, 8
        pop     ecx
        loop    print_loop

        push    fmtnl               ; print new line
        call    _printf
        add     esp, 4
        jmp     cont_search

search_finished:
        push    dword [nsols]       ; Print number of solutions
        push    fmtnsol
        call    _printf
        add     esp, 8        
        mov     eax, 0

finish:
        leave
        ret

[Evenbit]

Thank you! It looks nice.

BTW, I can confirm that if you remove the underscores ( change the "_main", "_printf", and "_scanf" symbols to just "main", "printf", and "scanf" ) it assembles ( using "-f elf" rather than "-f win32" option ) fine and runs under Linux.

Nathan.

[coded_hitec]

Hey thanks for the code gentleman
really handy for me