Orz/oneNewMethod.cc

   1 /*
   2  * A new method to solve the puzzles,
   3  * more nice orgnized, and more efficent I suppose.
   4  * (at least compared to my original one)
   5  *
   6  * this one take puzzles and std input,
   7  * an example puzzle could be found below:
   8  *      0 0 0 2 6 0 7 0 1
   9  *      6 8 0 0 7 0 0 9 0
  10  *      1 9 0 0 0 4 5 0 0
  11  *      8 2 0 1 0 0 0 4 0
  12  *      0 0 4 6 0 2 9 0 0
  13  *      0 5 0 0 0 3 0 2 8
  14  *      0 0 9 3 0 0 0 7 4
  15  *      0 4 0 0 5 0 0 3 6
  16  *      7 0 3 0 1 8 0 0 0
  17  *
  18  * after calculation, the correct output should be:
  19  *      +------+------+-----
  20  *      |4 3 5 |2 6 9 |7 8 1
  21  *      |6 8 2 |5 7 1 |4 9 3
  22  *      |1 9 7 |8 3 4 |5 6 2
  23  *      +------+------+-----
  24  *      |8 2 6 |1 9 5 |3 4 7
  25  *      |3 7 4 |6 8 2 |9 1 5
  26  *      |9 5 1 |7 4 3 |6 2 8
  27  *      +------+------+-----
  28  *      |5 1 9 |3 2 6 |8 7 4
  29  *      |2 4 8 |9 5 7 |1 3 6
  30  *      |7 6 3 |4 1 8 |2 5 9
  31  *
  32  * Yet, the core computing part is still a kind of brute force,
  33  * which is more intutive to implement.
  34  * It might be implemented to my CheaterHub project in the future,
  35  * but I'm getting really frustrated by 81 boxes in UI design.
  36  */
  37 #include <iostream>
  38 #include <vector>
  39
  40 using namespace std;
  41
  42 int main()
  43 {
  44     vector<vector<int>> ori(9, vector<int>(9));
  45     vector<pair<int, int>> todo;
  46     int cur = 0;
  47
  48     // Another idea, is pre-generate checking list
  49     // for each blank box in the puzzle,
  50     // it should save some runtime for less checking.
  51     for(int i = 0; i < 9; i++)
  52     {
  53         for(int j = 0; j < 9; j++)
  54         {
  55             cin >> ori[i][j];
  56             if(!ori[i][j])
  57                 todo.push_back({i, j});
  58         }
  59     }
  60
  61     cout << "********************" << endl;
  62
  63     while(cur < todo.size())
  64     {
  65         int x = todo[cur].first;
  66         int y = todo[cur].second;
  67         vector<bool> check(10, false);
  68
  69         // TODO: there are 6 overlapping checks,
  70         // including (x, y) itself twice.
  71         // column
  72         for(int i = 0; i < 9; i++)
  73             check[ori[i][y]] = true;
  74         // row
  75         for(int j = 0; j < 9; j++)
  76             check[ori[x][j]] = true;
  77         // 9x9 box
  78         int ibase = x / 3 * 3;
  79         int jbase = y / 3 * 3;
  80         for(int i = 0; i < 3; i++)
  81             for(int j = 0; j < 3; j++)
  82                 check[ori[i+ibase][j+jbase]] = true;
  83
  84         int k = ori[x][y] + 1;
  85         for(; k < 10; k++)
  86             if(!check[k]) break;
  87
  88         if(k > 9)
  89         {
  90             ori[x][y] = 0;
  91             cur--;
  92             continue;
  93         }
  94         else
  95         {
  96             ori[x][y] = k;
  97             cur++;
  98         }
  99     }
 100
 101     for(int i = 0; i < 9; i++)
 102     {
 103         if(i%3 == 0) cout << "+------+------+-----" << endl;
 104         for(int j = 0; j < 9; j++)
 105         {
 106             if(j%3 == 0) cout << "|";
 107             cout << ori[i][j] << " ";
 108         }
 109         cout << endl;
 110     }
 111
 112     return 0;
 113 }