1 #include <stdlib.h>
2 #include <stdio.h>
3 #include <iostream>
4 #include <string>
5 #include <list>
6 #include "puzgen.h"
7 #include "exceptions.h"
8 #include "utils.h"
9
10
11
Possibilities()12 Possibilities::Possibilities()
13 {
14 reset();
15 }
16
Possibilities(std::istream & stream)17 Possibilities::Possibilities(std::istream &stream)
18 {
19 for (int row = 0; row < PUZZLE_SIZE; row++)
20 for (int col = 0; col < PUZZLE_SIZE; col++)
21 for (int element = 0; element < PUZZLE_SIZE; element++)
22 pos[col][row][element] = readInt(stream);
23 }
24
reset()25 void Possibilities::reset()
26 {
27 for (int i = 0; i < PUZZLE_SIZE; i++)
28 for (int j = 0; j < PUZZLE_SIZE; j++)
29 for (int k = 0; k < PUZZLE_SIZE; k++)
30 pos[i][j][k] = k + 1;
31 }
32
checkSingles(int row)33 void Possibilities::checkSingles(int row)
34 {
35 int cellsCnt[PUZZLE_SIZE]; // count of elements in cells
36 int elsCnt[PUZZLE_SIZE]; // total count of elements in row
37 int elements[PUZZLE_SIZE]; // one element of each cell
38 int elCells[PUZZLE_SIZE]; // one cell of each element
39
40 memset(cellsCnt, 0, sizeof(cellsCnt));
41 memset(elsCnt, 0, sizeof(elsCnt));
42 memset(elements, 0, sizeof(elements));
43 memset(elCells, 0, sizeof(elCells));
44
45 // check if there is only one element left in cell(col, row)
46 for (int col = 0; col < PUZZLE_SIZE; col++)
47 for (int i = 0; i < PUZZLE_SIZE; i++) {
48 if (pos[col][row][i]) {
49 elsCnt[i]++;
50 elCells[i] = col;
51 cellsCnt[col]++;
52 elements[col] = i + 1;
53 }
54 }
55
56 bool changed = false;
57
58 // check for cells with single element
59 for (int col = 0; col < PUZZLE_SIZE; col++) {
60 if ((cellsCnt[col] == 1) && (elsCnt[elements[col] - 1] != 1)) {
61 // there is only one element in cell but it used somewhere else
62 int e = elements[col] - 1;
63 for (int i = 0; i < PUZZLE_SIZE; i++)
64 if (i != col)
65 pos[i][row][e] = 0;
66 changed = true;
67 }
68 }
69
70 // check for single element without exclusive cell
71 for (int el = 0; el < PUZZLE_SIZE; el++)
72 if ((elsCnt[el] == 1) && (cellsCnt[elCells[el]] != 1)) {
73 int col = elCells[el];
74 for (int i = 0; i < PUZZLE_SIZE; i++)
75 if (i != el)
76 pos[col][row][i] = 0;
77 changed = true;
78 }
79
80 if (changed)
81 checkSingles(row);
82 }
83
exclude(int col,int row,int element)84 void Possibilities::exclude(int col, int row, int element)
85 {
86 if (! pos[col][row][element - 1])
87 return;
88
89 pos[col][row][element - 1] = 0;
90
91 checkSingles(row);
92 }
93
set(int col,int row,int element)94 void Possibilities::set(int col, int row, int element)
95 {
96 for (int i = 0; i < PUZZLE_SIZE; i++)
97 if ((i != element - 1))
98 pos[col][row][i] = 0;
99 else
100 pos[col][row][i] = element;
101
102 for (int j = 0; j < PUZZLE_SIZE; j++)
103 if (j != col)
104 pos[j][row][element - 1] = 0;
105
106 checkSingles(row);
107 }
108
isPossible(int col,int row,int element)109 bool Possibilities::isPossible(int col, int row, int element)
110 {
111 return pos[col][row][element - 1] == element;
112 }
113
isDefined(int col,int row)114 bool Possibilities::isDefined(int col, int row)
115 {
116 int solvedCnt = 0, unsolvedCnt = 0;
117 for (int i = 0; i < PUZZLE_SIZE; i++)
118 if (! pos[col][row][i])
119 unsolvedCnt++;
120 else
121 solvedCnt++;
122 return ((unsolvedCnt == PUZZLE_SIZE-1) && (solvedCnt == 1));
123 }
124
125
getDefined(int col,int row)126 int Possibilities::getDefined(int col, int row)
127 {
128 for (int i = 0; i < PUZZLE_SIZE; i++)
129 if (pos[col][row][i])
130 return i + 1;
131 return 0;
132 }
133
134
isSolved()135 bool Possibilities::isSolved()
136 {
137 for (int i = 0; i < PUZZLE_SIZE; i++)
138 for (int j = 0; j < PUZZLE_SIZE; j++)
139 if (! isDefined(i, j))
140 return false;
141 return true;
142 }
143
144
isValid(SolvedPuzzle & puzzle)145 bool Possibilities::isValid(SolvedPuzzle &puzzle)
146 {
147 for (int row = 0; row < PUZZLE_SIZE; row++)
148 for (int col = 0; col < PUZZLE_SIZE; col++)
149 if (! isPossible(col, row, puzzle[row][col]))
150 return false;
151 return true;
152 }
153
154
getPosition(int row,int element)155 int Possibilities::getPosition(int row, int element)
156 {
157 int cnt = 0;
158 int lastPos = -1;
159
160 for (int i = 0; i < PUZZLE_SIZE; i++)
161 if (pos[i][row][element - 1] == element) {
162 cnt++;
163 lastPos = i;
164 }
165
166 return cnt == 1 ? lastPos : -1;
167 }
168
print()169 void Possibilities::print()
170 {
171 for (int row = 0; row < PUZZLE_SIZE; row++) {
172 std::cout << (char)('A' + row) << " ";
173 for (int col = 0; col < PUZZLE_SIZE; col++) {
174 for (int i = 0; i < PUZZLE_SIZE; i++)
175 if (pos[col][row][i])
176 std::cout << pos[col][row][i];
177 else
178 std::cout << " ";
179 std::cout << " ";
180 }
181 std::cout << std::endl;
182 }
183 }
184
makePossible(int col,int row,int element)185 void Possibilities::makePossible(int col, int row, int element)
186 {
187 pos[col][row][element-1] = element;
188 }
189
save(std::ostream & stream)190 void Possibilities::save(std::ostream &stream)
191 {
192 for (int row = 0; row < PUZZLE_SIZE; row++)
193 for (int col = 0; col < PUZZLE_SIZE; col++)
194 for (int element = 0; element < PUZZLE_SIZE; element++)
195 writeInt(stream, pos[col][row][element]);
196 }
197
198
shuffle(short arr[PUZZLE_SIZE])199 static void shuffle(short arr[PUZZLE_SIZE])
200 {
201 int a, b, c;
202
203 for (int i = 0; i < 30; i++) {
204 a = (int)(((double)PUZZLE_SIZE)*rand()/(RAND_MAX+1.0));
205 if ((a < 0) || (a >= PUZZLE_SIZE)) {
206 std::cerr << "Index error" << std::endl;
207 exit(1);
208 }
209 b = (int)(((double)PUZZLE_SIZE)*rand()/(RAND_MAX+1.0));
210 if ((b < 0) || (b >= PUZZLE_SIZE)) {
211 std::cerr << "Index error" << std::endl;
212 exit(1);
213 }
214 c = arr[a];
215 arr[a] = arr[b];
216 arr[b] = c;
217 }
218 }
219
220
canSolve(SolvedPuzzle & puzzle,Rules & rules)221 static bool canSolve(SolvedPuzzle &puzzle, Rules &rules)
222 {
223 Possibilities pos;
224 bool changed = false;
225
226 do {
227 changed = false;
228 for (Rules::iterator i = rules.begin(); i != rules.end(); i++) {
229 Rule *rule = *i;
230 if (rule->apply(pos)) {
231 changed = true;
232 if (! pos.isValid(puzzle)) {
233 std::cout << "after error:" << std::endl;
234 pos.print();
235 throw Exception(L"Invalid possibilities after rule " +
236 rule->getAsText());
237 }
238 }
239 }
240 } while (changed);
241
242 bool res = pos.isSolved();
243 return res;
244 }
245
246
removeRules(SolvedPuzzle & puzzle,Rules & rules)247 static void removeRules(SolvedPuzzle &puzzle, Rules &rules)
248 {
249 bool possible;
250
251 do {
252 possible = false;
253 for (Rules::iterator i = rules.begin(); i != rules.end(); i++) {
254 Rule *rule = *i;
255 Rules excludedRules = rules;
256 excludedRules.remove(rule);
257 if (canSolve(puzzle, excludedRules)) {
258 possible = true;
259 rules.remove(rule);
260 delete rule;
261 break;
262 }
263 }
264 } while (possible);
265 }
266
267
genRules(SolvedPuzzle & puzzle,Rules & rules)268 static void genRules(SolvedPuzzle &puzzle, Rules &rules)
269 {
270 bool rulesDone = false;
271
272 do {
273 Rule *rule = genRule(puzzle);
274 if (rule) {
275 std::wstring s = rule->getAsText();
276 for (std::list<Rule*>::iterator i = rules.begin();
277 i != rules.end(); i++)
278 if ((*i)->getAsText() == s) {
279 delete rule;
280 rule = NULL;
281 break;
282 }
283 if (rule) {
284 //printf("adding rule %s\n", rule->getAsText().c_str());
285 rules.push_back(rule);
286 rulesDone = canSolve(puzzle, rules);
287 }
288 }
289 } while (! rulesDone);
290 }
291
292
293 /*static void printPuzzle(SolvedPuzzle &puzzle)
294 {
295 for (int i = 0; i < PUZZLE_SIZE; i++) {
296 char prefix = 'A' + i;
297 for (int j = 0; j < PUZZLE_SIZE; j++) {
298 if (j)
299 std::cout << " ";
300 std::cout << prefix << puzzle[i][j];
301 }
302 std::cout << std::endl;
303 }
304 }
305
306
307 static void printRules(Rules &rules)
308 {
309 for (Rules::iterator i = rules.begin(); i != rules.end(); i++)
310 std::cout << (*i)->getAsText() << std::endl;;
311 }*/
312
313
genPuzzle(SolvedPuzzle & puzzle,Rules & rules)314 void genPuzzle(SolvedPuzzle &puzzle, Rules &rules)
315 {
316 for (int i = 0; i < PUZZLE_SIZE; i++) {
317 for (int j = 0; j < PUZZLE_SIZE; j++)
318 puzzle[i][j] = j + 1;
319 shuffle(puzzle[i]);
320 }
321
322 genRules(puzzle, rules);
323 removeRules(puzzle, rules);
324 //printPuzzle(puzzle);
325 //printRules(rules);
326 }
327
328
openInitial(Possibilities & possib,Rules & rules)329 void openInitial(Possibilities &possib, Rules &rules)
330 {
331 for (Rules::iterator i = rules.begin(); i != rules.end(); i++) {
332 Rule *r = *i;
333 if (r->applyOnStart())
334 r->apply(possib);
335 }
336 }
337
338
getHintsQty(Rules & rules,int & vert,int & horiz)339 void getHintsQty(Rules &rules, int &vert, int &horiz)
340 {
341 vert = 0;
342 horiz = 0;
343
344 for (Rules::iterator i = rules.begin(); i != rules.end(); i++) {
345 Rule::ShowOptions so = (*i)->getShowOpts();
346 switch (so) {
347 case Rule::SHOW_VERT: vert++; break;
348 case Rule::SHOW_HORIZ: horiz++; break;
349 default: ;
350 }
351 }
352 }
353
savePuzzle(SolvedPuzzle & puzzle,std::ostream & stream)354 void savePuzzle(SolvedPuzzle &puzzle, std::ostream &stream)
355 {
356 for (int row = 0; row < PUZZLE_SIZE; row++)
357 for (int col = 0; col < PUZZLE_SIZE; col++)
358 writeInt(stream, puzzle[row][col]);
359 }
360
loadPuzzle(SolvedPuzzle & puzzle,std::istream & stream)361 void loadPuzzle(SolvedPuzzle &puzzle, std::istream &stream)
362 {
363 for (int row = 0; row < PUZZLE_SIZE; row++)
364 for (int col = 0; col < PUZZLE_SIZE; col++)
365 puzzle[row][col] = readInt(stream);
366 }
367
368
getRule(Rules & rules,int no)369 Rule* getRule(Rules &rules, int no)
370 {
371 int j = 0;
372 for (Rules::iterator i = rules.begin(); i != rules.end(); i++) {
373 if (j == no)
374 return *i;
375 j++;
376 }
377 throw Exception(L"Rule is not found");
378 }
379
380
381 /*int main(int argc, char *argv[])
382 {
383 srand(time(NULL));
384
385 Rules rules;
386 Puzzle puzzle;
387
388 genPuzzle(puzzle, rules);
389 printPuzzle(puzzle);
390 printRules(rules);
391
392 return 0;
393 }*/
394
395