CDivideAndConquer Class Reference

Divide-and-conquer knight's tour and tourney generator. More...

#include <DivideAndConquer.h>

Inheritance diagram for CDivideAndConquer:

Public Member Functions
	CDivideAndConquer ()
	Constructor. More...
void	Generate (CBoard &b, CycleType t)
	Generate a tour or tourney. More...
Public Member Functions inherited from CTile
	CTile ()
	Constructor. More...
	~CTile ()
	Destructor. More...

Private Member Functions
int	Split (int left, int right)
	Split coordinates nearly in half. More...
void	Join (CBoard &b, int midx, int midy)
	Join 4 sub-boards. More...
void	Generate (CBoard &b, CycleType t, const CRect &rect)
	Recursion. More...
void	GenerateBaseCase (CBoard &b, const CRect &rect)
	Base of recursion. More...

Additional Inherited Members
Protected Attributes inherited from CTile
CBoard *	m_pTile6x6 = nullptr
	Pointer to a 6x6 chessboard.
CBoard *	m_pTile6x8 = nullptr
	Pointer to a 6x8 chessboard.
CBoard *	m_pTile8x6 = nullptr
	Pointer to an 8x6 chessboard.
CBoard *	m_pTile8x8 = nullptr
	Pointer to an 8x8 chessboard.
CBoard *	m_pTile8x10 = nullptr
	Pointer to an 8x10 chessboard.
CBoard *	m_pTile10x8 = nullptr
	Pointer to a 10x8 chessboard.
CBoard *	m_pTile10x10 = nullptr
	Pointer to a 10x10 chessboard.
CBoard *	m_pTile10x12 = nullptr
	Pointer to a 10x12 chessboard.
CBoard *	m_pTile12x10 = nullptr
	Pointer to a 12x10 chessboard.

Detailed Description

This divide-and-conquer algorithm used in this class was invented by me, the creator of this software, back in the 1990s. For more details, see Parberry, "An efficient algorithm for the knight's tour problem", Discrete Applied Mathematics, 73:251-260, 1997. It was also described in Parberry, "Scalability of a neural network for the knight's tour problem", Neurocomputing, 12:19-34, 1996. Loosely speaking, you divide a square chessboard into four quadrants, recursively create a closed knight's tour in each quadrant, and then join the four knight's tours by deleting four carefully chosen moves and inserting four to replace them.

Definition at line 48 of file DivideAndConquer.h.

Constructor & Destructor Documentation

CDivideAndConquer()

CDivideAndConquer::CDivideAndConquer

(

)

Default constructor.

Definition at line 30 of file DivideAndConquer.cpp.

Member Function Documentation

Generate() [1/2]

void CDivideAndConquer::Generate ( CBoard &  b, CycleType  t, const CRect &  rect  )

private

Generate a tour or tourney in a sub-board using divide-and-conquer. Requires that the board is directed, otherwise this function does nothing. This is a recursive function, but the depth of recursion is only \(\log_2 n + O(1)\) and the total work done is \(O(n^2)\) for an \(n \times n\) board (that is, time linear in the size of the board).

Parameters

b	[in, out] Board.
t	Tourney descriptor.
rect	Rectangle defining sub-board.

Definition at line 52 of file DivideAndConquer.cpp.

Generate() [2/2]

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

Generate a knight's tour or tourney.

Parameters

b	[in, out] Board.
t	Tourney descriptor.

Definition at line 37 of file DivideAndConquer.cpp.

GenerateBaseCase()

void CDivideAndConquer::GenerateBaseCase ( CBoard &  b, const CRect &  rect  )

private

Copy one of the base tiles in the base class CTile to a sub-board.

Parameters

b	[in, out] Board.
rect	Rectangle in which to place tile.

Definition at line 143 of file DivideAndConquer.cpp.

Join()

void CDivideAndConquer::Join ( CBoard &  b, int  midx, int  midy  )

private

Join together four tourneys created by the divide-and-conquer algorithm. Requires that the board is directed, otherwise this function does nothing. The base tours in CTour were carefully chosen so that they include the moves shown in the image below. This implies that all recursively created tours also include these moves.

We choose four of those edges \(A, B, C, D\) as shown at left in the image below and replace them with the edges \(E, F, G, H\) shown at right.

Parameters

b	[in, out] Board.
midx	Split x-coordinate.
midy	Split y-coordinate.

Definition at line 107 of file DivideAndConquer.cpp.

Split()

int CDivideAndConquer::Split ( int  left, int  right  )

private

Splits a pair of coordinates nearly in half such that both parts have even parity.

Parameters

left	Left coordinate.
right	Right coordinate.

Returns

The split of the two coordinates.

Definition at line 86 of file DivideAndConquer.cpp.