FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    new in forum, here my solver for test Goto page 1, 2  Next          Sudoku Programmers Forum Index -> Programming sudoku View previous topic :: View next topic   Author Message ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Mon May 05, 2008 6:05 pm    Post subject: new in forum, here my solver for test Hello, I'm new here, but i have been reading this forum for some time. I have done a sudoku solver as a first stage for a sudoku generator. The solver code is almost the same D. Knuth DLX code with some modifications to make it work with sudoku games. I think is pretty fast, but i will appreciate any test or benchmark from you guys. The code is free for any type of use (BSD license). Please check for code some post below Ignacio. Last edited by ignacio_ar on Tue May 06, 2008 11:42 am; edited 1 time in total Back to top gsf Joined: 18 Aug 2005 Posts: 411 : Location: NJ USA Items Posted: Mon May 05, 2008 7:02 pm    Post subject: Re: new in forum, here my solver for test I think your code mouse snarf missed a few lines specifically, there is a missing switch statement Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Mon May 05, 2008 8:02 pm    Post subject: Hello, you are right. seems is broken. But not the code. is a problem with the forum, not showing the code right. Check for code below Last edited by ignacio_ar on Sun May 11, 2008 12:39 pm; edited 1 time in total Back to top hobiwan Joined: 11 Feb 2008 Posts: 83 : Items Posted: Tue May 06, 2008 7:00 am    Post subject: ignacio_ar wrote: Cant post it complete. for some reason the forum delets some part of the code after a line: static columna *col_adr[1<<12]; and resumes when it finds a ">" If you want to use "<" or ">" in your posts you have to choose "Disable HTML in this post". Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Tue May 06, 2008 11:32 am    Post subject: tnx hobiwan i tried that and when i try to post msg i get: Quote: Registered member must have at least 5 postings to post any URL/Website Link and i also get that msg when i try to post a link for download. thats why i explin how to assemble the url. seems i have to post some more msg to reach the 5 post target. dam spammers and robots Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Tue May 06, 2008 11:35 am    Post subject: this is my 4th msg. seems like i have to become a 5 msg spammer to be considerd not a spammer and post a link Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Tue May 06, 2008 11:36 am    Post subject: now, this is 5th msg. I think after this i will be capable to enter link, so i will repost code and file link in next msg. Ignacio. Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Tue May 06, 2008 11:44 am    Post subject: command line is very simple: -h help -s<num> solve searching num solutions (default 1) -v verbose (prints more info ans stats) -q quiet (count solutions without printing them) If you want to verify if a sudoku is valid, with only 1 solution, the argument -s2 has to be set, to search for at least 2 solutions. Thats all. some input/ ouput texts are in spanish, but i believe is easy to understand the meaning. Thank you all. Great forum here! very instructive. Download link: http://www.fileshack.us/get_file.php?id=468187&file=fast_solv_9r.c Code: Code: /* * SUDOKU FAST SOLVER v.9 * Copyright (c) 2007,2008, Ignacio Zelaya * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are met: *     * Redistributions of source code must retain the above copyright *       notice, this list of conditions and the following disclaimer. *     * Redistributions in binary form must reproduce the above copyright *       notice, this list of conditions and the following disclaimer in the *       documentation and/or other materials provided with the distribution. *     * Neither the name of the author nor the *       names of its contributors may be used to endorse or promote products *       derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY Ignacio Zelaya ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * DISCLAIMED. IN NO EVENT SHALL Ignacio Zelaya BE LIABLE FOR ANY * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * primer release publico: * http://www.setbb.com/sudoku/viewtopic.php?p=9689&mforum=sudoku#9689 */ #include <stdio.h>   // printf(), putchar(), fgets(), <stdin> #include <stdlib.h>  // atoi() #include <string.h>  // strlen() #include <unistd.h>  // getopt() typedef struct nodo {   struct nodo *R, *L, *U, *D;   struct columna *C; } nodo; typedef struct columna {   nodo link;   int S; int N;   struct columna *R, *L; } columna; #define max_elem_sol 81+1 #define max_cols 325 #define max_nodos 2916 #define head arr_col[0] // GLOBAL vars // (1) user opts: int verbose=1;       // default=1 (para que imprima solucion) int SEARCH_LIMIT=1;  // soluciones SEARCH_LIMIT:  1 para velocidad  2: para verificar validez >2 busca mas soluciones // (2) dlx stuff   all initializad in make_links() static columna   arr_col[max_cols];    // columnas dlx static nodo      arr_nod[max_nodos];   // nodos dlx static int       max_rows=0;           // max rows es la cantidad maxima de filas/nodos bajo la columna con mayor filas/nodos static columna   *col_adr[1<<12];      // en la pos "nombre de col" guarda el puntero a la columan de ese nombre nodo             *sol[max_elem_sol];   // array donde se guargan los nodos solucion (solo se gurada un nodo del vector) int               matrix[81];          // matriz con clues/solucion. solve() lee esta matriz antes de resolver; int clues=0; int multi=0; // declaracion de funciones int make_links(void); int solve(void); static void cover_col(columna *); static void uncover_col(columna *); void prn_sol(void); void uso(void); // Main ----------------------------------------------------------------- int main(int argc, char *argv[]){   char buffer[300];                 // 300 chars space to read a line   char ch;                    register int k,c,prob=0;   register int soluc=0;   register int games=0;             // sudokus generados   register int status=0;   //analizamos la linea de comando   while ((ch=getopt(argc, argv, "s:qvh"))!=-1){     switch (ch){     case 's':       if(1>(SEARCH_LIMIT=atoi(optarg))) status=1;       break;     case 'q':       verbose=0;       break;     case 'v':       verbose++;       break;     case 'h':     default:       {uso(); return(0);}     }   }   if (status){     (void) printf("ERROR: parametros incorrectos.\t-h (help).\n");     return(status);   }   if (make_links()) {return(1);}   while ( fgets(buffer,300, stdin)){     if (strlen(buffer)<81){continue;} // linea muy corta     for (c=0, k=0; c<strlen(buffer); c++) {       if (k<81) {    matrix[k]=buffer[c]-46;    if (matrix[k]){   // si no es un .      matrix[k]-=2;      if (matrix[k]<0 || matrix[k]>9) {k=-1;}  // caracter invalido, reseteamos k    }    k++;       }     }     if (k!=81)  {continue;} // terminamos de leer la linea. Si no hay 81 caracteres validos, continuamos     prob++;     status=0;     status=solve();     if (status==1) {games++; soluc++;}     if (status>1)  {soluc+=status; (void) printf ("^ above problem, more than 1 sol\n");} // evitar sumar status negativos     if (status<0)  {(void) printf ("Invalid: incorrect data in problem # %d\n",prob);}     if (status==0) {(void) printf ("Invalid: no solution for problem # %d\n",prob);}   }   if (verbose > 1) {     (void) printf ("\nProblems loaded: %d  Solutions found: %d\n",prob,soluc);     if (SEARCH_LIMIT>1){       (void) printf ("Valid sudokus (with exact 1 solution): %d\n",games);     }     else {       (void) printf ("Warning: some problems could have more than one 1 solutions (use -s2 to verify)\n");     }      }   if (!verbose) { (void) printf("Total: %d\n",games);}   return(0); } void uso(void){   (void) printf ("usage:\n\ \t -h help\n\ \t -s<num> solve buscando num soluciones (default 1)\n\ \t -v verbose (prints more info ans stats)\n\ \t -q quiet (count solutions without printing them)\n"); } //----------------------------------------------- int solve(void){     register columna *col,*n;   register nodo *ve, *ho;   register int i, j, x, f, c, b, nu;   int tapadas[max_cols]; // en orden, guarda el nombre de cada col tapada. para usar con col_adr   int tcount=0;            // contador de tapadas   int min;   int single=0;   int soluciones=0;    int level=0;             // identificador de nivel de recursion   clues=0;   multi=0;   // carga un problema que se encuentra en matrix   for (i=9; i>0; i--){     for (j=9; j>0; j--){       if ( (nu = matrix[9*(i-1)+(j-1)]) ){    x=(0x100)+(i<<4)+j;    f=(0x200)+(i<<4)+nu;    c=(0x400)+(j<<4)+nu;    b=(0x800)+((3*((i-1)/3)+((j-1)/3)+1)<<4)+nu;    if ( 0x100 & ( col_adr[x]->S | col_adr[f]->S | col_adr[c]->S | col_adr[b]->S )){      soluciones=-1;       // seteamos soluciones en -1 para indicar error en los datos.      goto FIN;           // No retornamos aqui, vamos a fin para deshacer enlaces hechos antes del error    }    clues++;    tapadas[++tcount]=x; cover_col(col_adr[x]);    tapadas[++tcount]=f; cover_col(col_adr[f]);    tapadas[++tcount]=c; cover_col(col_adr[c]);    tapadas[++tcount]=b; cover_col(col_adr[b]);       }     }   }      NEXT:   min=max_rows;   col=head.R;   for ( n=head.R; n!=&(head); n=n->R){     if (n->S < min){       min=n->S;       col=n;       if (min<2) {break;}     }   }   if (col->S==1){single++;}   cover_col(col);   for ( ve=col->link.D; ve!=&(col->link); ve=ve->D){     sol[level]=ve;     for ( ho=ve->R; ho!=ve; ho=ho->R){       cover_col(ho->C);     }     level++;     if (head.R==&head){       soluciones++;       multi=81-clues-single;       if (verbose && soluciones <=SEARCH_LIMIT) { prn_sol(); }       goto UNDO;     }     if (soluciones<SEARCH_LIMIT){goto NEXT;}  // solo buscar hasta encontrar SEARCH_LIMIT soluciones   UNDO:     level--;     ve=sol[level];     sol[level]=NULL;     col=ve->C;     for (ho=ve->L; ho!=ve; ho=ho->L){       uncover_col(ho->C);     }   }   uncover_col (col);   if (col->S==1){single--;}   if (level==0){goto FIN; }   goto UNDO;  FIN:   do {     uncover_col(col_adr[tapadas[tcount--]]);   } while (tcount>0);   return(soluciones); } // cover ---------------------------------------------------------------- static void cover_col(columna *col){   register nodo *nodo_d;   register nodo *nodo_r;     col->R->L=col->L ;   col->L->R=col->R ;   col->S|=0x100;   for (nodo_d=col->link.D; nodo_d!=&(col->link); nodo_d=nodo_d->D){     nodo_r=nodo_d->R;  // abajo derecha     nodo_r->D->U=nodo_r->U;     nodo_r->U->D=nodo_r->D;     nodo_r->C->S-=1;     nodo_r=nodo_r->R; // derecha     nodo_r->D->U=nodo_r->U;     nodo_r->U->D=nodo_r->D;     nodo_r->C->S-=1;     nodo_r=nodo_r->R; // derecha     nodo_r->D->U=nodo_r->U;     nodo_r->U->D=nodo_r->D;     nodo_r->C->S-=1;   } } // uncover ---------------------------------------------------------------- static void uncover_col(columna *col){   register nodo *nodo_u;   register nodo *nodo_l;     for (nodo_u=col->link.U; nodo_u!=&(col->link); nodo_u=nodo_u->U){       nodo_l=nodo_u->L; // arriba izquierda       nodo_l->C->S+=1;       nodo_l->U->D=nodo_l;       nodo_l->D->U=nodo_l;       nodo_l=nodo_l->L; // izquierda       nodo_l->C->S+=1;       nodo_l->U->D=nodo_l;       nodo_l->D->U=nodo_l;       nodo_l=nodo_l->L; // izquierda       nodo_l->C->S+=1;       nodo_l->U->D=nodo_l;       nodo_l->D->U=nodo_l;   }   col->S&=0x0FF;   col->L->R=col;   col->R->L=col; } // prn_sol ---------------------------------------------------------------- void prn_sol(void){   register int i, j=0, f, x, nu=0;   //  register nodo *s;   int  prn_arr[81];   char c;   for (f=0; sol[f]!=NULL; f++){     x=sol[f]->C->N;     if (x<0x200){      // es coord 1ij   1<<9 = 0x200       i=(x & 0xF0)>>4;       j= x & 0x0F;       nu= sol[f]->R->C->N & 0x0F;     }     else if (x<0x400){ // es coord 2fn  1<<10 = 0x400       i= (x & 0xF0)>>4;       nu= x & 0x0F;          j= sol[f]->L->C->N & 0x0F;     }     else if (x<0x800){ // es coord 3cn 1<<10 = 0x800       nu= x & 0x0F;       j= (x & 0xF0)>>4;       i= (sol[f]->L->C->N & 0xF0)>>4;     }     else { // es box       i=(sol[f]->R->C->N & 0xF0)>>4;          j= sol[f]->R->C->N & 0x0F;       nu= sol[f]->R->R->C->N & 0x0F;     }     prn_arr[9*(i-1)+(j-1)]=  nu; //  agregamos dato  solucion   }   for (i=0; i<81; i++){     if (c=matrix[i]) {       putchar(c+48);  // imprimimos solucion     }     else { putchar(prn_arr[i]+48); }   }   putchar(10); } // make_links ------------------------------------------------------------ int make_links(void){   int i,j,k,f,c,b,n;   int id_nodo=0;        // ultimo nodo colocado   columna *col;   // data para  sudoku   int Pcols=324;          // columnas principales   int data_rows=729;      // cantidad de filas (verctores)   int nodes_per_row=4;    // cantidad de datos por cada fila (vector)   int filas[729*4];   int c1[324];   // generamos los datos de las columnas.   // Casillas=1ij  Filas=2fn  Columnas=3cn  Box=4bn   c=0;   for (k=8; k<12 ; k++){     for (f=1; f<10 ; f++){       for (n=1; n<10 ; n++){         c1[c]=(1<<k)+(f<<4)+n;         c++;       }     }   }   // generamos los datos de las filas filas   k=0;   for (f=1; f<10 ; f++){     for (c=1; c<10 ; c++){       b=(3*((f-1)/3)+((c-1)/3)+1);       for (n=1; n<10; n++){ // para los numeros 1..9    filas[k]  = (1<<8 ) + (f<<4)+ c;    filas[k+1]= (1<<9 ) + (f<<4)+ n;    filas[k+2]= (1<<10) + (c<<4)+ n;    filas[k+3]= (1<<11) + (b<<4)+ n;    k+=4;       }     }   }   // fin generar datos sudoku   head.R=&head;   head.L=&head;   head.S=0;   head.N=0;   // columnas principales   for (i=1; i<=Pcols; i++){     arr_col[i].R=&head;     arr_col[i].L=head.L;     arr_col[i].R->L=&arr_col[i];     arr_col[i].L->R=&arr_col[i];     arr_col[i].link.U=&arr_col[i].link;     arr_col[i].link.D=&arr_col[i].link;     arr_col[i].link.C=&arr_col[i];     arr_col[i].S=0;     arr_col[i].N=c1[i-1];     col_adr[arr_col[i].N]=&arr_col[i];   }   // rows   id_nodo=0;   for (i=0; i<data_rows; i++){     for (j=0; j<nodes_per_row; j++){       col=&(head);       while (col->N!=filas[i*4+j]){    col=col->R;    if (col==&(head)){      (void) printf ("columna no encontrada: %d\n",filas[i*4+j]);      return(1);    }       }       arr_nod[id_nodo].C=col;       arr_nod[id_nodo].U=col->link.U;       arr_nod[id_nodo].D=&(col->link);       arr_nod[id_nodo].U->D=&(arr_nod[id_nodo]);       arr_nod[id_nodo].D->U=&(arr_nod[id_nodo]);             if (j==0){ // si es el primero    arr_nod[id_nodo].R=&(arr_nod[id_nodo]);    arr_nod[id_nodo].L=&(arr_nod[id_nodo]);       }       else {    arr_nod[id_nodo].R=arr_nod[id_nodo-1].R;    arr_nod[id_nodo].L=&(arr_nod[id_nodo-1]);    arr_nod[id_nodo].R->L=&(arr_nod[id_nodo]);    arr_nod[id_nodo].L->R=&(arr_nod[id_nodo]);       }       col->S +=1;       if (col->S > max_rows){    max_rows=col->S;       }       id_nodo++;     }   }   max_rows++; // incrementamos en uno para que sea mayor siempre   i=max_elem_sol-1;   do {     sol[i] = NULL;     i--;   } while (i>=0);      for (i=0; i<81; i++){ // inicializar matriz     matrix[i]='0';   }   return(0); } Back to top Jean-Christophe Joined: 19 Mar 2006 Posts: 126 : Location: Belgium Items Posted: Wed May 07, 2008 9:53 am    Post subject: Re: new in forum, here my solver for test ignacio_ar wrote: I think is pretty fast, but i will appreciate any test or benchmark from you guys. Hi, I made some test and it is indeed pretty fast, compared to other fast solvers Well done ./fast_solv_9r -q < top50000.txt top50000 took 4.160 sec @ 1.8 GHz, searching first solution only 6677 puzzles/second/Ghz ./fast_solv_9r -s2 -q < top50000.txt top50000 took 5.070 sec @ 1.8 GHz, searching two first solutions, if any 5479 puzzles/second/Ghz Note: on my computer, sudocoup is not as fast as announced: ./sudocoup -s1.8 < top50000.txt 5787/s/GHz GC 8.6 C/n inf puzzles 50000 seconds 4.800010 propagations 13864666 nodes 0 Note: Both compiled with gcc v. 4.0.1 with -O3. Tested on PowerPC G5 @ 1.8 GHz single processor (Mac OS X). _________________ Jean-Christophe "When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. Back to top Sisophon2001 Joined: 05 Mar 2008 Posts: 32 : Location: Cambodia Items Posted: Wed May 07, 2008 1:36 pm    Post subject: Re: new in forum, here my solver for test Jean-Christophe wrote: <snip> ./fast_solv_9r -q < top50000.txt top50000 took 4.160 sec @ 1.8 GHz, searching first solution only 6677 puzzles/second/Ghz </snip> Did you add code to do the timing, or is there an easier way? I am using Linux, but also have windows computers. And even without timing code, I can see it is very fast. Congratulations to ignacio_ar. Thanks Garvan Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Wed May 07, 2008 11:32 pm    Post subject: Hey guys Tnx for feedback. i cant be sure on numbers related to "by Ghz" because i have an ams 2700+ but the real clock is 2.172 Ghz. Im not sure if intel Ghz's are equal to AMD Ghz's. For Garvan. Try the "time" command in unix. For windows i have a ntime command. Dont know where i download from. try google "ntime" Im proud it works fast. is just DLX with some minur tune ups. Regards. Ignacio. Back to top Sisophon2001 Joined: 05 Mar 2008 Posts: 32 : Location: Cambodia Items Posted: Thu May 08, 2008 6:21 am    Post subject: Hi, When I tested for speed against sudocoo I get very different results. Still its faster than anything I have done (about 450 puzzles/s/GHz on the same machine). Why is the MAC so different? Garvan Quote: garvan@ubuntu-desktop:~/programming/fbskb/util$ time ./sudocoo < top50000.sdm> /dev/null real 0m3.431s user 0m3.392s sys 0m0.008s garvan@ubuntu-desktop:~/programming/fbskb/util$ time ./fast_solv_9r -q < top50000.sdm> /dev/null real 0m6.460s user 0m6.392s sys 0m0.024s garvan@ubuntu-desktop:~/programming/fbskb/util$ Ubuntu 8.04 Intel Pentium 4 CPU 2.40GHz, Memory 1 GB Back to top Jean-Christophe Joined: 19 Mar 2006 Posts: 126 : Location: Belgium Items Posted: Thu May 08, 2008 8:07 am    Post subject: ignacio_ar wrote: i cant be sure on numbers related to "by Ghz" because i have an ams 2700+ but the real clock is 2.172 Ghz. Im not sure if intel Ghz's are equal to AMD Ghz's. Maybe not very accurate. But it still make sence to compare puzzles/second/GHz on the same computer. Sisophon2001 wrote: When I tested for speed against sudocoo I get very different results. I compared to sudocoup by Glenn Fowler (gsf), not sudocoo which I don't know. Here are the sources and other executables Note: gsf wrote two solvers. I compared to sudocoup, the one optimized for speed. _________________ Jean-Christophe "When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. Back to top Sisophon2001 Joined: 05 Mar 2008 Posts: 32 : Location: Cambodia Items Posted: Thu May 08, 2008 11:21 am    Post subject: Jean-Christophe, I have sudocoup also but the syntax you used Code: ./sudocoup -s1.8 < top50000.txt Is rejected and looking at the --help I can see no option to suppress text output, which would slow things down I think. We must have different versions. I could not find easily downloadable source code for any of the solvers on Glenn Fowler site. I have only the executables. I am planning to go back and try and figure out the INIT system to see if that gets me what I am looking for. I am interested to see how he made his solver 14 times faster than mine. I was pleased with ignacio_ar code because I can understand the algorithm (after a little research), and see why it is fast. If you look at my results for ./fast_solv_9r you will see that I got only 3225 puzzles/sec/GHz compared with your 6677 puzzles/second/Ghz. This is why I asked why the MAC appears to be so different. Garvan Back to top ignacio_ar Joined: 05 May 2008 Posts: 11 : Items Posted: Thu May 08, 2008 11:52 am    Post subject: Hello I dont know why you get those times. Im doing better on a slower computer under windows, and compiled with a not so great compiler (PellesC) compared to the one GCC. Have you compiled with the -O2 or -O3 flags? also, -s2 option will be some bit slower because it searchs for a possible second solution if any. Regards. Sisophon2001 wrote: Hi, When I tested for speed against sudocoo I get very different results. Still its faster than anything I have done (about 450 puzzles/s/GHz on the same machine). Why is the MAC so different? Garvan Ubuntu 8.04 Intel Pentium 4 CPU 2.40GHz, Memory 1 GB Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Programming sudoku All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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