#
8 Queens on the Board
<< Back

Use UI
Use Dll
External_Function GetTickCountU "GetTickCount" KERNEL32.DLL Returns UInteger
Define QUEENS for 8
Procedure DropAQueen Boolean[][] ByRef b Integer iX Integer iY
Integer xOffset yOffset iRow iCol
Move TRUE to b[iY][iX]
For xOffset From -1 to 1
For yOffset From -1 to 1
If (xOffset<>0 or yOffset<>0) Begin
Move iX to iCol
Move iY to iRow
Repeat
Add xOffset to iCol
Add yOffset to iRow
If (iCol<0 Or iCol>=QUEENS Or iRow<0 Or iRow>=QUEENS) Break
If (b[iRow][iCol] = FALSE) Move True to b[iRow][iCol]
Loop
End
Loop
Loop
End_Procedure
Global_Variable Integer gi
Procedure N_Queens Boolean[][] ByRef b Integer iCol
Boolean[QUEENS][QUEENS] lb
Integer iRow
Boolean bLastCol
Move (iCol >= (QUEENS-1)) to bLastCol
For iRow From 0 to (QUEENS-1)
If (b[iRow][iCol] = FALSE) Begin
If (bLastCol) Increment gi
Else Begin
Move b to lb
Send DropAQueen (&lb) iCol iRow
Send N_Queens (&lb) (iCol + 1)
End
End
Loop
End_Procedure
Procedure VDFMain
Boolean[QUEENS][QUEENS] b
UInteger uBegin uEnd
Move (GetTickCountU()) to uBegin
Send N_Queens (&b) 0
Move (GetTickCountU()) to uEnd
Showln "time: " (uEnd - uBegin) " - solutions:" gi
InKey FieldIndex
End_Procedure
Send VDFMain

###
This is a brute force method for finding all possible solutions to the eight queen puzzle. The solution doesn't exclude duplicates (such as the
same solution being rotated or mirrored). Whenever a solution is found, the global variable gi will be increased by one. The procedure
N_Queens are being called recursively to create temporary board lb. The cells in the 2D array b of boolean will contain the value
of TRUE if it is being occupied by a Queen or being attacked by a Queen, and FALSE if it is empty and not being attacked by any queen.

The performance goes down significantly as the constant QUEENS goes up. My computer would take too long to compute (as in I didn't want to keep waiting)
when QUEENS is greater than or equal to 14. This is all based on the performance in VDF. Just for fun, I did a C++ version here.

#include <windows.h>
#define QUEENS 8
void DropAQueen(BYTE b[][QUEENS], int x, int y)
{
int cx, cy, row, col;
b[y][x] = 1;
for (cx = -1; cx <=1; cx++)
for (cy = -1; cy <= 1; cy++)
{
if (cx != 0 || cy != 0)
{
col = x;
row = y;
for (;;)
{
col += cx;
row += cy;
if (col < 0 || col >= QUEENS || row < 0 || row >= QUEENS) break;
if (b[row][col] == 0) b[row][col] = 1;
}
}
}
}
int gi;
void N_Queens(BYTE b[][QUEENS], int col)
{
BYTE lb[QUEENS][QUEENS];
int row;
BOOL bLastCol = (col >= (QUEENS - 1));
for (row = 0; row < QUEENS; row++)
{
if (b[row][col] == 0)
{
if (bLastCol) gi++;
else
{
CopyMemory(lb, b, QUEENS*QUEENS);
DropAQueen(lb, col, row);
N_Queens(lb, col + 1);
}
}
}
}
int WINAPI WinMain(HINSTANCE hInstance,HINSTANCE,LPSTR lpCmdLine,int nCmdShow)
{
BYTE b[QUEENS][QUEENS];
TCHAR sz[32];
DWORD before, after;
ZeroMemory(b, QUEENS*QUEENS);
before = GetTickCount();
N_Queens(b, 0);
after = GetTickCount();
wsprintf(sz, TEXT("time: %u - solutions: %u"), after - before, gi);
MessageBox(NULL, sz, 0, 0);
ExitProcess(0);
return 0;
}

###
At QUEENS being 13, in VDF it took my machine 281.954 seconds to compute. In C++, with similar code, it only took 0.844 seconds to compute.