-
Notifications
You must be signed in to change notification settings - Fork 0
/
DancingLinks.h
121 lines (99 loc) · 2.95 KB
/
DancingLinks.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**
* DancingLinks.h declares the dancing links data structure and algorithm.
* @author Charlie Keaney
*/
#ifndef DANCING_LINKS_H
#define DANCING_LINKS_H 1
#include <iostream>
#define DEBUG_DISPLAY_CONSTRUCTION_INFO 0
#define DEBUG_DISPLAY_LINKING_INFO 0
#define DEBUG_DISPLAY_COVER_INFO 0
#define DEBUG_DISPLAY_OPTIONS_TO_CONSTRAINTS 0
#define DEBUG_DISPLAY_CONSTRAINTS_TO_OPTIONS 0
#define DEBUG_DISPLAY_SEARCH_CALLS 0
#define DEBUG_DISPLAY_SEARCH_CHOICE 0
#define DEBUG_DISPLAY_SEARCH_ACCESSES 0
#define DEBUG_DISPLAY_SEARCH_INFO 0
using namespace std;
class FourWayLinkedNode;
class DancingLinksNode;
class DancingLinksColumn;
class DancingLinksMatrix;
/** FourWayLinkedNode
* A class of data object used to represent generic nodes within the matrix.
* Serves as the foundation of all other objects to represent their four way
* doubly nature
*/
class FourWayLinkedNode {
private:
FourWayLinkedNode* up;
FourWayLinkedNode* down;
FourWayLinkedNode* left;
FourWayLinkedNode* right;
public:
FourWayLinkedNode();
FourWayLinkedNode* get_up();
FourWayLinkedNode* get_down();
FourWayLinkedNode* get_left();
FourWayLinkedNode* get_right();
void set_up(FourWayLinkedNode* n);
void set_down(FourWayLinkedNode* n);
void set_left(FourWayLinkedNode* n);
void set_right(FourWayLinkedNode* n);
};
/** DancingLinksNode
* A class of data object used to represent a non-top layer node
* within the dancing links matrix. Not a generic type for all
* nodes, since headers and the root do not have data and a column.
*/
class DancingLinksNode : public FourWayLinkedNode {
private:
DancingLinksColumn* column;
int data;
public:
DancingLinksNode(int, DancingLinksColumn*);
DancingLinksColumn* get_column();
int get_data();
DancingLinksNode* get_left();
DancingLinksNode* get_right();
};
/** DancingLinksColumn
* This class represents a column (a node on the top row) within the
* matrix used by the dancing links algorithm.
*/
class DancingLinksColumn : public FourWayLinkedNode {
private:
char* name;
int size;
public:
DancingLinksColumn(char* n);
~DancingLinksColumn();
char* get_name();
int get_size();
DancingLinksColumn* get_left();
DancingLinksColumn* get_right();
void insert_left(DancingLinksColumn* l);
void insert_right(DancingLinksColumn* r);
void cover();
void uncover();
void set_size(int s);
};
/** DancingLinksMatrix
* A class used to represent the entire matrix used by the dancing
* links algorithm as a data object.
*/
class DancingLinksMatrix {
private:
DancingLinksColumn* h;
public:
DancingLinksMatrix(bool piece_at_pos[], int num_columns, int num_rows);
~DancingLinksMatrix();
int full_search(int k, DancingLinksNode** o);
int partial_search(int k, DancingLinksNode** o);
int* solve();
int get_num_columns();
int get_num_rows();
void print_grid();
void print_setwise(DancingLinksNode** o);
};
#endif