File: sudoku-solve.C

package info (click to toggle)
gnudoq 0.94-2.1
  • links: PTS
  • area: main
  • in suites: jessie, jessie-kfreebsd, wheezy
  • size: 2,696 kB
  • ctags: 232
  • sloc: cpp: 2,695; makefile: 6
file content (661 lines) | stat: -rw-r--r-- 16,211 bytes parent folder | download | duplicates (4)
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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
#include "sudoku-solve.H"

#include <iostream>
#include <vector>
#include <cassert>
namespace sudoku
{
#ifndef SUDOKU_SOLVE_DEBUG
	const bool debug_output = false;
#else
	const bool debug_output = SUDOKU_SOLVE_DEBUG;
#endif
	rcb RCB(unsigned int index)
	{
		rcb t;
		t.row = index / COLS;
		t.col = index % COLS;
		t.bigbox = (t.row / 3) * 3 + (t.col / 3);
		return t;
	}

	unsigned int Index(const rcb& rcb)
	{
		return rcb.col + rcb.row * COLS;
	}

	bool Board::UnSet(unsigned int index)
	{
		if (item[index].val < 0)
		{
			return false;
		}

		--filled;

		int n = item[index].val;
		item[index].val = -1;

		rcb rcb = RCB(index);

		row[rcb.row].push(n);
		col[rcb.col].push(n);
		bigbox[rcb.bigbox].push(n);

		// possible moves are cross-section of all possible moves in groups
		item[index].poss = row[rcb.row];
		item[index].poss &= col[rcb.col] & bigbox[rcb.bigbox];

		// NOTE: division and remultiplication is not redundant: rounding!
		const unsigned int bigboxcol = rcb.bigbox % 3;
		const unsigned int bigboxrow = rcb.bigbox / 3;
		const unsigned int bigboxstart = bigboxrow * 27 + bigboxcol * 3;
		// add the number to the possible choices of the rest of the bigbox, ...
		{
			const unsigned int colstart = bigboxcol * 3;
			const unsigned int colend = colstart + 3;
			const unsigned int rowstart = bigboxrow * 3;
			const unsigned int rowend = rowstart + 3;

			unsigned int bigboxrowstart = bigboxstart;

			for (unsigned int r = rowstart; r < rowend; ++r)
			{
				Possible<int, 9> initial = row[r] & bigbox[rcb.bigbox];
				for (unsigned int c = colstart; c < colend; ++c)
				{
					const int i = bigboxrowstart + c - colstart;
					if (item[i].val < 0)
						item[i].poss = initial & col[c];
				}
				bigboxrowstart += COLS;
			}
		}
		// ... row, ...
		{
			const unsigned int rowindex = rcb.row * COLS;
			for (unsigned int bbc = 0; bbc < 3; ++bbc)
			{
				if (bbc == bigboxcol)
					continue;

				const unsigned int colstart = bbc * 3;
				const unsigned int colend = colstart + 3;

				Possible<int, 9> initial = row[rcb.row] & bigbox[bbc + bigboxrow * 3];

				for (unsigned int c = colstart; c < colend; ++c)
				{
					const int i = rowindex + c;
					if (item[i].val < 0)
						item[i].poss = initial & col[c];
				}
			}
		}
		// ... and column
		{
			for (unsigned int bbr = 0; bbr < 3; ++bbr)
			{
				if (bbr == bigboxrow)
					continue;

				const unsigned int rowstart = bbr * 3;
				const unsigned int rowend = rowstart + 3;

				Possible<int, 9> initial = col[rcb.col] & bigbox[bbr * 3 + bigboxcol];

				for (unsigned int r = rowstart; r < rowend; ++r)
				{
					const int i = rcb.col + r * COLS;
					if (item[i].val < 0)
						item[rcb.col + r * COLS].poss = initial & row[r];
				}
			}
		}
		return true;
	}

	bool Board::Set(unsigned int index, int n)
	{
		if (n == item[index].val)
			return true;
		if (n < 0)
		{
			return false;
		}

		rcb pos = RCB(index);
		// validate move
		if (item[index].val >= 0)
			return false;

		if (! (row[pos.row][n] && col[pos.col][n] && bigbox[pos.bigbox][n]))
			return false;

		++filled;
		item[index].val = n;
		item[index].poss.clear();
		//item[index].poss.push(n);

		row[pos.row].pop(n);
		col[pos.col].pop(n);
		bigbox[pos.bigbox].pop(n);

		// TODO: the following contains some redundancy, which should probably be eliminated
		// remove the number from the possible choices of the rest of the row, ...
		{
			const unsigned int rowstart = COLS * pos.row;
			const unsigned int rowmid = rowstart + pos.col;
			const unsigned int rowend = COLS * (pos.row + 1);
			for (unsigned int i = rowstart; i < rowmid; ++i)
				item[i].poss.pop(n);

			for (unsigned int i = rowmid + 1; i < rowend; ++i)
				item[i].poss.pop(n);
		}

		// ... column, ...
		{
			const unsigned int colstart = pos.col;
			const unsigned int colmid = colstart + pos.row * COLS;
			const unsigned int colend = BOXES;
			for (unsigned int i = colstart; i < colmid; i += COLS)
				item[i].poss.pop(n);

			for (unsigned int i = colmid + COLS; i < colend; i += COLS)
				item[i].poss.pop(n);
		}

		// ... and bigbox
		{
			// NOTE: division and remultiplication is not redundant: rounding!
			const unsigned int boxstart = (pos.row / 3) * 27 + (pos.col / 3) * 3;
			unsigned int boxrowstart = boxstart;
			for (unsigned int i = 0; i < 3; ++i)
			{
				for (unsigned int j = 0; j < 3; ++j)
				{
					item[boxrowstart + j].poss.pop(n);
				}
				boxrowstart += COLS;
			}
		}
		return true;
	}


	bool Board::Solveable()
	{
		for (int i = 0; i < BOXES; ++i)
		{
			if (item[i].val < 0 && item[i].poss.num() == 0)
				return false;
		}

		for (int bb = 0; bb < BIGBOXES; ++bb)
		{
			const unsigned int bbcol = (bb % 3);
			const unsigned int bbrow = (bb / 3);
			const unsigned int bbstart = bbrow * 27 + bbcol * 3;
			Possible<int,9> possible;
			possible.clear();
			for (int r = 0; r < 3; ++r)
			{
				for (int c = 0; c < 3; ++c)
				{
					possible |= item[bbstart + r * COLS + c].poss;
					//std::cout << bbstart + r * COLS + c << " ";
					//std::cout << possible.num() << " \n";
				}
			}
			//std::cout << std::endl;
			//std::cout << bigbox[bb].num() << " " << (possible & bigbox[bb]).num() << std::endl << std::endl;
			if (bigbox[bb].num() > (possible & bigbox[bb]).num())
				return false;
		}
		for (int c = 0; c < COLS; ++c)
		{
			Possible<int,9> possible;
			possible.clear();

			for (int r = 0; r < ROWS; ++r)
			{
				possible |= item[c + r * COLS].poss;
			}
			if (col[c].num() > (possible & col[c]).num())
				return false;
		}
		for (int r = 0; r < ROWS; ++r)
		{
			Possible<int,9> possible;
			possible.clear();
			unsigned int rowstart = r * COLS;
			for (int c = 0; c < ROWS; ++c)
			{
				possible |= item[c + rowstart].poss;
			}
			if (row[r].num() > (possible & row[r]).num())
				return false;
		}
		return true;
	}

	/*
	TODO: write a cleaner version of the puzzle generator, currently just use the old solver.
	bool Generate(Board& board, unsigned int fixed)
	{
		return false;
	}
	*/

	bool Solve(Board& board, std::vector<move>& moves)
	{
		// speed up the process a bit by doing all memory allocation up front
		moves.reserve(board.Blanks() + moves.size());
		//const unsigned int fixed = board.Filled();

/*		if (debug_output)
			board.Print<true>();*/

		while (board.Blanks() > 0)
		{
			// check whether we're in a deadlock situation
			if (!board.Solveable())
			{
				if (debug_output)
				{
					std::cout << "We've hit deadlock, trying to resolve. " << moves.size() << " previous moves.\n";
					board.Print<false>();
				}
				// retrace our steps until we come upon a 'random' or 'likely' move that can be amended
				while (true)
				{
					std::vector<move>::iterator cur = moves.end();
					do
					{
						// unsolveable if we've exhausted the possibilities of retracing
						if (cur == moves.begin())
							return false;

						--cur;
						if (debug_output)
						{
							std::cout << "Undo: <" << cur - moves.begin() << "> ";
							cur->Print();
						}
						assert(cur->Undo(board));
					}
					while (cur->kind <= MOVE_FORCED);

					
					{
						std::vector<move>::iterator del = cur;
						++del;
						if (debug_output)
						{
							std::cout << "Undoing " << moves.end() - del << " moves.\n";
							board.Print<false>();
						}
						moves.erase(del, moves.end());
					}

					{
						size_t move_id = cur - moves.begin();
						if (move_id == 9)
							board.Print<false>();
					}
					
					if (debug_output)
					{
						rcb pos(RCB(cur->index));
						std::cout << "Current move, " << cur - moves.begin() << " is at " << pos.col + 1 << ", " << pos.row + 1 << ", value: " << cur->value + 1 << ", " << 9 - cur->tries << " tries remain\n";
					}
					
					// must increment before test for next iteration, see NOTE below.
					++cur->tries;
					while (cur->tries < 10)
					{
						/* NOTE: we had ++cur->tries; on this line before. This was a
						 * problem as the loop didn't terminate on try 10. If the illegal
						 * 10th try was an allowed move, the check after the loop failed
						 * and the illegal move was propagated. Took me many hours to find.
						 * AAARGHHH!!!
						 */
						cur->value = (cur->value + 1) % 9;
						if (cur->Do(board))
						{
							if (board.Solveable())
								break;
							assert(cur->Undo(board));
						}
						// must increment before test for next iteration, see NOTE above.
						++cur->tries;
					}
					if (cur->tries < 10)
					{
						if (debug_output)
						{
							std::cout << "Trying value: " << cur->value + 1<< std::endl;
							if	(cur - moves.begin() == 9)
								board.Print<false>();
						}
						break;
					}
					if (debug_output)
					{
						std::cout << "Ran out of tries, will need to undo more moves.\n";
					}
					// run out of tries, have to backtrace yet further.
					moves.erase(cur);
				}
			}
			// board should now not be in deadlock
			assert(board.Solveable());
/*			if (debug_output)
				board.Print<true>();*/

			bool retrace = false;

			bool success_poss = true;
			bool success_opt = true;
			do
			{
				// first line of attack is to try to find and immediately perform forced
				// moves for boxes with only one placement possibility
				if (success_opt)
				{
					size_t start_moves = moves.size();
					if (debug_output)
					{
						std::cout << "Searching for boxes with only one placement possibility...";
					}
					
					success_poss = ForcedPossibilities(board, moves);
					if (debug_output)
					{
						std::cout << "found: " << moves.size() - start_moves << std::endl;
					}
					start_moves = moves.size();
					
					// if this leaves us in a dead end, go back to the drawing board.
					if (!board.Solveable())
					{
						retrace = true;
						break;
					}

					if (board.Blanks() == 0)
						return true;
				}

				/* the second type of forced moves arises from there only being one
				 * possible box to place a digit in the given row, column, or bigbox.
				 * Note that filling up one of these in rows can free another one up
				 * in columns and bigboxes, so we keep doing it as long as we keep
				 * finding them.
				 */
				if (success_poss || success_opt)
				{
					size_t start_moves = moves.size();
					if (debug_output)
					{
						std::cout << "Searching for rows, columns, and big-boxes with only one placement possibility...";
					}
					
					success_opt = ForcedOptions(board, moves);
					if (debug_output)
					{
						std::cout << "found: " << moves.size() - start_moves << std::endl;
						for (size_t i = start_moves; i < moves.size(); ++i)
						{
							std::cout << "DO: ";
							moves[i].Print();
						}
					}
					start_moves = moves.size();
					// if this leaves us in a dead end, go back to the drawing board.
					if (!board.Solveable())
					{
						retrace = true;
						break;
					}

					if (board.Blanks() == 0)
						return true;

					success_poss = false;
				}
			}
			while (success_poss || success_opt);

			if (retrace)
				continue;

			
			if (debug_output)
			{
				std::cout << "Begin speculative search for move " << moves.size() << ".\n";
			}
			/* once the forced moves have been exhausted, we need to make a 'likely'
			 * move. Such moves are based on trial and error, like random moves, but
			 * more directed, as they will go for the boxes with the fewest possible
			 * mistakes. */
			{
				// assemble list of spaces with <array index> possible moves, -1 is unset
				int poss[10] = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1};
				for (unsigned int index = 0; index < BOXES; ++index)
				{
					int free = board[index].poss.num();
					poss[free] = index;

					// 2 is always a winner (1 == forced, 0 == already set)
					if (free == 2)
						break;
				}

				move likely;
				likely.kind = MOVE_LIKELY;
				for (int best = 2; best < 10; ++best)
				{
					if (poss[best] >= 0)
					{
						if (debug_output)
						{
							rcb pos(RCB(poss[best]));
							std::cout << "Found location with " << best << " possible values at " << pos.col + 1 << ", " << pos.row + 1;
						}
						likely.index = poss[best];
						break;
					}
				}

				
				for (likely.value = 0; likely.value < 9; ++likely.value)
				{
					if (board[likely.index].poss[likely.value])
					{
						break;
					}
				}
				likely.tries = likely.value + 1;
				if (debug_output)
				{
					std::cout << ": setting to " << likely.value + 1 << std::endl;
				}
				
				likely.Do(board);
				moves.push_back(likely);
			}
			if (debug_output)
			{
				std::cout << "End speculative search.\n";
			}
			if (debug_output)
				board.Print<false>();
		}
/*		if (debug_output)
			board.Print<true>();*/

		return true;
	}

	bool ForcedPossibilities(Board& board, std::vector<move>& moves)
	{
		bool success = false;
		unsigned int index = 0;
		unsigned int tried = 0;
		while (tried < BOXES && board.Blanks() > 0 && board.Solveable())
		{
			if (board[index].poss.num() != 1)
			{
				++tried;
			}
			else
			{
				// forced move found!
				success = true;
				move force;
				force.kind = MOVE_FORCED;
				force.index = index;
				force.tries = 1;
				for (unsigned int n = 0; n < 9; ++n)
				{
					if (board[index].poss[n])
					{
						force.value = n;
						break;
					}
				}
				assert(force.value < 9);

				force.Do(board);
				moves.push_back(force);
//				if (debug_output)
// 					board.Print<true>();

				// reset try counter, as we may have created new forced moves
				tried = 0;
			}
			index = (index + 1) % BOXES;
		}
		return success;
	}


	bool FillOptions(Board& board, std::vector<move>& moves, const std::vector<unsigned int>& indices)
	{
		bool success = false;
		unsigned int options[9] = {0,0,0,0,0,0,0,0,0};
		int opt_index[9] = {-1,-1,-1,-1,-1,-1,-1,-1,-1};

		for (unsigned int i = 0; i < indices.size(); ++i)
		{
			const unsigned int index = indices[i];
			unsigned int left = board[index].poss.num();
			unsigned int n = 0;
			while (left > 0)
			{
				if (board[index].poss[n])
				{
					++options[n];
					opt_index[n] = index;
					--left;
				}
				++n;
			}
			assert(n <= 9);
		}

		for (unsigned int n = 0; n < 9; ++n)
		{
			if (options[n] == 1)
			{
				// bingo - this is exactly what we're looking for.
				move force;
				force.kind = MOVE_FORCED;
				force.index = opt_index[n];
				force.tries = 1;
				force.value = n;

				if (force.Do(board))
				{
					success = true;
					moves.push_back(force);
				}
				/*else
				{
					std::cout << "I'm pretty sure this is bad!\n";
				}
				

				// Actually, I've changed my mind. It's not necessarily bad and can happen occasionally.
				// However, the success indicator had to be moved, as it could potentially trigger an infinite loop.
				*/
				
				//if (debug_output)
				//	board.Print<true>();
			}
		}
		return success;
	}

	bool ForcedOptions(Board& board, std::vector<move>& moves)
	{
		bool success = false;

		std::vector<unsigned int> indices(9);

		// find and fill forced options for each row, ...
		for (unsigned int row = 0; row < ROWS; ++row)
		{
			const unsigned int rowstart = row * COLS;
			for (int i = 0; i < 9; ++i)
			{
				indices[i] = rowstart + i;
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;

		// ... column, ...
		for (unsigned int col = 0; col < COLS; ++col)
		{
			for (int i = 0; i < 9; ++i)
			{
				indices[i] = col + i * COLS;
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;
		// ... and bigbox.
		for (unsigned int bb = 0; bb < BIGBOXES; ++bb)
		{
			const unsigned int rowstart = (bb / 3) * 27;
			const unsigned int colstart = (bb % 3) * 3;
			const unsigned int rowend = rowstart + 27;
			const unsigned int colend = colstart + 3;
			unsigned int i = 0;
			for (unsigned int row = rowstart; row < rowend; row += COLS)
			{
				for (unsigned int c = colstart; c < colend; ++c)
				{
					indices[i] = row + c;
					++i;
				}
			}
			success |= FillOptions(board, moves, indices);
		}
		if (!board.Solveable())
			return false;
		return success;
	}

	void move::Print()
	{
		rcb pos(RCB(index));
		std::cout << "MOVE: Tile " << (char)('A' + pos.col) << (1 + pos.row) << ": value " << value + 1 << ", current try " << tries << ", kind " << kind << std::endl;
	}
}