src/suexg/gene_suexg_v12.c

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // sudokuki - C++ graphical sudoku game                                       //
   3 // Copyright (C) 2007-2009 Sylvain Vedrenne                                   //
   4 //                                                                            //
   5 // This program is free software; you can redistribute it and/or              //
   6 // modify it under the terms of the GNU General Public License                //
   7 // as published by the Free Software Foundation; either version 2             //
   8 // of the License, or (at your option) any later version.                     //
   9 //                                                                            //
  10 // This program is distributed in the hope that it will be useful,            //
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of             //
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the              //
  13 // GNU General Public License for more details.                               //
  14 //                                                                            //
  15 // You should have received a copy of the GNU General Public License along    //
  16 // with this program; if not, write to the Free Software Foundation, Inc.,    //
  17 // 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.              //
  18 ////////////////////////////////////////////////////////////////////////////////
  19 //                                                                            //
  20 // The source code below is the result of the initial work of Suexg's author  //
  21 //  -congratulations to him for making Suexg's source code public domain!-    //
  22 // plus modifications by Sudokuki's author, for adaptation to Sudokuki.       //
  23 //                                                                            //
  24 // "Suexg" is a sudoku generator written in C. "Suexg version 12" is included //
  25 // in Sudokuki since version 0.0.12_gtkmm of Sudokuki.                        //
  26 //                                                                            //
  27 ////////////////////////////////////////////////////////////////////////////////
  28 // The note below (between /* ... */) is from Suexg's author:                 //
  29 /******************************************************************************/
  30 /*     suexg version 12, small randomized sudoku-generator in C.              */
  31 /*                                                                            */
  32 /*     Generates about 24 sudokus per second with 1GHz CPU.                   */
  33 /*     Based on an exact cover solver, compiled with gcc3.2. Report bugs,     */
  34 /*     improvement suggestions,feedback to sterten@aol.com. For some          */
  35 /*     explanation of the solver see: http://magictour.free.fr/suexco.txt     */
  36 /*     This generator starts from an empty grid and adds clues completely     */
  37 /*     at random. There are faster pseudo-random methods which generate       */
  38 /*     up to 1000 sudokus per second.    [..]                                 */
  39 /*                                                                            */
  40 /*     Send sudokus with rating more than 100000 to sterten@aol.com so they   */
  41 /*     can be included in the list of hardest sudokus at                      */
  42 /*     http://magictour.free.fr/top94    [..]                                 */
  43 /*                                                                            */
  44 /*     This software is public domain.                                        */
  45 /******************************************************************************/
  46 #include <stdlib.h>
  47 #include <stdio.h>
  48
  49 #define MWC ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)))
  50
  51 unsigned zr = 362436069;
  52 unsigned wr = 521288629;
  53 int A[88];
  54 int C[88];
  55 int I[88];
  56 int P[88];
  57 int V[325];
  58 int W[325];
  59 int Col[730][5];
  60 int Row[325][10];
  61 int Cols[730];
  62 int Rows[325];
  63 int Uc[325];
  64 int Ur[730];
  65 int Two[888];
  66
  67 int a;
  68 int c;
  69 int d;
  70 int f;
  71 int i;
  72 int j;
  73 int k;
  74 int l;
  75 int p;
  76 int r;
  77 int n = 729;
  78 int m = 324;
  79 int s;
  80 int w;
  81 int x;
  82 int y;
  83
  84 int c1;
  85 int c2;
  86 int i1;
  87 int m0;
  88 int m1;
  89 int m2;
  90 int r1;
  91 int s1;
  92
  93 int clues;
  94 int min;
  95 int nodes;
  96 int nt;
  97 int rate;
  98 int sam1;
  99 int samples;
 100 //int seed;
 101 int solutions;
 102 char B[83] = "0111222333111222333111222333444555666"
 103     "444555666444555666777888999777888999777888999";
 104
 105 int solve();
 106
 107 //------------------------------------------------------------
 108 #ifdef __cplusplus
 109 extern "C" {
 110 #endif
 111 int
 112 grid_generate ( int seed, int requestedRatingMin, int requestedRatingMax, int** grid, int* rating, int** grid_with_clues )
 113 {
 114 //printf("requestedRatingMin: %d\n", requestedRatingMin);
 115 //printf("requestedRatingMax: %d\n", requestedRatingMax);
 116 //int k=0;
 117 //for (k=0; k<1000; k++) {
 118 //  //printf("MWC : %d\n", MWC);
 119 //}
 120
 121 //int ii = 0;
 122 //for(ii = 0; ii<89; ii++) {
 123 //  //printf("B[%d] = %d\n", ii, B[ii]);
 124 //}
 125
 126     zr ^= seed;
 127     wr += seed;
 128
 129     samples = 1; // number of grids to generate (here only one grid is generated)
 130     rate = 1; // if this value is not zero, the program will calculate the rating (for each grid)
 131
 132     for ( i=0; i<888; i++ )
 133     {
 134         j=1;
 135         while( j<=i )
 136         {
 137             j += j;
 138         }
 139         Two[i] = j-1;
 140     }
 141
 142     r=0;
 143     for ( x=1; x<=9; x++ )
 144     {
 145         for ( y=1; y<=9; y++ )
 146         {
 147             for ( s=1; s<=9; s++ )
 148             {
 149                 r++;
 150 ////printf("r : %d\n", r);
 151                 Cols[r] = 4;
 152                 Col[r][1] = x*9-9+y;
 153 ////printf("Col[%d][1] : %d\n", r, Col[r][1]);
 154                 Col[r][2] = (B[x*9-9+y]-48)*9-9+s+81;
 155 ////printf("Col[%d][2] : %d\n", r, Col[r][2]);
 156                 Col[r][3] = x*9-9+s+81*2;
 157 ////printf("Col[%d][3] : %d\n", r, Col[r][4]);
 158                 Col[r][4] = y*9-9+s+81*3;
 159 ////printf("Col[%d][4] : %d\n", r, Col[r][4]);
 160             }
 161         }
 162     }
 163     for ( c=1; c<=m; c++ )
 164     {
 165         Rows[c] = 0;
 166     }
 167     for ( r=1; r<=n; r++ )
 168     {
 169 ////printf("r : %d\n", r);
 170         for ( c=1; c<=Cols[r]; c++ )
 171         {
 172             a = Col[r][c];
 173 ////printf("a : %d\n", a);
 174             Rows[a]++;
 175             Row[a][Rows[a]] = r;
 176         }
 177     }
 178
 179     sam1 = 0;
 180
 181     m0s:
 182 //printf("m0s\n");
 183     sam1++;
 184     if ( sam1 > samples )
 185     {
 186         ////printf(".\n");
 187         return 0;
 188     }
 189
 190     m0:
 191 //printf("m0\n");
 192     for ( i=1; i<=81; i++ )
 193     {
 194         A[i] = 0;
 195     }
 196
 197     mr1:
 198 //printf("mr1\n");
 199     i1 = (MWC>>8)&127;
 200     if ( i1 > 80 )
 201     {
 202         goto mr1;
 203     }
 204     i1++;
 205     if ( A[i1] )
 206     {
 207         goto mr1;
 208     }
 209
 210     mr3:
 211 //printf("mr3\n");
 212     s = (MWC>>9)&15;
 213     if ( s>8 )
 214     {
 215         goto mr3;
 216     }
 217     s++;
 218     A[i1] = s;
 219     //printf("\nA[i1:%d] = s:%d\n", i1, s);
 220     m2 = solve();
 221
 222     // add a random clue and solve it. No solution ==> remove it again.
 223     // Not yet a unique solution ==> continue adding clues
 224     if ( m2<1 )
 225     {
 226         A[i1] = 0;
 227     }
 228     if ( m2 != 1 )
 229     {
 230         goto mr1;
 231     }
 232
 233     if ( solve() != 1 )
 234     {
 235         goto m0;
 236     }
 237     //now we have a unique-solution sudoku. Now remove clues to make it minimal
 238     {//EXPERIMENTAL: here is the grid with clues in it
 239
 240         int* p_sol;
 241         p_sol = *grid_with_clues;
 242
 243         for ( i=1; i<=81; i++ )
 244         {
 245           *p_sol = A[i];
 246           p_sol++;
 247         }
 248     }
 249     for ( i=1; i<=81; i++ )
 250     {
 251
 252         mr4:
 253 //printf("mr4\n");
 254         x = (MWC>>8)&127;
 255         if ( x>=i )
 256         {
 257             goto mr4;
 258         }
 259         x++;
 260         P[i] = P[x];
 261         P[x] = i;
 262     }
 263     for ( i1=1; i1<=81; i1++ )
 264     {
 265         s1 = A[P[i1]];
 266         A[P[i1]] = 0;
 267         if ( solve()>1 )
 268         {
 269             A[P[i1]] = s1;
 270         }
 271     }
 272
 273     if ( rate )
 274     {
 275         nt=0;
 276         for ( f=0; f<100; f++ )
 277         {
 278             solve();
 279             nt += nodes;
 280         }
 281         ////printf ( "new grid, rating:%6i", nt );
 282                 if (nt < requestedRatingMin || requestedRatingMax < nt) {
 283                         goto m0;
 284                 }
 285                 *rating = nt;
 286     }
 287
 288     {
 289
 290         int* p_table;
 291         p_table = *grid;
 292
 293         for ( i=1; i<=81; i++ )
 294         {
 295           *p_table = A[i];
 296           p_table++;
 297         }
 298     }
 299     goto m0s;
 300 }
 301 #ifdef __cplusplus
 302 }
 303 #endif
 304
 305 //-----------------------------------------------------------------------
 306 //-----------------------------------------------------------------------
 307 int solve()
 308 {//returns 0 (no solution), 1 (unique sol.), 2 (more than one sol.)
 309 //printf("solve()...\n");
 310
 311     for ( i=0; i<=n; i++ )
 312     {
 313         Ur[i] = 0;
 314     }
 315     for ( i=0; i<=m; i++ )
 316     {
 317         Uc[i] = 0;
 318     }
 319     clues = 0;
 320     for ( i=1; i<=81; i++ )
 321     {
 322         if ( A[i] )
 323         {
 324                 //printf("clues:%d", clues);
 325             clues++;
 326             r = i*9-9+A[i];
 327             for ( j=1; j<=Cols[r]; j++ )
 328             {
 329                 d=Col[r][j];
 330                 if ( Uc[d] )
 331                 {
 332                     return 0;
 333                 }
 334                 Uc[d]++;
 335                 for ( k=1; k<=Rows[d]; k++ )
 336                 {
 337                     Ur[Row[d][k]]++;
 338                 }
 339             }
 340         }
 341     }
 342
 343     for ( c=1; c<=m; c++ )
 344     {
 345         V[c] = 0;
 346         for ( r=1; r<=Rows[c]; r++ )
 347         {
 348             if ( Ur[Row[c][r]] == 0 )
 349             {
 350                 V[c]++;
 351             }
 352         }
 353     }
 354
 355     i = clues;
 356     m0 = 0;
 357     m1 = 0;
 358     solutions = 0;
 359     nodes = 0;
 360
 361     m2:
 362 //printf("M2 ");
 363     i++;
 364     I[i] = 0;
 365     min = n+1;
 366
 367     if ( i>81 || m0 )
 368     {
 369         goto m4;
 370     }
 371     if ( m1 )
 372     {
 373         C[i] = m1;
 374         goto m3;
 375     }
 376
 377     w = 0;
 378     for ( c=1; c<=m; c++ )
 379     {
 380         if ( !Uc[c] )
 381         {
 382             if ( V[c] < 2 )
 383             {
 384                 C[i] = c;
 385                 goto m3;
 386             }
 387             if ( V[c] <= min )
 388             {
 389                 w++;
 390                 W[w] = c;
 391             };
 392             if ( V[c] < min )
 393             {
 394                 w=1;
 395                 W[w]=c;
 396                 min=V[c];
 397             }
 398         }
 399     }
 400
 401     mr:
 402 //printf("MR ");
 403     c2 = MWC&Two[w];
 404     if ( c2 >= w )
 405     {
 406         goto mr;
 407     }
 408     C[i] = W[c2+1];
 409
 410     m3:
 411 //printf("M3 ");
 412     c = C[i];
 413     I[i]++;
 414     if ( I[i] > Rows[c] )
 415     {
 416         goto m4;
 417     }
 418     r = Row[c][I[i]];
 419     if ( Ur[r] )
 420     {
 421         goto m3;
 422     }
 423     m0=0;
 424     m1=0;
 425     nodes++;//if(nodes>9999 && part==0)return 0;
 426     for ( j=1; j <= Cols[r]; j++ )
 427     {
 428         c1=Col[r][j];
 429         Uc[c1]++;
 430     }
 431     for ( j=1; j<=Cols[r]; j++ )
 432     {
 433         c1=Col[r][j];
 434         for ( k=1; k<=Rows[c1]; k++ )
 435         {
 436             r1=Row[c1][k];
 437             Ur[r1]++;
 438             if ( Ur[r1] == 1 )
 439             {
 440                 for ( l=1; l<=Cols[r1]; l++ )
 441                 {
 442                     c2=Col[r1][l];
 443                     V[c2]--;
 444                     if ( Uc[c2]+V[c2] < 1 )
 445                     {
 446                         m0=c2;
 447                     }
 448                     if ( Uc[c2]==0 && V[c2]<2 )
 449                     {
 450                         m1=c2;
 451                     }
 452                 }
 453             }
 454         }
 455     }
 456     if ( i == 81 )
 457     {
 458         solutions++;
 459     }
 460     if ( solutions > 1 )
 461     {
 462         goto m9;
 463     }
 464     goto m2;
 465
 466     m4:
 467 //printf("M4 ");
 468     i--;
 469     c = C[i];
 470     r = Row[c][I[i]];
 471     if ( i == clues )
 472     {
 473         goto m9;
 474     }
 475     for ( j=1; j<=Cols[r]; j++ )
 476     {
 477         c1 = Col[r][j];
 478         Uc[c1]--;
 479         for ( k=1; k<=Rows[c1]; k++ )
 480         {
 481             r1 = Row[c1][k];
 482             Ur[r1]--;
 483             if ( Ur[r1] == 0 )
 484             {
 485                 for ( l=1; l<=Cols[r1]; l++ )
 486                 {
 487                     c2 = Col[r1][l];
 488                     V[c2]++;
 489                 }
 490             }
 491         }
 492     }
 493
 494     if ( i > clues )
 495     {
 496         goto m3;
 497     }
 498
 499     m9:
 500 //printf("\nsolve() => %d\n",solutions);
 501     return solutions;
 502 }
 503 //-----------------------------------------------------------------------
 504 // EOF