Chessboard. More...

#include <Board.h>

Inheritance diagram for CBoard:

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

	CBoard (UINT n)
	Constructor. More...

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

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

void	Shatter ()
	Shatter tourneys into more tourneys. More...

void	JoinUntilTour ()
	Join cycles to reduce tourney size. More...

void	Obfuscate ()
	Obfuscate function. More...

Public Member Functions inherited from CBaseBoard
	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...

Private Member Functions
void	FindRails (std::vector< CRail > &rails)
	Find all rails. More...

void	Switch (CRail &r)
	Switch a rail. More...

bool	IsRail (int s0, int d0, int s1, int d1)
	Rail test. More...

bool	IsRail (CRail &r)
	Rail test. More...

bool	Join ()
	Join cycles to reduce tourney size. More...

Additional Inherited Members
Protected Member Functions inherited from CBaseBoard
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 inherited from CBaseBoard
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

CBoard adds to CBaseBoard the additional functionality needed to shatter, join, and obfuscate tourneys. It contains an implementation of the new algorithms presented in the paper.

Definition at line 42 of file Board.h.

Constructor & Destructor Documentation

◆ CBoard() [1/4]

CBoard::CBoard ( )

Construct an empty board.

Definition at line 36 of file Board.cpp.

◆ CBoard() [2/4]

CBoard::CBoard ( UINT n )

Construct a square undirected board.

Parameters

n	Board width and height.

Definition at line 42 of file Board.cpp.

◆ CBoard() [3/4]

CBoard::CBoard	(	UINT	w,
		UINT	h
	)

Construct a rectangular undirected board.

Parameters

w	Board width.
h	Board height.

Definition at line 50 of file Board.cpp.

◆ CBoard() [4/4]

CBoard::CBoard	(	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 59 of file Board.cpp.

Member Function Documentation

◆ FindRails()

void CBoard::FindRails ( std::vector< CRail > & rails )

private

Find all rails. Assumes that the board is directed. The algorithm used is as follows. Suppose we have an \(n \times n\) board. Let \(0 < i \leq n\) be a cell index. The potential downward moves from cell \(i\) have move index \(4\), \(5\), \(6\), or \(7\).

If the move from cell \(i\) has index \(4\), then there are three potential rails incident with cell \(i\) and the corresponding parallel moves are separated from cell \(i\) by moves \(5\), \(6\), or \(7\), as shown below.

If the move from cell \(i\) has index \(5\), then there are three potential rails incident with cell \(i\), and the corresponding parallel moves are separated from cell \(i\) by moves \(4\), \(6\) or \(7\), as shown below.

If the move from cell \(i\) has index \(6\), then there are three potential rails incident with cell \(i\), and the corresponding parallel moves are separated from cell \(i\) by moves \(4\), \(5\) or \(7\), as shown below.

If the move from cell \(i\) has index \(7\), then there are three potential rails incident with cell \(i\), and the corresponding parallel moves are separated from cell \(i\) by moves \(4\), \(5\) or \(6\), as shown below.

We therefore iterate through \(0 < i \leq n\) and consider the two moves from cell \(i\). If one of these moves has index \(4\), then we check whether moves \(5\), \(6\), or \(7\) lead to a cell that also has move \(4\) from it. If so, then we add these rails to the rail vector provided to this function as a call-by-reference parameter. Similarly, we perform the respective checks when one of the moves from cell \(i\) has index \(5\), \(6\), or \(7\).

The rail list is permuted into random order before returning.

Parameters

rails [out] Rail list.

Definition at line 141 of file Board.cpp.

◆ IsRail() [1/2]

bool CBoard::IsRail	(	int	s0,
		int	d0,
		int	s1,
		int	d1
	)

private

Test whether four cells form a rail, that is, they are separated by knight's moves, the primary moves are present, and the cross moves are absent.

Parameters

s0	Index of source of first move.
d0	Index of destination of first move.
s1	Index of source of second move.
d1	Index of destination of second move.

Returns: true if the cells form a rail.

Definition at line 86 of file Board.cpp.

◆ IsRail() [2/2]

bool CBoard::IsRail ( CRail & r )

private

Test whether a rail is valid, that is, all moves are knight's moves, the primary moves are present, and the cross moves are absent. Calls CBaseBoard::IsRail(int, int, int, int) to do the actual work.

Parameters

r	Rail to be tested.

Returns: true if the rail is valid.

Definition at line 69 of file Board.cpp.

◆ Join()

bool CBoard::Join ( )

private

Join a tourney, that is, attempt to make it into a knight's tour by switching rails. Assumes that the tourney is directed. First a rail (multi-) graph is created with a vertex for each tourney and an edge for each cell-disjoint rail that connects them. Switching the rails in a spanning forest of the rail graph connects up as many cycles as it can (which may may not necessarily result in a knight's tour). For example, the following image shows the rail graph of a tourney at left. The numbers on the edges indicate the number of cell-disjoint rails that intersect two cycles. A breadth-first spanning tree of this graph is shown on the right.

Returns: true if the join succeeeded.

Definition at line 239 of file Board.cpp.

◆ JoinUntilTour()

void CBoard::JoinUntilTour ( )

Join a tourney until it becomes a knight's tour. Maintains directedness. Uses Join() to do the heavy lifting.

Definition at line 305 of file Board.cpp.

◆ Obfuscate()

void CBoard::Obfuscate ( )

Obfuscate a tourney by shattering it a few times. The board can be directed or undirected initially, but it will be undirected after obfuscating. The result should be a knight's tour in most cases.

Definition at line 214 of file Board.cpp.

◆ Shatter()

void CBoard::Shatter ( )

Shatter a tourney by switching a set of non-overlapping rails. Assumes that the board is directed.

Definition at line 199 of file Board.cpp.

◆ Switch()

void CBoard::Switch ( CRail & r )

private

Switch a rail. Assumes that the board is directed. The rails in the top row of this image get switched to the corresponding rails in the bottom row (and vice-versa).

Parameters

r A rail.

Definition at line 177 of file Board.cpp.

Public Member Functions

Private Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CBoard() [1/4]

◆ CBoard() [2/4]

◆ CBoard() [3/4]

◆ CBoard() [4/4]

Member Function Documentation

◆ FindRails()

◆ IsRail() [1/2]

◆ IsRail() [2/2]

◆ Join()

◆ JoinUntilTour()

◆ Obfuscate()

◆ Shatter()

◆ Switch()