Base chessboard. More...

#include <BaseBoard.h>

Inheritance diagram for CBaseBoard:

Public Member Functions
	CBaseBoard ()
	Constructor. More...

	CBaseBoard (UINT n)
	Constructor. More...

	CBaseBoard (UINT w, UINT h)
	Constructor. More...

	CBaseBoard (int move[], UINT w, UINT h)
	Constructor. More...

	~CBaseBoard ()
	Destructor. More...

void	Clear ()
	Clear the board of moves. More...

void	MakeDirected ()
	Make into a directed board. More...

void	MakeUndirected ()
	Make into an undirected board. More...

bool	IsTour ()
	Knight's tour test. More...

bool	IsTourney ()
	Tourney test. More...

bool	IsDirected ()
	Directed board test. More...

bool	IsUndirected ()
	Undirected board test. More...

bool	IsKnightMove (int i, int j)
	Knight's move test. More...

bool	IsUnused (int index)
	Test for unused cell. More...

bool	IsUnused (int pos, const MoveDelta &delta)
	Move is to unused cell. More...

bool	IsOnBoard (int pos, const MoveDelta &delta)
	Move stays on board. More...

int	GetAvailableMoveCount (int index)
	Get number of moves from a cell. More...

bool	InsertUndirectedMove (int src, int dest)
	Insert an undirected move. More...

bool	InsertDirectedMove (int src, int dest)
	Insert a directed move. More...

bool	DeleteMove (int src, int dest)
	Delete a move. More...

void	Save (std::string &name)
	Save board to a text file. More...

void	SaveToSVG (std::string &name)
	Save to an SVG file. More...

int	GetMoveIndex (int src, int dest)
	Get move index. More...

void	CopyToSubBoard (CBaseBoard &b, int x, int y)
	Copy to sub-board. More...

int	GetWidth ()
	Get width. More...

int	GetHeight ()
	Get height. More...

int	GetSize ()
	Get size. More...

int	operator[] (int index)
	Get a move from the board. More...

Protected Member Functions
bool	CellIndexInRange (int index)
	Index in range test. More...

bool	InRangeX (int x)
	X coordinate in range test. More...

bool	InRangeY (int y)
	Y coordinate in range test. More...

bool	IsMove (int i, int j)
	Move test. More...

int	GetDest (int i, const MoveDelta &delta)
	Get destination of move. More...

UINT	GetTourneyIds (int *&id)
	Get tourney identifier for each cell. More...

Protected Attributes
CRandom	m_cRandom
	PRNG.

UINT	m_nWidth = 0
	Board width in cells.

UINT	m_nHeight = 0
	Board height in cells.

UINT	m_nSize = 0
	Board size in cells.

int *	m_nMove = nullptr
	Primary move table.

int *	m_nMove2 = nullptr
	Secondary move table.

Detailed Description

The base chessboard provides the basic functionality needed to manipulate knight's tours and contains no new ideas from the paper. It records for each cell the two cells reachable from there via a knight's move from that cell while on a knight's tour or tourney. It is intended that the moves be knight's moves and that they form a tourney (a cycle cover of the knight's graph).

A board can be undirected or directed. The preferred state of the board is to be undirected, however, some of the algorithms that operate on knight's tours or tourneys run faster ondirected boards than on undirected ones up to a linear factor. We will use the convention that such algorithms will begin with a undirected board which they will first make directed, and that they will return an undirected board. There are obvious linear time algorithms for converting a tourney on an undirected board to a tourney on a directed board which maintaining the number of cycles, and vice-versa.

A directed board has two move tables m_nMove and m_nMove2. A knight's tour or tourney in a directed board can be found by starting at an unvisited cell i, moving to cell j = m_nMove[i], then repeatedly moving to either cell j = m_nMove[j] or m_nMove2[j] (whichever doesn't take us back to the previous cell) until cell i is reached again. For a tourney, repeat this until all cells have been visited. For a closed knight's tour it is sufficient to do this once.

An undirected board has only one move table m_nMove, and m_nMove2 is NULL. A knight's tour or tourney in an undirected board can be found by starting at an unvisited cell i, moving to cell j = m_nMove[i], then repeatedly moving to cell j = m_nMove[j] until cell i is reached again. For a tourney, repeat this until all cells have been visited. For a closed knight's tour it is sufficient to do this once.

Definition at line 69 of file BaseBoard.h.

Constructor & Destructor Documentation

◆ CBaseBoard() [1/4]

CBaseBoard::CBaseBoard ( )

Construct an empty board.

Definition at line 36 of file BaseBoard.cpp.

◆ CBaseBoard() [2/4]

CBaseBoard::CBaseBoard ( UINT n )

Construct a square undirected board.

Parameters

n	Board width and height.

Definition at line 42 of file BaseBoard.cpp.

◆ CBaseBoard() [3/4]

CBaseBoard::CBaseBoard	(	UINT	w,
		UINT	h
	)

Construct a rectangular undirected board.

Parameters

w	Board width.
h	Board height.

Definition at line 49 of file BaseBoard.cpp.

◆ CBaseBoard() [4/4]

CBaseBoard::CBaseBoard	(	int	move[],
		UINT	w,
		UINT	h
	)

Construct an undirected board from a move table.

Parameters

w	Board width.
h	Board height.
move	A \(w \times h\) move table.

Definition at line 68 of file BaseBoard.cpp.

◆ ~CBaseBoard()

CBaseBoard::~CBaseBoard ( )

Delete the move tables.

Definition at line 81 of file BaseBoard.cpp.

Member Function Documentation

◆ CellIndexInRange()

bool CBaseBoard::CellIndexInRange ( int index )

protected

Test whether a cell index is in the correct range to be on the board.

Parameters

index Cell index to test.

Returns: true if cell index is actually on the board.

Definition at line 102 of file BaseBoard.cpp.

◆ Clear()

void CBaseBoard::Clear ( )

Make every entry in the primary move table UNUSED and delete the secondary move table so that the cleared board is undirected.

Definition at line 89 of file BaseBoard.cpp.

◆ CopyToSubBoard()

void CBaseBoard::CopyToSubBoard	(	CBaseBoard &	b,
		int	x0,
		int	y0
	)

Copy a board into a sub-board of this board. Assumes that the board to be copied in is undirected.

Parameters

b	Undirected board to copy in.
x0	Column of first cell in which to copy b.
y0	Row of first cell in which to copy b.

Definition at line 443 of file BaseBoard.cpp.

◆ DeleteMove()

bool CBaseBoard::DeleteMove	(	int	src,
		int	dest
	)

Delete a move. Works for both directed and undirected boards.

Parameters

src	One end of move to delete.
dest	The other end of move to delete.

Returns: true if the delete was successful (the move was there).

Definition at line 528 of file BaseBoard.cpp.

◆ GetAvailableMoveCount()

int CBaseBoard::GetAvailableMoveCount ( int index )

Count the number of available moves from a given cell, that is, knight's moves that stay on the board and go to an unused cell. Assumes that the board is undirected.

Parameters

index Board cell index.

Returns: Number of moves from that that end up in unoccupied cells.

Definition at line 205 of file BaseBoard.cpp.

◆ GetDest()

int CBaseBoard::GetDest	(	int	i,
		const MoveDelta &	delta
	)

protected

Compute the destination of a move, given the cell index and the horizontal and vertical deltas of a move.

Parameters

i	Cell index.
delta	Move deltas.

Returns: Destination of the move from cell i with move deltas delta.

Definition at line 393 of file BaseBoard.cpp.

◆ GetHeight()

int CBaseBoard::GetHeight ( )

Reader function for height.

Returns: Height.

Definition at line 801 of file BaseBoard.cpp.

◆ GetMoveIndex()

int CBaseBoard::GetMoveIndex	(	int	src,
		int	dest
	)

Compute the index of a knight's move given the indexes of the cells. Returns UNUSED if the move is not as knight's move.

Parameters

src	Index of source cell.
dest	Index of destination cell.

Returns: The move index of the knight's move from src to dest.

Definition at line 408 of file BaseBoard.cpp.

◆ GetSize()

int CBaseBoard::GetSize ( )

Reader function for size (width times height).

Returns: Size.

Definition at line 808 of file BaseBoard.cpp.

◆ GetTourneyIds()

UINT CBaseBoard::GetTourneyIds ( int *& id )

protected

Assign a tourney identifier to each cell. This function works by numbering the cycles and sets the id entry for each cell in a cycle to be the cycle number in the order in which the cycles are found.

Parameters

id	[out] Array of tourney identifiers, one for each cell.

Returns: The number of cycles in the tourney.

Definition at line 599 of file BaseBoard.cpp.

◆ GetWidth()

int CBaseBoard::GetWidth ( )

Reader function for width.

Returns: Width.

Definition at line 794 of file BaseBoard.cpp.

◆ InRangeX()

bool CBaseBoard::InRangeX ( int x )

protected

Test whether a horizontal coordinate is on the board.

Parameters

x	An x-coordinate.

Returns: True if the x-coordinate is on the board.

Definition at line 110 of file BaseBoard.cpp.

◆ InRangeY()

bool CBaseBoard::InRangeY ( int y )

protected

Test whether a vertical coordinate is on the board.

Parameters

y	A y-coordinate.

Returns: True if the y-coordinate is on the board.

Definition at line 118 of file BaseBoard.cpp.

◆ InsertDirectedMove()

bool CBaseBoard::InsertDirectedMove	(	int	src,
		int	dest
	)

Insert a directed move. Assumes that the board is directed.

Parameters

src	One end of move to insert.
dest	The other end of move to insert.

Returns: true if the insert was successful (the cells were unused).

Definition at line 501 of file BaseBoard.cpp.

◆ InsertUndirectedMove()

bool CBaseBoard::InsertUndirectedMove	(	int	src,
		int	dest
	)

Insert an undirected move. Assumes that the board is undirected.

Parameters

src	One end of move to insert.
dest	The other end of move to insert.

Returns: true if the insert was successful (the cells were unused).

Definition at line 482 of file BaseBoard.cpp.

◆ IsDirected()

bool CBaseBoard::IsDirected ( )

Test whether the board is directed, that is, it is not undirected.

Returns: true If the board is directed.

Definition at line 319 of file BaseBoard.cpp.

◆ IsKnightMove()

bool CBaseBoard::IsKnightMove	(	int	i,
		int	j
	)

Test whether two cells are separated by a knight's move.

Parameters

i	Board cell index.
j	Board cell index.

Returns: true if j is a knight's move from i (and vice-versa)

Definition at line 138 of file BaseBoard.cpp.

◆ IsMove()

bool CBaseBoard::IsMove	(	int	i,
		int	j
	)

protected

Test whether a move is recorded in the move tables.

Parameters

i	Board index.
j	Board index.

Returns: true if there is a move from cell i to cell j on the board.

Definition at line 127 of file BaseBoard.cpp.

◆ IsOnBoard()

bool CBaseBoard::IsOnBoard	(	int	pos,
		const MoveDelta &	d
	)

Test whether a move stays on the board. Assumes that the board is undirected.

Parameters

pos	Cell index.
d	Move delta.

Returns: true If the cell move d away from pos is on the board.

Definition at line 190 of file BaseBoard.cpp.

◆ IsTour()

bool CBaseBoard::IsTour ( )

Knight's tour test for both directed and undirected boards.

Returns: true if this board contains a closed knight's tour.

Definition at line 240 of file BaseBoard.cpp.

◆ IsTourney()

bool CBaseBoard::IsTourney ( )

Tourney test for both directed and undirected boards.

Returns: true if this board contains a tourney.

Definition at line 268 of file BaseBoard.cpp.

◆ IsUndirected()

bool CBaseBoard::IsUndirected ( )

Test whether the board is undirected. If it is, then m_nMove2 will be NULL and vice-versa.

Returns: true If the board is undirected.

Definition at line 327 of file BaseBoard.cpp.

◆ IsUnused() [1/2]

bool CBaseBoard::IsUnused ( int index )

Test whether a cell is unused. Cells outside of the board are reported to be used. Note that this is different from the behaviour of GetMove(), which reports cells outside the board to be unused. Assumes that the board is undirected.

Parameters

index Cell index.

Returns: true if the cell with that index is unused.

Definition at line 161 of file BaseBoard.cpp.

◆ IsUnused() [2/2]

bool CBaseBoard::IsUnused	(	int	pos,
		const MoveDelta &	d
	)

Test whether a move ends up in an occupied (used) cell in a partially constructed knight's tour or tourney. If the move takes us off the board, then the cell is reported as used. Assumes that the board is undirected.

Parameters

pos	Board cell index.
d	Move deltas for a knight's move.

Returns: true If the cell move d away from pos is unused.

Definition at line 174 of file BaseBoard.cpp.

◆ MakeDirected()

void CBaseBoard::MakeDirected ( )

Make into a directed board by creating the second move table and copying the edges in the first move table into back edges in the second one.

Definition at line 335 of file BaseBoard.cpp.

◆ MakeUndirected()

void CBaseBoard::MakeUndirected ( )

Make into an undirected board by reorganizing the move order. It is assumed that the directed board contains a tourney. If not, then this function does nothing.

Definition at line 351 of file BaseBoard.cpp.

◆ operator[]()

int CBaseBoard::operator[] ( int index )

Get move from a cell. Cells outside of the board are reported as UNUSED. Note that this is different from the behaviour of IsUnused(), which reports cells outside the board to be used. Assumes that the board is undirected.

Parameters

index Cell index.

Returns: Move from the cell with that index.

Definition at line 232 of file BaseBoard.cpp.

◆ Save()

void CBaseBoard::Save ( std::string & name )

Save the board's move table to a text file. For example, if you saved an \(8 \times 8\) knight's tour, then it might look like the image below. For each board cell from top to bottom and left to right, the file lists the index of the move (in row-major order) that a knight on the knight's tour or tourney will use next when in cell. Assumes that the board is undirected.

Parameters

name	Root of file name.

Definition at line 571 of file BaseBoard.cpp.

◆ SaveToSVG()

void CBaseBoard::SaveToSVG ( std::string & name )

Save the board to an SVG file suitable for display on a web page. Open it up in your favorite browser. SVG files can be quite large, but the upside is that they are vector graphics, so they zoom very well without pixelization. Assumes that the board is undirected.

Parameters

name	Root of file name.

Definition at line 641 of file BaseBoard.cpp.

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CBaseBoard() [1/4]

◆ CBaseBoard() [2/4]

◆ CBaseBoard() [3/4]

◆ CBaseBoard() [4/4]

◆ ~CBaseBoard()

Member Function Documentation

◆ CellIndexInRange()

◆ Clear()

◆ CopyToSubBoard()

◆ DeleteMove()

◆ GetAvailableMoveCount()

◆ GetDest()

◆ GetHeight()

◆ GetMoveIndex()

◆ GetSize()

◆ GetTourneyIds()

◆ GetWidth()

◆ InRangeX()

◆ InRangeY()

◆ InsertDirectedMove()

◆ InsertUndirectedMove()

◆ IsDirected()

◆ IsKnightMove()

◆ IsMove()

◆ IsOnBoard()

◆ IsTour()

◆ IsTourney()

◆ IsUndirected()

◆ IsUnused() [1/2]

◆ IsUnused() [2/2]

◆ MakeDirected()

◆ MakeUndirected()

◆ operator[]()

◆ Save()

◆ SaveToSVG()