Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

short and fast sudoku-generator in C
Goto page Previous  1, 2, 3, 4
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
gsf

Joined: 18 Aug 2005
Posts: 411
:
Location: NJ USA

Items
PostPosted: Wed Jan 18, 2006 5:04 am    Post subject: Reply with quote

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:
Code:

seed = time(0);

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
View user's profile Send private message Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Jan 18, 2006 5:58 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
eclark

Joined: 28 Dec 2005
Posts: 70
:

Items
PostPosted: Wed Jan 18, 2006 7:36 pm    Post subject: Reply with quote

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
View user's profile Send private message
cormac.mcphillips

Joined: 02 Dec 2005
Posts: 4
:

Items
PostPosted: Thu Jan 19, 2006 12:52 pm    Post subject: Reply with quote

How do you set the difficulty level for Rolf Sandberg’s java Suduko generator??
Back to top
View user's profile Send private message
donaldf

Joined: 31 Dec 2005
Posts: 11
:
Location: Sweden

Items
PostPosted: Sun Jan 29, 2006 9:47 am    Post subject: Reply with quote

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 Smile

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
View user's profile Send private message Visit poster's website MSN Messenger
donaldf

Joined: 31 Dec 2005
Posts: 11
:
Location: Sweden

Items
PostPosted: Sun Jan 29, 2006 9:57 am    Post subject: Reply with quote

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" Cool ) it somewhat during that process.
_________________
It's better to seek forgiveness than to ask permission
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
donaldf

Joined: 31 Dec 2005
Posts: 11
:
Location: Sweden

Items
PostPosted: Sun Jan 29, 2006 1:22 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website MSN Messenger
sudo_fish

Joined: 06 Apr 2006
Posts: 1
:
Location: USA

Items
PostPosted: Thu Apr 06, 2006 4:11 pm    Post subject: symmetrical puzzle Reply with quote

is it possible to use it to generate symmetrical sudoku?
Back to top
View user's profile Send private message
Lummox JR

Joined: 07 Sep 2005
Posts: 202
:

Items
PostPosted: Sun Apr 09, 2006 6:46 pm    Post subject: Reply with quote

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
View user's profile Send private message
dersimon

Joined: 06 Dec 2006
Posts: 1
:

Items
PostPosted: Wed Dec 06, 2006 8:18 am    Post subject: Sudoku solving with dukuso's generator Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page Previous  1, 2, 3, 4
Page 4 of 4

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron