-
Notifications
You must be signed in to change notification settings - Fork 0
/
hidden_single.cpp
175 lines (153 loc) · 4.96 KB
/
hidden_single.cpp
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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include "hidden_single.h"
const int HS_ROW = 1;
const int HS_COL = 2;
const int HS_BOX = 3;
HiddenSingle::HiddenSingle(Target _target, int _type, std::vector<Key> _keys, std::vector<Spot> _roots, std::vector<int> _root_types, int _val) {
target = _target;
type = _type;
keys = _keys;
roots = _roots;
root_types = _root_types;
val = _val;
}
void HiddenSingle::apply(BitMatrix* bits) {
bits->set_value(target.spot, val);
}
void HiddenSingle::full_display(Output* out) {
// display roots
for(int i=0; i < roots.size(); i++) {
out->highlight_cell(roots[i], 0.8, 1.0, 1.0);
}
// display rule and spot
if(type == HS_ROW) {
out->highlight_row(target.spot.row, 0.9, 0.9, 0.9);
out->highlight_cell(target.spot, 1.0, 0.8, 0.8);
out->highlight_candidate(target.spot, val, 1.0, 0.5, 0.5);
} else if(type == HS_COL) {
out->highlight_col(target.spot.col, 0.9, 0.9, 0.9);
out->highlight_cell(target.spot, 1.0, 0.8, 0.8);
out->highlight_candidate(target.spot, val, 1.0, 0.5, 0.5);
} else if(type == HS_BOX) {
out->highlight_box(boxid_of_spot(target.spot), 0.9, 0.9, 0.9);
out->highlight_cell(target.spot, 1.0, 0.8, 0.8);
out->highlight_candidate(target.spot, val, 1.0, 0.5, 0.5);
}
}
void HiddenSingle::display_keys(Output* out) {
for(int i=0; i < keys.size(); i++) {
float weight = (keys[i].multiplicity == 1 ? 0.0 : (keys[i].multiplicity == 2 ? 0.5 : 0.8));
out->outline_cell(keys[i].spot, 1.5, 1.0, weight, weight);
}
}
std::vector<Target> HiddenSingle::target_list() {
std::vector<Target> ret;
ret.push_back(target);
return ret;
}
std::vector<Key> HiddenSingle::key_list() {
return keys;
}
Pattern* HiddenSingle::clone() {
return (new HiddenSingle(*this));
}
void HiddenSingle::describe(std::ostream& out) {
out << this;
}
std::ostream& operator<<(std::ostream& out, HiddenSingle* hs) {
out << "Hidden Single (" << (hs->type == HS_BOX ? "box" : (hs->type == HS_ROW ? "row" : "col")) << ")" << std::endl;
out << "\tTarget: " << hs->target;
return out;
}
void unit_hidden_singles(Bits* bits, std::vector<HiddenSingle>* ret, std::vector<Spot>& spots, int type) {
for(int i=0; i < spots.size(); i++) {
// for each spot p in unit
Spot p = spots[i];
if(bits->has_value(p)) { continue; }
// find candidates for all other spots in unit
int bitsum = 0;
for(int k=0; k < spots.size(); k++) {
if(k == i) { continue; }
bitsum |= bits->bit_of_spot(spots[k]);
}
// candidates for all spots in unit
int allbits = bitsum | bits->bit_of_spot(p);
if(bitsum == allbits) { continue; }
// must be one bit (candidate) not in others. call it val
int val = first_bit_int(allbits - bitsum);
std::vector<Key> possiblekeys;
std::vector<Spot> roots;
std::vector<int> root_types;
for(int k=0; k < spots.size(); k++) {
// for each other spot in unit
if(k == i) { continue; }
Spot px = spots[k];
// covers will hold all spots that would need to be removed
std::vector<Spot> covers = bits->covers_of_spot(px, val);
if(bits->has_value(px)) {
// if a blocker, add it to covers
covers.push_back(px);
} else {
// handle roots for display
int pxboxid = boxid_of_spot(px);
for(int m=0; m < covers.size(); m++) {
if(in_spots(roots, covers[m])) { continue; }
if(pxboxid == boxid_of_spot(covers[m])) {
roots.push_back(covers[m]);
root_types.push_back(HS_BOX);
} else if(px.row == covers[m].row) {
roots.push_back(covers[m]);
root_types.push_back(HS_ROW);
} else if(px.col == covers[m].col) {
roots.push_back(covers[m]);
root_types.push_back(HS_COL);
}
}
}
// make sure all covers (and if applicable the blocker) are possible
bool possible = true;
for(int m=0; m < covers.size(); m++) {
possible = possible && bits->is_possible(covers[m]);
}
if(!possible) { continue; }
// merge covers into possiblekeys
int mult = covers.size();
for(int m=0; m < covers.size(); m++) {
// for each cover
int coveridx = idx_of_keys(possiblekeys, covers[m]);
if(coveridx >= 0) {
// cover is already in possiblekeys
// set multiplicity to minimum
if(possiblekeys[coveridx].multiplicity > mult) {
possiblekeys[coveridx].multiplicity = mult;
}
} else {
// cover not already in possiblekeys
// add to possiblekeys
possiblekeys.push_back(Key(covers[m], mult));
}
}
}
ret->push_back(HiddenSingle(Target(p, val), type, possiblekeys, roots, root_types, val));
}
}
std::vector<HiddenSingle> find_hidden_singles(Bits* bits) {
std::vector<HiddenSingle> ret;
for(int i=0; i < 9; i++) {
// boxes
for(int j=0; j < 9; j++) {
std::vector<Spot> spots = spots_of_box(j);
unit_hidden_singles(bits, &ret, spots, HS_BOX);
}
// rows
for(int j=0; j < 9; j++) {
std::vector<Spot> spots = spots_of_row(j);
unit_hidden_singles(bits, &ret, spots, HS_ROW);
}
// cols
for(int j=0; j < 9; j++) {
std::vector<Spot> spots = spots_of_col(j);
unit_hidden_singles(bits, &ret, spots, HS_COL);
}
}
return ret;
}