8 Queens on the Board << Back

There is this eight queens puzzle. Now solve it in VDF.

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.