TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
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.
