Sudoku Programmers :: View topic - new in forum, here my solver for test

FAQ

Memberlist

Usergroups

Profile

new in forum, here my solver for test
Goto page Previous 1, 2

Sudoku Programmers Forum Index -> Programming sudoku

View previous topic :: View next topic

Author

Message

Jean-Christophe

Joined: 19 Mar 2006

Posts: 126

Location: Belgium

Items

Posted: Thu May 08, 2008 1:42 pm Post subject:

ignacio_ar wrote:

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.

Sisophon2001 gave timings of its own solver, not yours.

ignacio_ar wrote:

Have you compiled with the -O2 or -O3 flags?

I complied both your solver and sudocoup with -O3 as I said.
I didn't compare with -O2.

ignacio_ar wrote:

also, -s2 option will be some bit slower because it searchs for a possible
second solution if any.

I know, that's why I tested both the default (-s1) and -s2.

Sisophon2001 wrote:

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 can see att changed their license policy. I downloaded an older version, before this change of policy. The version I tested was released 2006-02-14. As far as I can see, it also stops at first solution found and does not output any solution, just the stats at the end of the process.

Hopefully gsf will come and give some more explanations.

Sisophon2001 wrote:

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.

No idea! It should give similar speeds, provided you too compiled with gcc 4.0 with -O3. Surely not such a big difference, it's about twice slower for you. Shocked

_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

Jean-Christophe

Joined: 19 Mar 2006

Posts: 126

Location: Belgium

Items

Posted: Thu May 08, 2008 3:03 pm Post subject:

Sisophon2001 wrote:

I have sudocoup also but the syntax you used

Code:

./sudocoup -s1.8 < top50000.txt

I've just dowloaded the lastest sources. Authenticate as indicated at the very bottom of the CPL License which you're supposed to read and should agree with, isn't it ?

Then I just compiled without any change

Code:

g5-de-jc:/Volumes/SansTitre3/ast-sudoku.2008-02-02/src/cmd/sudoku jcgodart$ gcc -O3 -o sudocoup sudocoup.c
sudocoup.c: In function 'main':
sudocoup.c:1309: warning: pointer targets in assignment differ in signedness
g5-de-jc:/Volumes/SansTitre3/ast-sudoku.2008-02-02/src/cmd/sudoku jcgodart$ ./sudocoup --help
NAME
sudocoup - 9x9 sudoku solver

SYNOPSIS
sudocoup [ options ] [ puzzle ... | < puzzle.file ... ]

DESCRIPTION
sudocoup solves 9x9 sudoku puzzles defined by the literal puzzle
operands or puzzles read from the standard input if there are no puzzle
operands, and solves each puzzle. A solvable puzzle has exactly one solution.
The solver stops on the first solution for each puzzle.

OPTIONS
-sN Normalize solving time for a processor speed of N (default GHz.)

There are a few compile time options that may degrade performance. Other
compile time options control puzzle order (4..64) and QWH (quasigroup
with holes or latin square) vs. sudoku. See the source for details.

DETAILS
<snip>
IMPLEMENTATION
version sudocoup 9x9 (AT&T Research) 2007-10-11
author Glenn Fowler <gsf AT research.att.com>
copyright Copyright (c) 2005-2007 AT&T Knowledge Ventures
license http://www.opensource.org/licenses/cpl1.0.txt
g5-de-jc:/Volumes/SansTitre3/ast-sudoku.2008-02-02/src/cmd/sudoku jcgodart$ ./sudocoup -s1.8 < /Volumes/SansTitre3/top50000.txt
5798/s/GHz GC 8.6 C/n inf puzzles 50000 seconds 4.790782 propagations 13864666 nodes 0

As you can see, the -sN option is avail, and the only output produced are the stats. No significant difference in solving speed compared to the older version I initially used.

BTW the help shows a release dated 2007-10-11, whereas the package is dated 2008-02-02...
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

gsf

Joined: 18 Aug 2005

Posts: 411

Location: NJ USA

Items

Posted: Fri May 09, 2008 2:00 am Post subject:

ignacio_ar
your dlx fastsolv is a very nice implementation

here are the user time puz/sec/Ghz on a linux pentium 4 gcc -O3

Code:

solver top50000 sudoku17(47461)
------ -------- ---------------
fastsolv 7331 8012
sudocoup 3213 5381
sudocoo 7621 153
sudoku -qFN 3496 3164

fastsolv and sudoku are the most consistent across different input
sudocoo is terrible with small number of clues (that is mitigated by a one time forward check in sudoku(1))

re different performance on powerpc -- my guess is the code layout
in my implementations (serendipitously) favors the pentium architecture
L1/L2 cache usage / availability also has a big effect on performance

re package version stamp vs package components
a package gets its version stamp when the package is created
it may contain components with older timestamps
ast-sudoku-2008-02-02 contains { sudoku sodocoo sudocoup pseudocoup }
some with version stamps older than 2008-02-02

{ sodocoo sudocoup pseudocoup } are standalone and compile from one source file
features are enabled by compile time -Dname=value
read the source to see what the -D's enable

{ sudoku } is built from a few separate source files, best done via the Makefile

Sisophon2001

Joined: 05 Mar 2008

Posts: 32

Location: Cambodia

Items

Posted: Sat May 10, 2008 7:54 am Post subject:

Hi I compiled fast_solv_9r in windows, and get full speed, so the half-speed I get on my Linux box must be something about my hardware. This computer must be six or seven years old now, so maybe it is time for an upgrade. I also found the correct download for the code of the gfs solvers (I was just me clicking the wrong download last time ). When I compile gfs's code in Linux, I get even faster results than the pre-compiled version I downloaded! I had a look at the code of sudocoo already, very neat! I used the -O3 option on all code compiled, and tried a few other options also, so it can not be that. Garvan

ignacio_ar

Joined: 05 May 2008

Posts: 11

Items

Posted: Sun May 11, 2008 1:27 pm Post subject:

Hello

I'm back from a week trip. Thank you all for the feedback.
Im pleased to read you like the implementation. Special
from gsf.

Initially was a solver, then I turned into a generator. Later i speed up.
Finally I extracted the solver and do some more optimizations.
The result, fast_solver_9r, is the solver posted here.

My code need a bit more of clean up:
By inspecting the code now ( i writed all this in nov/2007)
I found some remains from generator, like:

Code:

int clues=0;
int multi=0;

multi was used in generator to count the times when there was no column with only one node below it. For the solver is not neded.
I just deleted all unnecessary lines, and come with a little fast code.

Here it is: FAST SOLVER v.9 r2

Dowload link:
http://www.fileshack.us/get_file.php?id=480815&file=fast_solv_9r2.c

Code:

/*
* SUDOKU FAST SOLVER v.9 r2
* 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: (r y r2)
* 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;

// 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 soluciones=0;
int level=0; // identificador de nivel de recursion

// 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
}
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;}
}
}
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++;
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 (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);
}

Display posts from previous:

	Sudoku Programmers Forum Index -> Programming sudoku	All times are GMT Goto page Previous 1, 2
Page 2 of 2

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