dancing_links Class Template Reference
[Node Algorithms]

#include <adobe/dancing_links.hpp>

List of all members.

---

Detailed Description

template<std::size_t Rows, std::size_t Cols>
class adobe::dancing_links< Rows, Cols >

The implementation is based on the Dancing Links Algorithm paper published by Knuth:

http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz

This class is an implementation of the "1-cover" problem:

Given a matrix of 1s and 0s, is there a subset of the rows such that there is one and only one 1 in each column?

It turns out a lot of interesting problems can be encoded in such a way that the 1-cover algorithm can be used to solve them (For example, counting the number of possible solutions to a Sudoku puzzle). Knuth talks in general about exact-cover problems (placing dominoes on a chessboard, the N-queens problem, etc.), and how each of these are specializations of the 1-cover problem, and so can be solved by this algorithm.

Definition at line 86 of file dancing_links.hpp.

Public Member Functions
std::size_t	search (std::size_t max_solutions)
template<typename ResultCallback>
std::size_t	search (std::size_t max_solutions, ResultCallback callback)
void	set (std::size_t row, std::size_t col)
void	set_secondary_column (std::size_t col)

---

Member Function Documentation

std::size_t search

(

std::size_t

max_solutions

)

Performs a search looking for solutions to the 1-cover problem.

Parameters:

max_solutions

Maximum number of solutions to find before breaking out of the search.

Returns:

the number of solutions actually found

Definition at line 117 of file dancing_links.hpp.

std::size_t search	(	std::size_t	max_solutions,
		ResultCallback	callback
	)

Performs a search looking for solutions to the 1-cover problem. When a solution is found the callback is called once for every row in the solution. The signature for the callback is:

void (*ResultCallback)(std::size_t row, bool last_row_in_solution);

Parameters:

	max_solutions	Maximum number of solutions to find before breaking out of the search.
	callback	callback

Returns:

the number of solutions actually found

Definition at line 102 of file dancing_links.hpp.

void set	(	std::size_t	row,
		std::size_t	col
	)

Establishes a 1-node at the intersection of [ row, col ].

Parameters:

	row	The row in which the node will be set
	col	The column in which the node will be set

Precondition:

You must start with the top-left node and work to the right, then down, when setting nodes in the matrix. i.e., This must be the right-bottom-most node you have set to this point.

Definition at line 95 of file dancing_links.hpp.

void set_secondary_column

(

std::size_t

col

)

Secondary columns take dancing links to the next step, in that they allow for a column to be optionally used zero or one times. This essentially allows for a condition that can be met once but no more than once.

Parameters:

col

The column which will be made secondary

Definition at line 98 of file dancing_links.hpp.