Ir para o conteúdo
MKaks

Sudoku

Mensagens Recomendadas

MKaks

Boas Malta :)

Para a cadeira de Programação e Algoritmia temos de fazer um programinha que gera uma grelha de Sudoku resolvida.

Encontrei um fluxograma pelo qual me tenho guiado para ir elaborando as funções (tem código também mas não o entendo xD) (http://www.codeproject.com/Articles/23206/Sudoku-Algorithm-Generates-a-Valid-Sudoku-in-0-018).

O problema é que há aqui um pormenor/condiçao que me esta a escapar para que, quando não tenho mais numeros possiveis de se usar (linha nrs diferentes de 1-9 / coluna nrs diferentes de 1-9 / 3x3 nrs diferentes de 1-9), limpe não sei se todos se alguns numeros para que voltando a colocalos de modo diferente possa prosseguir no varrimento da matriz até chegar ao fim, gerando um sudoku resolvido.

Peço desculpa em antemão mas, ainda não me obriguei ao treino de comentar o código xD

#include <stdio.h>
int tabuleiro[9][9]={{0}};
int lista[9][9][9]={{{0}}};
int main(){
int alea;
srand(time(0));
coloca();
mostra();
}
void mostra(){
int i,j;
for(i=1;i<=19;i++){
    for(j=1;j<=19;j++){
        if(i==1&&j==1)
            printf("\xc9");
        else if(i==1 && (j==7 || j==13))
            printf("\xcb");
        else if(i==1 && j==19)
            printf("\xbb");
        else if((i==7 || i==13) && j==1)
            printf("\xcc");
        else if((i==7 || i==13) && j==19)
            printf("\xb9");
        else if(i==19 && j==1)
            printf("\xc8");
        else if(i==19 && (j==7 || j==13))
            printf("\xca");
        else if(i==19 && j==19)
            printf("\xbc");
        else if((i==1 || i==7 || i==13 || i==19) && (j!=7 && j!=13))
            printf("\xcd");
        else if((i!=7 && i!=13) && (j==1 || j==7 || j==13 || j==19))
            printf("\xba");
        else if((i==7 && j==7) || (i==7 && j==13) || (i==13 && j==7) || (i==13 && j==13))
            printf("\xce");
        else if(i%2==0 && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
            printf("\xb3");
        else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && j%2==0)
            printf("\xc4");
        else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
            printf("\xc5");
        else if(tabuleiro[i/2-1][j/2-1]==0)
            printf(" ");
        else
            printf("%d",tabuleiro[i/2-1][j/2-1]);
    }
    printf("\n");
}
}
int aleatorio(int i, int j){
int a;
int min = 1;
int max = 9;
do{
    a = min + rand() % (max - min + 1);
}while(lista[i][j][a]==1);
return a;

}
int coloca(){
int i,j,alea,b;
for(i=0;i<=8;i++){
    for(j=0;j<=8;j++){
        mostra();
        do{
            alea=aleatorio(i,j);
            b=colocaBem(alea,i,j);
        //tabuleiro[i][j] = aleatorio();
        }while(b==0);
    }
}
}
int colocaBem(int alea, int linha, int coluna){

int i,j,a,b;
for(i=0;i<=8;i++){
        if(tabuleiro[linha][i] == alea)
            return 0;
}
for(i=0;i<=8;i++){
    if(tabuleiro[i][coluna] == alea)
            return 0;
}
a=linha/3;
b=coluna/3;
for(i=0;i<=2;i++){
    for(j=0;j<=2;j++)
        if(tabuleiro[i+a*3][j+b*3]==alea)
            return 0;
}
VerificaDispLista(linha,coluna,alea);
return 1;
}
void VerificaDispLista(int i, int j, int alea){
if(lista[i][j][alea-1]==0){
    tabuleiro[i][j]=alea;
    lista[i][j][alea-1]=1;
}
}
void PercorreLista(int i, int j){
int k,c;
for(k=0;k<=8;k++){
    if(lista[i][j][k]==1)
        c++;
}
if(c==9){
    lista[i][j][k]=0;
    lista[i][j-1][k]=0;
}
}

Obrigada e FelizNatal :)

MKaks

Editado por pmg
Falta LP

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

epa, que confusão do camando !!!

quem criou o fluxograma não está claramente dentro dos métodos mais simples de criar uma solução:

eu dou-te um algoritmo para seguites muito melhor e 10000x mais fácil

- criar uma matrix 9x9
- preencher a matrix com uma solução válida

- para N trocas
 - ler um numero aleatório que the escolha uma das seguintes operações:
   - linha
     - escolher aleatóriamente 2 linhas diferentes de um bloco de 3 linhas
     - trocas as linhas
   - coluna
     - escolher aleatóriamente 2 colunas diferentes de um bloco de 3 colunas
     - trocas as linhas
   - um bloco de 3 linhas
     - escolher aleatóiamente 2 blocos de linhas
     - trocar os blocos
   - um bloco de 3 colunas
     - escolher aleatóiamente 2 blocos de colunas
     - trocar os blocos
   - transposta pela diagonal principal
     - efectuar a transposta
   - transposta pela diagonal secundária
     - efectuar a transposta

- já está !!!!

ps : eu tenho o código feito em 100 linhas com comentários minimalistas, por isso tenta que vais ver que é simples


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

não ... é comente um número aleatório de trocas a serem efectuadas. nada mais que um ciclo de 0 a Naleatório

não sei onde foste tirar a ideia de gerar N matrizes, mas é tudo feito numa única matriz !!!!

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
MKaks

Ou seja, se efectuo uma daquelas trocas (linhas, colunas diagonais, etc) ou se as faço todas, e várias vezes, é isso?

Editado por MKaks

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

para te simplificar a vida:

- efectua N1 trocas do primeiro tipo (troca de linha dentro de um bloco de 3 linhas)

- efectua N2 trocas do segundo tipo (troca de colunas dentro de um bloco de 3 colunas)

- efectua N3 trocas do terceiro tipo (troca de dois blocos de linhas)

- efectua N4 tricas do quarto tipo (troca de dois blocos de colunas)

- efectua N5 trocas do quinto tipo (transposta pela diagonal principal)

- efectua N6 trocas do sexto tipo (transposta pela diagonal secundária)


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
MKaks

Bem tenho aqui o meu código mas gerou-me um sudoku inválido -.- e não percebo porquê...

#include <stdio.h>
int MatrizMae[9][9]={{6,8,2,9,4,7,5,1,3},{3,1,4,6,2,5,7,9,8},{9,7,5,8,3,1,4,6,2},{2,5,7,3,8,6,9,4,1},{1,4,6,7,9,2,3,8,5},{8,9,3,1,5,4,6,2,7},{7,6,9,2,1,3,8,5,4},{4,2,8,5,7,9,1,3,6},{5,3,1,4,6,8,2,7,9}};
void mostra(){
   int i,j;
   for(i=1;i<=19;i++){
    for(j=1;j<=19;j++){
	    if(i==1&&j==1)
		    printf("\xc9");
	    else if(i==1 && (j==7 || j==13))
		    printf("\xcb");
	    else if(i==1 && j==19)
		    printf("\xbb");
	    else if((i==7 || i==13) && j==1)
		    printf("\xcc");
	    else if((i==7 || i==13) && j==19)
		    printf("\xb9");
	    else if(i==19 && j==1)
		    printf("\xc8");
	    else if(i==19 && (j==7 || j==13))
		    printf("\xca");
	    else if(i==19 && j==19)
		    printf("\xbc");
	    else if((i==1 || i==7 || i==13 || i==19) && (j!=7 && j!=13))
		    printf("\xcd");
	    else if((i!=7 && i!=13) && (j==1 || j==7 || j==13 || j==19))
		    printf("\xba");
	    else if((i==7 && j==7) || (i==7 && j==13) || (i==13 && j==7) || (i==13 && j==13))
		    printf("\xce");
	    else if(i%2==0 && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
		    printf("\xb3");
	    else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && j%2==0)
		    printf("\xc4");
	    else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
		    printf("\xc5");
	    else if(MatrizMae[i/2-1][j/2-1]==0)
		    printf(" ");
	    else
		    printf("%d",MatrizMae[i/2-1][j/2-1]);
    }
    printf("\n");
   }
}
int aleatorio(){
   int min = 1;
   int max = 9;
   return  min + rand() % (max - min + 1);
}
int aleatorioSwitch(){
   int min = 1;
   int max = 6;
   return  min + rand() % (max - min + 1);
}
int aleatorio3(){
   int min = 0;
   int max = 2;
   return  min + rand() % (max - min + 1);
}
void linha(){
   int k,i,j,aux;
   i=aleatorio();
   if(i<=3){
    do{
	    j=aleatorio();
    }while(j==i||j>3);
   }else if(i<=6){
    do{
	    j=aleatorio();
    }while(j==i||(j<=3||j>=7));
   }
   else if(i<=9){
    do{
	    j=aleatorio();
    }while(j==i||j<7);
   }

   for(k=1;k<=9;k++){
    aux=MatrizMae[i][k];
    MatrizMae[j][k]=MatrizMae[i][k];
    MatrizMae[j][k]=aux;
   }
}
void coluna(){
   int k,i,j,aux;
   i=aleatorio();
   if(i<=3){
    do{
	    j=aleatorio();
    }while(j==i||j>3);
   }
   else if(i<=6){
    do{
	    j=aleatorio();
    }while(j==i||(j<=3||j>=7));
   }
   else if(i<=9){
    do{
	    j=aleatorio();
    }while(j==i||j<7);
   }
   for(k=1;k<=9;k++){
    aux=MatrizMae[k][i];
    MatrizMae[k][j]=MatrizMae[k][i];
    MatrizMae[k][j]=aux;
   }
}
void BlocoLinhas(){
   int h,k,i,j,aux;
   i=aleatorio3()*3;
   do{
    j=aleatorio3()*3;
   }while(j==i);
   for(h=0;h<3;h++){
    for(k=0;k<9;k++){
	    aux=MatrizMae[i+h][k];
	    MatrizMae[i+h][k]=MatrizMae[j+h][k];
	    MatrizMae[j+h][k]=aux;
    }
   }
}
void BlocoColunas(){
   int h,k,i,j,aux;
   i=aleatorio3()*3;
   do{
    j=aleatorio3()*3;
   }while(j==i);
   for(h=0;h<3;h++){
    for(k=0;k<9;k++){
	    aux=MatrizMae[k][i+h];
	    MatrizMae[k][i+h]=MatrizMae[k][j+h];
	    MatrizMae[k][j+h]=aux;
    }
   }
}
void DiagonalPrincipal(){
   int i,j,aux;
   for(i=0;i<9;i++){
    for(j=0;j<=i;j++){
	    aux=MatrizMae[i][j];
	    MatrizMae[i][j]=MatrizMae[j][i];
	    MatrizMae[j][i]=aux;
    }
   }
}
void DiagonalSecundaria(){
   int i,j,aux;
   for(i=0;i<9;i++){
    for(j=0;j<=(8-i);j++){
	    aux=MatrizMae[i][j];
	    MatrizMae[i][j]=MatrizMae[8-j][8-i];
	    MatrizMae[8-j][8-i]=aux;
    }
   }
}
void CriaNovaMatriz(){
   int i,a,x;
   x=aleatorio();
   for(i=0;i<=x;i++){
    a=aleatorioSwitch();
    switch(a){
	    case 1: linha();
			    break;
	    case 2: coluna();
			    break;
	    case 3: BlocoLinhas();
			    break;
	    case 4: BlocoColunas();
			    break;
	    case 5: DiagonalPrincipal();
			    break;
	    case 6: DiagonalSecundaria();
			    break;
    }
   }
}
int main(){
   mostra();
   CriaNovaMatriz();
   mostra();
   return 0;
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

o teu código é muto confuso, e tens métodos que mais tarde (quando estiveres mais habituado) verás que estas a dar uma volta tremenda para fazer algo simples.

no entanto (muito por alto) não vi nada de groceiro.

testa uma das 6 funções de cada vez

força a chamada da função a testar uma única vez e verifica se está realmente correcto ...

para dizer mais teria de olhar bastante tempo para o teu código, e infelizmente agora não posso.

no entanto estás no bom caminho.

quando tiveres isso a funcionar, apresento-te o meu código


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
MKaks

Já encontrei uns erros e consegui corrigi-los, mas tentei fazer 1000 ou 10'000 sudokus e só um ou dois é que são válidos, apesar de as minhas funções estarem a efectuar as trocas correctamente... O que estarei a fazer mal?

#include <stdio.h>
int MatrizMae[9][9]={{6,8,2,9,4,7,5,1,3},{3,1,4,6,2,5,7,9,8},{9,7,5,8,3,1,4,6,2},{2,5,7,3,8,6,9,4,1},{1,4,6,7,9,2,3,8,5},{8,9,3,1,5,4,6,2,7},{7,6,9,2,1,3,8,5,4},{4,2,8,5,7,9,1,3,6},{5,3,1,4,6,8,2,7,9}};
void mostra(){
   int i,j;
   for(i=1;i<=19;i++){
    for(j=1;j<=19;j++){
	    if(i==1&&j==1)
		    printf("\xc9");
	    else if(i==1 && (j==7 || j==13))
		    printf("\xcb");
	    else if(i==1 && j==19)
		    printf("\xbb");
	    else if((i==7 || i==13) && j==1)
		    printf("\xcc");
	    else if((i==7 || i==13) && j==19)
		    printf("\xb9");
	    else if(i==19 && j==1)
		    printf("\xc8");
	    else if(i==19 && (j==7 || j==13))
		    printf("\xca");
	    else if(i==19 && j==19)
		    printf("\xbc");
	    else if((i==1 || i==7 || i==13 || i==19) && (j!=7 && j!=13))
		    printf("\xcd");
	    else if((i!=7 && i!=13) && (j==1 || j==7 || j==13 || j==19))
		    printf("\xba");
	    else if((i==7 && j==7) || (i==7 && j==13) || (i==13 && j==7) || (i==13 && j==13))
		    printf("\xce");
	    else if(i%2==0 && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
		    printf("\xb3");
	    else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && j%2==0)
		    printf("\xc4");
	    else if((i==3 || i==5 || i==9 || i==11 || i==15 || i==17) && (j==3 || j==5 || j==9 || j==11 || j==15 || j==17))
		    printf("\xc5");
	    else if(MatrizMae[i/2-1][j/2-1]==0)
		    printf(" ");
	    else
		    printf("%d",MatrizMae[i/2-1][j/2-1]);
    }
    printf("\n");
   }
}
int aleatorio(){
   int min = 1;
   int max = 9;
   return  min + rand() % (max - min + 1);
}
int aleatorioSwitch(){
   int min = 1;
   int max = 6;
   return  min + rand() % (max - min + 1);
}
int aleatorio3(){
   int min = 0;
   int max = 2;
   return  min + rand() % (max - min + 1);
}
void linha(){
   int k,i,j,aux;
   i=aleatorio()-1;
   if(i<3){
    do{
	    j=aleatorio()-1;
    }while(j==i||j>=3);
   }else if(i<6){
    do{
	    j=aleatorio()-1;
    }while(j==i||(j<3||j>=7));
   }
   else if(i<9){
    do{
	    j=aleatorio()-1;
    }while(j==i||j<6);
   }
   for(k=0;k<9;k++){
    aux=MatrizMae[i][k];
    MatrizMae[i][k]=MatrizMae[j][k];
    MatrizMae[j][k]=aux;
   }
}
void coluna(){
   int k,i,j,aux;
   i=aleatorio()-1;
   if(i<3){
    do{
	    j=aleatorio()-1;
    }while(j==i||j>=3);
   }else if(i<6){
    do{
	    j=aleatorio()-1;
    }while(j==i||(j<3||j>=7));
   }
   else if(i<9){
    do{
	    j=aleatorio()-1;
    }while(j==i||j<6);
   }
   for(k=0;k<9;k++){
    aux=MatrizMae[k][i];
    MatrizMae[k][i]=MatrizMae[k][j];
    MatrizMae[k][j]=aux;
   }
}
void BlocoLinhas(){
   int h,k,i,j,aux;
   i=aleatorio3()*3;
   do{
    j=aleatorio3()*3;
   }while(j==i);
   for(h=0;h<3;h++){
    for(k=0;k<9;k++){
	    aux=MatrizMae[i+h][k];
	    MatrizMae[i+h][k]=MatrizMae[j+h][k];
	    MatrizMae[j+h][k]=aux;
    }
   }
}
void BlocoColunas(){
   int h,k,i,j,aux;
   i=aleatorio3()*3;
   do{
    j=aleatorio3()*3;
   }while(j==i);
   for(h=0;h<3;h++){
    for(k=0;k<9;k++){
	    aux=MatrizMae[k][i+h];
	    MatrizMae[k][i+h]=MatrizMae[k][j+h];
	    MatrizMae[k][j+h]=aux;
    }
   }
}
void DiagonalPrincipal(){
   int i,j,aux;
   for(i=0;i<9;i++){
    for(j=0;j<i;j++){
	    aux=MatrizMae[i][j];
	    MatrizMae[i][j]=MatrizMae[j][i];
	    MatrizMae[j][i]=aux;
    }
   }
}
void DiagonalSecundaria(){
   int i,j,aux;
   for(i=0;i<9;i++){
    for(j=0;j<=(8-i);j++){
	    aux=MatrizMae[i][j];
	    MatrizMae[i][j]=MatrizMae[8-j][8-i];
	    MatrizMae[8-j][8-i]=aux;
    }
   }
}
void CriaNovaMatriz(){
   int i,a,x;
   x=aleatorio();
   for(i=0;i<x;i++){
    a=aleatorioSwitch();
    switch(a){
	    case 1: linha();
			    break;
	    case 2: coluna();
			    break;
	    case 3: BlocoLinhas();
			    break;
	    case 4: BlocoColunas();
			    break;
	    case 5: DiagonalPrincipal();
			    break;
	    case 6: DiagonalSecundaria();
			    break;
    }
   }
}
int Verifica(){
   int num,k,m,i,j,contLinha,contColuna,contBloco;
   for(num=1;num<=9;num++){
    for(i=0;i<9;i++){
	    contLinha=0;
	    contColuna=0;
	    for(j=0;j<9;j++){
		    if(MatrizMae[i][j]==num)
			    contLinha++;
		    if(MatrizMae[j][i]==num)
			    contColuna++;
	    }
	    if(contLinha!=1)
		    return 1;
	    if(contColuna!=1)
		    return 1;
    }
    for(i=0;i<3;i++){
	    for(j=0;j<3;j++){
		    contBloco=0;
		    for(k=0;k<3;k++){
			    for(m=0;m<3;m++){
				    if(MatrizMae[i*3+k][j*3+m]==num)
					    contBloco++;
			    }
		    }
		    if(contBloco!=1)
			    return 1;
	    }
    }
   }
   return 0;
}
int main(){
   int i,a=0;
   for(i=0;i<10000;i++){
    CriaNovaMatriz();
    if(Verifica()==1)
	    a++;
   }
   printf("%d errados\n",a);
   //mostra();
   /*do{
    CriaNovaMatriz();
   }while(Verifica()==1*/
   //mostra();
   return 0;
}

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
djthyrax

Não conheço esse método de gerar sudokus... Onde viste isso HappyHippyHippo?


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
MKaks

Entretanto alterei o meu main para alterar sempre o tabuleiro inicial, dando menos puzzles errados. Podes-me explicar qual é a lógica por trás do algoritmo?Gostava de perceber porque não dá sempre puzzles certos, ou se é suposto não dar sempre certo.

int main(){

   int i,a=0;
   memcpy(BackUp,MatrizMae,sizeof(int)*9*9);
   srand(time(0));
   for(i=0;i<200;i++){
    memcpy(MatrizMae,BackUp,sizeof(int)*9*9);
    CriaNovaMatriz();
    if(Verifica()==1)
	    a++;
    else mostra();
   }
   printf("%d errados\n",a);

   /*mostra();
   do{
    CriaNovaMatriz();
   }while(Verifica()==1);
   mostra();*/
   return 0;
}

Obrigado por toda a ajuda :)

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

a razão porque tens imensos erros é simples : estás a construir matrizes a partir de uma matriz errada

agora o erro inicial está aqui:

if(i<3){
 do{
   j=aleatorio()-1;         // j = valor de 0-8
 }while(j==i||j>=3);        // valores permitidos : 0, 1 e 2 e diferente de i
}else if(i<6){
 do{
   j=aleatorio()-1;         // j = valor de 0-8
 }while(j==i||(j<3||j>=7)); // valores permitidos : 3, 4, 5 e 6 e diferente de i
}else if(i<9){
 do{
   j=aleatorio()-1;         // j = valor de 0-8
 }while(j==i||j<6);         // valores permitidos : 6, 7 e 8 e diferente de i
}

Não conheço esse método de gerar sudokus... Onde viste isso HappyHippyHippo?

veio do modelo de simplificação usado para calcular o número mínimo necessário de pistas que devem existir

https://www.youtube.com/embed/MlyTq-xVkQE?feature=oembed

Editado por HappyHippyHippo

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
djthyrax

Não conhecia HappyHippyHippo, bom link.

MKaks, depois de apresentares esse trabalho podias era por aí o código completo, sempre podia ajudar alguém. :thumbsup:


Não peças ajuda por PM! A tua dúvida vai ter menos atenção do que se for postada na secção correcta do fórum!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

e agora só para desmotivar :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 9

void print_sudoku(char sudoku[size][size]) {
char i, j;

/* print board */
for (i = 0; i < SIZE; i++) {
	if (!(i % 3))
		printf("+------+------+------+\n");

	for (j = 0; j < SIZE; j++) {
		if (!(j % 3))
			printf("|");
		printf("%2d", sudoku[i][j]);
	}
	printf("|\n");
}
printf("+------+------+------+\n");
}

void swap(char (*sudoku)[size][size], char x1, char y1, char x2, char y2) {
char aux;

/* swap */
aux = (*sudoku)[x1][y1];
(*sudoku)[x1][y1] = (*sudoku)[x2][y2];
(*sudoku)[x2][y2] = aux;
}

int main(int argc, char ** argv) {
char sudoku[size][size] = {{1, 2, 3, 4, 5, 6, 7, 8, 9},
                           {7, 8, 9, 1, 2, 3, 4, 5, 6},
                           {4, 5, 6, 7, 8, 9, 1, 2, 3},
                           {9, 1, 2, 3, 4, 5, 6, 7, 8},
                           {6, 7, 8, 9, 1, 2, 3, 4, 5},
                           {3, 4, 5, 6, 7, 8, 9, 1, 2},
                           {8, 9, 1, 2, 3, 4, 5, 6, 7},
                           {5, 6, 7, 8, 9, 1, 2, 3, 4},
                           {2, 3, 4, 5, 6, 7, 8, 9, 1}};
char i, j, k;
unsigned int iter, steps, select, type, block, swap1, swap2;

/* start random number generation */
srand(time(NULL));

/* select a number from 1000 to 1000000 */
steps = (rand() % (1000000 - 1000)) + 1000;

/* swap cycle */
for (iter = 0; iter < steps; iter++) {
	select = rand();

	/* select action parameters from the random number */
	type  = ( select        & 0xff) % 6;
	block = ((select >>  8) & 0xff) % 3;
	swap1 = ((select >> 16) & 0xff) % 3;
	swap2 = ((select >> 24) & 0xff) % 3;
	swap2 = swap2 == swap1 ? (swap2 + 1) % 3 : swap2;

	/* check for swap type */
	switch (type) {
		case 0:
			/* column swap cycle step */
			for (j = 0; j < SIZE; j++)
				swap(&sudoku, j, block * 3 + swap1, j, block * 3 + swap2);
			break;
		case 1:
			/* line swap cycle step */
			for (j = 0; j < SIZE; j++)
				swap(&sudoku, block * 3 + swap1, j, block * 3 + swap2, j);
			break;
		case 2:
			/* column block swap cycle step */
			for (k = 0; k < 3; k++)
				for (j = 0; j < SIZE; j++)
					swap(&sudoku, j, swap1 * 3 + k, j, swap2 * 3 + k);
			break;
		case 3:
			/* line block swap cycle step */
			for (k = 0; k < 3; k++)
				for (j = 0; j < SIZE; j++)
					swap(&sudoku, swap1 * 3 + k, j, swap2 * 3 + k, j);
			break;
		case 4:
			/* major diagonal swap cycle step */
			for (k = 1; k < SIZE; k++)
				for (j = 0; j < k; j++)
					swap(&sudoku, k, j, j, k);
			break;
		case 5:
			/* minor diagonal swap cycle step */
			for (k = 0; k < SIZE - 1; k++)
				for (j = 0; j < SIZE - k - 1; j++)
					swap(&sudoku, k, j, SIZE - j - 1, SIZE - k - 1);
			break;
	}
}

print_sudoku(sudoku);

return 0;
}

  • Voto 1

IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

@HappyHippyHippo, podes-me explicar melhor como é que funcionam os bitwise aqui? Já agora, o que são as transpostas que referes no pseudocódigo?

block = ((select >> 8) & 0xff) % 3;

swap1 = ((select >> 16) & 0xff) % 3;

swap2 = ((select >> 24) & 0xff) % 3;

swap2 = swap2 == swap1 ? (swap2 + 1) % 3 : swap2;

Editado por polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

@HappyHippyHippo, podes-me explicar melhor como é que funcionam os bitwise aqui?

block = ((select >> 8) & 0xff) % 3;

swap1 = ((select >> 16) & 0xff) % 3;

swap2 = ((select >> 24) & 0xff) % 3;

swap2 = swap2 == swap1 ? (swap2 + 1) % 3 : swap2;

haha estou a ver que gostaste :D

ora bem, o pretendido é ter 4 números aleatórios de um único número aleatório (não vou entrar no pormenor que é um pseudo-aleatório) ...

primeiro é necessário verificar qual os limites para cada valor que quero:

type - de 0 a 5

block - de 0 a 2

swap1 - de 0 a 2

swap2 - de 0 a 2

agora, se eu "partir" um número de 32 bits em 4 partes iguais, tenho 8 bits em cada parte, que me dá valores de 0 a 256 (o que é mais do que suficiente !!!)

então, num primeiro passo, estou a mover os bits para a direita, visualmente o que estou a fazer é:

aleatorio - AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
type      - AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD  select
block     - ........AAAAAAAABBBBBBBBCCCCCCCC (select >> 8)
swap1     - ................AAAAAAAABBBBBBBB (select >> 16)
swap2     - ........................AAAAAAAA (select >> 24)

depois estou a seleccionar somente os 8 bits menos significativos de cada um dos valores, visualmente:

type      - ........................DDDDDDDD ( select       ) & 0xff
block     - ........................CCCCCCCC ((select >> 8) ) & 0xff
swap1     - ........................BBBBBBBB ((select >> 16)) & 0xff
swap2     - ........................AAAAAAAA ((select >> 24)) & 0xff

de seguida, como tenho limites que pretendo que os número não ultrapassem, descubro o resto da divisão pelo limite superior :

type      - DDDDDDDD % 6 // (( select       ) & 0xff) % 6 >> resulta num número de 0 a 5
block     - CCCCCCCC % 3 // (((select >> 8) ) & 0xff) % 3 >> resulta num número de 0 a 2
swap1     - BBBBBBBB % 3 // (((select >> 16)) & 0xff) % 3 >> resulta num número de 0 a 2
swap2     - AAAAAAAA % 3 // (((select >> 24)) & 0xff) % 3 >> resulta num número de 0 a 2

no final, pretendo que o swap1 seja diferente de swap2.

para isso basta somar o valor unitário e voltar a calcular o resto da divisão inteira.

isto porque, caso swap1 for igual a swap2, desta forma serão estes os casos que resultam:

swap1 | swap2
0    |  1
1    |  2
2    |  0

logo garanto que swap1 é diferente de swap 2:

swap2 =
       swap2 == swap1 ?  // se swap2 for igual a swap1
       (swap2 + 1) % 3 : // aplico a fórmula descrita
       swap2;            // fica tudo na mesma


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

haha estou a ver que gostaste :D

ora bem, o pretendido é ter 4 números aleatórios de um único número aleatório (não vou entrar no pormenor que é um pseudo-aleatório) ...

primeiro é necessário verificar qual os limites para cada valor que quero:

type - de 0 a 5

block - de 0 a 2

swap1 - de 0 a 2

swap2 - de 0 a 2

agora, se eu "partir" um número de 32 bits em 4 partes iguais, tenho 8 bits em cada parte, que me dá valores de 0 a 256 (o que é mais do que suficiente !!!)

então, num primeiro passo, estou a mover os bits para a direita, visualmente o que estou a fazer é:

aleatorio - AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD
type - AAAAAAAABBBBBBBBCCCCCCCCDDDDDDDD select
block - ........AAAAAAAABBBBBBBBCCCCCCCC (select >> 8)
swap1 - ................AAAAAAAABBBBBBBB (select >> 16)
swap2 - ........................AAAAAAAA (select >> 24)

depois estou a seleccionar somente os 8 bits menos significativos de cada um dos valores, visualmente:

type - ........................DDDDDDDD ( select ) & 0xff
block - ........................CCCCCCCC ((select >> 8) ) & 0xff
swap1 - ........................BBBBBBBB ((select >> 16)) & 0xff
swap2 - ........................AAAAAAAA ((select >> 24)) & 0xff

de seguida, como tenho limites que pretendo que os número não ultrapassem, descubro o resto da divisão pelo limite superior :

type - DDDDDDDD % 6 // (( select ) & 0xff) % 6 >> resulta num número de 0 a 5
block - CCCCCCCC % 3 // (((select >> 8) ) & 0xff) % 3 >> resulta num número de 0 a 2
swap1 - BBBBBBBB % 3 // (((select >> 16)) & 0xff) % 3 >> resulta num número de 0 a 2
swap2 - AAAAAAAA % 3 // (((select >> 24)) & 0xff) % 3 >> resulta num número de 0 a 2

no final, pretendo que o swap1 seja diferente de swap2.

para isso basta somar o valor unitário e voltar a calcular o resto da divisão inteira.

isto porque, caso swap1 for igual a swap2, desta forma serão estes os casos que resultam:

swap1 | swap2
0 | 1
1 | 2
2 | 0

logo garanto que swap1 é diferente de swap 2:

swap2 =
	swap2 == swap1 ?  // se swap2 for igual a swap1
	(swap2 + 1) % 3 : // aplico a fórmula descrita
	swap2;			// fica tudo na mesma

Por acaso vi o tópico e achei interessante :thumbsup:

Eu se fosse há uns tempos atrás não ia entender nada, mas surpresa a minha que entendi :D , eu vi o vídeo que colocaste, também ajudou a perceber a parte não relativa aos bitwise xD ...

Obrigado! E quando há questão das transportas?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

Já agora que também fiz um programita para gerar uma solução sudoku.. Queria fazer um programa que resolvesse um sudoku, dado alguns valores como o que costumamos ver nos jornais e revistas.. Mas não quero fazer uma coisa lenta que demore anos para nos imprimir a solução, alguém me podia indicar que passos é que devo seguir para resolver o sudoku?

A minha solução passava por guardar todos os números possíveis de colocar em cada "casa" vazia e depois verificar que números já podia ter a certeza de fazerem parte de x casa mediante essa informação.. e depois continuar a eliminar números até chegar há solução possível.. Mas penso que esta não seja a melhor abordagem, seria lento.

Já agora, @Happy,podes-me explicar porque temos que colocar o ponteiro de sudoku entre () ? Porque não funciona simplesmente *sudoku[MAX][MAX] ?

Editado por polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
pmg

... porque temos que colocar o ponteiro de sudoku entre () ? Porque não funciona simplesmente *sudoku[MAX][MAX] ?

Acho que te estas a referir ao codigo

void swap(char (*sudoku)[size][size], char x1, char y1, char x2, char y2) {
       char aux;

       /* swap */
       aux = (*sudoku)[x1][y1];
       (*sudoku)[x1][y1] = (*sudoku)[x2][y2];
       (*sudoku)[x2][y2] = aux;
}

Naquele codigo, sudoku é um ponteiro para uma matriz de caracteres

Para aceder ao conteudo apontado por um ponteiro é necessario o asterisco (ou "->" quando se trata de estruturas).

A expressao *sudoku[4][2] "aplica" primeiro o indexamento de arrays e o asterisco no fim ((* ( (sudoku[4]) [2]) )) o que é invalido.

A expressao (*sudoku)[4][2] "aplica" primeiro o asterisco.


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
polska

Acho que te estas a referir ao codigo

void swap(char (*sudoku)[size][size], char x1, char y1, char x2, char y2) {
	char aux;

	/* swap */
	aux = (*sudoku)[x1][y1];
	(*sudoku)[x1][y1] = (*sudoku)[x2][y2];
	(*sudoku)[x2][y2] = aux;
}

Naquele codigo, sudoku é um ponteiro para uma matriz de caracteres

Para aceder ao conteudo apontado por um ponteiro é necessario o asterisco (ou "->" quando se trata de estruturas).

A expressao *sudoku[4][2] "aplica" primeiro o indexamento de arrays e o asterisco no fim ((* ( (sudoku[4]) [2]) )) o que é invalido.

A expressao (*sudoku)[4][2] "aplica" primeiro o asterisco.

Certo já entendi :)

Só mais uma pergunta, em caso de vector e não matrix isto já não é necessário certo?


Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
HappyHippyHippo

terá de ser sempre de ter em conta o tipo e valor de dados a serem enviados para a função.

eu enviei a referência da variável existente no main, logo necessito sempre de fazer essa brincadeira.


IRC : sim, é algo que ainda existe >> #p@p

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.