CWarnsdorff Class Reference

Knight's tour and tourney generator using Warnsdorff's heuristic. More...

#include <Warnsdorff.h>

Public Member Functions
	CWarnsdorff (int seed)
	Constructor. More...
void	Generate (CBoard &b, CycleType t)
	Generate a tour or tourney. More...

Private Member Functions
int	RandomClosedWalk (CBoard &b, int start)
	Create closed random walk. More...
bool	GenerateTour (CBoard &b)
	Generate a knight's tour. More...
bool	GenerateTourney (CBoard &b)
	Generate a tourney. More...

Private Attributes
CRandom	m_cRandom
	PRNG.

Detailed Description

Warnsdorff's Algorithm is a random walk that optimistically joins up to make one or more cycles aided by Warnsdorff's Heuristic which works. as follows Instead of choosing a random next move, it chooses a move at random from the set of moves that lead to a cell that has remaining the smallest number ofavailable moves to an unvisited square. The tourney version attempts to make a cycle as soon as possible, while the tour version holds off doing so for as long as possible. This results in distinctive patterns in the knight's tours and tourneys generated. For example, the image below shows a tourney with the cycles in color (left) and a knight's tour (right) generated by this algorithm.

See Conrad, Hindrichs, Morsy, and Wegener, "Wie es dem springer gelang schachbretter beliebiger groesse und zwischen beliebig vorgegebenen anfangs und endfeldern vollstaendig abzuschreiten", Spektrum der Wissenschaft, pages 10-14, 1992, and Conrad, Hindrichs, Morsy, and Wegener, "Solution of the knight's Hamiltonian path problem on chessboards", Discrete Applied Mathematics, 50(2):125-134, 1994.

Definition at line 57 of file Warnsdorff.h.

Constructor & Destructor Documentation

CWarnsdorff()

CWarnsdorff::CWarnsdorff

(

int

seed

)

The default constructor seeds the PRNG.

Parameters

seed	A random number seed.

Definition at line 35 of file Warnsdorff.cpp.

Member Function Documentation

Generate()

void CWarnsdorff::Generate	(	CBoard &	b,
		CycleType	t
	)

Generate a knight's tour or tourney using Warnsdorff's algorithm.

Parameters

b	[out] Board.
t	Cycle type.

Definition at line 265 of file Warnsdorff.cpp.

GenerateTour()

bool CWarnsdorff::GenerateTour ( CBoard &  b )

private

Attempt to generate a random knight's tour.

Parameters

b	[out] Board for generated tour.

Returns

true if generation is successful.

Definition at line 44 of file Warnsdorff.cpp.

GenerateTourney()

bool CWarnsdorff::GenerateTourney ( CBoard &  b )

private

Attempt to generate a random tourney.

Parameters

b	[in, out] Chessboard.

Returns

true if generation is successful.

Definition at line 137 of file Warnsdorff.cpp.

RandomClosedWalk()

int CWarnsdorff::RandomClosedWalk ( CBoard &  b, int  start  )

private

Take a random walk and close it into a cycle at the first opportunity.

Parameters

b	[in, out] Chessboard.
start	Index of the first cell on the walk.

Returns

Index of the last cell on the walk.

Definition at line 187 of file Warnsdorff.cpp.