这是我的数独程序，可惜不会图形界面

andalousie

这个是我们程序与算法综合课程设计的一道题。叫做数独游戏。
源代码

1. #include <iostream>
   
2. #include <fstream>
   
3. #include <cstdlib>
   
4. #include <ctime>
   
5. #include <algorithm>
   
6. 
   
7. typedef unsigned bitfield;
   
8. 
   
9. static const bitfield maskMax = 512;
   
10. static const bitfield allSet = 511;
    
11. 
    
12. enum difficulty { EASY, MEDIUM, DIFFICULT, EVIL, DEFAULT };
    
13. 
    
14. // Returns the size of the set
    
15. static unsigned bitCount(bitfield bits)
    
16. {
    
17.     unsigned result = 0;
    
18.     bitfield mask = 1;
    
19. 
    
20.     while(mask != maskMax)
    
21.     {
    
22.         if (bits & mask)
    
23.             result++;
    
24.         mask *= 2;
    
25.     }
    
26. 
    
27.     return result;
    
28. }
    
29. 
    
30. // Returns a bitfield representing {num}
    
31. static inline bitfield bitFor(unsigned num)
    
32. {
    
33.     return 1 << (num - 1);
    
34. }
    
35. 
    
36. class BlankList
    
37. {
    
38. public:
    
39.     BlankList()
    
40.     {
    
41.         for (unsigned i = 0; i < 9; ++i)
    
42.             rows[i] = cols[i] = allSet;
    
43.         for (unsigned i = 0; i < 3; ++i)
    
44.             for (unsigned j = 0; j < 3; ++j)
    
45.                 blocks[i][j] = allSet;
    
46.     }
    
47. 
    
48.     void elim(unsigned i, unsigned j, unsigned n)
    
49.     {
    
50.         bitfield bit = bitFor(n);
    
51.         rows[i] &= ~bit;
    
52.         cols[j] &= ~bit;
    
53.         blocks[i/3][j/3] &= ~bit;
    
54.     }
    
55. 
    
56.     void cancel(unsigned i, unsigned j, unsigned n)
    
57.     {
    
58.         bitfield bit = bitFor(n);
    
59.         rows[i] |= bit;
    
60.         cols[j] |= bit;
    
61.         blocks[i/3][j/3] |= bit;
    
62.     }
    
63. 
    
64.     bitfield possible(unsigned i, unsigned j)
    
65.     {
    
66.         return rows[i] & cols[j] & blocks[i/3][j/3];
    
67.     }
    
68. private:
    
69.     bitfield rows[9], cols[9];
    
70.     bitfield blocks[3][3];
    
71. };
    
72. 
    
73. class Board
    
74. {
    
75. public:
    
76.     Board()
    
77.     {
    
78.         for (unsigned i = 0; i < 9; ++i)
    
79.             for (unsigned j = 0; j < 9; ++j)
    
80.                 matrix[i][j] = 0;
    
81.     }
    
82.     Board(unsigned seed)
    
83.     {
    
84.         for (unsigned i = 0; i < 9; ++i)
    
85.             for (unsigned j = 0; j < 9; ++j)
    
86.                 matrix[i][j] = 0;
    
87. 
    
88.         std::srand(seed);
    
89.         _random_fill();
    
90.     }
    
91.     void set(unsigned row, unsigned col, unsigned val)
    
92.     {
    
93.         matrix[row][col] = val;
    
94.         if (matrix[row][col])
    
95.             Blank.elim(row, col, val);
    
96.     }
    
97.     unsigned unset(unsigned row, unsigned col)
    
98.     {
    
99.         unsigned val = matrix[row][col];
    
100.         if (val)
     
101.             Blank.cancel(row, col, val);
     
102.         matrix[row][col] = 0;
     
103.         return val;
     
104.     }
     
105.     bitfield mask_check(unsigned i, unsigned j, bitfield mask)
     
106.     {
     
107.         return Blank.possible(i, j) & mask;
     
108.     }
     
109.     bitfield house_check(bitfield possible, unsigned i, unsigned j)
     
110.     {
     
111.         unsigned row_base = i / 3 * 3;
     
112.         unsigned col_base = j / 3 * 3;
     
113.         for (unsigned row = row_base; row < row_base + 3; ++row)
     
114.             for (unsigned col = col_base; col < col_base + 3; ++col)
     
115.             {
     
116.                 if ((row == i && col == j) || matrix[row][col])
     
117.                     continue;
     
118.                 possible &= ~Blank.possible(row, col);
     
119.             }
     
120.         return possible;
     
121.     }
     
122.     bitfield rl_check(bitfield tricky, unsigned i, unsigned j)
     
123.     {
     
124.         bitfield row_hidden = allSet;
     
125.         bitfield col_hidden = allSet;
     
126.         for (unsigned row = 0; row < 9; ++row)
     
127.             if (!matrix[row][j] && row != i)
     
128.                 col_hidden &= ~Blank.possible(row, j);
     
129.         for (unsigned col = 0; col < 9; ++col)
     
130.             if (!matrix[i][col] && col != j)
     
131.                 row_hidden &= ~Blank.possible(i, col);
     
132.         return tricky & (row_hidden | col_hidden);
     
133.     }
     
134.     void hidden_fill()
     
135.     {
     
136.         bool again;
     
137.         do
     
138.         {
     
139.             again = false;
     
140.             for (unsigned i = 0; i < 9; ++i)
     
141.             {
     
142.                 for (unsigned j = 0; j < 9; ++j)
     
143.                 {
     
144.                     if (matrix[i][j]) continue;
     
145.                     bitfield possible = Blank.possible(i, j);
     
146.                     if (bitCount(possible) == 1)
     
147.                     {
     
148.                         set(i, j, numFor(possible));
     
149.                         again = true;
     
150.                         continue;
     
151.                     }
     
152.                     bitfield tricky = house_check(possible, i, j);
     
153.                     if (bitCount(tricky) == 1)
     
154.                     {
     
155.                         set(i, j, numFor(tricky));
     
156.                         again = true;
     
157.                         continue;
     
158.                     }
     
159.                     tricky = rl_check(tricky, i, j);
     
160.                     if (bitCount(tricky) == 1)
     
161.                     {
     
162.                         set(i, j, numFor(tricky));
     
163.                         again = true;
     
164.                         continue;
     
165.                     }
     
166.                 }
     
167.             }
     
168.         }
     
169.         while (again);
     
170.     }
     
171.     unsigned remaining()
     
172.     {
     
173.         unsigned count = 0;
     
174.         for (unsigned i = 0; i < 9; ++i)
     
175.             for (unsigned j = 0; j < 9; ++j)
     
176.                 if (!matrix[i][j])
     
177.                     ++count;
     
178.         return count;
     
179.     }
     
180.     bool findMin(unsigned& row, unsigned& col)
     
181.     {
     
182.         bool found = false;
     
183.         unsigned count = 10;
     
184. 
     
185.         for (unsigned i = 0; i < 9; ++i)
     
186.             for (unsigned j = 0; j < 9; ++j)
     
187.             {
     
188.                 if (!matrix[i][j] &&
     
189.                         bitCount(Blank.possible(i, j)) < count)
     
190.                 {
     
191.                     count = bitCount(Blank.possible(i, j));
     
192.                     row = i;
     
193.                     col = j;
     
194.                     found = true;
     
195.                 }
     
196.             }
     
197.         return found;
     
198.     }
     
199.     bool backtrack(unsigned depth)
     
200.     {
     
201.         unsigned row, col;
     
202.         if (!findMin(row, col))
     
203.             if (!depth)
     
204.                 return true;
     
205.             else
     
206.                 return false;
     
207. 
     
208.         // Iterate through the possible values this cell could have
     
209.         unsigned num = 1;
     
210.         bitfield mask = bitFor(num);
     
211.         while (mask != maskMax)
     
212.         {
     
213.             if (mask_check(row, col, mask))
     
214.             {
     
215.                 set(row, col, num);
     
216.                 if (backtrack(depth-1))
     
217.                     return true;
     
218.                 unset(row, col);
     
219.             }
     
220. 
     
221.             // Advance to the next number
     
222.             mask *= 2;
     
223.             num++;
     
224.         }
     
225.         return false;
     
226.     }
     
227.     unsigned value(unsigned i, unsigned j)
     
228.     {
     
229.         return matrix[i][j];
     
230.     }
     
231.     bool assert(unsigned i, unsigned j, unsigned val)
     
232.     {
     
233.         return matrix[i][j] == val;
     
234.     }
     
235.     void print_board(std::ostream & out)
     
236.     {
     
237.         for (unsigned i = 0; i < 9; ++i)
     
238.         {
     
239.             for (unsigned j = 0; j < 9; ++j)
     
240.             {
     
241.                 out << matrix[i][j] << " ";
     
242.             }
     
243.             out << std::endl;
     
244.         }
     
245.     }
     
246. private:
     
247.     unsigned matrix[9][9];
     
248.     BlankList Blank;
     
249. 
     
250.     static unsigned numFor(bitfield bit)
     
251.     {
     
252.         unsigned num = 0;
     
253.         while (bit)
     
254.         {
     
255.             bit >>= 1;
     
256.             ++num;
     
257.         }
     
258.         return num;
     
259.     }
     
260.     bool _fill(bool is_big, unsigned place,
     
261.                unsigned num, bitfield usable = allSet)
     
262.     {
     
263.         if (is_big)
     
264.         {
     
265.             if (num == 10)
     
266.                 return true;
     
267.             if (place == 9)
     
268.                 return _fill(is_big, 0, num + 1);
     
269.         }
     
270.         if (place == 9)
     
271.             return true;
     
272.         static unsigned look_up[] =
     
273.         {
     
274.             0,  1,  2,
     
275.             9,  10, 11,
     
276.             18, 19, 20
     
277.         };
     
278.         static unsigned base[] =
     
279.         {
     
280.             0,  3,  6,
     
281.             27, 30, 33,
     
282.             54, 57, 60
     
283.         };
     
284.         unsigned block;
     
285.         bitfield usable_blocks = allSet;
     
286.         while (usable_blocks)
     
287.         {
     
288.             while (true)
     
289.             {
     
290.                 block = std::rand() % 9;
     
291.                 if (usable_blocks & bitFor(block + 1))
     
292.                     break;
     
293.             }
     
294.             usable_blocks &= ~bitFor(block + 1);
     
295.             if (bitFor(block + 1) & usable)
     
296.             {
     
297.                 unsigned loc = base[block] + look_up[place];
     
298.                 unsigned row = loc / 9, col = loc % 9;
     
299.                 if (!matrix[row][col] &&
     
300.                         (bitFor(num) & Blank.possible(row, col)))
     
301.                 {
     
302.                     set(row, col, num);
     
303.                     usable &= ~bitFor(block + 1);
     
304.                     if (_fill(is_big, place + 1, num, usable))
     
305.                         return true;
     
306.                     unset(row, col);
     
307.                     usable |= bitFor(block + 1);
     
308.                 }
     
309.             }
     
310.         }
     
311.         return false;
     
312.     }
     
313. 
     
314.     void _random_fill()
     
315.     {
     
316.         for (unsigned i = 1; i <= 4; ++i)
     
317.             _fill(false, 0, i);
     
318.         while (true)
     
319.             if (_fill(true, 0, 5))
     
320.                 break;
     
321.     }
     
322. };
     
323. 
     
324. class Holes
     
325. {
     
326. public:
     
327.     Holes(Board & board)
     
328.         : puzzle(board)
     
329.     {}
     
330.     void digHoles(difficulty level)
     
331.     {
     
332.         static unsigned look_up[] =
     
333.         {
     
334.             0,  1,  2,
     
335.             9,  10, 11,
     
336.             18, 19, 20
     
337.         };
     
338.         static unsigned base[] =
     
339.         {
     
340.             0,  3,  6,
     
341.             27, 30, 33,
     
342.             54, 57, 60
     
343.         };
     
344.         for (unsigned i = 0; i < 9; ++i)
     
345.         {
     
346.             unsigned array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
     
347.             unsigned diff = _random_by_level(level);
     
348.             std::random_shuffle(array, array + 9);
     
349.             for (unsigned j = 0; j < diff; ++j)
     
350.             {
     
351.                 unsigned loc = base[i] + look_up[array[j]];
     
352.                 unsigned row = loc / 9, col = loc % 9;
     
353.                 _valid_dig(row, col, level);
     
354.             }
     
355.         }
     
356.     }
     
357.     Board& to_play()
     
358.     {
     
359.         return puzzle;
     
360.     }
     
361. private:
     
362.     Board puzzle;
     
363. 
     
364.     unsigned _random_by_level(difficulty level)
     
365.     {
     
366.         unsigned random = 5;
     
367. 
     
368.         switch (level)
     
369.         {
     
370.         case EASY:
     
371.             random = std::rand() % 2 + 4;
     
372.             break;
     
373.         case MEDIUM:
     
374.             random = std::rand() % 3 + 5;
     
375.             break;
     
376.         case DIFFICULT:
     
377.             random = std::rand() % 4 + 5;
     
378.         case EVIL:
     
379.             random = std::rand() % 4 + 6;
     
380.             break;
     
381.         default:
     
382.             break;
     
383.         }
     
384.         return random;
     
385.     }
     
386. 
     
387.     void _valid_dig(unsigned i, unsigned j, difficulty level)
     
388.     {
     
389.         unsigned val = puzzle.unset(i, j);
     
390.         for (unsigned num = 1; num <= 9; ++num)
     
391.         {
     
392.             if (num != val &&
     
393.                     puzzle.mask_check(i, j, bitFor(num)))
     
394.             {
     
395.                 Board bd = puzzle;
     
396.                 bd.set(i, j, num);
     
397.                 bd.hidden_fill();
     
398.                 if (bd.backtrack(bd.remaining()))
     
399.                 {
     
400.                     puzzle.set(i, j, val);
     
401.                     return;
     
402.                 }
     
403.             }
     
404.         }
     
405.     }
     
406. };
     
407. 
     
408. class Sudoku
     
409. {
     
410. public:
     
411.     Sudoku(const char * name, bool play = false)
     
412.         : in(name)
     
413.     {
     
414.         unsigned num = 0;
     
415.         for (unsigned i = 0; i < 9; ++i)
     
416.         {
     
417.             for (unsigned j = 0; j < 9; ++j)
     
418.             {
     
419.                 in >> num;
     
420.                 _board.set(i, j, num);
     
421.             }
     
422.         }
     
423.         _board.print_board(std::cout);
     
424.         _answer = _board;
     
425.         if (_solve())
     
426.         {
     
427.             if (!play)
     
428.             {
     
429.                 std::cout << "The answer is:" << std::endl;
     
430.                 _answer.print_board(std::cout);
     
431.             }
     
432.         }
     
433.         else
     
434.             std::cout << "The sudoku is not solvable!" << std::endl;
     
435.     }
     
436.     Sudoku(difficulty level, std::ostream & out)
     
437.     {
     
438.         generate(level, out);
     
439.     }
     
440.     void generate(difficulty level, std::ostream & out)
     
441.     {
     
442.         _answer = Board(static_cast<unsigned>(std::time(0)));
     
443.         Holes game(_answer);
     
444.         game.digHoles(level);
     
445.         _board = game.to_play();
     
446.         _board.print_board(out);
     
447.     }
     
448.     void play(unsigned& row, unsigned& col, unsigned& val)
     
449.     {
     
450.         if (_board.mask_check(row, col, bitFor(val)))
     
451.             if (_answer.assert(row, col, val))
     
452.             {
     
453.                 _board.set(row, col, val);
     
454.                 system("cls");
     
455.                 _board.print_board(std::cout);
     
456.             }
     
457.             else
     
458.                 std::cout << "You've chosen the wrong number.\n";
     
459.         else
     
460.             std::cout << "Your play violated the rules.\n";
     
461.     }
     
462.     bool is_complete()
     
463.     {
     
464.         for (unsigned i = 0; i < 9; ++i)
     
465.             for (unsigned j = 0; j < 9; ++j)
     
466.                 if (!_answer.assert(i, j, _board.value(i, j)))
     
467.                     return false;
     
468.         return true;
     
469.     }
     
470. private:
     
471.     std::ifstream in;
     
472.     Board _board;
     
473.     Board _answer;
     
474. 
     
475.     bool _solve()
     
476.     {
     
477.         _answer.hidden_fill();
     
478.         if (_answer.backtrack(_answer.remaining()))
     
479.             return true;
     
480.         else
     
481.             return false;
     
482.     }
     
483. };
     
484. 
     
485. int main()
     
486. {
     
487.     char mode = 0;
     
488.     std::cout << "Input puzzle file (I) or Generate one (G): ";
     
489.     std::cin >> mode;
     
490.     if (mode == 'I')
     
491.     {
     
492.         char file[100];
     
493.         bool flag;
     
494.         std::cout << "Please specify the file: ";
     
495.         std::cin >> file;
     
496. AM:
     
497.         std::cout << "Automatically (A) solve it or Manually (M): ";
     
498.         std::cin >> mode;
     
499.         if (mode == 'A')
     
500.             flag = false;
     
501.         else if (mode == 'M')
     
502.             flag = true;
     
503.         else
     
504.         {
     
505.             std::cout << "Invalid Input!\n";
     
506.             goto AM;
     
507.         }
     
508. 
     
509.         system("cls");
     
510.         Sudoku puzzle(file, flag);
     
511.         if (flag)
     
512.         {
     
513.             unsigned row, col, val;
     
514.             while (!puzzle.is_complete())
     
515.             {
     
516.                 std::cout << "Enter a position and a number (i, j, num): ";
     
517.                 std::cin >> row >> col >> val;
     
518.                 puzzle.play(row, col, val);
     
519.             }
     
520.             std::cout << "You have completed the puzzle." << std::endl;
     
521.         }
     
522.     }
     
523.     else if (mode == 'G')
     
524.     {
     
525.         std::cout << "Which Level: Easy (E) Medium (M) Difficult(D) Evil(U) ";
     
526.         std::cin >> mode;
     
527.         difficulty level;
     
528.         bool flag;
     
529.         switch (mode)
     
530.         {
     
531.         case 'E':
     
532.             level = EASY;
     
533.             break;
     
534.         case 'M':
     
535.             level = MEDIUM;
     
536.             break;
     
537.         case 'D':
     
538.             level = DIFFICULT;
     
539.             break;
     
540.         case 'U':
     
541.             level = EVIL;
     
542.             break;
     
543.         default:
     
544.             level = DEFAULT;
     
545.             break;
     
546.         }
     
547. SP:
     
548.         std::cout << "Save it to a file (S) or Play now (P): ";
     
549.         std::cin >> mode;
     
550.         if (mode == 'S')
     
551.             flag = false;
     
552.         else if (mode == 'P')
     
553.             flag = true;
     
554.         else
     
555.         {
     
556.             std::cout << "Invalid Input!\n";
     
557.             goto SP;
     
558.         }
     
559. 
     
560.         if (flag)
     
561.         {
     
562.             system("cls");
     
563.             Sudoku puzzle(level, std::cout);
     
564.             unsigned row, col, val;
     
565.             while (!puzzle.is_complete())
     
566.             {
     
567.                 std::cout << "Enter a position and a number (i, j, num): ";
     
568.                 std::cin >> row >> col >> val;
     
569.                 puzzle.play(row, col, val);
     
570.             }
     
571.             std::cout << "You have completed the puzzle." << std::endl;
     
572.         }
     
573.         else
     
574.         {
     
575.             std::ofstream ofs("Sudoku.out");
     
576.             Sudoku puzzle(level, ofs);
     
577.             std::cout << "Saved as Sudoku.out" << std::endl;
     
578.         }
     
579.     }
     
580.     system("pause");
     
581. }

复制代码

可执行文件 Sudoku.zip (8.63 KB, 下载次数: 1)

2014-6-28 07:50 上传

点击文件名下载附件

andalousie

（1） 需求和规格说明

在一个9×9的大正方形中，包含9个3×3的小正方形。如图4所示。可以看到，其每行、每列、每个小正方形，都有9个空格。

要求只用1到9这些数字，填满大正方形中所有的81个空格，同时满足：

（1）在每列的9个空格中分别填入1到9，且每个数字在此列中只能出现一次；

（2）在每行的9个空格中分别填入1到9，且每个数字在此行中只能出现一次；

（3）在每个小正方形的9个空格中分别填入1到9，且每个数字在此正方形中只能出现一次；

游戏一开始会给定了某些空格的值。参加游戏的人根据这些已知的值以及上面的约束条件，推理出剩余的空格的值。

（2） 设计

根据上述需求，采用unsigned类型进行存储，并且通过简单的位运算来获取对应的格子上可填入的数字。有两个基本类：BlankList和Board，分别用来获取数独上空白位置可填入的数字，以及对一个数独棋盘的一系列操作。另外，还有一个作为用户接口的类Sudoku，提供初始化数独、生成数独、以及数独求解的操作；一个Holes类，用来给已经生成的完全数独进行“挖洞”，以生成真正的数独。

由于各个类的功用和数据相同成分不多，因此我采用的是潜入对象的做法，而没有使用继承。除了少数需要全局使用的变量和函数意外，数据基本都封装在各个类里面。在参考网上一些代码的基础上，我自己特别补充了hidden_fill方法，个人认为可以一定程度缩小解空间，所以引入了此方法对数独中naked single类型、hiddensingle类型、还有full house类型的确定解进行了筛查。之后再进行回溯进行求解。生成棋盘则是采用了回溯的方法，而不是采用Las Vegas的随机方法，旨在使完全数独生成更加随机化。

属性和方法定义

类名	成员类别	类型	成员名	描述
BlankList	属性	bitfield	rows[9]	对应行可填数
		bitfield	cols[9]	对应列可填数
		bitfield	blocks[9]	对应房子可填数
	方法	void	elim(unsigned, unsigned,  unsigned)	在增添数据时，从可填数中除去该数字
		void	cancel(unsigned, unsigned,  unsigned)	在删除数据时，从可填数中增添该数字
		bitfield	possible(unsigned,  unsigned)	返回对应格子的可填数（在只考虑行、列、房子不冲突的情况下）
Board	属性	unsigned	matrix[9][9]	9*9格子的二维数组
		BlankList	Blank	嵌入的BlankList对象，用于存储可填数
	方法		Board()	构造函数，用于已存在的数独
			Board(unsigned)	传入随机数种子的构造函数，用于生成新的完全数独
		void	set(unsigned, unsigned, unsigned)	用于设置一个格子上的值
		bool	unset(unsigned, unsigned)	用于取消设置一个格子的值，并返回取消的值
		bitfield	mask_check(unsigned,  unsigned, bitfield mask)	检查mask代表的数字中可填的
		bitfield	house_check(bitfield,  unsigned, unsigned)	从possible里筛选出需要填的格子意外同一个房子中，其他未填格子中都不可能的数
		bitfield	rl_check(bitfield,  unsigned unsigned)	从tricky里筛选出对应行或对应列中，其他未填格子中都不可能的数
		void	hidden_fill()	填入可以确定的值
		unsigned	remaining()	未填的格子数量
		bool	findMin(unsigned&, unsigned&)	查找可填数数量最少的格子
		bool	backtrack(unsigned)	回溯求解
		unsigned	value(unsigned, unsigned)	(i, j)格子中的值
		bool	assert(unsigned, unsigned,  unsigned)	确认(i, j)中的值是否为val
		void	print_board(std::ostream  &)	输出整个数独
		unsigned	numFor()
		bool	_fill(bool, unsigned,  unsigned, bitfield)	完全数独的填充，针对填入数大小决定是否回溯到上一个数
		void	_random_fill()	递归完全数独填充，调用_fill函数
Holes	属性	Board	puzzle	嵌入的Board对象
	方法	void	digHoles(difficulty)	“挖洞”操作
		Board	to_play	返回挖洞结束的数独
		unsigned	_random_by_level(difficulty)	根据难度随机生成每个房子里挖洞的数目
		void	_valid_dig(unsigned,  unsigned, difficulty)	只挖有效的洞（要求挖完剩下的是有唯一解的数独）
Sudoku	属性	std::ifstream	in	输入文件流
		Board	_board	正在使用的数独
		Board	_answer	当前数独的答案
	方法		Sudoku(const char *, bool)	输入文件的构造函数
			Sudoku(difficulty, std::ostream &)	自动产生数独的构造函数
		void	generate(difficulty, std::ostream &)	产生一个给定难度的数独
		void	play(unsigned&,unsigned&, unsigned&)	玩家输入对应位置数值
		bool	is_complete()	确认是否正确完成
		bool	_solve()	求解过程

andalousie

新的测试代码，部分。

1. 
   
2. class Board
   
3. {
   
4. public:
   
5.     Board()
   
6.         : remains(81)
   
7.     {
   
8.         for (unsigned i = 0; i < 9; ++i)
   
9.             for (unsigned j = 0; j < 9; ++j)
   
10.             {
    
11.                 matrix[i][j] = 0;
    
12.                 memory[i][j] = allSet;
    
13.             }
    
14.     }
    
15.     Board(unsigned seed)
    
16.         : remains(81)
    
17.     {
    
18.         for (unsigned i = 0; i < 9; ++i)
    
19.             for (unsigned j = 0; j < 9; ++j)
    
20.             {
    
21.                 matrix[i][j] = 0;
    
22.                 memory[i][j] = allSet;
    
23.             }
    
24. 
    
25.         std::srand(seed);
    
26.         _random_fill();
    
27.     }
    
28.     void set(unsigned row, unsigned col, unsigned val, bool advanced = false)
    
29.     {
    
30.         matrix[row][col] = val;
    
31.         if (matrix[row][col])
    
32.         {
    
33.             Blank.elim(row, col, val);
    
34.             --remains;
    
35.         }
    
36.         if (advanced)
    
37.             _update(row, col);
    
38.     }
    
39.     unsigned unset(unsigned row, unsigned col)
    
40.     {
    
41.         unsigned val = matrix[row][col];
    
42.         if (val)
    
43.         {
    
44.             Blank.cancel(row, col, val);
    
45.             ++remains;
    
46.         }
    
47.         matrix[row][col] = 0;
    
48.         return val;
    
49.     }
    
50.     bitfield mask_check(unsigned i, unsigned j, bitfield mask)
    
51.     {
    
52.         return Blank.possible(i, j) & mask & memory[i][j];
    
53.     }
    
54.     bitfield house_check(unsigned i, unsigned j, bool advanced = false)
    
55.     {
    
56.         bitfield house_hidden = allSet;
    
57.         unsigned row_base = i / 3 * 3;
    
58.         unsigned col_base = j / 3 * 3;
    
59.         for (unsigned row = row_base; row < row_base + 3; ++row)
    
60.             for (unsigned col = col_base; col < col_base + 3; ++col)
    
61.             {
    
62.                 if ((row == i && col == j) || matrix[row][col])
    
63.                     continue;
    
64.                 house_hidden &= advanced ? ~memory[row][col] : ~Blank.possible(row, col);
    
65.             }
    
66.         return house_hidden;
    
67.     }
    
68.     bitfield row_check(unsigned i, unsigned j, bool advanced = false)
    
69.     {
    
70.         bitfield row_hidden = allSet;
    
71.         for (unsigned col = 0; col < 9; ++col)
    
72.             if (!matrix[i][col] && col != j)
    
73.                 row_hidden &= advanced ? ~memory[i][col] : ~Blank.possible(i, col);
    
74.         return row_hidden;
    
75.     }
    
76.     bitfield col_check(unsigned i, unsigned j, bool advanced = false)
    
77.     {
    
78.         bitfield col_hidden = allSet;
    
79.         for (unsigned row = 0; row < 9; ++row)
    
80.             if (!matrix[row][j] && row != i)
    
81.                 col_hidden &= advanced ? ~memory[row][j] : ~Blank.possible(row, j);
    
82.         return col_hidden;
    
83.     }
    
84.     bitfield decide(bitfield & possible, bitfield & house,
    
85.                     bitfield & row,      bitfield & col)
    
86.     {
    
87.         if (bitCount(possible) == 1)
    
88.             return possible;
    
89. 
    
90.         bitfield check1 = possible & house;
    
91.         if (bitCount(check1) == 1)
    
92.             return check1;
    
93. 
    
94.         bitfield check2 = possible & row;
    
95.         if (bitCount(check2) == 1)
    
96.             return check2;
    
97. 
    
98.         bitfield check3 = possible & col;
    
99.         if (bitCount(check3) == 1)
    
100.             return check3;
     
101. 
     
102.         bitfield check = check1 & check2;
     
103.         if (bitCount(check) == 1)
     
104.             return check;
     
105. 
     
106.         check = check1 & check3;
     
107.         if (bitCount(check) == 1)
     
108.             return check;
     
109. 
     
110.         check = check2 & check3;
     
111.         if (bitCount(check) == 1)
     
112.             return check;
     
113. 
     
114.         check &= check1;
     
115.         if (bitCount(check) == 1)
     
116.             return check;
     
117. 
     
118.         return 0;
     
119.     }
     
120.     void hidden_fill()
     
121.     {
     
122.         bool again;
     
123.         do
     
124.         {
     
125.             again = false;
     
126.             for (unsigned i = 0; i < 9; ++i)
     
127.             {
     
128.                 for (unsigned j = 0; j < 9; ++j)
     
129.                 {
     
130.                     if (matrix[i][j]) continue;
     
131.                     bitfield possible = Blank.possible(i, j);
     
132.                     bitfield house = house_check(i, j);
     
133.                     bitfield row = row_check(i, j);
     
134.                     bitfield col = col_check(i, j);
     
135.                     bitfield to_check = decide(possible, house, row, col);
     
136.                     if (to_check)
     
137.                     {
     
138.                         set(i, j, numFor(to_check));
     
139.                         again = true;
     
140.                     }
     
141.                 }
     
142.             }
     
143.         }
     
144.         while (again);
     
145.     }
     
146.     bitfield candidate_check(unsigned i, unsigned j)
     
147.     {
     
148.         bitfield row_locked(0), col_locked(0), row_i(0), col_j(0);
     
149.         unsigned row_base = i / 3 * 3;
     
150.         unsigned col_base = j / 3 * 3;
     
151.         unsigned total_count = 0;
     
152.         for (unsigned row = row_base; row < row_base + 3; ++row)
     
153.         {
     
154.             if (row == i)
     
155.             {
     
156.                 for (unsigned col = col_base; col < col_base + 3; ++col)
     
157.                 {
     
158.                     if (matrix[row][col])
     
159.                         continue;
     
160.                     row_i |= memory[row][col];
     
161.                 }
     
162.             }
     
163.             else
     
164.             {
     
165.                 for (unsigned col = col_base; col < col_base + 3; ++col)
     
166.                 {
     
167.                     if (matrix[row][col])
     
168.                         continue;
     
169.                     row_locked |= memory[row][col];
     
170.                     ++total_count;
     
171.                 }
     
172.             }
     
173.         }
     
174.         if (total_count && total_count == bitCount(row_locked))
     
175.             memory[i][j] &= ~row_locked;
     
176.         bitfield pointing = row_i & ~row_locked;
     
177.         if (pointing)
     
178.             for (unsigned col = 0; col < 9; ++col)
     
179.             {
     
180.                 if (matrix[i][col] || (col >= col_base && col < col_base + 3))
     
181.                     continue;
     
182.                 memory[i][col] &= ~pointing;
     
183.             }
     
184. 
     
185.         total_count = 0;
     
186.         for (unsigned col = col_base; col < col_base + 3; ++col)
     
187.         {
     
188.             if (col == j)
     
189.             {
     
190.                 for (unsigned row = row_base; row < row_base + 3; ++row)
     
191.                 {
     
192.                     if (matrix[row][col])
     
193.                         continue;
     
194.                     col_j |= memory[row][col];
     
195.                 }
     
196.             }
     
197.             else
     
198.             {
     
199.                 for (unsigned row = row_base; row < row_base + 3; ++row)
     
200.                 {
     
201.                     if (matrix[row][col])
     
202.                         continue;
     
203.                     col_locked |= memory[row][col];
     
204.                     ++total_count;
     
205.                 }
     
206.             }
     
207.         }
     
208.         if (total_count && total_count == bitCount(col_locked))
     
209.             memory[i][j] &= ~col_locked;
     
210.         pointing = col_j & ~col_locked;
     
211.         if (pointing)
     
212.             for (unsigned row = 0; row < 9; ++row)
     
213.             {
     
214.                 if (matrix[row][j] || (row >= row_base && row < row_base + 3))
     
215.                     continue;
     
216.                 memory[row][j] &= ~pointing;
     
217.             }
     
218. 
     
219.                 for (unsigned col = 0; col < 9; ++col)
     
220.                 {
     
221.                         if (matrix[i][col] || (col >= col_base && col < col_base + 3))
     
222.                                 continue;
     
223.                         row_i &= ~memory[i][col];
     
224.                 }
     
225.                 if (row_i)
     
226.                 {
     
227.                         for (unsigned r = row_base; r < row_base + 3; ++r)
     
228.                                 for (unsigned c = col_base; c < col_base + 3; ++c)
     
229.                                 {
     
230.                                         if (r == i || matrix[r][c])
     
231.                                                 continue;
     
232.                                         memory[r][c] &= ~row_i;
     
233.                                 }
     
234.                 }
     
235. 
     
236.                 for (unsigned row = 0; row < 9; ++row)
     
237.                 {
     
238.                         if (matrix[row][j] || (row >= row_base && row < row_base + 3))
     
239.                                 continue;
     
240.                         col_j &= ~memory[row][j];
     
241.                 }
     
242.                 if (col_j)
     
243.                 {
     
244.                         for (unsigned r = row_base; r < row_base + 3; ++r)
     
245.                                 for (unsigned c = col_base; c < col_base + 3; ++c)
     
246.                                 {
     
247.                                         if (c == j || matrix[r][c])
     
248.                                                 continue;
     
249.                                         memory[r][c] &= ~col_j;
     
250.                                 }
     
251.                 }
     
252.         return memory[i][j];
     
253.     }
     
254.     void advanced_fill()
     
255.     {
     
256.         bool again;
     
257.         unsigned sum;
     
258.         for (unsigned i = 0; i < 9; ++i)
     
259.             for (unsigned j = 0; j < 9; ++j)
     
260.                 if (!matrix[i][j])
     
261.                     memory[i][j] &= Blank.possible(i, j);
     
262. 
     
263.         do
     
264.         {
     
265.             again = false;
     
266.             sum   = 0;
     
267.             for (unsigned i = 0; i < 9; ++i)
     
268.                 for (unsigned j = 0; j < 9; ++j)
     
269.                     sum += memory[i][j];
     
270. 
     
271.             for (unsigned i = 0; i < 9; ++i)
     
272.             {
     
273.                 for (unsigned j = 0; j < 9; ++j)
     
274.                 {
     
275.                     if (matrix[i][j]) continue;
     
276.                     bitfield possible = candidate_check(i, j);
     
277.                     //print_possible();
     
278.                     bitfield house = house_check(i, j, true);
     
279.                     bitfield row = row_check(i, j, true);
     
280.                     bitfield col = col_check(i, j, true);
     
281.                     bitfield to_check = decide(possible, house, row, col);
     
282.                     if (to_check)
     
283.                         set(i, j, numFor(to_check), true);
     
284.                 }
     
285.             }
     
286. 
     
287.             for (unsigned i = 0; i < 9; ++i)
     
288.                 for (unsigned j = 0; j < 9; ++j)
     
289.                     sum -= memory[i][j];
     
290.             if (sum) again = true;
     
291.         }
     
292.         while (again);
     
293.     }
     
294.     unsigned remaining()
     
295.     {
     
296.         return remains;
     
297.     }
     
298.     bool findMin(unsigned& row, unsigned& col)
     
299.     {
     
300.         bool found = false;
     
301.         unsigned count = 10;
     
302. 
     
303.         for (unsigned i = 0; i < 9; ++i)
     
304.             for (unsigned j = 0; j < 9; ++j)
     
305.             {
     
306.                 if (!matrix[i][j] && (bitCount(Blank.possible(i, j)
     
307.                                         & memory[i][j])) < count)
     
308.                 {
     
309.                     count = bitCount(Blank.possible(i, j) & memory[i][j]);
     
310.                     row = i;
     
311.                     col = j;
     
312.                     found = true;
     
313.                 }
     
314.             }
     
315.         return found;
     
316.     }
     
317.     bool backtrack(unsigned depth)
     
318.     {
     
319.         unsigned row, col;
     
320.         if (!findMin(row, col))
     
321.             if (!depth)
     
322.                 return true;
     
323.             else
     
324.                 return false;
     
325. 
     
326.         // Iterate through the possible values this cell could have
     
327.         unsigned num = 1;
     
328.         bitfield mask = bitFor(num);
     
329.         while (mask != maskMax)
     
330.         {
     
331.             if (mask_check(row, col, mask))
     
332.             {
     
333.                 set(row, col, num);
     
334.                 if (backtrack(depth-1))
     
335.                     return true;
     
336.                 unset(row, col);
     
337.             }
     
338. 
     
339.             // Advance to the next number
     
340.             mask *= 2;
     
341.             num++;
     
342.         }
     
343.         return false;
     
344.     }
     
345.     unsigned value(unsigned i, unsigned j)
     
346.     {
     
347.         return matrix[i][j];
     
348.     }
     
349.     bool assert(unsigned i, unsigned j, unsigned val)
     
350.     {
     
351.         return matrix[i][j] == val;
     
352.     }
     
353.     void print_possible()
     
354.     {
     
355.         for (unsigned i = 0; i < 9; ++i)
     
356.         {
     
357.             for (unsigned j = 0; j < 9; ++j)
     
358.             {
     
359.                 output << memory[i][j] << " ";
     
360.             }
     
361.             output << std::endl;
     
362.         }
     
363.         output << std::endl;
     
364.     }
     
365.     void print_board(std::ostream & out)
     
366.     {
     
367.         for (unsigned i = 0; i < 9; ++i)
     
368.         {
     
369.             for (unsigned j = 0; j < 9; ++j)
     
370.             {
     
371.                 out << matrix[i][j] << " ";
     
372.             }
     
373.             out << std::endl;
     
374.         }
     
375.         out << std::endl;
     
376.     }
     
377. private:
     
378.     unsigned matrix[9][9];
     
379.     bitfield memory[9][9];
     
380.     unsigned remains;
     
381.     BlankList Blank;
     
382. 
     
383.     static unsigned numFor(bitfield bit)
     
384.     {
     
385.         unsigned num = 0;
     
386.         while (bit)
     
387.         {
     
388.             bit >>= 1;
     
389.             ++num;
     
390.         }
     
391.         return num;
     
392.     }
     
393.     void _update(unsigned row, unsigned col)
     
394.     {
     
395.         unsigned row_base = row / 3 * 3;
     
396.         unsigned col_base = col / 3 * 3;
     
397.         unsigned r, c;
     
398. 
     
399.         for (unsigned i = 0; i < 9; ++i)
     
400.         {
     
401.             if (!matrix[row][i])
     
402.                 memory[row][i] &= Blank.possible(row, i);
     
403.             if (!matrix[i][col])
     
404.                 memory[i][col] &= Blank.possible(i, col);
     
405.             r = row_base + i / 3;
     
406.             c = col_base + i % 3;
     
407.             if (r != row && c != col && !matrix[r][c])
     
408.                 memory[r][c] &= Blank.possible(r, c);
     
409.         }
     
410.     }
     
411.     bool _fill(bool is_big, unsigned block, unsigned num)
     
412.     {
     
413.         if (is_big)
     
414.         {
     
415.             if (num == 10)
     
416.                 return true;
     
417.             if (block == 9)
     
418.                 return _fill(is_big, 0, num + 1);
     
419.         }
     
420.         if (block == 9)
     
421.             return true;
     
422.         static unsigned look_up[] =
     
423.         {
     
424.             0,  1,  2,
     
425.             9,  10, 11,
     
426.             18, 19, 20
     
427.         };
     
428.         static unsigned base[] =
     
429.         {
     
430.             0,  3,  6,
     
431.             27, 30, 33,
     
432.             54, 57, 60
     
433.         };
     
434.         unsigned place;
     
435.         bitfield available = allSet;
     
436.         while (available)
     
437.         {
     
438.             while (true)
     
439.             {
     
440.                 place = std::rand() % 9;
     
441.                 if (available & bitFor(place + 1))
     
442.                     break;
     
443.             }
     
444.             available &= ~bitFor(place + 1);
     
445. 
     
446.             unsigned loc = base[block] + look_up[place];
     
447.             unsigned row = loc / 9, col = loc % 9;
     
448.             if (!matrix[row][col] &&
     
449.                     (bitFor(num) & Blank.possible(row, col)))
     
450.             {
     
451.                 set(row, col, num);
     
452.                 if (_fill(is_big, block + 1, num))
     
453.                     return true;
     
454.                 unset(row, col);
     
455.             }
     
456.         }
     
457.         return false;
     
458.     }
     
459. 
     
460.     void _random_fill()
     
461.     {
     
462.         for (unsigned i = 1; i <= 5; ++i)
     
463.             _fill(false, 0, i);
     
464.         if (!_fill(true, 0, 6))
     
465.                         std::cout << "Error" << std::endl;
     
466.     }
     
467. };
     
468. 
     
469. class Holes
     
470. {
     
471. public:
     
472.     Holes(Board & board)
     
473.         : puzzle(board)
     
474.     {}
     
475.     void digHoles(difficulty level)
     
476.     {
     
477.         static unsigned look_up[] =
     
478.         {
     
479.             0,  1,  2,
     
480.             9,  10, 11,
     
481.             18, 19, 20
     
482.         };
     
483.         static unsigned base[] =
     
484.         {
     
485.             0,  3,  6,
     
486.             27, 30, 33,
     
487.             54, 57, 60
     
488.         };
     
489.         for (unsigned i = 0; i < 9; ++i)
     
490.         {
     
491.             unsigned array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
     
492.             unsigned diff = _random_by_level(level);
     
493.             std::random_shuffle(array, array + 9);
     
494.             for (unsigned j = 0; j < diff; ++j)
     
495.             {
     
496.                 unsigned loc = base[i] + look_up[array[j]];
     
497.                 unsigned row = loc / 9, col = loc % 9;
     
498.                 _valid_dig(row, col, level);
     
499.             }
     
500.         }
     
501.     }
     
502.     Board& to_play()
     
503.     {
     
504.         return puzzle;
     
505.     }
     
506. private:
     
507.     Board puzzle;
     
508. 
     
509.     unsigned _random_by_level(difficulty level)
     
510.     {
     
511.         unsigned random = 5;
     
512. 
     
513.         switch (level)
     
514.         {
     
515.         case EASY:
     
516.             random = std::rand() % 7 + 3;
     
517.             break;
     
518.         case MEDIUM:
     
519.             random = std::rand() % 5 + 3;
     
520.             break;
     
521.         case DIFFICULT:
     
522.             random = std::rand() % 5 + 4;
     
523.             break;
     
524.         case EVIL:
     
525.             random = std::rand() % 5 + 5;
     
526.             break;
     
527.         default:
     
528.             break;
     
529.         }
     
530.         return random;
     
531.     }
     
532. 
     
533.     void _valid_dig(unsigned i, unsigned j, difficulty level)
     
534.     {
     
535.         unsigned val = puzzle.unset(i, j);
     
536.                 if (level == EASY)
     
537.                 {
     
538.                         Board bd = puzzle;
     
539.                         bd.hidden_fill();
     
540.                         if (bd.remaining())
     
541.                         {
     
542.                                 puzzle.set(i, j, val);
     
543.                                 return;
     
544.                         }
     
545.                 }
     
546.         for (unsigned num = 1; num <= 9; ++num)
     
547.         {
     
548.             if (num != val &&
     
549.                     puzzle.mask_check(i, j, bitFor(num)))
     
550.             {
     
551.                 Board bd = puzzle;
     
552.                 bd.set(i, j, num);
     
553.                 bd.hidden_fill();
     
554.                                 bd.advanced_fill();
     
555.                 if (bd.backtrack(bd.remaining()))
     
556.                 {
     
557.                     puzzle.set(i, j, val);
     
558.                     return;
     
559.                 }
     
560.             }
     
561.         }
     
562.     }
     
563. };
     
564. 
     
565. class Sudoku
     
566. {
     
567. public:
     
568.     Sudoku(const char * name, bool play = false)
     
569.     {
     
570.         std::ifstream in(name);
     
571.         unsigned num = 0;
     
572.         for (unsigned i = 0; i < 9; ++i)
     
573.         {
     
574.             for (unsigned j = 0; j < 9; ++j)
     
575.             {
     
576.                 in >> num;
     
577.                 _board.set(i, j, num);
     
578.             }
     
579.         }
     
580.         _board.print_board(std::cout);
     
581.         _answer = _board;
     
582.         /*        if (_solve())
     
583.                 {
     
584.                     if (!play)
     
585.                     {
     
586.                         std::cout << "The answer is:" << std::endl;
     
587.                         _answer.print_board(std::cout);
     
588.                     }
     
589.                 }
     
590.                 else
     
591.                     std::cout << "The sudoku is not solvable!" << std::endl;*/
     
592.         solve();
     
593.     }
     
594.     Sudoku(difficulty level, std::ostream & out)
     
595.     {
     
596.         generate(level, out);
     
597.     }
     
598.     void generate(difficulty level, std::ostream & out)
     
599.     {
     
600.         _answer = Board(static_cast<unsigned>(std::time(0)));
     
601.                 while (true)
     
602.                 {
     
603.                         Holes game(_answer);
     
604.                         game.digHoles(level);
     
605.                         Board bd = game.to_play();
     
606.                         bd.hidden_fill();
     
607.                         if (level > EASY && !bd.remaining())
     
608.                                 continue;
     
609.                         bd.advanced_fill();
     
610.                         if (level > MEDIUM && !bd.remaining())
     
611.                                 continue;
     
612.                         if (level > DIFFICULT && bd.remaining() < 30)
     
613.                                 continue;
     
614.                         _board = game.to_play();
     
615.                         break;
     
616.                 }
     
617.         _board.print_board(out);
     
618.     }
     
619.     void play(unsigned& row, unsigned& col, unsigned& val)
     
620.     {
     
621.         if (_board.mask_check(row, col, bitFor(val)))
     
622.             if (_answer.assert(row, col, val))
     
623.             {
     
624.                 _board.set(row, col, val);
     
625.                 system("cls");
     
626.                 _board.print_board(std::cout);
     
627.             }
     
628.             else
     
629.                 std::cout << "You've chosen the wrong number.\n";
     
630.         else
     
631.             std::cout << "Your play violated the rules.\n";
     
632.     }
     
633.     bool is_complete()
     
634.     {
     
635.         for (unsigned i = 0; i < 9; ++i)
     
636.             for (unsigned j = 0; j < 9; ++j)
     
637.                 if (!_answer.assert(i, j, _board.value(i, j)))
     
638.                     return false;
     
639.         return true;
     
640.     }
     
641. private:
     
642.     Board _board;
     
643.     Board _answer;
     
644. 
     
645.     bool _solve()
     
646.     {
     
647.         _answer.hidden_fill();
     
648.         if (_answer.backtrack(_answer.remaining()))
     
649.             return true;
     
650.         else
     
651.             return false;
     
652.     }
     
653. 
     
654.     void solve()
     
655.     {
     
656.         //std::ofstream out("Sudoku.out");
     
657.         _answer.hidden_fill();
     
658.         _answer.advanced_fill();
     
659.                 _answer.backtrack(_answer.remaining());
     
660.         _answer.print_board(std::cout);
     
661.     }
     
662. };

复制代码