fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include <ctype.h>
  6. #include <assert.h>
  7. #include <chrono>
  8.  
  9. class muTimer
  10. {
  11.     using Clock = std::chrono::high_resolution_clock;
  12.     bool active = false;
  13.     Clock::duration   duration_;
  14.     Clock::time_point start_ = Clock::now(), stop_ = Clock::now();
  15.  
  16.     muTimer(const muTimer&)             = delete;
  17.     muTimer& operator=(const muTimer&)  = delete;
  18. public:
  19.     using ns       = std::chrono::nanoseconds;
  20.     using mks      = std::chrono::microseconds;
  21.     using ms       = std::chrono::milliseconds;
  22.     muTimer() { reset(); start(); }
  23.     ~muTimer() = default;
  24.     muTimer& reset()
  25.     {
  26.         duration_ = std::chrono::nanoseconds(0);
  27.         active    = false;
  28.         return *this;
  29.     }
  30.     muTimer& start()
  31.     {
  32.         if (!active)
  33.         {
  34.             start_ = Clock::now();
  35.             active = true;
  36.         }
  37.         return *this;
  38.     }
  39.     muTimer& stop()
  40.     {
  41.         if (active)
  42.         {
  43.             stop_      = Clock::now();
  44.             duration_ += stop_ - start_;
  45.             active     = false;
  46.         }
  47.         return *this;
  48.     }
  49.     template<typename T = mks>
  50.         unsigned long long duration()
  51.     {
  52.         return static_cast<unsigned long long>
  53.             (std::chrono::duration_cast<T>(stop_-start_).count());
  54.     }
  55. };
  56.  
  57.  
  58. class Sudoku
  59. {
  60. public:
  61.     Sudoku(bool clean = true);
  62.     Sudoku(const Sudoku&s)              { memcpy(p,s.p,sizeof(p)); }
  63.     Sudoku(const char *);
  64.     Sudoku& operator = (const Sudoku&s) { memcpy(p,s.p,sizeof(p)); return *this; }
  65.     ~Sudoku() {};
  66.  
  67.     int    operator()(int r, int c) const;
  68.     int&   operator()(int r, int c) { return p[r-1][c-1]; }
  69.     int    ok        () const;
  70.     void   shuffle   (int count = 3);
  71.     void   out       () const;
  72.     int    zeros     () const;
  73.     Sudoku solidSolve() const;
  74.     Sudoku addZeros  (int max) const;
  75.     Sudoku solve     (int&count) const;
  76.  
  77.     void Generate();
  78. private:
  79.     bool Gen();
  80.     static void trySolve(Sudoku&s, Sudoku& result, int& count );
  81.     void swapSqR(int i, int j);
  82.     void swapSqC(int i, int j);
  83.     void swapRow(int i, int j);
  84.     void swapCol(int i, int j);
  85.     void permut (int*perm);
  86.     void swap(int&i,int&j) { int t = i; i = j; j = t; }
  87.     int  check(int r, int c) const;       // ?  ? - ?
  88.     int  checkCount(int r, int c) const;  // ? ??
  89.     int p[9][9];
  90. };
  91.  
  92. inline int  Sudoku::zeros() const /*fold00*/
  93. {
  94.     int z = 0;
  95.     for(int i = 0; i < sizeof(p)/sizeof(int); ++i)
  96.         if (*((int*)p+i) == 0) ++z;
  97.     return z;
  98. }
  99.  
  100. inline int Sudoku::ok() const /*fold00*/
  101. {
  102.     if (zeros()) return -1;
  103.     static const char cstr[] = "-+++++++++";
  104.     // ?? ?  ?
  105.     for(int r = 0; r < 9; ++r)
  106.     {
  107.         char h[11] = {0}, v[11] = {0};
  108.         memset(h,'-',10); memset(v,'-',10);
  109.         for(int c = 0; c < 9; ++c)
  110.         {
  111.             h[p[r][c]] = '+';
  112.             v[p[c][r]] = '+';
  113.         }
  114.         if (strcmp(h,cstr)) return 0;
  115.         if (strcmp(v,cstr)) return 0;
  116.     }
  117.     // ?? ?
  118.     for(int i = 0; i < 3; ++i)
  119.         for(int j = 0; j < 3; ++j)
  120.         {
  121.             char s[11] = {0};
  122.             memset(s,'-',10);
  123.             for(int r = i*3; r < i*3+3; ++r)
  124.                 for(int c = j*3; c < j*3 + 3; ++c)
  125.                     s[p[r][c]] = '+';
  126.             if (strcmp(s,cstr))
  127.                 return 0;
  128.         }
  129.     return 1;
  130. }
  131.  
  132. inline int Sudoku::check(int r, int c) const /*fold00*/
  133. {
  134.     int allow[9] = {1,2,3,4,5,6,7,8,9};
  135.     // ?? ??
  136.     for(int x = 0; x < 9; ++x)
  137.     {
  138.         if (p[x][c] && (r != x)) allow[p[x][c]-1] = 0;
  139.         if (p[r][x] && (c != x)) allow[p[r][x]-1] = 0;
  140.     }
  141.     // ?? 
  142.     int rq = (r/3)*3;
  143.     int cq = (c/3)*3;
  144.     for(int x = 0; x < 3; ++x)
  145.         for(int y = 0; y < 3; ++y)
  146.         {
  147.             int rx = rq + x;
  148.             int cy = cq + y;
  149.  
  150.             if (p[rx][cy] && ((rx != r) || (cy != c)))
  151.                 allow[p[rx][cy]-1] = 0;
  152.         }
  153.  
  154.     int nonzero = 0;
  155.     int result  = 0;
  156.     for(int i = 0; i < 9; ++i)
  157.         if (allow[i])
  158.         {
  159.             if (++nonzero > 1) break;
  160.             result = allow[i];
  161.         }
  162.     if (nonzero != 1) return 0;
  163.     return result;
  164. }
  165.  
  166. inline int Sudoku::checkCount(int r, int c) const /*FOLD00*/
  167. {
  168.     int allow[9] = {1,2,3,4,5,6,7,8,9};
  169.     // ?? ??
  170.     for(int x = 0; x < 9; ++x)
  171.     {
  172.         if (p[x][c] && (r != x)) allow[p[x][c]-1] = 0;
  173.         if (p[r][x] && (c != x)) allow[p[r][x]-1] = 0;
  174.     }
  175.     // ?? 
  176.     int rq = (r/3)*3;
  177.     int cq = (c/3)*3;
  178.     for(int x = 0; x < 3; ++x)
  179.         for(int y = 0; y < 3; ++y)
  180.         {
  181.             int rx = rq + x;
  182.             int cy = cq + y;
  183.  
  184.             if (p[rx][cy] && ((rx != r) || (cy != c)))
  185.                 allow[p[rx][cy]-1] = 0;
  186.         }
  187.  
  188.     int nonzero = 0;
  189.     for(int i = 0; i < 9; ++i)
  190.         if (allow[i])
  191.         {
  192.             ++nonzero;
  193.         }
  194.     return nonzero;
  195. }
  196.  
  197. Sudoku Sudoku::solidSolve() const /*fold00*/
  198. {
  199.     Sudoku s(*this);
  200.     while(s.zeros())
  201.     {
  202.         bool found = false;
  203.         for(int i = 0; i < 9; ++i)
  204.             for(int j = 0; j < 9; ++j)
  205.                 if (s.p[i][j] == 0)
  206.                 {
  207.                     int res = s.check(i,j);
  208.                     if (res)
  209.                     {
  210.                         found = true;
  211.                         s.p[i][j] = res;
  212.                     }
  213.                 }
  214.         if (!found) break;
  215.     }
  216.     return s;
  217. }
  218.  
  219.  
  220.  
  221. Sudoku::Sudoku(const char * s) /*FOLD00*/
  222. {
  223.     for(int r = 0; r < 9; ++r)
  224.         for(int c = 0; c < 9; ++c)
  225.         {
  226.             while(!isdigit(*s)) ++s;
  227.             p[r][c] = *s - '0';
  228.             ++s;
  229.         }
  230. }
  231.  
  232.  
  233. Sudoku::Sudoku(bool clean) /*FOLD00*/
  234. {
  235.     static int sd[9][9] = {
  236.         {1,2,3,4,5,6,7,8,9},
  237.         {4,5,6,7,8,9,1,2,3},
  238.         {7,8,9,1,2,3,4,5,6},
  239.         {2,3,1,5,6,4,8,9,7},
  240.         {5,6,4,8,9,7,2,3,1},
  241.         {8,9,7,2,3,1,5,6,4},
  242.         {3,1,2,6,4,5,9,7,8},
  243.         {6,4,5,9,7,8,3,1,2},
  244.         {9,7,8,3,1,2,6,4,5}
  245.     };
  246.  
  247.     if (clean)
  248.     {
  249.         for(int i = 0; i < 9; ++i)
  250.             for(int j = 0; j < 9; ++j)
  251.                 p[i][j] = 0;
  252.     }
  253.     else
  254.     {
  255.         Generate();
  256.         //for(int i = 0; i < 9; ++i)
  257.         //    for(int j = 0; j < 9; ++j)
  258.         //        p[i][j] = sd[i][j];
  259.         //shuffle();
  260.     }
  261. }
  262.  
  263. void Sudoku::permut (int*perm) /*FOLD00*/
  264. {
  265.     for(int i = 0; i < 9; ++i)
  266.         for(int j = 0; j < 9; ++j)
  267.             p[i][j] = perm[p[i][j]-1];
  268. }
  269.  
  270. void Sudoku::out() const /*fold00*/
  271. {
  272.     for(int i = 0; i < 9; ++i)
  273.     {
  274.         for(int j = 0; j < 9; ++j)
  275.             printf("%d",p[i][j]);
  276.         printf("\n");
  277.     }
  278. }
  279.  
  280. void Sudoku::shuffle(int count) /*FOLD00*/
  281. {
  282.     int perm[9] = {1,2,3,4,5,6,7,8,9};
  283.     for(int k = 8; k > 0; --k)
  284.     {
  285.         swap(perm[k],perm[rand()%k]);
  286.     }
  287.     int i,j,l;
  288.     for(int k = 0; k < count; k++)
  289.     {
  290.         i = rand()%3; j = rand()%3;  swapSqR(i,j);
  291.         i = rand()%3; j = rand()%3;  swapSqC(i,j);
  292.         i = rand()%3; j = rand()%3;  l = rand()%3; swapRow(i+l*3,j+l*3);
  293.         i = rand()%3; j = rand()%3;  l = rand()%3; swapCol(i+l*3,j+l*3);
  294.         permut(perm);
  295.     }
  296. }
  297.  
  298. void Sudoku::swapSqR(int i, int j) /*fold00*/
  299. {
  300.     if ((i>=0)&&(i<=2)&&
  301.         (j>=0)&&(j<=2)&&
  302.         (i != j))
  303.     {
  304.         for(int r = 0; r < 3; ++r)
  305.             for(int c = 0; c < 9; ++c)
  306.             {
  307.                 swap(p[i*3+r][c],p[j*3+r][c]);
  308.             }
  309.     }
  310. }
  311. void Sudoku::swapSqC(int i, int j) /*fold00*/
  312. {
  313.     if ((i>=0)&&(i<=2)&&
  314.         (j>=0)&&(j<=2)&&
  315.         (i != j))
  316.     {
  317.         for(int c = 0; c < 3; ++c)
  318.             for(int r = 0; r < 9; ++r)
  319.             {
  320.                 swap(p[r][i*3+c],p[r][j*3+c]);
  321.             }
  322.     }
  323. }
  324. void Sudoku::swapRow(int i, int j) /*fold00*/
  325. {
  326.     if ((i>=0)&&(i<=8)&&
  327.         (j>=0)&&(j<=8)&&
  328.         (i/3 == j/3)&&
  329.         (i != j))
  330.     {
  331.         for(int c = 0; c < 9; ++c)
  332.             swap(p[i][c],p[j][c]);
  333.     }
  334. }
  335. void Sudoku::swapCol(int i, int j) /*fold00*/
  336. {
  337.     if ((i>=0)&&(i<=8)&&
  338.         (j>=0)&&(j<=8)&&
  339.         (i/3 == j/3)&&
  340.         (i != j))
  341.     {
  342.         for(int r = 0; r < 9; ++r)
  343.             swap(p[r][i],p[r][j]);
  344.     }
  345. }
  346.  
  347. int  Sudoku::operator()(int r, int c) const /*fold00*/
  348. {
  349.     if (r < 0) return -1;
  350.     if (c < 0) return -1;
  351.     if (r > 8) return -1;
  352.     if (c > 8) return -1;
  353.     return p[r][c];
  354. }
  355.  
  356. Sudoku Sudoku::addZeros(int max) const /*FOLD00*/
  357. {
  358.     Sudoku s(*this); // ?
  359.     while(s.zeros() < max)
  360.     {
  361.         int nonzeros = 81 - s.zeros();
  362.         bool added = false;
  363.         //printf("Zeros = %d\n",s.zeros());
  364.         for(int i = 0; i < nonzeros; ++i) // ?...
  365.         {
  366.             Sudoku t(s); // ?
  367.             int q = rand()%nonzeros;
  368.             for(int r = 0; r < 9; ++r)
  369.             {
  370.                 for(int c = 0; c < 9; ++c)
  371.                 {
  372.                     if (t.p[r][c] == 0) continue;
  373.                     if (q > 0)
  374.                     {
  375.                         --q;
  376.                         continue;
  377.                     }
  378.                     t.p[r][c] = 0;
  379.                     int count = 1;
  380.                     //Sudoku sol = t.solidSolve();
  381.                     Sudoku sol = t.solidSolve();
  382.                     if ((sol.ok() == 1)&&(count == 1))
  383.                     {
  384.                         added = true;
  385.                         //printf("s.zeros() = %d\n",s.zeros());
  386.                         //printf("Added...\n");
  387.                         s = t;
  388.                         //printf("s.zeros() = %d\n",s.zeros());
  389.                         break;
  390.                     }
  391.                 }
  392.                 if (added) break;
  393.             }
  394.             if (added) break;
  395.         }
  396.         if (!added) // ?  ... ?? 
  397.         {
  398.             for(int i = 0; i < nonzeros; ++i) // ?...
  399.             {
  400.                 Sudoku t(s); // ?
  401.                 int q = rand()%nonzeros;
  402.                 for(int r = 0; r < 9; ++r)
  403.                 {
  404.                     for(int c = 0; c < 9; ++c)
  405.                     {
  406.                         if (t.p[r][c] == 0) continue;
  407.                         if (q > 0)
  408.                         {
  409.                             --q;
  410.                             continue;
  411.                         }
  412.                         t.p[r][c] = 0;
  413.                         int count;
  414.                         Sudoku sol = t.solve(count);
  415.                         if ((sol.ok() == 1)&&(count == 1))
  416.                         {
  417.                             added = true;
  418.                             //printf("s.zeros() = %d\n",s.zeros());
  419.                             //printf("Added...\n");
  420.                             s = t;
  421.                             //printf("s.zeros() = %d\n",s.zeros());
  422.                             break;
  423.                         }
  424.                     }
  425.                     if (added) break;
  426.                 }
  427.                 if (added) break;
  428.             }
  429.         }
  430.         if (!added) break;
  431.     }
  432.     return s;
  433. }
  434.  
  435.  
  436. Sudoku Sudoku::solve(int&count) const /*FOLD00*/
  437. {
  438.     Sudoku s = solidSolve();
  439.     if (s.ok() == 1)
  440.     {
  441.         count = 1;
  442.         return s;
  443.     }
  444.     s = *this;
  445.     count = 0;
  446.     Sudoku res = s;
  447.     trySolve(s,res,count);
  448.     return res;
  449. }
  450.  
  451. int level = 0;
  452.  
  453. void Sudoku::trySolve(Sudoku&s, Sudoku&res, int&count) /*FOLD00*/
  454. {
  455.     if (s.zeros() == 0) return; //  ?
  456.     if (count > 1)      return;
  457.  
  458.     ++level;
  459.     //printf("             Level %3d, zeros %3d, count %2d\r",level,s.zeros(), count);
  460.     //fflush(stdout);
  461.  
  462.     // ? 
  463.     int r = -1, c = -1;
  464.     int cnt = 9;
  465.     for(int x = 0; x < 9; ++x)
  466.     {
  467.         for(int y = 0; y < 9; ++y)
  468.         {
  469.             if (s.p[x][y]) continue;
  470.             int count = s.checkCount(x,y);
  471.             if (cnt >= count)
  472.             {
  473.                 r = x;
  474.                 c = y;
  475.                 cnt = count;
  476.             }
  477.         }
  478.     }
  479.  
  480.     assert((r >= 0) && (c >= 0));
  481.  
  482.     // ?? ? ? ?
  483.     int allow[9] = { 1,2,3,4,5,6,7,8,9 };
  484.     for(int x = 0; x < 9; ++x)
  485.     {
  486.         if (s.p[r][x]) allow[s.p[r][x]-1] = 0;
  487.         if (s.p[x][c]) allow[s.p[x][c]-1] = 0;
  488.     }
  489.     for(int x = 0; x < 3; ++x)
  490.         for(int y = 0; y < 3; ++y)
  491.             if (s.p[(r/3)*3+x][(c/3)*3+y])
  492.                 allow[s.p[(r/3)*3+x][(c/3)*3+y]-1] = 0;
  493.  
  494.     for(int i = 0; i < 9; ++i)
  495.     {
  496.         if (allow[i] == 0) continue;
  497.         s.p[r][c] = allow[i];
  498.         Sudoku v = s.solidSolve();
  499.         if (v.ok() == 1) // ? 
  500.         {
  501.             res = v;
  502.             count++;
  503.             if (count > 1) break;
  504.             continue;
  505.         }
  506.         trySolve(s,res,count);
  507.         if (count > 1) break;
  508.     }
  509.     s.p[r][c] = 0;
  510.     --level;
  511. }
  512.  
  513.  
  514. void Sudoku::Generate()
  515. {
  516.     for(int r = 0; r < 9; ++r)
  517.         for(int c = 0; c < 9; ++c)
  518.             p[r][c] = (r == 0) ? c + 1 : 0;
  519.     Gen();
  520.     shuffle();
  521. }
  522.  
  523. bool Sudoku::Gen()
  524. {
  525.     if (zeros() == 0) return true;
  526.     // ?  ?
  527.     int r, c;
  528.     for(int x = 0; x < 9; ++x)
  529.         for(int y = 0; y < 9; ++y)
  530.         {
  531.             if (p[x][y]) continue;
  532.             r = x;
  533.             c = y;
  534.             break;
  535.         }
  536.  
  537.     // ?? ? ? ?
  538.     int allow[9] = { 1,2,3,4,5,6,7,8,9 };
  539.     for(int x = 0; x < 9; ++x)
  540.     {
  541.         if (p[r][x]) allow[p[r][x]-1] = 0;
  542.         if (p[x][c]) allow[p[x][c]-1] = 0;
  543.     }
  544.     for(int x = 0; x < 3; ++x)
  545.         for(int y = 0; y < 3; ++y)
  546.             if (p[(r/3)*3+x][(c/3)*3+y])
  547.                 allow[p[(r/3)*3+x][(c/3)*3+y]-1] = 0;
  548.  
  549.     // ??  ? ?
  550.     for(int k = 8; k > 0; --k)
  551.         swap(allow[k],allow[rand()%k]);
  552.     for(int k = 0; k < 9; ++k)
  553.     {
  554.         if (allow[k] == 0) continue;
  555.         p[r][c] = allow[k];
  556.         if (zeros() == 0)
  557.         {
  558.             if (ok() == 1)
  559.             {
  560.                 //printf("---------\n");
  561.                 //out();
  562.                 //printf("---------\n");
  563.                 return true;
  564.             }
  565.         }
  566.         if (Gen()) return true;
  567.     }
  568.     p[r][c] = 0;
  569.     return false;
  570. }
  571.  
  572. int main(int argc, const char * argv[]) /*FOLD00*/
  573. {
  574.  
  575.     muTimer mt;
  576.     srand(time(0));
  577.     Sudoku s("800000000003600000070090200050007000000045700000100030001000068008500010090000400");
  578.     int count;
  579.     s = s.solve(count);
  580.     mt.stop();
  581.     s.out();
  582.     printf("Count = %d\n",count);
  583.     printf("Zeros = %d\n",s.zeros());
  584.  
  585.     printf("%llu mks\n",mt.duration());
  586.  
  587.     exit(0);
  588.     Sudoku t = s;
  589.     t.Generate();
  590.     t.out();
  591.     printf("Zeros = %d, ok = %d\n",t.zeros(), t.ok());
  592. }
  593.  
Success #stdin #stdout 0.31s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452
Count = 1
Zeros = 0
306623 mks
https://ideone.com/xE2Ma7
language:
C++14 (gcc 8.3)
created:
3 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!