Diagonální sudoku II – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Diagonální sudoku II – C / C++ – Fórum – Programujte.comDiagonální sudoku II – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Epoxi
~ Anonymní uživatel
35 příspěvků
19. 10. 2013   #1
-
0
-

Zdravím, dokázal by mi nekdo optimalizovat kod?

/*
 *
 * Sudoku X solver v1.0
 * ====================
 *
 */

 /* Testoval jsem nasledujici sudoku :
  * 0 0 7 9 0 0 0 0 5    0 0 0 9 0 0 0 0 0    0 0 0 0 0 6 5 0 9    0 0 0 0 0 0 0 0 0   0 0 5 0 0 0 9 3 0
  * 0 2 5 3 0 0 0 0 7    8 0 0 0 0 0 3 0 4    0 0 1 0 0 0 0 0 0    0 0 1 0 0 0 0 0 0   0 0 7 8 0 0 1 0 0
  * 0 8 0 2 0 0 0 0 0    0 0 0 0 0 0 7 0 0    0 0 2 5 0 0 0 0 0    0 0 2 5 0 0 0 0 0   0 0 4 0 0 0 0 0 0
  * 0 0 0 0 0 0 6 0 0    1 7 0 4 0 0 5 0 0    0 0 4 0 0 0 8 0 1    0 0 4 0 0 0 8 0 1   0 0 0 6 0 4 3 7 0
  * 0 0 6 0 0 0 8 0 0    0 0 0 0 2 0 0 0 0    0 0 0 0 8 0 0 0 0    0 0 0 0 8 0 0 0 0   4 0 0 0 0 0 0 0 8
  * 0 0 9 0 0 0 0 0 0    0 0 6 0 0 1 0 4 3    7 0 8 0 0 0 9 0 0    7 0 8 0 0 0 9 0 0   0 3 1 7 0 2 0 0 0
  * 0 0 0 0 0 9 0 4 0    0 0 8 0 0 0 0 0 0    0 0 0 0 0 7 4 0 0    0 0 0 0 0 7 4 0 0   0 0 0 0 0 0 7 0 0
  * 6 0 0 0 0 3 1 9 0    5 0 3 0 0 0 0 0 2    0 0 0 0 0 0 2 0 0    0 0 0 0 0 0 2 0 0   0 0 2 0 0 9 6 0 0
  * 7 0 0 0 0 2 3 0 0    0 0 0 0 0 2 0 0 0    5 0 6 4 0 0 0 0 0    5 0 6 4 0 0 0 0 0   0 6 8 0 0 0 4 0 0
  */

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

#define MIN 3   /*Rozmery malych ctverecku*/

#define MAX 9   /*Rozmery sudoku*/

#define FALSE 0 /*hodnoty do return nebo do vysledku*/
#define TRUE 1

char sudoku[MAX][MAX]; /* sudoku */
long int citac;       /* citac */

/*------Funkce ktere kontroluji zadani atd.------*/
int zadej_zadani(void);
int zadej_radek(int radek);
int zkontroluj_vstupni_zadani(void);
int zkontroluj_vstupni_radky(void);
int zkontroluj_vstupni_radek(int radek);
int zkontroluj_vstupni_sloupce(void);
int zkontroluj_vstupni_sloupec(int sloupec);
int zkontroluj_vstupni_ctverecky(void);
int zkontroluj_vstupni_ctverecek(int ctverecek);
void transformuj_ctverecek(char buffer[], int ctverecek);
int zkontroluj_diagonalu(void);
int zkontroluj_vstupni_diagonalu(int i);
int zkontroluj_druhou_diagonalu(void);
int zkontroluj_druhou_vstupni_diagonalu(int i);

/*------Funkce pro reseni------*/
void vyres_sudoku(void);
int volne_pole_cislo(int cislo, int radek, int sloupec);
void transformuj_ctverecek_poli(char buffer[], int radek, int sloupec);
/*-------Ostatni-------*/
void zobraz_sudoku_cekani(void);
void zobraz_sudoku(void);
void obrazek(int cislo);
int hotove_sudoku(void);
void cekani(void);


int main(void)
{
	printf("\n******* SUDOKU *******\n\n");
	printf("Sudoku zobrazuje reseni krok po kroku.\n\n");
	printf("Zadej %d radku o %d cislech.\n", MAX, MAX);
	printf("Cisla mohou byt oddelena libovolnym znakem\n");
	printf("Zadej nulu pro prazdne pole.\n");
	printf("Pro ukonceni zadej pismeno Q.\n\n");
	while (zadej_zadani()) {
		citac = 0;
		vyres_sudoku();
		zobraz_sudoku();
		if (! hotove_sudoku()) printf("Neco je spatne\n");
		printf("Pocet testu: %ld\n\n", citac);
	}/*konec while*/
	printf("\n");
	return 0;
}

/*------Funkce pro reseni------*/

int zadej_zadani(void) /* Funkce pozada o zadani na kazdem radku 9 cisel */
{
	int radek;

	printf("Zadejte prosim zadani: \n");

	while (TRUE){
		for (radek = 0; radek < MAX; radek++){
			if (! zadej_radek(radek)) return (FALSE);
		}/*konec for*/
		printf("\n Problem sudoku: \n");
		zobraz_sudoku();
		if (zkontroluj_vstupni_zadani()) return(TRUE);
		else printf("\n");
	}/*konec while*/
}/*konec zadej_zadani*/

int zadej_radek(int radek) /*Do pole se zadavaji cisla od 0 do 9, nezalezi jestli jsou oddelena od sebe nebo ne. /
                           /*Pouze prvnich 9 cisel bude nacteno*/
                           /*Pouzil jsem fgets() s gets() to nemusi fungovat*/
 {
	int c, i;
	int sloupec = 0;
	int vysledek = TRUE;

	/*Nulovani pole*/
	for (i = 0; i < MAX; i++) {
		sudoku[radek][i] = 0;
	}/*konec for*/
	printf("radek %d : ", radek + 1);
	while(TRUE){
		c = getc(stdin);
		if (c == feof(stdin) || c == 0x0A) return vysledek;
		else if ((c == 'Q') || (c == 'q')) vysledek = FALSE;
		/*Prevede zadani do radku sudoku*/
		else if ((vysledek) && (sloupec < MAX) && (c >= '0') && (c <= '9')) {
            sudoku[radek][sloupec++] = c - 48;
		}/*konec if*/
	}/* konec while*/
}/*konec zadej_radek*/

int zkontroluj_vstupni_zadani(void) /*Jednotlive funkce zkontroluji, jestli nebylo spatne zadano zadani*/
{                                    /*Tim se vyhneme dalsim problemum*/
	int vysledek = TRUE;

	if (! zkontroluj_vstupni_radky())         vysledek = FALSE;
	if (! zkontroluj_vstupni_sloupce())       vysledek = FALSE;
	if (! zkontroluj_vstupni_ctverecky())     vysledek = FALSE;
    if (! zkontroluj_diagonalu())             vysledek = FALSE;
    if (! zkontroluj_druhou_diagonalu())      vysledek = FALSE;

	return vysledek;
}/*konec zkontroluj_vstupni_zadani*/

int zkontroluj_diagonalu(void) /*Zkontroluje, jestli nejsou dve stejna cisla na digonale*/
{                              /*pomoci nasledujici funkce*/
	int i;
	int vysledek = TRUE;

		if (! zkontroluj_vstupni_diagonalu(i)) vysledek = FALSE;

	return vysledek;
}

int zkontroluj_vstupni_diagonalu(int i)
{
	int j, k , l;

	for (i = 0; i < MAX - 1; i++) {
		if ( sudoku[i][i] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (sudoku[j][j] == sudoku[i][i]) {
				printf("chyba v digonale na radku %d a %d: stejna cisla\n", i + 1, j + 1);
             return FALSE;
			}/*konec if*/
		}/*konec for j*/
	}/*konec for i*/
	return TRUE;
}/*konec zkontroluj_vstupni_diagonalu*/

int zkontroluj_druhou_diagonalu(void) /*Zkontroluje, jestli nejsou dve stejna cisla na digonale*/
{                                     /*pomoci nasledujici funkce*/
	int i;
	int vysledek = TRUE;

		if (! zkontroluj_druhou_vstupni_diagonalu(i)) vysledek = FALSE;

	return vysledek;
}

int zkontroluj_druhou_vstupni_diagonalu(int i)
{
	int j, k , l, m , n;
	for (i = 0; i < MAX - 1; i++) {
       k = 8;
       m = 0;
	   m = k - i;
		if ( sudoku[i][m] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
		    n = 8;
		    l = 0;
		    l = n - j;
			if (sudoku[j][l] == sudoku[i][m]) {
				printf("Chyba v diagonale na radku %d a %d: stejna cisla\n", i + 1, j + 1);
             return FALSE;
			}/*konec if*/
		}/*konec for j*/
	}/*konec for i*/
	return TRUE;
}/*konec zkontroluj_druhou_vstupni_diagonalu*/

int zkontroluj_vstupni_radky(void) /*Zkontroluje, jestli nejsou dve stejna cisla na radkach*/
{
	int radek;
	int vysledek = TRUE;
	for (radek = 0; radek < MAX; radek++) {
		if (! zkontroluj_vstupni_radek(radek)) vysledek = FALSE;
	}/*konec for*/
	return vysledek;
}/*konec zkontroluj_vstupni_radky*/

int zkontroluj_vstupni_radek(int radek) /*Zkontroluje, jestli nejsou dve stejna cisla na radkach */
{
	int i, j;

	for (i = 0; i < MAX - 1; i++) {
		if ( sudoku[radek][i] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (sudoku[radek][i] == sudoku[radek][j]) {
				printf("Chyba radku %d: stejna cisla\n", radek + 1);
				return FALSE;
			}/*konec if*/
		}/*konec for j*/
	}/*konec for i*/
	return TRUE;
}/* konec zkontroluj_vstupni_radek*/

int zkontroluj_vstupni_sloupce(void) /*Zkontroluje, jestli nejsou stejna cisla ve sloupcich*/
{
	int sloupec;
	int vysledek = TRUE;
	for (sloupec = 0; sloupec < MAX; sloupec++) {
		if (! zkontroluj_vstupni_sloupec(sloupec)) vysledek = FALSE;
	}/*konec for*/
	return vysledek;
}/*konec zkontroluj_vstupni_sloupce*/

int zkontroluj_vstupni_sloupec(int sloupec) /*Zkontroluje, jestli nejsou stejna cisla ve sloupci*/
{
	int i, j;
	for (i = 0; i < MAX - 1; i++) {
		if ( sudoku[i][sloupec] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (sudoku[i][sloupec] == sudoku[j][sloupec]) {
				printf("Chyba sloupec %d: stejna cisla\n", sloupec + 1);
				return FALSE;
			}/*konec if*/
		}/*konec for j*/
	}/*konec for i*/
	return TRUE;
}/*konec zkontroluj_vstupni_sloupec*/


int zkontroluj_vstupni_ctverecky(void) /*Zkontroluje, jestli nejsou stejna ciala v malych ctvercich (3x3)*/
{
	int ctverecek;
	int vysledek = TRUE;
	for (ctverecek = 0; ctverecek < MAX; ctverecek++) {
		if (! zkontroluj_vstupni_ctverecek(ctverecek)) vysledek = FALSE;
	}/*konec for*/
	return vysledek;
}/*konec zkontroluj_vstupni_ctverecky*/

int zkontroluj_vstupni_ctverecek(int ctverecek) /*Zkontroluje, jestli nejsou stejna cisla v malem cverci (3x3)*/
{
	char buffer[MAX + 10];
	int i, j;

	transformuj_ctverecek(buffer, ctverecek);

	for (i = 0; i < MAX - 1; i++) {
		if (buffer[i] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (buffer[i] == buffer[j]) {
				printf("Chyba v 3x3 %d: stejna cisla\n", ctverecek + 1);
				return FALSE;
			}/*konec if*/
		}/*konec for j*/
	}/*konec for  */
	return TRUE;
}/*konec zkontroluj_vstupni_ctverecek*/

void transformuj_ctverecek(char buffer[], int ctverecek) /*Prevede ctverec 3x3 do 1-dimenzionalniho pole*/
{
	int i, j, k, l, m;

	k = (((ctverecek) % MIN) * MIN);
	l = (((ctverecek + MIN) / MIN) * MIN) - MIN;
	m = 0;
	for (j = l; j < l + MIN; j++) {
		for (i = k; i < k + MIN; i++) {
			buffer[m++] = sudoku[j][i];
		}/*konec for i*/
	}/*konec for j*/
}/*konec transformuj_ctverecek*/

/*------Funkce pro reseni------*/

void vyres_sudoku(void) /*rekurzivni funkce*/
{
	int radek, sloupec, cislo, buffer_cislo;

	for (radek = 0; radek < MAX; radek++) {
		for (sloupec = 0; sloupec < MAX; sloupec++) {
			if (sudoku[radek][sloupec]) continue;
			for (cislo = 1; cislo <= MAX; cislo++) {
				if (! volne_pole_cislo(cislo, radek, sloupec)) continue;
				buffer_cislo = sudoku[radek][sloupec];
				sudoku[radek][sloupec] = cislo;
				citac++;
				/*zobraz_sudoku_cekani();*/
				vyres_sudoku();
				if (hotove_sudoku()) return;
                sudoku[radek][sloupec] = buffer_cislo;
			}/*konec for cislo*/
			return;
		}/*konec for sloupec*/
	}/*konec for radek*/
	return;
}/*konec vyres_sudoku */

int volne_pole_cislo(int cislo, int radek, int sloupec) /*Funkce testuje, jestli cislo uz je v poli, radku, 3x3 nebo diagonale*/
{                                                       /* V jednotlivych pripadech, jestli je uz cislo pouzito, vraci FALSE */
	char buffer[MAX + 10];
	int i, j, k, l, m, n;


	for (i = 0; i < MAX; i++) if (sudoku[radek][i] == cislo)   return(FALSE);
	for (i = 0; i < MAX; i++) if (sudoku[i][sloupec] == cislo) return(FALSE);

	for (i = 0; i < MAX - 1; i++) {
		if ( sudoku[i][i] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (sudoku[j][j] == sudoku[i][i]) return (FALSE);
        }
    }

	for (i = 0; i < MAX - 1; i++) {
       k = 8;
       m = 0;
	   m = k - i;
		if ( sudoku[i][m] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
		    n = 8;
		    l = 0;
		    l = n - j;
			if (sudoku[j][l] == sudoku[i][m]) return (FALSE);
        }
    }

	transformuj_ctverecek_poli(buffer, radek, sloupec);
	for (i = 0; i < MAX; i++) if (buffer[i] == cislo) return (FALSE);
	/* Jestli se mozne dane cislo doplnit podle splnenych podminek vrati funkce TRUE*/
	return(TRUE);
}/*konec volne_pole_cislo*/

void transformuj_ctverecek_poli(char buffer[], int radek, int sloupec) /*Transformuje 3x3 ctverec do 1-dimenzionalniho pole*/
{
	int i, j, k;

	while ((radek % MIN) != 0) radek--;
	while ((sloupec % MIN) != 0) sloupec--;
	k = 0;
	for (j = radek; j < radek + MIN; j++) {
		for (i = sloupec; i < sloupec + MIN; i++) {
			buffer[++k] = sudoku[j][i];
		}/*konec for i*/
	}/*konec for j*/
}/*konec transformuj_ctverecek_poli*/

/*-------Ostatni-------*/
void zobraz_sudoku_cekani(void) /*Zobrazi sudoku a bude cekat na stisknuti klavesy*/
{
	zobraz_sudoku();
	printf("%ld, zadejte klavesu pro pokracovani", citac);
	cekani();
}/*konec zobraz_sudoku_cekani */

void zobraz_sudoku(void) /*zobraz sudoku*/
{
	int radek, sloupec;
	for (radek = 0; radek < MAX; radek++) {
		for (sloupec = 0; sloupec < MAX; sloupec++) {
			printf(" %1d ", sudoku[radek][sloupec]);
			if ( ((sloupec % MIN) == MIN - 1) && (sloupec < MAX - 1) ) {
				printf(" | ");
			}
		}/*konec for sloupec*/
		printf("\n");
		if ( ((radek % MIN) == MIN - 1) && (radek < MAX-1) ) {
			obrazek(33);
		}
	}/*konec for radek*/
	printf("\n");
}/*konec zobraz_sudoku*/

void obrazek(int cislo) /*zobrazuje dany znak, aby byl vysledek prehlednejsi*/
{
	int i;
	for (i = 1; i <= cislo; i++) {
		printf("-");
	}
	printf("\n");
}/*konec obrazek*/

int hotove_sudoku(void)                 /*zkontroluje, jestli je sudoku hotove(plne)*/
{                                       /*jestli ano vraci TRUE, jestli ne vraci FALSE*/
	int radek, sloupec;                 /*zacina od konce*/
	for (radek = MAX - 1; radek >= 0; radek--) {
		for (sloupec = MAX - 1; sloupec >= 0; sloupec--) {
			if (sudoku[radek][sloupec] == 0 ) {
				return FALSE;
			}
		}/*konec for sloupec*/
	}/*konec for radek*/
	return TRUE;
}/*konec hotove_sudoku*/

void cekani(void) /*Ceka na stisk klavesy enter*/
{
	char c;
	while(TRUE){
		c = fgetc(stdin);
		if (c == feof(stdin) || c == 0x0A) return;
	}/*konec while*/
}/*konec funkce cekani*/


Posílal jsem kód do školy, protože nemám tušení proč mi to funguje jenom pro některé řešení. Bylo mi nápsáno : nemám používat globální proměnné nejsou zde třeba. To je ok. Pak si mám rozdělit funkce a main() zvlášt. Třetí bod a to bude asi kámen úrazu tohoto programu, že nekteré proměnné nemusí fungovat správně.  

int volne_pole_cislo(int cislo, int radek, int sloupec) /*Funkce testuje, jestli cislo uz je v poli, radku, 3x3 nebo diagonale*/
{                                                       /* V jednotlivych pripadech, jestli je uz cislo pouzito, vraci FALSE */
	char buffer[MAX + 10];
	int i, j, k, l, m, n;


	for (i = 0; i < MAX; i++) if (sudoku[radek][i] == cislo)   return(FALSE);
	for (i = 0; i < MAX; i++) if (sudoku[i][sloupec] == cislo) return(FALSE);

	for (i = 0; i < MAX - 1; i++) {
		if ( sudoku[i][i] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
			if (sudoku[j][j] == sudoku[i][i]) return (FALSE);
        }
    }

	for (i = 0; i < MAX - 1; i++) {
       k = 8;
       m = 0;
	   m = k - i;
		if ( sudoku[i][m] == 0 ) continue;
		for (j = i + 1; j < MAX; j++) {
		    n = 8;
		    l = 0;
		    l = n - j;
			if (sudoku[j][l] == sudoku[i][m]) return (FALSE);
        }
    }

	transformuj_ctverecek_poli(buffer, radek, sloupec);
	for (i = 0; i < MAX; i++) if (buffer[i] == cislo) return (FALSE);
	/* Jestli se mozne dane cislo doplnit podle splnenych podminek vrati funkce TRUE*/
	return(TRUE);
}/*konec volne_pole_cislo*/

Problém bych viděl zde.

Nahlásit jako SPAM
IP: 82.99.176.–
Reklama
Reklama
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 136 hostů

Podobná vlákna

Diagonalní sudoku — založil Epoxi

Cantorova diagonalni metoda — založil tanned88

Sudoku X — založil Epoxi

Sudoku backtraking — založil Oxydentist

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý