fork(5) download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std ;
  4.  
  5. struct SetOfSmallInts
  6. {
  7.     int ival;
  8.  
  9.     SetOfSmallInts()
  10.     {
  11.         ival = 0;
  12.     }
  13. };
  14.  
  15. const SetOfSmallInts emptySet;
  16.  
  17. SetOfSmallInts makeSet(int i)
  18. {
  19.     SetOfSmallInts s;
  20.     s.ival = i;
  21.     return s;
  22. }
  23.  
  24. SetOfSmallInts remove(int x, SetOfSmallInts s)
  25. {
  26.     return makeSet(s.ival & ~(1 << x));
  27. }
  28.  
  29. SetOfSmallInts singletonSet(int x)
  30. {
  31.     return makeSet(1 << x);
  32. }
  33.  
  34. SetOfSmallInts rangeSet(int x, int y)
  35. {
  36.     if (x > y) return emptySet;
  37.     else return makeSet(((1 << (y - x + 1)) - 1) << x);
  38. }
  39.  
  40. bool isEmpty(SetOfSmallInts s)
  41. {
  42.     return s.ival == 0;
  43. }
  44.  
  45. int smallest(SetOfSmallInts s)
  46. {
  47.     int i, val;
  48.  
  49.     val = s.ival;
  50.     if (val == 0) return 0;
  51.  
  52.     i = 0;
  53.     if ((val & 31) == 0) { val = val >> 5; i = 5; }
  54.     if ((val & 7) == 0)  { val = val >> 3; i += 3; }
  55.     while ((val & 1) == 0) {
  56.         val = val >> 1;
  57.         i++;
  58.     }
  59.     return i;
  60. }
  61.  
  62. int onlyMember(SetOfSmallInts s)
  63. {
  64.     int x;
  65.  
  66.     x = smallest(s);
  67.     if (x != 0 && isEmpty(remove(x, s))) return x;
  68.     else return 0;
  69. }
  70.  
  71. bool isSingleton(SetOfSmallInts s)
  72. {
  73.     return onlyMember(s) != 0;
  74. }
  75.  
  76. int size(SetOfSmallInts s)
  77. {
  78.     int n, r;
  79.  
  80.     n = 0;
  81.     r = s.ival;
  82.     while (r != 0) {
  83.         if (r & 1) n++;
  84.         r = r >> 1;
  85.     }
  86.     return n;
  87. }
  88.  
  89. bool member(int x, SetOfSmallInts s)
  90. {
  91.     return ((1 << x) & s.ival) != 0;
  92. }
  93.  
  94. SetOfSmallInts insert(int x, SetOfSmallInts s)
  95. {
  96.     return makeSet(s.ival | (1 << x));
  97. }
  98.  
  99.  
  100.  
  101. SetOfSmallInts setDifference(SetOfSmallInts s, SetOfSmallInts t)
  102. {
  103.     return makeSet(s.ival & ~t.ival);
  104. }
  105.  
  106. SetOfSmallInts setUnion(SetOfSmallInts s, SetOfSmallInts t)
  107. {
  108.     return makeSet(s.ival | t.ival);
  109. }
  110.  
  111. SetOfSmallInts setIntersection(SetOfSmallInts s, SetOfSmallInts t)
  112. {
  113.     return makeSet(s.ival & t.ival);
  114. }
  115.  
  116.  
  117. typedef SetOfSmallInts Puzzle[9][9];
  118. typedef SetOfSmallInts* PuzzleSection[9];
  119.  
  120. void copyPuzzle(Puzzle pp, Puzzle p)
  121. {
  122.     int i, j;
  123.     for (i = 0; i < 9; i++)
  124.     {
  125.         for (j = 0; j < 9; j++)
  126.         {
  127.             pp[i][j] = p[i][j];
  128.         }
  129.     }
  130. }
  131.  
  132. void getRow(PuzzleSection R, Puzzle p, int i)
  133. {
  134.     int j;
  135.     for (j = 0; j < 9; j++)
  136.     {
  137.         R[j] = &(p[i][j]);
  138.     }
  139. }
  140.  
  141. void getColumn(PuzzleSection R, Puzzle p, int j)
  142. {
  143.     int i;
  144.     for (i = 0; i < 9; i++)
  145.     {
  146.         R[i] = &(p[i][j]);
  147.     }
  148. }
  149.  
  150. void getSquare(PuzzleSection R, Puzzle p, int k)
  151. {
  152.     int i;
  153.     for (i = 0; i < 9; i++)
  154.     {
  155.         R[i] = &(p[k - k % 3 + i / 3][3 * (k % 3) + i % 3]);
  156.     }
  157. }
  158.  
  159. void readPuzzle(Puzzle p)
  160. {
  161.     char c;
  162.     SetOfSmallInts set = rangeSet(1, 9);
  163.     for (int i = 0; i < 9; i++)
  164.     {
  165.         for (int j = 0; j < 9; j++)
  166.         {
  167.             cin >> c;
  168.             if (c == '-') p[i][j] = set;
  169.             else p[i][j] = singletonSet(c - '0');
  170.         }
  171.     }
  172. }
  173.  
  174. void printPuzzle(Puzzle p)
  175. {
  176.    int k;
  177.    for(int i=0; i < 9; i++)
  178.    {
  179. 	  for(int j=0; j < 9; j++)
  180. 	  {
  181. 		   k= onlyMember(p[i][j]);
  182. 		   if (j == 3 || j == 6) cout << " ";
  183. 		   if (k == 0) cout << "-";
  184. 		   else cout << k;
  185. 	   }
  186. 	   if (i==2 || i == 5) cout << "\n";
  187. 	   cout <<"\n";
  188.    }
  189. }
  190.  
  191. void showPuzzle(Puzzle p)
  192. {
  193.     for (int i = 0; i < 9; i++)
  194.     {
  195.         for (int j = 0; j < 9; j++)
  196.         {
  197.             std::cout << '[';
  198.  
  199.             for (unsigned k = 1; k <= 9; ++k)
  200.                 if (member(k, p[i][j]))
  201.                     std::cout << k;
  202.  
  203.             std::cout << "] ";
  204.         }
  205.         cout << '\n';
  206.     }
  207. }
  208.  
  209.  
  210. bool tacticOneOnSection(PuzzleSection section)
  211. {
  212.     bool changed = false;
  213.  
  214.     for (unsigned i = 0; i < 9; ++i)
  215.     {
  216.         SetOfSmallInts* cell = section[i];
  217.  
  218.         if (isSingleton(*cell))
  219.         {
  220.             const int number = onlyMember(*cell);
  221.  
  222.             for (unsigned j = 0; j < 9; ++j)
  223.                 if (i != j && member(number, *section[j]))
  224.                 {
  225.                     *section[j] = remove(number, *section[j]);
  226.                     changed = true;
  227.                 }
  228.         }
  229.     }
  230.  
  231.     return changed;
  232. }
  233.  
  234. bool tacticOne(Puzzle puzzle)
  235. {
  236.     bool changed = false;
  237.  
  238.     for (unsigned i = 0; i < 9; ++i)
  239.     {
  240.             PuzzleSection section;
  241.  
  242.             getRow(section, puzzle, i);
  243.             if (tacticOneOnSection(section))
  244.                 changed = true;
  245.  
  246.             getColumn(section, puzzle, i);
  247.             if (tacticOneOnSection(section))
  248.                 changed = true;
  249.  
  250.             getSquare(section, puzzle, i);
  251.             if (tacticOneOnSection(section))
  252.                 changed = true;
  253.     }
  254.  
  255.     return changed;
  256. }
  257.  
  258. int main()
  259. {
  260.     Puzzle p;
  261.     readPuzzle(p);
  262.     printPuzzle(p);
  263.     std::cout << '\n';
  264.  
  265.     showPuzzle(p);
  266.     std::cout << '\n';
  267.  
  268.     while (tacticOne(p))
  269.     {
  270.         showPuzzle(p);
  271.         std::cout << '\n';
  272.  
  273.         printPuzzle(p);
  274.         std::cout << '\n';
  275.     }
  276. }
Success #stdin #stdout 0s 3348KB
comments (?)
stdin
copy 
1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4
stdout
copy 
1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4

[1] [123456789] [123456789] [4] [8] [9] [123456789] [123456789] [6] 
[7] [3] [123456789] [123456789] [123456789] [123456789] [123456789] [4] [123456789] 
[123456789] [123456789] [123456789] [123456789] [123456789] [1] [2] [9] [5] 
[123456789] [123456789] [7] [1] [2] [123456789] [6] [123456789] [123456789] 
[5] [123456789] [123456789] [7] [123456789] [3] [123456789] [123456789] [8] 
[123456789] [123456789] [6] [123456789] [9] [5] [7] [123456789] [123456789] 
[9] [1] [4] [6] [123456789] [123456789] [123456789] [123456789] [123456789] 
[123456789] [2] [123456789] [123456789] [123456789] [123456789] [123456789] [3] [7] 
[8] [123456789] [123456789] [5] [1] [2] [123456789] [123456789] [4] 

[1] [5] [25] [4] [8] [9] [3] [7] [6] 
[7] [3] [2589] [2] [56] [6] [18] [4] [1] 
[46] [468] [8] [3] [367] [1] [2] [9] [5] 
[34] [489] [7] [1] [2] [48] [6] [5] [39] 
[5] [49] [129] [7] [46] [3] [149] [12] [8] 
[234] [4] [6] [8] [9] [5] [7] [12] [123] 
[9] [1] [4] [6] [37] [78] [58] [258] [2] 
[6] [2] [5] [89] [4] [48] [158] [3] [7] 
[8] [67] [3] [5] [1] [2] [9] [6] [4] 

15- 489 376
73- 2-6 -41
--8 3-1 295

--7 12- 65-
5-- 7-3 --8
-46 895 7--

914 6-- --2
625 -4- -37
8-3 512 964

[1] [5] [2] [4] [8] [9] [3] [7] [6] 
[7] [3] [9] [2] [5] [6] [8] [4] [1] 
[4] [6] [8] [3] [7] [1] [2] [9] [5] 
[3] [8] [7] [1] [2] [4] [6] [5] [9] 
[5] [9] [1] [7] [6] [3] [4] [2] [8] 
[23] [4] [6] [8] [9] [5] [7] [1] [3] 
[9] [1] [4] [6] [3] [7] [5] [8] [2] 
[6] [2] [5] [9] [4] [8] [1] [3] [7] 
[8] [7] [3] [5] [1] [2] [9] [6] [4] 

152 489 376
739 256 841
468 371 295

387 124 659
591 763 428
-46 895 713

914 637 582
625 948 137
873 512 964

[1] [5] [2] [4] [8] [9] [3] [7] [6] 
[7] [3] [9] [2] [5] [6] [8] [4] [1] 
[4] [6] [8] [3] [7] [1] [2] [9] [5] 
[3] [8] [7] [1] [2] [4] [6] [5] [9] 
[5] [9] [1] [7] [6] [3] [4] [2] [8] 
[2] [4] [6] [8] [9] [5] [7] [1] [3] 
[9] [1] [4] [6] [3] [7] [5] [8] [2] 
[6] [2] [5] [9] [4] [8] [1] [3] [7] 
[8] [7] [3] [5] [1] [2] [9] [6] [4] 

152 489 376
739 256 841
468 371 295

387 124 659
591 763 428
246 895 713

914 637 582
625 948 137
873 512 964
https://ideone.com/0QNNwc
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!