|
| View previous topic :: View next topic |
| Author |
Message |
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
 Posted: Fri Dec 30, 2005 2:46 pm Post subject: |
 |
|
here is what Rolf Sandberg just sent me:
see also:
http://www.klepphelmer.com/Sudoku/DLXEngine.java
JavaSudoku (C) R. Sandberg 2005
-------------------------------
- Contents
----------
-- Introduction
-- Automatic Sudoku generation and solving
-- Entering a Sudoku
-- Solving a Sudoku by hand
-- Solving support
-- When you get tired of a Sudoku
-- Credits
-- Todo
- Introduction
--------------
JavaSudoku is an application for you who like to solve Sudoku puzzles, but dislike all the
ink stains that is the result of manual candidate list management in a newspaper. A nicely
solved Sudoku shall be nice and clean, and not cluttered with pencil marks all over.
- Automatic Sudoku generation and solving
-------------------------------
JavaSudoku supports automatic generation and solving of Sudoku puzzles. The puzzles generated
are rated and has exactly one solution. The solver solve any(?) Sudoku within a fraction of a
second. Creds to Günter Stertenbrink for the DLX generator and solver which was ported to
Java by the author of the application. The application should be portable over platforms
since it is implemented in Java. However, it is only tested on a XP platform yet.
- Entering a Sudoku
-------------------
Sudouku can be entered in three ways:
-- By hand
Just select <Actions> - <Enter new puzzle by hand>, and the application will go into
puzzle entering mode. Enter the keys of the puzzle of your today's newspaper or whatever.
When ready, select <Actions> - <Enter new puzzle by hand> again, and the application will
enter SUdoku solving mode.
-- Opening a solved puzzle from a file
Just select <File> - <Open Puzzle>, select a valid Sudoku puzzle file and click OK. A
valid sudoku puzzle file is a text file with the extension .SDK, and that begins with a
81 character text string of dots (.) representing empty cells and single digits (1 .. 9)
representing keys. All other characters will either generate an error or produce a very
strange Sudoku-ish creature....
-- Generating a new Sudoku
Just select <Actions> - <Generate new puzzle> and choose a difficulty level.
- Solving a Sudoku by hand
--------------------------
Walk the Sudoku board with the arrow keys or by moving the mouse pointer over the board. The
cell that will receive input is indicated with yellow color.
- Enter a digit in the active cell by pressing the appropriate number key. If the digit
entered produces a Sudoku board with no solution, the erratical cell is indicated by red.
- Remove a digit by pressing <space> (removes the digit) or by pressing <backspace> (one step
back in history)
The backspace key give the option to step back in the solving history at any time, from one
step back to the entire history.
- Solving support
-----------------
-- Candidate lists
All possible candidates can be shown for each cell. Select <Options> - <Show candidate
lists> to toggle candidate list visibility.
-- Single candidate colouring
Single candidates for a cell are colored in magenta. Select <Options> - <Color singles>
to toggle single candidate coloring.
-- Unique candidates
Candidates unique for a cell are colored in orange. Unique candidates are unique for a row,
a column or a 3x3 box. Select <Options> - <Color unique candidates> to toggle unique
candidate coloring.
-- Remove a candidate from the candidate list of a cell
Press '-' and the appropritate number key to remove a candidate from the candidate list of
the active cell.
-- Reset the candidate list of a cell
Press the shit key and 'R' to reset the candidate list of the active cell.
- When you get tired of a Sudoku
--------------------------------
When you
-- Get tired of a certain Sudoku, or
-- You just want to show the darned thing who is the Boss, or
-- You really want to loose your entire Sudoku solver self confidence
Then invoke the DLX solver by selecting <Action> - <Solve>. It will tame any completely wild
Sudoku in a fraction of a second.
- Credits
---------
-- Credit to Günter Stertenbrink for making his C-code Dancing Links implementations available
to public. Took me a day to port the generator (suexg) to Java, and another day to port the
solver (suexco), which indicates that it was quality code.
In the spirit of Günters attitude to copyright issues, which really is a true copyleft
attitude, anyone interested in the Java port of his code may humbly ask the author of this
application for a copy at <mailto:rolf@klepphelmer.com>. No support provided, however.
- Todo
------
-- Add history bookmarks support to support what-if strategies
-- Optimize generation strategy so shorten generation time
==============================================
| Code: |
/*
* DLXEngine.java
*
* Created on den 30 december 2005, 01:04
*
* To change this template, choose Tools | Options and locate the template under
* the Source Creation and Management node. Right-click the template and choose
* Open. You can then make changes to the template in the Source Editor.
*/
package SudokuLogic;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Date;
/**
*
* @author Rolf Sandberg
*/
class dlx_solver {
static final int M = 8; // change this for larger grids. Use symbols as in L[] below
static final int M2 = M * M;
static final int M4 = M2 * M2;
long zr=362436069, wr=521288629;
long MWC() {
return ((zr=36969*(zr&65535)+(zr>>16))^(wr=18000*(wr&65535)+(wr>>16)));
}
int A0[][] = new int[M2 + 9][M2 + 9],
A[][] = new int[M2 + 9][M2 + 9],
Rows[] = new int[4 * M4 + 9],
Cols[] = new int[M2 * M4 + 9],
Row[][] = new int[4 * M4 + 9][M2 + 9];
int Col[][] = new int[M2 * M4 + 9][5],
Ur[] = new int[M2 * M4 + 9],
Uc[] = new int[4 * M4 + 9],
V[] = new int[M2 * M4 + 9];
int C[] = new int[M4 + 9],
I[] = new int[M4 + 9],
T[] = new int[M2 * M4 + 9],
P[] = new int[M2 * M4 + 9];
int Mr[] = {0,1,63,1023,4095,16383,46655,131071,262143};
int Mc[] = {0,1,63,511,1023,4095,8191,16383,16383};
int Mw[] = {0,1,3,15,15,31,63,63,63};
int nocheck = 0, max, _try_,
rnd = 0, min, clues, gu, tries;
long Node[] = new long[M4 + 9];
long nodes, tnodes, solutions, vmax, smax, time0, time1, t1, x1;
double xx, yy;
int q, a, p, i, i1, j, k, l, r, r1,
c, c1, c2, n, N = 0, N2, N4,
m, m0, m1, x, y, s;
char L[] = {'.',
'1','2','3','4','5','6','7','8','9',
'A','B','C','D','E','F','G','H','I',
'J','K','L','M','N','O','P','Q','R',
'S','T','U','V','W','X','Y','Z','a',
'b','c','d','e','f','g','h','i','j',
'k','l','m','n','o','p','q','r','s',
't','u','v','w','x','y','z','#','*','~'
};
static final int M6 = 10;
static final int M7 = 11;
static final int RESTART = 12;
static final int M22 = 13;
static final int M3 = 14;
static final int M44 = 15;
static final int NEXT_TRY = 16;
static final int END = 30;
String solve(String puzzle) {
String result = new String();
int STATE = M6;
vmax = 4000000;
smax = 25;
p = 1;
q = 0;
Date t = new Date();
t1 = t.getTime();
zr ^= t1;
wr += t1;
if(rnd < 999) {
zr ^= rnd;
wr += rnd;
for(i = 1; i < rnd; i++)
MWC();
}
if(q > 0) {
vmax=99999999;
smax=99999999;
}
N = 3;
N2 = N * N;
N4 = N2 * N2;
m = 4 * N4;
n = N2 * N4;
if(puzzle.length() < N4){
return "Error, puzzle incomplete";
}
System.out.println("Puzzle length: " + puzzle.length());
System.out.println(puzzle);
t = new Date();
time0 = t.getTime();
while (STATE != END) {
switch (STATE) {
case M6:
//System.out.println("State: M6");
clues = 0;
i = 0;
for(x = 0; x < N2; x++) for(y = 0; y < N2; y++) {
c = puzzle.charAt(x * N2 + y);
j = 0;
if(c == '-' || c == '.'|| c == '0' || c == '*'){
A0[x][y] = j;
i++;
} else {
while(L[j] != c && j <= N2)
j++;
if(j <= N2){
A0[x][y] = j;
if(j > 0)
clues++;
i++;
}
}
}
if(clues == N4) {
clues--;
A0[1][1] = 0;
}
for(x = 0; x < N2; x++)
for(y = 0; y < N2; y++)
System.out.print(String.valueOf(A0[x][y]));
System.out.println();
if(p < 8) {
for(i = 0; i <= N4; i++)
Node[i]=0;
}
tnodes = 0;
case RESTART:
//System.out.println("State: RESTART");
r = 0;
for(x = 1; x <= N2; x++) for(y = 1; y <= N2; y++) for(s = 1; s <= N2; s++) {
r++;
Cols[r] = 4;
Col[r][1] = x*N2-N2+y;
Col[r][4] = (N * ((x - 1) / N) + (y - 1) / N) * N2 + s + N4;
Col[r][3]=x * N2 - N2 + s + N4 * 2;
Col[r][2]=y * N2 - N2 + s + N4 * 3;
}
for(c = 1; c <= m; c++) Rows[c]=0;
for(r = 1; r <= n; r++) for(c = 1; c <= Cols[r]; c++) {
x = Col[r][c];
Rows[x]++;
Row[x][Rows[x]] = r;
}
for(x = 0; x < N2; x++) for(y = 0; y < N2; y++)
A[x][y] = A0[x][y];
for(i = 0; i <= n; i++) Ur[i] = 0;
for(i = 0; i <= m; i++) Uc[i] = 0;
solutions = 0;
for(x = 1; x <= N2; x++) for(y = 1; y <= N2; y++) if(A[x-1][y-1] > 0) {
r = x * N4 - N4 + y * N2 - N2 + A[x-1][y-1];
for(j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
if(Uc[c1] > 0 && nocheck == 0) {
STATE = NEXT_TRY;
break;
}
Uc[c1]++;
for(k = 1; k <= Rows[c1]; k++) {
r1 = Row[c1][k];
Ur[r1]++;
}
}
if(STATE == NEXT_TRY)
break;
}
if(STATE == NEXT_TRY)
break;
if(rnd > 0 && rnd != 17 && rnd != 18)
shuffle();
for(c = 1; c <= m; c++) {
V[c] = 0;
for(r = 1; r <= Rows[c]; r++) if(Ur[Row[c][r]] == 0)
V[c]++;
}
i = clues;
nodes = 0;
m0 = 0;
m1 = 0;
gu = 0;
solutions = 0;
case M22:
//System.out.println("State: M22");
i++;
I[i] = 0;
min = n+1;
if(i > N4 || m0 > 0){
STATE = M44;
break;
}
if(m1 > 0) {
C[i] = m1;
STATE = M3;
break;
}
for(c = 1; c <= m; c++) if(Uc[c] == 0) {
if(V[c] <= min) c1 = c;
if(V[c] < min) {
min = V[c];
C[i] = c;
if(min < 2) {
STATE = M3;
break;
}
}
}
if(STATE == M3)
break;
gu++;
if(min > 2) {
STATE = M3;
break;
}
if((rnd&255) == 18) if((nodes&1) > 0) {
c = m + 1;
c--;
while(Uc[c]> 0 || V[c] != 2)
c--;
C[i] = c;
}
if((rnd&255) == 17) {
c1 = (int)(MWC() & Mc[N]);
while(c1 >= m)
c1 = (int)(MWC() & Mc[N]);
c1++;
for(c = c1; c <= m; c++) if(Uc[c] == 0) if(V[c] == 2) {
C[i] = c;
STATE = M3;
break;
}
for(c = 1; c < c1; c++) if(Uc[c] == 0)if(V[c] == 2) {
C[i] = c;
STATE = M3;
break;
}
}
case M3:
//System.out.println("State: M3");
c = C[i];
I[i]++;
if(I[i] > Rows[c]) {
STATE = M44;
break;
}
r = Row[c][I[i]];
if(Ur[r] > 0) {
STATE = M3;
break;
}
m0 = 0;
m1 = 0;
if(q > 0 && i > 32 && i < 65) if((MWC()&127) < q) {
STATE = M3;
break;
}
k = N4;
x = (r - 1) / k + 1;
y = ((r - 1) % k) / j + 1;
s =(r - 1) % j + 1;
// System.out.println("IXYS " + i + "," + x + "," + y +"," + s);
if((p&1) > 0) {
j = N2;
k = N4;
x = (r - 1) / k + 1;
y =((r - 1) % k) / j + 1;
s =(r - 1) % j + 1;
A[x-1][y-1] = s;
if(i == k) {
for(x = 0; x < j; x++) for(y = 0; y < j; y++)
result = result.concat(String.valueOf(L[A[x][y]]));
result = result.concat(" #\n");
}
}
for(j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
Uc[c1]++;
}
for(j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
for(k = 1; k <= Rows[c1]; k++) {
r1 = Row[c1][k];
Ur[r1]++;
if(Ur[r1] == 1) for(l = 1; l <= Cols[r1]; l++) {
c2 = Col[r1][l];
V[c2]--;
if(Uc[c2] + V[c2] < 1) m0 = c2;
if(Uc[c2] == 0 && V[c2] < 2) m1 = c2;
}
}
}
Node[i]++;
tnodes++;
nodes++;
if(rnd > 99 && nodes > rnd) {
// System.out.println("restart");
STATE = RESTART;
break;
}
if(i == N4) solutions++;
if(solutions >= smax) {
System.out.println("smax xolutions found");
if(_try_ == 1) System.out.print("+");
STATE = NEXT_TRY; // Should be M6?
break;
}
if(tnodes > vmax) {
if(_try_ == 1) System.out.print("-");
STATE = NEXT_TRY; // Should be M6?
break;
}
STATE = M22;
break;
case M44:
//System.out.println("State: M44");
i--;
c = C[i];
r = Row[c][I[i]];
if(i == clues) {
STATE = NEXT_TRY;
break;
}
for(j = 1; j <= Cols[r]; j++) {
c1 = Col[r][j];
Uc[c1]--;
for(k = 1; k <= Rows[c1]; k++) {
r1 = Row[c1][k];
Ur[r1]--;
if(Ur[r1] == 0) for(l = 1; l <= Cols[r1]; l++) {
c2 = Col[r1][l];
V[c2]++;
}
}
}
if(p > 0) {
j = N2;
k = N4;
x = (r - 1) / k + 1;
y = ((r - 1) % k) / j + 1;
s = (r - 1) % j + 1;
A[x-1][y-1] = 0;
}
if(i > clues){
STATE = M3;
break;
}
case NEXT_TRY:
//System.out.println("State: NEXT_TRY");
t = new Date();
time1 = t.getTime();
x1 = time1 - time0;
time0 = time1;
if(q > 0) {
xx = 128;
yy = 128 - q;
xx = xx / yy;
yy = solutions;
for(i = 1; i < 33; i++) yy = yy * xx;
System.out.println("clues: " + clues + " estimated solutions:" + yy + " time " + x1 + "ms");
STATE = END;
// STATE = M6;
break;
}
if((p == 0 || p == 1) && tnodes <= 999999) {
if(solutions >= smax)
result = result.concat("More than " + solutions + " solutions ( bad sudoku!! ) " + tnodes + " nodes " + gu + " guesses, time " + x1 + " ms");
else if (solutions == 1)
result = result.concat(solutions + " solution " + tnodes + " nodes " + gu + " guesses, time " + x1 + " ms");
else
result = result.concat(solutions + " solutions ( bad sudoku!! ) " + tnodes + " nodes " + gu + " guesses, time " + x1 + " ms");
STATE = END;
// STATE = M6;
break;
}
if(p == 6) {
System.out.println(solutions);
STATE = END;
// STATE = M6;
break;
}
if(p == 0 || p == 1) {
System.out.println(solutions + " solution(s), " + tnodes + " nodes " + gu + " guesses, time " + x1 + "ms");
// result = result.concat(solutions + " solutions " + tnodes + " nodes " + gu + " guesses, time " + x1 + " ms");
}
if(p > 5) {
x = 0;
for(i = 1; i <= N4; i++) {
x += Node[i];
System.out.print(Node[i]);
if(i % 9 == 0)
System.out.println();
}
System.out.println(x);
}
STATE = END;
break;
} // end of switch statement
} // end of while loop
// System.out.println("State: Exit");
return result;
}
int shuffle() {
for(i = 1; i <= m; i++) {
a = (int)((MWC()>>8) & Mc[N]);
while(a >= i)
a = (int)((MWC()>>8) & Mc[N]);
a++;
P[i] = P[a];
P[a] = i;
}
for(c = 1; c <= m; c++) {
Rows[c] = 0;
T[c] = Uc[c];
}
for(c = 1; c <= m; c++)
Uc[P[c]] = T[c];
for(r = 1; r <= n; r++) for(i = 1; i <= Cols[r]; i++) {
c = P[Col[r][i]];
Col[r][i] = c;
Rows[c]++;
Row[c][Rows[c]] = r;
}
for(i = 1; i <= n; i++) {
a = (int)((MWC()>>8) & Mr[N]);
while(a >= i)
a = (int)((MWC()>>8) & Mr[N]);
a++;
P[i] = P[a];
P[a] = i;
}
for(r = 1; r <= n; r++) {
Cols[r] = 0;
T[r] = Ur[r];
}
for(r = 1; r <= n; r++)
Ur[P[r]] = T[r];
for(c = 1; c <= m; c++) for(i = 1; i <= Rows[c]; i++) {
r = P[Row[c][i]];
Row[c][i] = r;
Cols[r]++;
Col[r][Cols[r]] = c;
}
for(r = 1; r <= n; r++) {
for(i = 1; i <= Cols[r]; i++) {
a = (int)((MWC()>>8) & 7);
while(a >= i)
a = (int)((MWC()>>8) & 7);
a++;
P[i] = P[a];
P[a] = i;
}
for(i = 1; i <= Cols[r]; i++)
T[i] = Col[r][P[i]];
for(i = 1; i <= Cols[r]; i++)
Col[r][i] = T[i];
}
for(c = 1; c <= m; c++) {
for(i = 1; i <= Rows[c]; i++) {
a = (int)((MWC()>>8) & Mw[N]);
while(a >= i)
a = (int)((MWC()>>8) & Mw[N]);
a++;
P[i] = P[a];
P[a] = i;
}
for(i = 1; i <= Rows[c]; i++)
T[i] = Row[c][P[i]];
for(i = 1; i <= Rows[c
]; i++)
Row[c][i] = T[i];
}
return 0;
}
/** Creates a new instance of dlx_solver */
public dlx_solver() {
}
}
class dlx_generator {
long zr = 362436069, wr = 521288629;
long MWC() {
return ((zr = 36969 *(zr & 65535) + (zr >> 16)) ^ ( wr = 18000 * (wr & 65535) + (wr >> 16)));
}
int Rows[] = new int[325],
Cols[] = new int[730],
Row[][] = new int[325][10],
Col[][] = new int[730][5],
Ur[] = new int[730],
Uc[] = new int[325],
V[] = new int[325],
W[] = new int[325];
int P[] = new int[88],
A[] = new int[88],
C[] = new int[88],
I[] = new int[88],
Two[] = new int[888];
char B[]= {'0',
'1','1','1','2','2','2','3','3','3',
'1','1','1','2','2','2','3','3','3',
'1','1','1','2','2','2','3','3','3',
'4','4','4','5','5','5','6','6','6',
'4','4','4','5','5','5','6','6','6',
'4','4','4','5','5','5','6','6','6',
'7','7','7','8','8','8','9','9','9',
'7','7','7','8','8','8','9','9','9',
'7','7','7','8','8','8','9','9','9'
};
char H[][] = new char[326][7];
long c2, w;
int b, f, s1, m0, c1,
r1, l, i1, m1, m2, a, p,
i, j, k, r, c, d, n = 729,
m = 324, x, y, s;
int mi1, mi2, q7, part, nt, rate, nodes, seed,
solutions, min, samples, sam1, clues;
char L[]= {'.','1','2','3','4','5','6','7','8','9'};
static final int M0S = 10;
static final int M0 = 11;
static final int MR1 = 12;
static final int MR3 = 13;
static final int MR4 = 14;
static final int M2 = 15;
static final int M3 = 16;
static final int M4 = 17;
static final int M9 = 18;
static final int MR = 19;
static final int END = 20;
// Set to true to generate debug output
boolean DBG = false;
void dbg(String s) {
if(DBG)
System.out.println(s);
}
public dlx_generator() {
dbg("In constructor");
}
void saveSudokuToFile(String s) {
FileOutputStream FO = null;
byte[] buffer = new byte[s.length()+1];
int i = 0;
while (i < s.length()){
buffer[i] = (byte) s.charAt(i);
i++;
}
try {
FO = new FileOutputStream("generated_sudoku.sdk");
FO.write(buffer);
FO.close();
} catch (IOException IOE) {
// Well, well, well....
return;
}
}
public String generate(long Seed, int Samples, int Rate){
int STATE = M0S;
String result = new String();
dbg("Entering generate");
seed = (int)Seed;
zr = zr ^ seed;
wr = wr + seed;
samples = 1000000000;
if (Samples > 0)
samples = Samples;
// Set to 1 for rating, set to 2 for rating and hint
rate = 0;
if(Rate > 0)
rate = Rate;
if(rate > 2)
rate = 2;
for(i = 0; i < 888; i++) {
j = 1;
while(j <= i)
j += j;
Two[i] = j - 1;
}
r = 0;
for(x = 1; x <= 9; x++) for(y = 1; y <= 9; y++) for(s = 1;s <= 9; s++) {
r++;
Cols[r] = 4;
Col[r][1] = x * 9 - 9 + y;
Col[r][2] = (B[x * 9 - 9 + y] - 48) * 9 - 9 + s + 81;
Col[r][3] = x * 9 - 9 + s + 81 * 2;
Col[r][4] = y * 9 - 9 + s + 81 * 3;
}
for(c = 1; c <= m; c++) Rows[c] = 0;
for(r = 1; r <= n; r++) for(c = 1; c <= Cols[r]; c++) {
a = Col[r][c];
Rows[a]++;
Row[a][Rows[a]] = r;
}
c = 0;
for(x = 1; x <= 9; x++) for(y = 1; y <= 9; y++) {
c++;
H[c][0] = 'r';
H[c][1] = L[x];
H[c][2] = 'c';
H[c][3] = L[y];
H[c][4] = 0;
}
c = 81;
for(b = 1; b <= 9; b++) for(s = 1; s <= 9; s++) {
c++;
H[c][0] = 'b';
H[c][1] = L[b];
H[c][2] = 's';
H[c][3] = L[s];
H[c][4] = 0;
}
c = 81 * 2;
for(x = 1; x <= 9; x++) for(s = 1; s <= 9; s++) {
c++;
H[c][0] = 'r';
H[c][1] = L[x];
H[c][2] = 's';
H[c][3] = L[s];
H[c][4] = 0;
}
c = 81 * 3;
for(y = 1; y <= 9; y++) for(s = 1; s <= 9; s++) {
c++;
H[c][0] = 'c';
H[c][1] = L[y];
H[c][2] = 's';
H[c][3] = L[s];
H[c][4] = 0;
}
dbg("Entering state machine");
sam1 = 0;
while(STATE != END) {
switch (STATE) {
case M0S:
dbg("Entering state M0S");
sam1++;
if(sam1 > samples) {
dbg("*** Finishing. New state: END");
STATE = END;
break;
}
case M0:
dbg("Entering state M0");
for(i = 1; i <= 81; i++) A[i] = 0;
part = 0;
q7 = 0;
case MR1:
dbg("Entering state MR1");
i1 = (int)((MWC()>>8)&127);
if(i1 > 80) {
dbg("New state: MR1");
STATE = MR1;
break;
}
i1++;
if(A[i1] > 0) {
dbg("New state: MR1");
STATE = MR1;
break;
}
case MR3:
dbg("Entering state MR3");
s = (int)((MWC()>>9)&15);
if(s > 8) {
dbg("New state: MR3");
STATE = MR3;
break;
}
s++;
A[i1] = s;
m2 = solve();
q7++;
if(m2 < 1)
A[i1] = 0;
if(m2 != 1){
dbg("New state: MR1");
STATE = MR1;
break;
}
part++;
dbg("####### Generated Sudoku in MR3!");
if(solve() != 1) {
dbg("Solve returned again, but no single solution");
dbg("New state: M0");
STATE = M0;
break;
}
case MR4:
dbg("Entering state MR4");
for(i = 1; i <= 81; i++){
x = (int)((MWC()>>8)&127);
while(x >= i) {
x = (int)((MWC()>>8)&127);
dbg("##### MR4, while x >= i x: " + x + ", i: " + i);
}
x++;
P[i] = P[x];
P[x]=i;
}
for(i1 = 1; i1 <= 81; i1++){
s1 = A[P[i1]];
A[P[i1]] = 0;
if(solve() > 1) A[P[i1]] = s1;
}
if(rate > 0){
nt = 0;
mi1 = 9999;
for(f = 0; f < 100; f++){
solve();
nt += nodes;
if(nodes < mi1) {
mi1 = nodes;
mi2 = C[clues];
}
}
result = result.concat("Rating:" + nt + "# ");
if(rate > 1) {
result = result.concat("hint: " + String.valueOf(H[mi2]).substring(0, 4) + " #\n");
} else
result = result.concat("\n");
}
for(i = 1; i <= 81; i++) {
result = result.concat(String.valueOf(L[A[i]]));
if(i%9 == 0) {
result = result.concat("\n");
}
}
result = result.concat("\n");
default:
dbg("Default case. New state M0S");
STATE = M0S;
break;
} // end of switch statement
} // end of while loop
return result;
}
int solve(){//returns 0 (no solution), 1 (unique sol.), 2 (more than one sol.)
int STATE = M2;
for(i = 0; i <= n; i++) Ur[i] = 0;
for(i = 0; i <= m; i++) Uc[i] = 0;
clues = 0;
for(i = 1; i <= 81; i++) if(A[i] > 0){
clues++;
r = i * 9 - 9 + A[i];
for(j = 1; j <= Cols[r]; j++){
d = Col[r][j];
if(Uc[d] > 0) return 0;
Uc[d]++;
for(k = 1; k <= Rows[d]; k++){
Ur[Row[d][k]]++;
}
}
}
for(c = 1; c <= m; c++) {
V[c] = 0;
for(r = 1; r <= Rows[c]; r++) if(Ur[Row[c][r]] == 0)
V[c]++;
}
i = clues;
m0 = 0;
m1 = 0;
solutions = 0;
nodes = 0;
dbg("Solve: Entering state machine");
while(STATE != END) {
switch(STATE) {
case M2:
dbg("Entering state M2");
i++;
I[i] = 0;
min = n+1;
if((i > 81) || (m0 > 0)){
dbg("New state: M4");
STATE = M4;
break;
}
if(m1 > 0){
dbg("New state: M3");
C[i] = m1;
STATE = M3;
break;
}
w = 0;
for(c = 1; c <= m; c++) if(Uc[c] <= 0){
if(V[c] < 2){
C[i] = c;
STATE = M3;
break;
}
if(V[c] <= min){
w++;
W[(int)w] = c;
}
;
if(V[c] < min){
w = 1;
W[(int)w] = c;
min = V[c];
}
}
if(STATE == M3) {
dbg("***** break in for loop detected");
break;
}
case MR:
dbg("Entering state MR");
c2 = (MWC()&Two[(int)w]);
while (c2 >= w){
dbg("In MR c2: " + c2 + ", w: " + w);
c2 = (MWC()&Two[(int)w]);
}
C[i] = W[(int)c2 + 1];
case M3:
dbg("Entering state M3");
c = C[i];
I[i]++;
if(I[i] > Rows[c]){
dbg("New state: M4");
STATE = M4;
break;
}
r = Row[c][I[i]];
if(Ur[r] > 0){
dbg("New state: M3");
STATE = M3;
break;
}
m0 = 0;
m1 = 0;
nodes++;
for(j = 1; j <= Cols[r]; j++){
c1 = Col[r][j];
Uc[c1]++;
}
for(j = 1; j <= Cols[r]; j++){
c1 = Col[r][j];
for(k = 1; k <= Rows[c1]; k++){
r1 = Row[c1][k];
Ur[r1]++;
if(Ur[r1] == 1) for(l = 1; l <= Cols[r1]; l++){
c2 = Col[r1][l];
V[(int)c2]--;
if(Uc[(int)c2] + V[(int)c2] < 1)
m0 = (int)c2;
if(Uc[(int)c2] == 0 && V[(int)c2] < 2)
m1 = (int)c2;
}
}
}
if(i == 81)
solutions++;
if(solutions > 1) {
dbg("After solutions: New state: M9");
STATE = M9;
break;
}
dbg("New state: M2");
STATE = M2;
break;
case M4:
dbg("Entering state M4");
i--;
c = C[i];
r = Row[c][I[i]];
if(i == clues) {
dbg("After clues: New state: M9");
STATE = M9;
break;
}
for(j = 1; j <= Cols[r]; j++){
c1 = Col[r][j];
Uc[c1]--;
for(k = 1; k <= Rows[c1]; k++){
r1 = Row[c1][k];
Ur[r1]--;
if(Ur[r1] == 0) for(l = 1; l <= Cols[r1]; l++){
c2 = Col[r1][l];
V[(int)c2]++;
}
}
}
if(i > clues) {
dbg("New state: M3");
STATE = M3;
break;
}
case M9:
dbg("*** Entering state M9 solutions: " + solutions);
STATE = END;
break;
default:
dbg("*** Fell into default clause, solutions: " + solutions);
STATE = END;
break;
} // end of switch statement
} // end of while statement
dbg("****returning solutions: " + solutions);
return solutions;
}
}
/**
*
* @author Rolf Sandberg
*/
public class DLXEngine {
dlx_generator generator;
dlx_solver solver;
public DLXEngine() {
generator = new dlx_generator();
solver = new dlx_solver();
}
String generate(int minrating, int maxrating){
Date t = new Date();
long start = t.getTime(), seed;
int rating = 0, tries = 0;;
String ss = new String(), temp = new String();
// Generator:
// First arg: rand seed
// Second arg: #samples, ignored if <= 0
// Third arg: rating and hints, ignored if <= 0
while(rating < minrating || rating > maxrating) {
tries++;
t = new Date();
seed = t.getTime();
ss = generator.generate(seed, 1, 1);
rating = Integer.valueOf(ss.substring(ss.indexOf(':')+1, ss.indexOf('#')));
System.out.println(minrating + ", " + maxrating + ", " + rating);
}
t = new Date();
long end = t.getTime();
System.out.println("Time: " + String.valueOf(end - start) + " milliseconds, tries: " + tries + ", average " + (end-start)/tries);
System.out.println("Generated Sudoku:\n" + ss);
return ss;
}
String solve(String s){
String result = solver.solve(s);
return result;
}
}
|
|
|
| Back to top |
|
 |
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sat Dec 31, 2005 12:45 pm Post subject: Rand... |
|
|
Well, as far as I can see, the MWC is a rand generator as good as any, albeit somewhat Quick and Dirty, and the only thing that would differ with swapping to another one would be a different string of sudokus. It would not do anything to the performance of the program, not in a predictable way anyway.
What differs though, is the seeding. The only way to get a true random number generator is to seed any pseudorandom generator truely randomly. A true boot strap lifters problem  (I usually seed with the system clock, because that is the nearest you get to a random number, actually - it is the result of a random action from a human being.)
Anyone who has examined the distribution of the output from MWC, by the way?
Edit: Oops, wrong thread...
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sat Dec 31, 2005 12:47 pm Post subject: |
|
|
doubleclick removed.
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sat Dec 31, 2005 12:52 pm Post subject: |
|
|
... and btw: The Java code above is the Java portation of the suex solver and generator. The app described in the text file is my Sudoku app, written actuallt just to exercise some programming, I haven't written a line of code in more than ten years
I'm impressed by the performance, anyway. The generator generates some 100 puzzles in seven seconds on a 1.6 GHz laptop, and the solver takes some 16 ms average to solve a puzzle. In Java, an interpreted bytecodecompiled language
/R
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| Ikzann
| | Joined: 03 Jan 2006 | | Posts: 5 | | : | |
Items |
|
| Posted: Tue Jan 03, 2006 3:45 pm Post subject: |
|
|
| Why not just use the standard random()? Is it too slow? |
|
| Back to top |
|
|
| Ikzann
| | Joined: 03 Jan 2006 | | Posts: 5 | | : | |
Items |
|
| Posted: Wed Jan 04, 2006 1:23 am Post subject: |
|
|
| I cleaned up the code - removed some of the gotos (replaced them with loops, etc.), and made it much easier to read (in my opinion). You can find the code here. |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Wed Jan 04, 2006 7:42 am Post subject: |
|
|
| Ikzann wrote: | | Why not just use the standard random()? Is it too slow? |
Well, as far as I can see, any pseudo random generator can be used. The distribution of the generated set of random numbers will, however, have an impact on (for sure) which puzzles are generated, and (possibly and very unpredictably) on the performance of the solver.
Further, the implementation of random() is both compiler dependent and platform dependent, so using a fix random number generator is a way to generate conformity independently of where the code is executed.
Performance? Well, using a C macro instead of a function call explicitly breathes optimization....
<Edit> Nice work with the code, btw. I just replaced all gotos with a more explicit state machine, easier to read somehow, and un-optimizing.
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| Ikzann
| | Joined: 03 Jan 2006 | | Posts: 5 | | : | |
Items |
|
| Posted: Wed Jan 04, 2006 9:02 pm Post subject: |
|
|
donaldf: Can we have your modifications?
Note: If you're using GCC, compile with '-03'. It takes much longer to compile (2-3 seconds instead of .5 on my 800Mhz G4), but it runs 2x as fast for me.
Edit: Finished cleaning up the code. It's much prettier now, and would never win the prize in the obfuscation contest. See above link. |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Thu Jan 05, 2006 7:33 am Post subject: |
|
|
[quote="Ikzann"]donaldf: Can we have your modifications?
My code is tha java code above, I don't work in C for the moment (my hard ddrive is all full of sales material for the moment  ) but it has changed quite a bit since I posted it on my web site. I will do a new posting on the web site when I have done some cleanup job this weekend I'll notify you.
The main idea for me has been
- leave working code untouched
- replace all gotos with breaks in a switch statement (java doesn't support goto)
and all of a sudden, a previously hidden state machine appears
<Edit> Oops, the weekend came early this week Code is updated. Look at http://www.klepphelmer.com/Sudoku/DLXEngine.java
/R
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| eclark
| | Joined: 28 Dec 2005 | | Posts: 70 | | : | |
Items |
|
| Posted: Sat Jan 07, 2006 10:12 am Post subject: |
|
|
| what would I change to generate 4x4(16's) ? changing the m doesn't work |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sun Jan 08, 2006 6:23 pm Post subject: |
|
|
| eclark wrote: | | what would I change to generate 4x4(16's) ? changing the m doesn't work |
No idea. But if you snoop around here, you'll find a fixed version of Guenter's code. I know I have seen it, but no idea of where, unfortunately.
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| wingalls
| | Joined: 15 Jan 2006 | | Posts: 1 | | : | | Location: Sunny San Diego, CA, USA |
Items |
|
| Posted: Sun Jan 15, 2006 4:32 am Post subject: |
|
|
| dukuso wrote: | here is a Java-version by Rolf Sandberg.
He wants me to mention, that it's not being supported. |
Be sure to thank Rolf Sandberg for his contribution. Java is close enough to Javascript that I was able to port easily enough. I intend to include the code in my Konfabulator Widget , that is if it is permitted by the author.
The question of BSD was raised earlier without a final response. If I credit Mr Sandberg in the source, is it okay to use his (modified) code?
Also, what scale is being used for the "Rating" of the puzzle? Is it a common standard that I can view somewhere? Is there a cutoff number for puzzles that cannot be solved by logic alone?
Thank you. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Tue Jan 17, 2006 4:00 pm Post subject: |
|
|
sorry, I haven't been following this the last days. I'm not so much interested in sudoku actually.
Thanks Ikzann for making it more "readable". Yes, I know most people will
probably prefer your version, but tastes are different. I like it to be compact.
eclark, Bo has posted a 16*16 version, we made some effort to get it faster. There is also an actual Perl version, which someone sent me,
send email when someone is interested.
See my latest version from November below.
wingalls: since Rolf Sandberg allowed to post the code to public, I assume it's
OK to use it. Ask him in email.
The rating is just the number of placements in the algorithm which should be
almost proportional to the running time. The average is taken over several
randomized trials. See also:
http://magictour.free.fr/suexrate.exe
http://magictour.free.fr/suexrat9.exe
http://magictour.free.fr/sudoku.htm
| Code: |
// speed-optimized for hard 16*16s , new trick: remember how good
// column-choices were ! (see lines with a ~)
#include <stdio.h>
#include <time.h>
#define N 4 // 16*16-sudoku
#define N2 N*N
#define N4 N2*N2
#define MWC ( (zr=36969*(zr&65535)+(zr>>16)) ^ (wr=18000*(wr&65535)+(wr>>16)) )
int A[N4+9],Ur[N2*N4+1],Uc[4*N4+1],V[N2*N4+1];
int Rows[4*N4+1],Cols[N2*N4+1],Row[4*N4+1][N2+1],Col[N2*N4+1][5];
int C[N4+1],I[N4+1],Node[N4+1],Two[N4*4+9],C0[N4*4+9],P[N4+9];
int M1[N4+9][4*N4+9],N1[N4+9][4*N4+9],Z1[N4+9][4*N4+9]; //~
int s1,i1,t1,i4,c0,m0,m1,try,i,j,k,l,r,r1,c,c1,c2,n=N4*N2,m=4*N4,x,y,s;
int sam,samples,smax,min,clues,nodes,guesses,solutions;
unsigned zr=362436069, wr=521288629;
char L[18]=".123456789ABCDEFG";
FILE *file;
int solve(int);
int reduce(int);
int unreduce(int);
int main(int argc,char*argv[]){clock();
if(argc<2){m5:printf("\nusage:suexg16f samples \n\n");
printf("generates samples sudokus\n");
exit(1);}
x=rawclock();zr+=x;wr^=x;
sscanf(argv[1],"%i",&samples);
for(i=1;i<=m;i++){j=1;while(j<i)j+=j;Two[i]=j-1;}
r=0;k=N;l=N2;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)for(s=1;s<=N2;s++){
r++;Cols[r]=4;
Col[r][1]=x*N2-N2+y;
Col[r][2]=(k*((x-1)/k)+(y-1)/k)*l+s+N4;
Col[r][3]=x*N2-N2+s+N4*2;
Col[r][4]=y*N2-N2+s+N4*3;}
for(i=1;i<=m;i++)Rows[i]=0;
for(r=1;r<=n;r++)for(i=1;i<=Cols[r];i++){
c=Col[r][i];Rows[c]++;Row[c][Rows[c]]=r;}
for(sam=1;sam<=samples;sam++){
m0:for(i=1;i<=N4;i++)A[i]=0;
solve(1);
for(i=1;i<=N4;i++){mr4:x=MWC&255;if(x>=i)goto mr4;x++;P[i]=P[x];P[x]=i;}
for(i1=1;i1<=N4;i1++)if(A[P[i1]]){s1=A[P[i1]];A[P[i1]]=0;if(solve(2)>1)A[P[i1]]=s1;}
if((file=fopen("sudoku.16","at"))==NULL){fclose(file);printf("\nfile-error\n\n");exit(1);}
for(i=1;i<=N4;i++)fprintf(file,"%c",L[A[i]]);fprintf(file,"\n");fclose(file);
for(i=1;i<=N4;i++)printf("%c",L[A[i]]);printf("\n");
}
printf("%i sudokus generated in %i/%isec.\n",samples,clock(),CLOCKS_PER_SEC);
return 0;}
int solve(int smax){
for(i=0;i<=N4>>4;i++)for(j=1;j<=m;j++){N1[i][j]=0;Z1[i][j]=0;} //~
for(i=0;i<=n;i++)Ur[i]=0;for(i=0;i<=m;i++)Uc[i]=0;
clues=0;for(x=1;x<=N2;x++)for(y=1;y<=N2;y++)
if(A[x*N2-N2+y]){clues++;r=x*N4-N4+y*N2-N2+A[x*N2-N2+y];
for(j=1;j<=Cols[r];j++){c1=Col[r][j];if(Uc[c1])return -1;Uc[c1]++;
for(k=1;k<=Rows[c1];k++){r1=Row[c1][k];Ur[r1]++;}}}
for(c=1;c<=m;c++){V[c]=0;for(r=1;r<=Rows[c];r++)if(Ur[Row[c][r]]==0)V[c]++;}
m0=0;m1=0;guesses=0;i=clues;solutions=0;
m2:i++;I[i]=0;min=n+1;if(i>N4 || m0)goto m4;if(m1){C[i]=m1;goto m3;}
c0=0;for(c=1;c<=m;c++)if(!Uc[c]){if(V[c]<=min){c0++;C0[c0]=c;}
if(V[c]<min){min=V[c];c0=1;C[i]=c;C0[c0]=c;if(min<2)goto m3;}}
if(min>1)guesses++;
m2a:c1=MWC&Two[c0];if(c1>=c0)goto m2a;c1++;C[i]=C0[c1];
min=999999;i4=i>>4;
for(j=c1;j<=c0;j++){c=C0[j];if(N1[i4][c]<min*Z1[i4][c]){ //~
min=N1[i4][c]/Z1[i4][c];C[i]=c;}} //~
for(j=1;j<c1;j++){c=C0[j];if(N1[i4][c]<min*Z1[i4][c]){ //~
min=N1[i4][c]/Z1[i4][c];C[i]=c;}} //~
m3:c=C[i];I[i]++;if(I[i]>Rows[c])goto m4;
r=Row[c][I[i]];if(Ur[r])goto m3;m0=0;m1=0;
if(smax==1){j=N2;k=N4;x=(r-1)/k+1;y=((r-1)%k)/j+1;s=(r-1)%j+1;A[x*N2-N2+y]=s;}
for(j=1;j<=Cols[r];j++){c1=Col[r][j];Uc[c1]++;}
for(j=1;j<=Cols[r];j++)reduce(Col[r][j]);
Node[i]++;nodes++;
M1[i][c]=nodes; //~ remember nodes
if(i==N4){solutions++;if(smax==1)return 1;}
if(solutions>1)return 2;goto m2;
m4:c=C[i];
N1[i>>4][c]+=nodes-M1[i][c];Z1[i>>4][c]++; //~ column-statistics
i--;c=C[i];r=Row[c][I[i]];
for(j=1;j<=Cols[r];j++)unreduce(Col[r][j]);
if(i>clues)goto m3;
return solutions;}
int reduce(int c){ // deletes c and N[c], updates V[],m0,m1
int r,c2,k,l;
for(k=1;k<=Rows[c];k++){r=Row[c][k];Ur[r]++;if(Ur[r]==1)
for(l=1;l<=Cols[r];l++){c2=Col[r][l];V[c2]--;
if(Uc[c2]+V[c2]<1)m0=c2;if(Uc[c2]==0 && V[c2]<2)m1=c2;}}}
int unreduce(int c){
int r,c2,k,l;
Uc[c]--;
for(k=1;k<=Rows[c];k++){r=Row[c][k];Ur[r]--;
if(Ur[r]==0)for(l=1;l<=Cols[r];l++){c2=Col[r][l];V[c2]++;}}}
|
Last edited by dukuso on Wed Jan 18, 2006 2:42 am; edited 1 time in total |
|
| Back to top |
|
|
| eclark
| | Joined: 28 Dec 2005 | | Posts: 70 | | : | |
Items |
|
| Posted: Tue Jan 17, 2006 9:12 pm Post subject: |
|
|
Thanks though it errors out on
So I assume you just wanted gettimeofday so I used that
Thanks Much appreciated. |
|
| Back to top |
|
|
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Wed Jan 18, 2006 2:58 am Post subject: |
|
|
yes, just an initialisation of the random number generator.
Maybe gettimeofday is more common, more compatible.
If you can send the version with gettimeofday to sterten@aol.com
I'd like to post the replacement.
I also forgot to use {code} above, so it was badly formatted,
it's corrected now. Maybe we had a faster version,
I just tested it and I felt it was slower than the best we had.
Check also Bo's post and webpage:
http://www.setbb.com/sudoku/viewtopic.php?t=456&mforum=sudoku
http://web.telia.com/~u88910365/ |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
