|
| View previous topic :: View next topic |
| Author |
Message |
| gsf
| | Joined: 18 Aug 2005 | | Posts: 411 | | : | | Location: NJ USA |
Items |
|
 Posted: Wed Jan 18, 2006 5:04 am Post subject: |
 |
|
| dukuso wrote: | yes, just an initialisation of the random number generator.
Maybe gettimeofday is more common, more compatible.
|
long time no post
this might be more portable, but is limited to 1 second granularity:
also, I generated 10 using the posted generator and
ran it through my speed solver it took 0.24 sec to solve all 10
I have similar problems generating difficult puzzles
the generator clunks for a long time just to have the solver act as if it were cat(1)
do you have any ideas on tuning the 16x16 difficulty? |
|
| Back to top |
|
 |
| dukuso
| | Joined: 14 Jul 2005 | | Posts: 424 | | : | | Location: germany |
Items |
|
| Posted: Wed Jan 18, 2006 5:58 am Post subject: |
|
|
maybe ask Gordon Royle to produce 16*16 sudokus with minimal
number of clues ?
That was how I got most of my hardest 9*9s.
You can always play around a bit with hillclimbing,
changing one clue, solving, rechange the clue again, if there was no improvement, etc.
trying to increase
the solving time this way. |
|
| Back to top |
|
|
| eclark
| | Joined: 28 Dec 2005 | | Posts: 70 | | : | |
Items |
|
| Posted: Wed Jan 18, 2006 7:36 pm Post subject: |
|
|
| dukuso wrote: | 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.
|
sorry I'm away from the computer right now but Here is the code. I ran indent over it so its a little bit nicer.
| 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>
#include <stdio.h>
#include <sys/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 ();
//These are for out rancom number x
unsigned int seed;
struct timeval tv;
if (argc < 2) {
m5:printf ("\nusage:suexg16f samples \n\n");
printf ("generates samples sudokus\n");
exit (1);
}
gettimeofday (&tv, 0);
x = tv.tv_sec + tv.tv_usec;
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]++;
}
}
}
|
|
|
| Back to top |
|
|
| cormac.mcphillips
| | Joined: 02 Dec 2005 | | Posts: 4 | | : | |
Items |
|
| Posted: Thu Jan 19, 2006 12:52 pm Post subject: |
|
|
| How do you set the difficulty level for Rolf Sandberg’s java Suduko generator?? |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sun Jan 29, 2006 9:47 am Post subject: |
|
|
| cormac.mcphillips wrote: | | How do you set the difficulty level for Rolf Sandberg’s java Suduko generator?? |
Hi,
Well, you don't. The generator is fast enough to allow for generating, say, 20 puzzles at a time and then look for a puzzle with appropriate rating among those. It usually takes 2 seconds to find a puzzle with a rating of 25000 or more on my 1.4 GHz laptop that way. In Java 
Here's how I do it:
| Code: |
String generate(int minrating, int maxrating){
Date t = new Date();
long start = t.getTime(), seed;
int tries = 0, i, samples = 5;
long rating = 0;
String ss[] = new String[samples],
temp = new String();
for(tries = 0; tries < samples; tries++)
ss[tries] = new String();
tries = 1;
// Generator:
// First arg: rand seed
// Second arg: #samples, ignored if <= 0
// Third arg: rating and hints, ignored if <= 0
// Task: Find a Sudoku with a rating in a specified interval.
// Do it by generating samples and examine them
// Continue until an appropriate puzzle is found.
while(tries < 9999999) {
tries++;
t = new Date();
seed = t.getTime();
ss = generator.generate(seed, samples, 0);
for(i = 0; i < samples; i++) {
rating = generator.rate(ss[i].replace("\n","").trim());
if(rating > minrating && rating < maxrating) {
return ss[i];
}
}
System.out.println(minrating + ", " + maxrating + ", " + rating + ", looping");
}
return ss[0];
}
|
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sun Jan 29, 2006 9:57 am Post subject: |
|
|
| wingalls wrote: |
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?
Thank you. |
Hi,
Be my guest. The code is all Guenters property, the only thing I did was to port it to Java and destroy ("modify"  ) it somewhat during that process.
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| donaldf
| | Joined: 31 Dec 2005 | | Posts: 11 | | : | | Location: Sweden |
Items |
|
| Posted: Sun Jan 29, 2006 1:22 pm Post subject: |
|
|
BTW, I have upgraded (well, well, well....) my website-
http://www.klepphelmer.com/Sudoku
_________________
It's better to seek forgiveness than to ask permission |
|
| Back to top |
|
|
| sudo_fish
| | Joined: 06 Apr 2006 | | Posts: 1 | | : | | Location: USA |
Items |
|
| Posted: Thu Apr 06, 2006 4:11 pm Post subject: symmetrical puzzle |
|
|
| is it possible to use it to generate symmetrical sudoku? |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Sun Apr 09, 2006 6:46 pm Post subject: |
|
|
I don't know about that code in particular, but my own build algorithm can be modified for symmetry (I've done so myself).
1) Add about 18 givens from the available set, being sure to exclude choices that conflict with ones you've added.
2) Solve with a backtracking algorithm like DLX. If no solutions exist, delete givens at random one at a time and try again.
3) Until the puzzle has only one solution, add a given from one of the solutions already discovered, and re-solve.
4) Keep removing givens at random until no more can be deleted.
For symmetry, all you have to do is add step 2b) add givens that are symmetrical to existing givens. Then in steps 3 and 4, you only add or delete symmetrical groups. |
|
| Back to top |
|
|
| dersimon
| | Joined: 06 Dec 2006 | | Posts: 1 | | : | |
Items |
|
| Posted: Wed Dec 06, 2006 8:18 am Post subject: Sudoku solving with dukuso's generator |
|
|
| dukuso, can you show me how to remodel your generator (which includes already a dlx solver) to a pure and fast dlx solver (especially for big sudokus 16x16, 25x25 or 36x36)? |
|
| 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
