Sudoku X – C / C++ – Fórum – Programujte.com

Čau, zkoušel jste někdo programovat sudoku X ? Už mi dochází nápady jak to provést, vždycky se najde jedno zadání, které mi vyvrátí, že aktuálni kód je správně. Přijde mi, že jedním typem algoritmu nejde pokrýt všechny případy narozdíl od normálního suddoku.

a neřešil jsi to tady v půlce listopadu?

hu

no představ si že jo a kdybych to už dávno měl, tak by se asi neptal.

Nastudoval jsem tvoje kódy, ale napadají mě 2 způsoby řešení.

1) klasicky, "tupé" procházení stavového prostoru, kdy na jednotlivá volná políčka budeš dosazovat postupně všechna čísla a kontrolovat, jestli výsledek je správné řešení

2) vytvoříš si pole trojrozměrné pole, do kterého si zapíšeš pro jednotlivé pozice, která čísla tam připadají v úvahu (tj. podíváš se, jestli to samé číslo už není ve sloupci, řádku, 3x3buňce nebo na diagonále) a pak začneš doplňovat do výsledku tam, kde připadá v úvahu pouze jedno číslo a po každém přidání "vyškrtáš" z toho pole možností toto číslo, tj. znovu ho přegeneruješ

Výhodou 1. možnosti je, že pokud existuje řešení, tak ho najde. Nevýhodou je, že to může chvilku trvat.

Výhodou 2. možnosti je, že jdeš přímo za výsledkem, ale pokud jsou na začátku ve všech volných pozicích, alespoň 2 možnosti, tak by si s tím musel do toho algoritmu počítat a vlastně tam přidat částečně variantu 1.

Vždycky jsem postupoval tak, že jsem si napsal kod pro normalni sudoku a pak se ho snažil nějak modifikovat, tak aby řešilo sudoku X, Zatím jsem s tím moc neuspěl. Variantu jsem 1 jsem se snažil vytvořit a neměla velký úspěch, proto mi přijde vhodnější varianta 2. Jeste si nedokazu presne predstavit jak by to mělo vypadat.

 Napada ma takyto sposob:

//policko reprezentujuce cislo:
struct Filed{
	int x;		//0 ak na policku nie je ziadne cislo alebo cislo <1, 9>
	bool poss_map[9];//mapa cisiel ktore mozu byt umiestnene na toto policko (index 0 reprezentuje cislo 1, index 1 reprezentuje cislo 2, ...)
}

//herna plocha:
struct GameField{
	Filed fields[9][9];	//vsetky policka
}

1. Najprv na zaklade existujucich policok ktore maju definovany atribut @x naplnis @poss_map-y (podla pravidiel sudoku X). 
2.  Potom vyplnis @x pre vsetky policka kde @poss_map obsahuje len 1 hodnotu.
3. Ak neexistuje taka situacia, tak si najdes policko kde je co najmenej moznosti (idealne 2) a pre kazdu moznost vygenerujes novu hernu plochu (GameField), pre kazdu tuto plochu spravis bod (2).
4. Vynulujes vsetky @poss_map zo vsetkych fieldoch vo vsetkych hernych plochach
5. vrat sa na bod (1) a opakuj dokym mas volne policka.

No takhle, mám tři kódy, tento je poslední a nenapadá mě jak to dodělat na Sudoku X. Tento je teda s trojrozmernym polem. Pokud bych si oznacoval do toho navic diagonaly, tak to nefunguje. Nejake hinty?

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


FILE *fr;
FILE *fw;

int i, j, k, dost, n, vyber;
int e, f;


int sudoku[9][9];
int r[81];
int s[81];
int t[81];
int p[9][9][9];

char *jmeno = "sudoku.txt";
int radek, sloupec;

int oznac(short u, short v, short x) {

  short i, j;

  for(i = 0; i < 9; i++)
    if(p[u][i][x] == e) p[u][i][x] = f;
  for(i = 0; i < 9; i++)
    if(p[i][v][x] == e) p[i][v][x] = f;
      if(u < 3) u = 0;
    else
     if (u < 6) u = 3;
       else u = 6;
     if (v < 3) v = 0;
       else
     if (v < 6) v = 3;
       else v = 6;

for (i = u; i < u + 3; i++)
  for (j = v; j < v + 3; j++)
    if(p[i][j][x] == e) p[i][j][x] = f;
return 0;
}

int main(void)
{
  printf("Sudoku solver v1.0\n");
  printf("==================\n");

  int a;

  printf("\nZadejte zadani, 0 predstavuje prazdne pole\n\n");

  for(radek = 0; radek < 9; radek++) {
    printf("zadejte hodnoty %d. radku\n", radek + 1);
    for(sloupec = 0; sloupec < 9; sloupec++)
      scanf("%d",&sudoku[radek][sloupec]);
  }

  a = 1;
  while(a > 0) {
    printf("kontrolni vypis\n");

    for(radek = 0; radek < 9; radek++) {
      for(sloupec = 0; sloupec < 9; sloupec++)
      printf("%d ", sudoku[radek][sloupec]);

    printf("\n");
  }
  printf("zadejte c.radku pro opravu nebo nulu pro konec\n");
  scanf("%d", &a);

  if(a != 0) {
    for (sloupec = 0; sloupec < 9; sloupec++)
      scanf("%d  ", &sudoku[k-1][sloupec]);

  }
  fw = fopen(jmeno, "w");

  for(radek = 0; radek < 9; radek++)
    for(sloupec = 0; sloupec < 9; sloupec++)
      fprintf(fw, "%d\n", sudoku[radek][sloupec]);

  fclose(fw);
  }

 if((fr = fopen(jmeno, "rt")) == NULL){
   printf("Soubor nebyl otevren\n");
   return 1;
 }

 for(i = 0; i < 9; i++)
   for(j = 0; j < 9; j++)
     fscanf(fr, "%d", &sudoku[i][j]);

printf("\nzadani\n\n");

for(i = 0; i < 9; i++) {
  for(j = 0;j < 9; j++)
    printf("%d ", sudoku[i][j]);
  printf("\n");
}

e = 0; f = 1;

for (i = 0; i < 9; i++)
  for(j = 0; j < 9; j++)
    if(sudoku[i][j] > 0) oznac(i, j, sudoku[i][j]);  
n = 0; k = 1;
i = 0; j = 0;

while(i < 9) {
  if(sudoku[i][j] == 0){
    dost = 0;
    while ((k < 10) && (dost == 0)){
      if(p[i][j][k] == 0){
        printf("%d", p[i][j][k]);
        sudoku[i][j] = k; e = 0; dost = 1;
        r[n] = i; s[n] = j; t[n] = k; n++; f = n + 1; oznac(i,j,k);
      }
      else k++;
    }
    if (dost == 0) {
      do{
      n--;
        if(n < 0) {
          printf("neexistuje reseni\n");
          scanf("%d", &e);
          return 1;
        }
        else {
          i = r[n]; j = s[n]; k = t[n]; e = n+2; f = 0;
           oznac(i,j,k);  sudoku[i][j] = 0; k++;
         }
      }
      while( k >= 10);
      continue;
    }
  }
  k = 1; j++; if(j >= 9) {i++; j = 0;}
}
printf("\nvysledek\n\n");

for(i = 0; i < 9; i++) {
  for(j = 0;j < 9; j++)
    printf("%d ", sudoku[i][j]);
  printf("\n");
}
scanf("%d", &e);
return 0;
}

int oznac(short u, short v, short x)
do teto funkce jsem chtel napsat neco jako
for(i = 0; i < 9; i++) if(p[i][i][x] == e) p[i][i][x] = f;
pak do tohoto

if(p[i][j][k] == 0){ printf("%d", p[i][j][k]); sudoku[i][j] = k; e = 0; dost = 1; r[n] = i; s[n] = j; t[n] = k; n++; f = n + 1; oznac(i,j,k); } at vklada do pole sudooku[i][i] = k, samozrejme podle podminky osetrit at priradi nulu. Nic takoveho nefunguje, kdyz se vhodne modifikuje nastane problem jako u predchozich sudoku.