PDA

Visualizza la versione completa : [c++] sudoku


mondobimbi
26-04-2008, 10:35
ci sono stati ultimamente un paio di thread con argomento il sudoku che mi hanno intrigato notevolmente tanto che, essendo appassionato di sudoku, ho provato a scrivere un generatore di sudoku.
E' solamente una bozza ma ho riscontrato il seguente problema che spero qualcuno esperto in sudoku possa risolvere: dopo la generazione di una soluzione valida di sudoku (una griglia 9x9 che ne rispetti i vincoli), il sudoku giocabile viene generato tramite la eliminazione di caselle di gioco. Ho provato a toglierle in maniera random (da 25 a 35 seconda la difficoltà che si vuole conferire al gioco) ma il risultato è un sudoku, dato in pasto a mia moglia, la vera esperta della famiglia, che spesso riporta più di una soluzione ed ha uno schema sospetto. L'algoritmo di generazione cerca una soluzione tra un set di numeri casuale e in caso l'inserimento di un numero fallisca cerca di fare uno scambio valido con un numero precedente già inserito. Se comnque non riesce fallisce e riprova con una nuova sequenza casuale. Alcune volte nonostante ripetute prove lo schema non viene trovato e il programma fallisce con necessità di riavviarlo.
Riporto quello che ho pensato, è copiabile e compilabile. L'ultima parte del main genera un file postscript e quindi tramite una chiamata al programma ps2pdf il file pdf da cui è possibile stampare lo schema generato (questa parte utilizza fork e non funziona quindi sotto windows e va' cancellata, in questo caso si dispone unicamente del file postscript dal nome soluzione.ps e non del pdf, e si ha bisogno quindi di un programma apposito per stamparlo). In ogni caso o schermo vengono stampate schema di gioco e soluzione.


#include <stdlib.h>
#include <fstream>
#include <iostream>


#include <unistd.h> /* per fork(), getpid(), getppid() */
#include <string.h> /* per strerror() */
#include <errno.h> /* per errno */
#include <sys/types.h> /* per pid_t */
#include <sys/wait.h> /* per wait() */


using namespace std;

class Sudoku {

int sudoku[9][9];

int soluzione[9][9];

public:

Sudoku ();

bool genera ();

bool make(int difficolta);

int elemento (int i, int j) ;

bool print () ;

};



class Riquadro {

int v[9], ri[9], co[9];

Sudoku *sudo;

public :

Riquadro (Sudoku *s);

void genera (int row, int col);

void print();

bool check(int n);

};



class Sequenza {


int max; // il valore massimo
int num_seq; //

int * riga;
int pos;

public:
Sequenza (int _max=9, int _num=9) :
pos(0), max(_max), num_seq(_num) {
/* initialize random seed: */
riga = new int[num_seq];

for (int i = 0; i < num_seq; i++) {
int j = 0;
int r = 1 + rand() % max;
while (j < i) {
if (riga[j] == r) {
// genera un nuovo numero
r = 1 + rand() % max;
j = -1;
}
j++;
}
riga[i] = r;
}
}
~Sequenza () {
delete [] riga;
}
int get() {
if (pos <=num_seq)
return riga[pos++];
else
return (0);
}
int unget() {
if (pos >= 0)
return riga[pos--];
else
return (0);
}
void shift() {
int tmp = riga[pos];
for (int i=pos; i < num_seq-1; i++)
riga[i]=riga[i+1];
riga[num_seq-1]=tmp;
}
};



Riquadro::Riquadro (Sudoku *s) : sudo(s)
{
}

void Riquadro::genera(int row, int col)
{

Sudoku *s = sudo;

int r = row / 3;
int c = col / 3;
int val = 0;

for (int i = r * 3; i < r * 3 + 3; i++)
for (int j = c * 3; j < c * 3 + 3; j++) {
if (i==row && j==col)
v[val++] = 0;
else
v[val++] = s->elemento(i, j);
}

for (int i = 0; i < 9; i++)
ri[i]=s->elemento(row, i);
ri[col]=0;

for (int i = 0; i < 9; i++)
co[i]=s->elemento(i, col);
co[row]=0;

}

void Riquadro::print()
{
for (int i = 0; i < 9; i++)
cout << v[i] << "\t" ;
}

bool Riquadro::check(int n)
{
for (int i=0; i < 9; i++)
if (v[i] == n || ri[i] == n || co[i] == n) return false;
return true;
}

Sudoku::Sudoku ()
{
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
sudoku [i][j] = 0;
}

bool Sudoku::genera ()
{

Riquadro q(this);

// per tutte le righe
for (int i = 0; i < 9; i++) {
Sequenza r;
// per tutte le colonne
for (int j = 0; j < 9; j++) {
int n = r.get();
q.genera(i, j);

int count=0;
while (!q.check(n)) {
if (count == 10) return false;
r.unget();
r.shift();
int n1 = r.get();
if (n == n1 || count==9) {
// vai indietro e scambia se possibile
for (int i1 = 0; i1 <= i; i1++) {
for (int j1 = 0; j1 <= j; j1++) {
if (i1==4)
int nn=100;
int n2 = sudoku[i1][j1];
sudoku[i1][j1]=0;
Riquadro q1(this);
Riquadro q2(this);
q1.genera(i1, j1);
q2.genera(i, j);
if (n1 !=n2 && q2.check(n2) && q1.check(n1)) {
sudoku[i1][j1]=n1;
sudoku[i][j] = n;
q.genera(i, j);
i1=i+1;
j1=j+1;
n=n2;
}
else
sudoku[i1][j1]=n2;
}
}
}
else
n = n1;
count++;
}
sudoku[i][j] = n;
}
}

// salva la soluzione
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
soluzione[i][j]=sudoku [i][j] ;

return true;

}

bool Sudoku::make(int difficolta) {

for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++)
sudoku [i][j] = soluzione[i][j];

// crea il sudoku eliminando
// alcune caselle
Sequenza r(81, difficolta);
for (int i = 0; i < difficolta; i++) {
int val = r.get()-1;
int row = val / 9;
int col = val % 9;
sudoku[row][col] = 0;
}
}


int Sudoku::elemento (int i, int j) {
return sudoku[i][j];
}

bool Sudoku::print () {
// per tutte le righe
for (int i = 0; i < 9; i++) {
// per tutte le colonne
for (int j = 0; j < 9; j++) {
cout << elemento(i,j) << "\t";
}
cout << "\n";
}
}

int main(int argc, char **argv)
{

int caselle_vuote ;
if (argc != 2) {
cout << "Utilizzo nome_programma numero_caselle_vuote." << endl;
cout << "Valore default 30." << endl;
caselle_vuote = 30;
}
else
caselle_vuote= atoi(argv[1]);

srand(time(NULL));

Sudoku s;

int count = 0;
while (!s.genera()) {
cout << "." ;
if (count++ == 2000) {
cout << endl << "Spiacente non sono riuscito a creare il sudoku." << endl;
cout << "Lanciare il programma nuovamente sperando in maggior fortuna." << endl;
return (0);
}
}

cout << "\n";
s.print();
cout << "\n";

s.make(caselle_vuote);

cout << "------\n";
s.print();

ofstream f ( "soluzione.ps", ios_base::out );

f << "newpath" << "\n";
f << "70 650 moveto" << "\n";
f << "520 650 lineto" << "\n";
f << "520 200 lineto" << "\n";
f << "70 200 lineto" << "\n";
f << "closepath" << "\n";
f << "4 setlinewidth" << "\n";
f << "stroke" << "\n";

for (int i = 0; i < 2; i++) {

f << 220 + 150*i << " 650 moveto" << "\n";
f << 220 + 150*i << " 200 lineto" << "\n";
f << "4 setlinewidth" << "\n";
f << "stroke" << "\n";

f << "70 " << 350+150*i << " moveto\n";
f << "520 " << 350+150*i << " lineto\n";
f << "4 setlinewidth" << "\n";
f << "stroke" << "\n";

}

for (int i = 0; i < 8; i++) {

f << 120 + 50*i << " 650 moveto" << "\n";
f << 120 + 50*i << " 200 lineto" << "\n";
f << "1 setlinewidth" << "\n";
f << "stroke" << "\n";

f << "70 " << 250+50*i << " moveto\n";
f << "520 " << 250+50*i << " lineto\n";
f << "1 setlinewidth" << "\n";
f << "stroke" << "\n";

}

f << "/Times-Bold findfont" << "\n";
f << "20 scalefont setfont" << "\n";
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (s.elemento(i,j) != 0) {
f << 90+50*j << " " << 620 - 50*i << " moveto" << "\n";
f << "(" << s.elemento(i,j) << ") show"<< "\n";
}
}
}

f << "showpage" << "\n";

f.close();

/*
*********************************************
in windows tutto il codice che segue va tolto
*********************************************
*/


pid_t pid; /* PID del processo figlio */
pid_t wpid; /* PID per wait() */
int status; /* Stato ritornato da wait() */

/* Si crea il processo figlio */
pid = fork();

if (pid == -1) {
/* La chiamata fork() e' fallita */
fprintf(stderr, "%s: Failed to fork()\n", strerror(errno));
exit(EXIT_FAILURE);
} else if (pid == 0) {
/* Questo e' il processo figlio */
static char *argv[] = { "ps2pdf", "soluzione.ps", NULL };

printf("PID %ld: Child started, parent is %ld.\n",
(long) getpid(), (long) getppid());

/*
* Chiama execv() per rimpiazzare il processo corrente con
* /bin/ps. Se il programma ps non e' presente nella
* directory /bin del tuo sistema, puoi cambiare il
* percorso (assoluto) del primo argomento di execv().
*/
execv("/usr/bin/ps2pdf", argv);
/*
* Se il controllo e' giunto qui allora si e' verificato
* un errore nella chiamata execv().
*/
fprintf(stderr, "%s: execv()\n", strerror(errno)); }
else {
/* Questo e' il processo padre */
printf("PID %ld: Started child PID %ld.\n", (long) getpid(),
(long) pid);

/* Aspettiamo che il processo figlio termini */
wpid = wait(&status); /* Child's exit status */

if (wpid == -1) {
/* La chiamata a wait() e' fallita. */
fprintf(stderr, "%s: wait()\n", strerror(errno));
return 1;
} else {
/* Il processo figlio e' terminato */
if (WIFEXITED(status)) {
/* Uscita normale -- stampa dello stato */
printf("Exited: $? = %d\n",
WEXITSTATUS(status));
} else if (WIFSIGNALED(status)) {
/*
* Uscita anormale -- il processo figlio
* e' terminato a causa di un segnale
*/
printf("Signal: %d%s\n",
WTERMSIG(status), WCOREDUMP(status)
? " with core file." : "");
} else {
/* Il processo e' stato fermato */
printf("Stopped.\n");
}
}
}

return (0);

}

buon divertimento
:madai!?:
sergio

Loading