2 * Sudokuki - essential sudoku game
\r
3 * Copyright (C) 2007-2013 Sylvain Vedrenne
\r
5 * This program is free software: you can redistribute it and/or modify
\r
6 * it under the terms of the GNU General Public License as published by
\r
7 * the Free Software Foundation, either version 3 of the License, or
\r
8 * (at your option) any later version.
\r
10 * This program is distributed in the hope that it will be useful,
\r
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
13 * GNU General Public License for more details.
\r
15 * You should have received a copy of the GNU General Public License
\r
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
\r
18 package net.jankenpoi.sudokuki.generator.suexg;
\r
20 import java.util.Random;
\r
22 import net.jankenpoi.sudokuki.SudokuGrid;
\r
23 import net.jankenpoi.sudokuki.generator.SudokuGenerator;
\r
26 *****************************************************************************
\r
27 * This file results from Suexg's author initial work in the public domain *
\r
28 * and from Sudokuki's author. *
\r
30 * This is a GPLv3+ Java transposition of Suexg's original C source code. *
\r
31 * N.B: Instructions like 'goto label' are valid in C but not in Java, *
\r
32 * so I have transposed them using 'continue' inside a global while loop *
\r
33 * with boolean values and 'if' instructions to simulate the labels. *
\r
34 * And I replaced the B[] char table using the actual char values as int *
\r
35 *****************************************************************************
\r
36 * "Suexg version 12" is included in Sudokuki since version 0.0.12_gtkmm *
\r
37 * of Sudokuki. The two reasons why I chose Suexg in the first place are *
\r
38 * that it works and that it was public domain, so GPL compatible. *
\r
39 * **************************************************************************
\r
40 * The note below (between * ... *) is from Suexg's author: *
\r
41 * **************************************************************************
\r
42 * * suexg version 12, small randomized sudoku-generator in C. * *
\r
44 * * Generates about 24 sudokus per second with 1GHz CPU. * *
\r
45 * * Based on an exact cover solver, compiled with gcc3.2. Report bugs, * *
\r
46 * * improvement suggestions,feedback to sterten@aol.com. For some * *
\r
47 * * explanation of the solver see: http://magictour.free.fr/suexco.txt * *
\r
48 * * This generator starts from an empty grid and adds clues completely * *
\r
49 * * at random. There are faster pseudo-random methods which generate * *
\r
50 * * up to 1000 sudokus per second. [..] * *
\r
52 * * Send sudokus with rating more than 100000 to sterten@aol.com so they * *
\r
53 * * can be included in the list of hardest sudokus at * *
\r
54 * * http://magictour.free.fr/top94 [..] * *
\r
56 *****************************************************************************
\r
58 class SuexgJava extends SuexgGenerator {
\r
60 private static long zr = 362436069;
\r
61 private static long wr = 521288629;
\r
62 private final static int[] A = new int[88];
\r
63 private final static int[] C = new int[88];
\r
64 private final static int[] I = new int[88];
\r
65 private final static int[] P = new int[88];
\r
66 private final static int[] V = new int[325];
\r
67 private final static int[] W = new int[325];
\r
68 private final static int[][] Col = new int[730][5];
\r
69 private final static int[][] Row = new int[325][10];
\r
70 private final static int[] Cols = new int[730];
\r
71 private final static int[] Rows = new int[325];
\r
72 private final static int[] Uc = new int[325];
\r
73 private final static int[] Ur = new int[730];
\r
74 private final static int[] Two = new int[888];
\r
76 private static int a;
\r
77 private static int c;
\r
78 private static int d;
\r
79 private static int f;
\r
80 private static int i;
\r
81 private static int j;
\r
82 private static int k;
\r
83 private static int l;
\r
84 private static int r;
\r
85 private static int n = 729;
\r
86 private static int m = 324;
\r
87 private static int s;
\r
88 private static int w;
\r
89 private static int x;
\r
90 private static int y;
\r
92 private static int c1;
\r
93 private static int c2;
\r
94 private static int i1;
\r
95 private static int m0;
\r
96 private static int m1;
\r
97 private static int m2;
\r
98 private static int r1;
\r
99 private static int s1;
\r
101 private static int clues;
\r
102 private static int min;
\r
103 private static int nodes;
\r
104 private static int nt;
\r
105 private static int rate;
\r
106 private static int sam1;
\r
107 private static int samples;
\r
108 // private static int seed;
\r
109 private static int solutions;
\r
110 private final static int[] B = new int[] { 48, 49, 49, 49, 50, 50, 50, 51,
\r
111 51, 51, 49, 49, 49, 50, 50, 50, 51, 51, 51, 49, 49, 49, 50, 50, 50,
\r
112 51, 51, 51, 52, 52, 52, 53, 53, 53, 54, 54, 54, 52, 52, 52, 53, 53,
\r
113 53, 54, 54, 54, 52, 52, 52, 53, 53, 53, 54, 54, 54, 55, 55, 55, 56,
\r
114 56, 56, 57, 57, 57, 55, 55, 55, 56, 56, 56, 57, 57, 57, 55, 55, 55,
\r
115 56, 56, 56, 57, 57, 57 };
\r
117 private static int MWC() {
\r
119 zr = 36969 * (zr & 65535) + (zr >> 16);
\r
120 wr = 18000 * (wr & 65535) + (wr >> 16);
\r
121 result = (int) (zr ^ wr);
\r
126 public synchronized SudokuGrid generateGrid(final int requestedRatingMin, final int requestedRatingMax) {
\r
127 Random rand = new Random(System.currentTimeMillis());
\r
129 int[] grid = new int[81];
\r
130 int[] gridAndClues = new int[81];
\r
131 int[] rating = new int[] { -1 };
\r
132 int seed = rand.nextInt();
\r
133 gridGenerate(seed, requestedRatingMin, requestedRatingMax, grid, rating, gridAndClues);
\r
135 //printGrid(gridAndClues);
\r
137 SudokuGrid sudoku = new SudokuGrid(grid);
\r
143 gridGenerate(final int seed, final int requestedRatingMin, final int requestedRatingMax, final int[] grid, final int[] rating,
\r
144 final int[] grid_with_clues) {
\r
147 * boolean values used to simulate the infamous goto used in the
\r
148 * original C suexg algorithm
\r
150 boolean gotoM0S = true;
\r
151 boolean gotoMR1 = false, gotoMR3 = false, gotoM0 = false;
\r
156 samples = 1; // number of grids to generate (here only one grid is
\r
158 rate = 1; // if this value is not zero, the program will calculate the
\r
159 // rating (for each grid)
\r
161 for (i = 0; i < 888; i++) {
\r
170 for (x = 1; x <= 9; x++) {
\r
171 for (y = 1; y <= 9; y++) {
\r
172 for (s = 1; s <= 9; s++) {
\r
175 Col[r][1] = x * 9 - 9 + y;
\r
176 Col[r][2] = (B[x * 9 - 9 + y] - 48) * 9 - 9 + s + 81;
\r
177 Col[r][3] = x * 9 - 9 + s + 81 * 2;
\r
178 Col[r][4] = y * 9 - 9 + s + 81 * 3;
\r
182 for (c = 1; c <= m; c++) {
\r
185 for (r = 1; r <= n; r++) {
\r
186 for (c = 1; c <= Cols[r]; c++) {
\r
189 Row[a][Rows[a]] = r;
\r
200 if (sam1 > samples) {
\r
210 for (i = 1; i <= 81; i++) {
\r
219 i1 = (MWC() >> 8) & 127;
\r
222 continue; // these 2 instructions stand for: goto mr1;
\r
227 continue; // these 2 instructions stand for: goto mr1;
\r
235 s = (MWC() >> 9) & 15;
\r
238 continue; // these 2 instructions stand for: goto mr3;
\r
244 // add a random clue and solve it. No solution ==> remove it
\r
246 // Not yet a unique solution ==> continue adding clues
\r
252 continue; // these 2 instructions stand for: goto mr1;
\r
255 if (solve() != 1) {
\r
257 continue; // these 2 instructions stand for: goto m0;
\r
259 // now we have a unique-solution sudoku. Now remove clues to
\r
261 {// EXPERIMENTAL: here is the grid with clues in it
\r
262 for (i = 1; i <= 81; i++) {
\r
263 grid_with_clues[i - 1] = A[i];
\r
266 for (i = 1; i <= 81; i++) {
\r
271 x = (MWC() >> 8) & 127;
\r
277 for (i1 = 1; i1 <= 81; i1++) {
\r
287 for (f = 0; f < 100; f++) {
\r
292 if (nt < requestedRatingMin|| requestedRatingMax < nt) {
\r
301 for (i = 1; i <= 81; i++) {
\r
302 grid[i - 1] = A[i];
\r
306 continue; // these 2 instructions stand for: goto m0s;
\r
307 } // end of gotoMR3 if
\r
309 } // outer while loop
\r
312 // -----------------------------------------------------------------------
\r
313 // -----------------------------------------------------------------------
\r
315 private static int solve() {// returns 0 (no solution), 1 (unique sol.), 2
\r
320 * boolean values used to simulate the infamous goto used in the
\r
321 * original C suexg algorithm
\r
323 boolean gotoM2 = true, gotoM3 = false, gotoM4 = false, gotoMR = false;
\r
325 for (i = 0; i <= n; i++) {
\r
328 for (i = 0; i <= m; i++) {
\r
332 for (i = 1; i <= 81; i++) {
\r
335 r = i * 9 - 9 + A[i];
\r
336 for (j = 1; j <= Cols[r]; j++) {
\r
342 for (k = 1; k <= Rows[d]; k++) {
\r
349 for (c = 1; c <= m; c++) {
\r
351 for (r = 1; r <= Rows[c]; r++) {
\r
352 if (Ur[Row[c][r]] == 0) {
\r
364 whileloop: while (true) {
\r
374 if (i > 81 || m0 != 0) {
\r
376 continue; // simulates: goto m4;
\r
381 continue; // simulates: goto m3;
\r
385 for (c = 1; c <= m; c++) {
\r
390 continue whileloop; // simulates: goto m3;
\r
411 c2 = (MWC() & Two[w]);
\r
414 continue; // simulates: goto mr;
\r
426 if (I[i] > Rows[c]) {
\r
428 continue; // simulates: goto m4;
\r
433 continue; // simulates: goto m3;
\r
437 nodes++;// if(nodes>9999 && part==0)return 0;
\r
438 for (j = 1; j <= Cols[r]; j++) {
\r
442 for (j = 1; j <= Cols[r]; j++) {
\r
444 for (k = 1; k <= Rows[c1]; k++) {
\r
448 for (l = 1; l <= Cols[r1]; l++) {
\r
451 if (Uc[c2] + V[c2] < 1) {
\r
454 if (Uc[c2] == 0 && V[c2] < 2) {
\r
464 if (solutions > 1) {
\r
465 break; // simulates: goto m9;
\r
468 continue; // simulates: goto m2;
\r
479 break; // simulates: goto m9;
\r
481 for (j = 1; j <= Cols[r]; j++) {
\r
484 for (k = 1; k <= Rows[c1]; k++) {
\r
488 for (l = 1; l <= Cols[r1]; l++) {
\r
498 continue; // simulates: goto m3;
\r
503 } // outer while loop
\r
509 private static final SuexgJava INSTANCE;
\r
511 INSTANCE = new SuexgJava();
\r
514 public static SudokuGenerator getGenerator() {
\r
OSDN Git Service
