N Queens Puzzle is a puzzle which asks you to place N chess queens on an NxN chess board so that no two queens are attacking each other. Two queens are attacking each other if they are on the same row, diagonal or column. I solved it using recursion in the dialect of AEC that's targeting WebAssembly. However, the dialect of AEC that's targeting x86 doesn't support custom functions (let alone recursion), so I cannot solve it the same way in it. So I solved it in the AEC dialect targeting x86 using stack instead of using recursion.
;A very advanced example: Solving the n-Queens Puzzle.
; https://flatassembler.github.io/nQueensPuzzle.html
AsmStart
macro pushIntegerToTheSystemStack x
{
sub esp,4
fld dword [x]
fistp dword [esp]
}
macro pushPointerToTheSystemStack x
{
sub esp,4
lea ebx,[x]
mov [esp],ebx
}
macro pushStringToTheSystemStack x
{
sub esp,4
mov dword [esp],x
}
format PE console
entry start
include 'win32a.inc'
section '.text' code executable
start:
AsmEnd
enterTheNumberString <= "Enter the number of queens.", 10, 0
floatSign <= "%f", 0
AsmStart
pushPointerToTheSystemStack enterTheNumberString
call [printf]
add esp, 4 ;Cleaning up the system stack. When writing in assembly, there is no compiler to do that for you.
pushPointerToTheSystemStack n
pushPointerToTheSystemStack floatSign
call [scanf]
add esp, 8
AsmEnd
topOfMyStack := 1
numberOfSolutions := 0
myStack[topOfMyStack * (n + 1)] := 0
While topOfMyStack > 0
howManyQueensAreOnTheBoard := myStack[topOfMyStack * (n + 1)]
i := 0
While i < howManyQueensAreOnTheBoard
queens[i] := myStack[topOfMyStack * (n + 1) + i + 1]
i := i + 1
EndWhile
topOfMyStack := topOfMyStack - 1
If howManyQueensAreOnTheBoard = n
numberOfSolutions := numberOfSolutions + 1
i := 0
While i < n
integerSignFollowedBySpace <= "%d ", 0
'A' + i ;The compiler will store this into the variable "result"
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp, 4
AsmEnd
queens[i] + 1
AsmStart
pushIntegerToTheSystemStack result
pushPointerToTheSystemStack integerSignFollowedBySpace
call [printf]
add esp, 8
AsmEnd
i := i + 1
EndWhile
AsmStart
pushPointerToTheSystemStack newLineString
call [printf]
add esp, 4
AsmEnd
twoSpacesAndPlus <= " +",0
AsmStart
pushPointerToTheSystemStack twoSpacesAndPlus
call [printf]
add esp, 4
AsmEnd
column := 0
While column < n
minusFollowedByPlus <= "-+", 0
AsmStart
pushPointerToTheSystemStack minusFollowedByPlus
call [printf]
add esp, 4
AsmEnd
column := column + 1
EndWhile
AsmStart
pushPointerToTheSystemStack newLineString
call [printf]
add esp, 4
AsmEnd
row := n - 1
While row > 0 | row = 0
integerSignPrecededBySpace <= " %d",0
integerSign <= "%d",0
If row + 1 < 10
row + 1
AsmStart
pushIntegerToTheSystemStack result
pushPointerToTheSystemStack integerSignPrecededBySpace
call [printf]
add esp, 8
AsmEnd
Else
row + 1
AsmStart
pushIntegerToTheSystemStack result
pushPointerToTheSystemStack integerSign
call [printf]
add esp, 8
AsmEnd
EndIf
'|'
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp,4
AsmEnd
column := 0
While column < n
(queens[column] = row) ? 'Q' : (mod(row + column, 2) = 1) ? ' ' : '*'
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp, 4
AsmEnd
'|'
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp,4
AsmEnd
column := column + 1
EndWhile
AsmStart
pushPointerToTheSystemStack newLineString
call [printf]
add esp, 4
AsmEnd
row := row - 1
column := 0
AsmStart
pushPointerToTheSystemStack twoSpacesAndPlus
call [printf]
add esp, 4
AsmEnd
While column < n
AsmStart
pushPointerToTheSystemStack minusFollowedByPlus
call [printf]
add esp, 4
AsmEnd
column := column + 1
EndWhile
AsmStart
pushPointerToTheSystemStack newLineString
call [printf]
add esp, 4
AsmEnd
EndWhile
threeSpaces <= " ", 0
AsmStart
pushPointerToTheSystemStack threeSpaces
call [printf]
add esp, 4
AsmEnd
column := 0
While column < n
'A' + column
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp, 4
AsmEnd
' '
AsmStart
pushIntegerToTheSystemStack result
call [putchar]
add esp, 4
AsmEnd
column := column + 1
EndWhile
AsmStart
pushPointerToTheSystemStack newLineString
call [printf]
add esp, 4
AsmEnd
Else
rowOfTheQueenWeAreAboutToAdd := n - 1
columnOfTheQueenWeAreAboutToAdd := howManyQueensAreOnTheBoard
While rowOfTheQueenWeAreAboutToAdd > 0 | rowOfTheQueenWeAreAboutToAdd = 0
isThereAQueenInTheSameRow := 0
i := 0
While i < howManyQueensAreOnTheBoard
If queens[i] = rowOfTheQueenWeAreAboutToAdd
isThereAQueenInTheSameRow := 1
EndIf
i := i + 1
EndWhile
isThereAQueenOnTheSameGlavnaDijagonala := 0 ;Sorry, I don't know how to say "glavna dijagonala" and "sporedna dijagonala" in English, and I am not wasting my time looking that up.
i := 0
While i < howManyQueensAreOnTheBoard
If queens[i] + i = rowOfTheQueenWeAreAboutToAdd + columnOfTheQueenWeAreAboutToAdd
isThereAQueenOnTheSameGlavnaDijagonala := 1
EndIf
i := i + 1
EndWhile
isThereAQueenOnTheSameSporednaDijagonala := 0
i := 0
While i < howManyQueensAreOnTheBoard
If queens[i] - i = rowOfTheQueenWeAreAboutToAdd - columnOfTheQueenWeAreAboutToAdd
isThereAQueenOnTheSameSporednaDijagonala := 1
EndIf
i := i + 1
EndWhile
isThereAQueenOnTheSameDiagonal := isThereAQueenOnTheSameGlavnaDijagonala = 1 | isThereAQueenOnTheSameSporednaDijagonala = 1
If not(isThereAQueenInTheSameRow = 1) & not(isThereAQueenOnTheSameDiagonal = 1)
topOfMyStack := topOfMyStack + 1
myStack[topOfMyStack * (n + 1)] := howManyQueensAreOnTheBoard + 1
i := 0
While i < howManyQueensAreOnTheBoard
myStack[topOfMyStack * (n + 1) + i + 1] := queens[i]
i := i + 1
EndWhile
myStack[topOfMyStack * (n + 1) + howManyQueensAreOnTheBoard + 1] := rowOfTheQueenWeAreAboutToAdd
EndIf
rowOfTheQueenWeAreAboutToAdd := rowOfTheQueenWeAreAboutToAdd - 1
EndWhile
EndIf
EndWhile
foundSolutionsString <= "Found %d solutions!", 10, 0
AsmStart
pushIntegerToTheSystemStack numberOfSolutions
pushPointerToTheSystemStack foundSolutionsString
call [printf]
add esp, 8
invoke system, _pause
invoke exit, 0
_pause db "PAUSE",0
newLineString db 10,0
section '.rdata' readable writable
result dd ?
n dd ?
myStack dd 1024 dup(?)
queens dd 16 dup(?)
topOfMyStack dd ?
i dd ?
numberOfSolutions dd ?
howManyQueensAreOnTheBoard dd ?
rowOfTheQueenWeAreAboutToAdd dd ?
columnOfTheQueenWeAreAboutToAdd dd ?
isThereAQueenInTheSameRow dd ?
isThereAQueenOnTheSameGlavnaDijagonala dd ?
isThereAQueenOnTheSameSporednaDijagonala dd ?
isThereAQueenOnTheSameDiagonal dd ?
row dd ?
column dd ?
section '.idata' data readable import
library msvcrt,'msvcrt.dll' ;Microsoft Visual C Runtime Library (comes with Windows 98 and newer).
import msvcrt,printf,'printf',system,'system',exit,'exit',scanf,'scanf',putchar,'putchar'
AsmEnd
You have the .exe file in this ZIP archive, it is called nQueensPuzzle.exe.
1 Answer 1
macro pushIntegerToTheSystemStack x macro pushPointerToTheSystemStack x macro pushStringToTheSystemStack x
integerSignFollowedBySpace <= "%d ", 0 twoSpacesAndPlus <= " +",0 minusFollowedByPlus <= "-+", 0
howManyQueensAreOnTheBoard dd ? rowOfTheQueenWeAreAboutToAdd dd ? columnOfTheQueenWeAreAboutToAdd dd ? isThereAQueenInTheSameRow dd ? isThereAQueenOnTheSameGlavnaDijagonala dd ? isThereAQueenOnTheSameSporednaDijagonala dd ? isThereAQueenOnTheSameDiagonal dd ?
Throughout your program, I see these very descriptive names for the user-defined symbols (macro, string, variable, ...). I'm just not too sure that their extreme lengths aren't impairing readability. Not everybody uses a super-wide screen (or a tiny-characters font).
FASM has a line continuation character, so maybe you could use it to turn
isThereAQueenOnTheSameDiagonal := isThereAQueenOnTheSameGlavnaDijagonala = 1 | isThereAQueenOnTheSameSporednaDijagonala = 1
into the slightly more readable:
isThereAQueenOnTheSameDiagonal :=\
isThereAQueenOnTheSameGlavnaDijagonala = 1 |\
isThereAQueenOnTheSameSporednaDijagonala = 1
;Sorry, I don't know how to say "glavna dijagonala" and "sporedna dijagonala" in English, and I am not wasting my time looking that up.
LMGTFY
On https://en.wikipedia.org/wiki/Main_diagonal are mentioned a lot of possible translations. I prefer next replacements:
isThereAQueenOnTheSameMainDiagonal dd ?
isThereAQueenOnTheSameAntiDiagonal dd ?
But wait, it gets better: you don't need these variables at all. I closely looked at the program and found that they're short-lived and only have to hold a couple of temporary values that you immediately after combine in the isThereAQueenOnTheSameDiagonal variable. I suggest next improved version requiring but a single While loop:
isThereAQueenOnTheSameDiagonal := 0
i := 0
While i < howManyQueensAreOnTheBoard
If queens[i] + i = rowOfTheQueenWeAreAboutToAdd + columnOfTheQueenWeAreAboutToAdd
isThereAQueenOnTheSameDiagonal := 1
EndIf
If queens[i] - i = rowOfTheQueenWeAreAboutToAdd - columnOfTheQueenWeAreAboutToAdd
isThereAQueenOnTheSameDiagonal := 1
EndIf
i := i + 1
EndWhile
macro pushPointerToTheSystemStack x { sub esp,4 lea ebx,[x] mov [esp],ebx } macro pushStringToTheSystemStack x { sub esp,4 mov dword [esp],x }
Why does this pushPointerToTheSystemStack macro use the EBX register? And why does it use LEA instead of the more efficient MOV?
You can write it identically to the pushStringToTheSystemStack macro. And if you care about codesize, then just write push x within the macro.
Or alternatively, don't waste a macro and directly write the push instruction in the ASM block (eg. pushPointerToTheSystemStack enterTheNumberString becomes push enterTheNumberString).