4. Sudoku Löser in C

Sudoku Löser in C

  • J

    Hallo,

    im Rahmen meines Studiums sollen wir im Fach Informatik ein Programm in C entwerfen, welches ein beliebig vorgegebenes Sudoku löst.
    Folgende Aufgabenstellung wurde uns gegeben:

    - das Programm soll einfache Prozeduren für die Lösung benutzen
    - zusätzlich soll das programm für die iterative Lösungssuche rekursive Prozeduren einsetzen
    - der Quellcode der einzelnen Funktionen soll aus nicht mehr als 45 Anweisungen bestehen
    - die Aufteilung des programms in Funktionen hat nach den prinzipien "strong cohesion" und "loose coupling" zu erfolgen
    - der aktuelle Lösungszustand ist als "struct"-Variable zu speichern

    Bis jetzt habe ich folgendes Programm noch ohne Strukturen geschrieben, welches die Möglichkeiten pro Feld heraussucht und nach dem Ausschlussverfahren (Möglichkeiten pro Zeile, Spalte und 3er-Block) schon einzelne Zahlen ermittelt. Der dritte Index von Sudoku steht an der Nullten Stelle für eine Variable oder feste Variable - ist als Kommentar im Programm erklärt. Der dritte Index von 1 bis 9 steht für die Möglichkeiten an zahlen in diesem Feld. ist also bei [3], [4], [5] die Werte 1, 0, 1 , so heißt das, dass eine 3 oder 5 in diesem Feld, dass du die ersten beide Indexe bestimmt wird, stehen muss.
    Eventuell schlechte Einrückungen kommen vom Compiler LCCWin32, welchen wir nutzen...

    meine Frage ist jetzt: Wie mach ich weiter? Ich weiß nicht, wie ich das systematische Probieren umsetzen soll.. was habt ihr für Vorschläge?

    #include <stdio.h>

int main(void)
{ int zeile,spalte,element,
      laufvar,laufvar2,laufvar3,
	  block_s,block_z,
	  anz_ausgeschl;
  char vorgabe[9][9]
    = { '0', '7', '0',  '6', '0', '0',  '0', '8', '0',
	    '6', '0', '0',  '5', '0', '0',  '0', '0', '0',
		'0', '0', '9',  '0', '0', '4',  '0', '5', '0',

		'1', '2', '0',  '0', '0', '0',  '9', '6', '0',
		'0', '0', '0',  '0', '2', '0',  '4', '0', '0',
		'0', '0', '6',  '0', '0', '0',  '0', '0', '0',

		'0', '0', '0',  '4', '3', '0',  '1', '0', '7',
		'2', '0', '5',  '1', '0', '0',  '0', '0', '0',
		'0', '0', '0',  '0', '0', '0',  '8', '0', '0'
	  };

  char sudoku[9][9][10];

  // Überprüfen auf feste und variable Eingaben
     // 0. Element = 1 --> Wert variabel
	 // 0. Element = 0 --> Wert fest
  for (zeile = 0; zeile < 9; zeile++)
    for (spalte = 0; spalte < 9; spalte++)
	{ for (element = 0; element <= 9; element++)
        sudoku[zeile][spalte][element]='0';
	  switch (vorgabe[zeile][spalte])
      { case '0' : { for (laufvar = 0; laufvar <= 9; laufvar++)
	                   sudoku[zeile][spalte][laufvar]='1';
                     break;
				   };
		default  : { for (laufvar = 1; laufvar <=9; laufvar++)
			           sudoku[zeile][spalte][laufvar] = '.';
					 break;
				   };
	  };
	  switch (vorgabe[zeile][spalte])
	  { case '1' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][1]='1';
			         break;
				   };
		case '2' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][2]='1';
			         break;
				   };
		case '3' : { sudoku[zeile][spalte][0]='0';
		         	 sudoku[zeile][spalte][3]='1';
			         break;
				   };
		case '4' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][4]='1';
			         break;
				   };
		case '5' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][5]='1';
			         break;
				   };
		case '6' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][6]='1';
			         break;
				   };
		case '7' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][7]='1';
			         break;
				   };
		case '8' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][8]='1';
			         break;
				   };
		case '9' : { sudoku[zeile][spalte][0]='0';
		        	 sudoku[zeile][spalte][9]='1';
			         break;
				   };
	  };
	};

  // Vorgegebene Zahlen als Möglichkeiten aus
  // Zeile, Spalte und Block entfernen
  for (zeile = 0; zeile < 9; zeile++)
    for (spalte = 0; spalte < 9; spalte++)
      if (sudoku[zeile][spalte][0] == '1') // Wenn variabel ...

	  // Loeschen der Festwertzahl als Mgl. aus Zeile
	  { for (laufvar = 0; laufvar < 9; laufvar++)
		  if (sudoku[laufvar][spalte][0] == '0') // Wenn fest
	        for (laufvar2 = 1; laufvar2 <= 9; laufvar2++)
			  if (sudoku[laufvar][spalte][laufvar2] == '1')
			    sudoku[zeile][spalte][laufvar2] = '.';

		// Loeschen der Festwertzahl als Mgl. aus Spalte
		for (laufvar = 0; laufvar < 9; laufvar++)
		  if (sudoku[zeile][laufvar][0] == '0') // Wenn fest
	        for (laufvar2 = 1; laufvar2 <= 9; laufvar2++)
			  if (sudoku[zeile][laufvar][laufvar2] == '1')
			    sudoku[zeile][spalte][laufvar2] = '.';

		// Loeschen der Festwertzahl als Mgl. aus Block
		  // Bestimmen des aktuellen Blocks
		if (zeile < 3)
		  block_z = 3;
	    else if ( (zeile >= 3) && (zeile < 6) )
		  block_z = 6;
	    else if (zeile >= 6)
		  block_z = 9;
	    if (spalte < 3)
		  block_s = 3;
	    else if ( (spalte >= 3) && (spalte < 6) )
		  block_s = 6;
	    else if (spalte >= 6)
		  block_s = 9;

	    for (laufvar = block_z-3; laufvar < block_z; laufvar++)
		  for (laufvar2 = block_s-3; laufvar2 < block_s; laufvar2++)
		    if (sudoku[laufvar][laufvar2][0] == '0')
		      for (laufvar3 = 1; laufvar3 <= 9; laufvar3++)
			    if (sudoku[laufvar][laufvar2][laufvar3] == '1')
			      sudoku[zeile][spalte][laufvar3] = '.';
	  };

  // Wenn alle Ziffern bis auf eine ausgeschlossen sind, dann ist diese
  // als Festwertzahl zuzuordnen
  for (zeile = 0; zeile < 9; zeile ++)
	for (spalte = 0; spalte < 9; spalte++)
	  if (sudoku[zeile][spalte][0] == '1') // Wenn variabel ...
	  { anz_ausgeschl = 0;
		for (element = 1; element <= 9; element++)
	      if (sudoku[zeile][spalte][element] == '.')
	        anz_ausgeschl++;
		if (anz_ausgeschl == 8)
		  sudoku[zeile][spalte][0] = '0';
	  }

  // Ausgabe
  printf("Eingegebene Matrix:\n");
  for (zeile = 0; zeile < 9; zeile ++)
  { printf("\n");
	for (spalte = 0; spalte < 9; spalte++)
    { printf(" %c", vorgabe[zeile][spalte] );
    };
  };
  printf("\n\n");

  printf("Moeglichkeiten Matrix:\n");
  for (zeile = 0; zeile <9; zeile++)
  { printf("\n");
    if ( (zeile == 3) || (zeile == 6) )
	  printf("\n");
    for (spalte = 0; spalte <9; spalte++)
	{ if ( (spalte == 3) || (spalte == 6) )
	  printf(" ");
	  printf("  ");
	  for (element = 0; element <=9; element++)
	    printf("%c", sudoku[zeile][spalte][element]);
    };
  };

  // systematisches Probieren

  return(0);
}
    0
  • J

    Habe das Programm mit Strukturen geschrieben..
    Weiterhin bleibt aber die Frage: Wie soll ich nach dem Aussortieren der Möglichkeiten der Zahlen für die einzelnen Felder durch überprüfen, ob Zahlen im Block, der gleichen Zeile und der gleichen Spalte bereits vorhanden sind, weiter fortfahren?
    Eigentlich steht ja jetzt nur systematisches Probieren an, aber wie kann man das bewerkstelligen?

    #include <stdio.h>

struct dt_sudoku
{ char vorgabe[9][9];
  char moeglichk[9][9][10];
};

typedef struct dt_sudoku sud;

// Eingabe
void eingabe(sud *sdk)
{ int zeile, spalte;
  char eing[9][9] = { '0', '7', '0',  '6', '0', '0',  '0', '8', '0',
                      '6', '0', '0',  '5', '0', '0',  '0', '0', '0',
	                  '0', '0', '9',  '0', '0', '4',  '0', '5', '0',

		              '1', '2', '0',  '0', '0', '0',  '9', '6', '0',
		              '0', '0', '0',  '0', '2', '0',  '4', '0', '0',
		              '0', '0', '6',  '0', '0', '0',  '0', '0', '0',

		              '0', '0', '0',  '4', '3', '0',  '1', '0', '7',
		              '2', '0', '5',  '1', '0', '0',  '0', '0', '0',
		              '0', '0', '0',  '0', '0', '0',  '8', '0', '0'
	                };
  // Eingabe wird an sdk übergeben, um raus aus Funktion
  for (zeile = 0; zeile < 9; zeile++)
    for (spalte = 0; spalte < 9; spalte++)
      // Pfeil-Operator
	  sdk->vorgabe[zeile][spalte] = eing[zeile][spalte];
	  // oder als Punkt-Operator
	  //(*sdk).vorgabe[zeile][spalte] = eing[zeile][spalte];
  return;
};

// Festwertzahlen in der Eingabe bestimmen
void festwertzahlen_bestimmen(sud *sdk)
{ int zeile, spalte, element, laufvar;
  // Überprüfen auf feste und variable Eingaben
     // 0. Element = 1 --> Wert variabel
	 // 0. Element = 0 --> Wert fest
  for (zeile = 0; zeile < 9; zeile++)
    for (spalte = 0; spalte < 9; spalte++)
	{ for (element = 0; element <= 9; element++)
        (*sdk).moeglichk[zeile][spalte][element]='0';
	  switch ((*sdk).vorgabe[zeile][spalte])
      { case '0' : { for (laufvar = 0; laufvar <= 9; laufvar++)
	                   (*sdk).moeglichk[zeile][spalte][laufvar]='1';
                     break;
				   };
		default  : { for (laufvar = 1; laufvar <=9; laufvar++)
			           (*sdk).moeglichk[zeile][spalte][laufvar] = '.';
					 break;
				   };
	  };
	  switch ((*sdk).vorgabe[zeile][spalte])
	  { case '1' : { (*sdk).moeglichk[zeile][spalte][1]='1';
			         break;
				   };
		case '2' : { (*sdk).moeglichk[zeile][spalte][2]='1';
			         break;
				   };
		case '3' : { (*sdk).moeglichk[zeile][spalte][3]='1';
			         break;
				   };
		case '4' : { (*sdk).moeglichk[zeile][spalte][4]='1';
			         break;
				   };
		case '5' : { (*sdk).moeglichk[zeile][spalte][5]='1';
			         break;
				   };
		case '6' : { (*sdk).moeglichk[zeile][spalte][6]='1';
			         break;
				   };
		case '7' : { (*sdk).moeglichk[zeile][spalte][7]='1';
			         break;
				   };
		case '8' : { (*sdk).moeglichk[zeile][spalte][8]='1';
			         break;
				   };
		case '9' : { (*sdk).moeglichk[zeile][spalte][9]='1';
			         break;
				   };
	  };
	  // Zusatz zu zweiter Switch-Anweisung, bei Zahl in Eingabe
	  // 0. Element = fest
	  if ((*sdk).vorgabe[zeile][spalte] != '0')
	    (*sdk).moeglichk[zeile][spalte][0]='0';
	};
  return;
};

// Vorgegebene Zahlen als Möglichkeiten aus
// Zeile, Spalte und Block entfernen
void moeglichkeiten_bestimmen(sud *sdk)
{ int zeile,spalte,
      laufvar,laufvar2,laufvar3,
	  block_s,block_z;
  for (zeile = 0; zeile < 9; zeile++)
    for (spalte = 0; spalte < 9; spalte++)
      if ((*sdk).moeglichk[zeile][spalte][0] == '1') // Wenn variabel ...

	  // Loeschen der Festwertzahl als Mgl. aus Zeile
	  { for (laufvar = 0; laufvar < 9; laufvar++)
		  if ((*sdk).moeglichk[laufvar][spalte][0] == '0') // Wenn fest
	        for (laufvar2 = 1; laufvar2 <= 9; laufvar2++)
			  if ((*sdk).moeglichk[laufvar][spalte][laufvar2] == '1')
			    (*sdk).moeglichk[zeile][spalte][laufvar2] = '.';

		// Loeschen der Festwertzahl als Mgl. aus Spalte
		for (laufvar = 0; laufvar < 9; laufvar++)
		  if ((*sdk).moeglichk[zeile][laufvar][0] == '0') // Wenn fest
	        for (laufvar2 = 1; laufvar2 <= 9; laufvar2++)
			  if ((*sdk).moeglichk[zeile][laufvar][laufvar2] == '1')
			    (*sdk).moeglichk[zeile][spalte][laufvar2] = '.';

		// Loeschen der Festwertzahl als Mgl. aus Block
		  // Bestimmen des aktuellen Blocks
		if (zeile < 3)
		  block_z = 3;
	    else if ( (zeile >= 3) && (zeile < 6) )
		  block_z = 6;
	    else if (zeile >= 6)
		  block_z = 9;
	    if (spalte < 3)
		  block_s = 3;
	    else if ( (spalte >= 3) && (spalte < 6) )
		  block_s = 6;
	    else if (spalte >= 6)
		  block_s = 9;

	    for (laufvar = block_z-3; laufvar < block_z; laufvar++)
		  for (laufvar2 = block_s-3; laufvar2 < block_s; laufvar2++)
		    if ((*sdk).moeglichk[laufvar][laufvar2][0] == '0')
		      for (laufvar3 = 1; laufvar3 <= 9; laufvar3++)
			    if ((*sdk).moeglichk[laufvar][laufvar2][laufvar3] == '1')
			      (*sdk).moeglichk[zeile][spalte][laufvar3] = '.';
	  };
  return;
};

void zuordnung_festwertzahlen(sud *sdk)
{ int zeile, spalte, element, anz_ausgeschl;
  // Wenn alle Ziffern bis auf eine ausgeschlossen sind, dann ist diese
  // als Festwertzahl zuzuordnen
  for (zeile = 0; zeile < 9; zeile ++)
	for (spalte = 0; spalte < 9; spalte++)
	  if ((*sdk).moeglichk[zeile][spalte][0] == '1') // Wenn variabel ...
	  { anz_ausgeschl = 0;
		for (element = 1; element <= 9; element++)
	      if ((*sdk).moeglichk[zeile][spalte][element] == '.')
	        anz_ausgeschl++;
		if (anz_ausgeschl == 8)
		  (*sdk).moeglichk[zeile][spalte][0] = '0';
	  };
};

// Ausgabe
void ausgabe(sud *sdk)
{ int zeile, spalte, element;
  printf("Eingegebene Matrix:\n");
  for (zeile = 0; zeile < 9; zeile ++)
  { printf("\n");
	for (spalte = 0; spalte < 9; spalte++)
    { printf(" %c", (*sdk).vorgabe[zeile][spalte] );
    };
  };
  printf("\n\n");
  printf("Moeglichkeiten Matrix:\n");
  for (zeile = 0; zeile <9; zeile++)
  { printf("\n");
    if ( (zeile == 3) || (zeile == 6) )
	  printf("\n");
    for (spalte = 0; spalte <9; spalte++)
	{ if ( (spalte == 3) || (spalte == 6) )
	  printf(" ");
	  printf("  ");
	  for (element = 0; element <=9; element++)
	    printf("%c", (*sdk).moeglichk[zeile][spalte][element]);
    };
  };
  printf("\n");
  return;
};

// Hauptprogramm
int main(void)
{ sud sdk;
  eingabe(&sdk);
  festwertzahlen_bestimmen(&sdk);
  moeglichkeiten_bestimmen(&sdk);
  zuordnung_festwertzahlen(&sdk);
  ausgabe(&sdk);

  // systematisches Probieren

  return(0);
    0
  • C

    10 Bits passen immer in ein int, deshalb wäre die kanonische Deklaration:

    int moeglichk[9][9];

/* Wenn alle Elemente in moeglichk auf 0 gesetzt sind,
setzt man die Bits etwa so: */
moeglichk[a][b] &= (1 << i);
/* Und liest sie etwa so aus:*/
ist_5_noch_moeglich = moeglichk[a][b] & (1 << 4)

    Statt (*pt).elem schreibt man eleganter pt->elem.

    In Zeile 47 und 57 hast du zwei gleiche switches, den unteren mit einer menge redundatem Code daran. Das verdirbt einem leider das Verständnis.

    Lass die leeren Anweisungen weg z.B. Zeile 51, 55, 56.

    Ohne zu zählen, wette ich, dass deine funktion moeglichkeiten_bestimmen mehr als 45 Anweisungen hat... 😉

    Wenn man probieren muss gibt es zwei Fälle: im ersten hat man die Lösung erraten, im zweiten wird man einen Widerspruch erhalten, d.h. die Möglichkeiten werden irgendwo für keine Ziffer mehr bestehen.

    0
  • J

    Hallo,

    was meisnt du mit leeren Anweisungen? Kann doch nicht einfach die schließenden Klammern weglassen? Denn eine Vorgabe für den Stil unserer Programme ist die "freie Sicht"... Das heißt, dass öffnende und schließende Klammer vertikal untereinander stehen sollen, um die Einrückungen zu sehen.

    Deinen Code verstehe ich leider nicht so ganz. Kannst du mir das nochmal erläutern?

    0
  • C

    Ein Semikolon ';' schließt eine einzige Anweisung ab, ein Block wird
    durch die Klammer '}' geschlossen.
    Von Verzweigungen hängen einzelne Anweisungen oder Blöcke ab.
    Also bedeutet

    while(cond)
    do();

    das gleiche wie

    while(cond) {
    do();
}

    Daher bedeutet

    while(cond) {
    do();
};

    das gleiche wie

    while(cond)
    do();
;     /* <----- leere Anweisung */

    Denn eine Vorgabe für den Stil unserer Programme ist die
    "freie Sicht"...

    Damit hast du's dann aber recht schwer mit sowas:

    case '0' : { for (laufvar = 0; laufvar <= 9; laufvar++)

    weil du immer die schliessende Klammer mit Leerzeichen in
    die freie Sicht rücken must...

    Es ist viel schönerer Stil, zusammengehörige Boolsche Variablen in
    einigen Bits zu speichern, als dafür chars zu verwenden.
    Eine int-Variable bietet dir auf deinem System
    sizeof(int) Bytes = 8 * sizeof(int) Bits Speicherplatz.
    C stellt bitweise Operatoren zur Verfügung (~ & ^ | << >>).
    Die sollte man halt schon kennen. Dann drei Makros und fertig:

    /* 1111111111 binär ist hexadezimal 0x03ff */
#define ALLEM (0x03ff)
/* um herauszufinden, ob ZIFFER moeglich ist */
#define MOEGL(INTEGER, ZIFFER) \
        ((INTEGER & (1 << (ZIFFER - 1))) ? 1 : 0)
/* um ZIFFER moeglich zu machen */
#define SETZEM(INTEGER, ZIFFER) \
        (INTEGER | (1 << (ZIFFER - 1)))
/* um ZIFFER unmoeglich zu machen */
#define LOESCHEM(INTEGER, ZIFFER) \
        (INTEGER & ~(1 << (ZIFFER - 1)))

/* dann könnte ich das so machen */
unsigned int i = ALLEM;
printf("%d\n", MOEGL(i, 5)); /* ist 5 moeglich? */
i = LOESCHEM(i, 5);
printf("%d\n", MOEGL(i, 5)); /* ist 5 moeglich? */
i = SETZEM(i, 5);
printf("%d\n", MOEGL(i, 5)); /* ist 5 moeglich? */
/* Und ich hätte 810 chars (810 bytes) getauscht
gegen 81 ints (für gewöhnlich 324 bytes) aber short würde ja auch reichen */

    Du darfst eben nicht verwirrst sein, weil wir Integers benutzen, um Bits zu
    setzen. Für uns sollen die Stellen der Binärzahl ja bedeuten, ob die der
    Stelle zugeordnete Ziffer noch möglich ist. Z.B. die Binärzahl

    (führende Nullstellen) 10 1000 0010

    soll für uns bedeuten, dass nur mehr die Ziffern 10 (zehnte Stelle),
    8 (achte Stelle) und 2 (zweite Stelle) möglich sind.
    Es darf dich nicht betrüben, dass diese Zahl für printf was anderes bedeutet,
    nämlich

    512 + 128 + 2 = 642

    Alle Möglichkeiten bestehen also bei

    (führende Nullstellen) 11 1111 1111 = 0x03ff = 1023

    Bei den Makros gehe ich davon aus, dass ZIFFER der Zahlenwert der Ziffer ist,
    also 5 für '5', nicht ihr ASCII Wert 53. Wenn du die Ziffer als ASCII Wert hast,
    rechnest du um mit Ziffer = ASCII_Wert - '0'.

    Erklär mir bitte trotzdem, warum du in den Zeilen 47 und 57 den gleichen
    switch hast und warum du beim zweiten überhaupt einen switch verwendest!

    Die Zeilen 57 bis 85 kann mann stark verkürzen:

    if (sdk->vorgabe[zeile][spalte] > '0' && sdk->vorgabe[zeile][spalte] <= '9')
    sdk->moeglichk[zeile][spalte][sdk->vorgabe[zeile][spalte] - '0'] = '1';

    Die beiden Zeilen haben den gleichen Effekt wie deine 29. 🙄

    - der aktuelle Lösungszustand ist als "struct"-Variable zu speichern

    Du kannst deinem Lehrer ruhig sagen, dass das eine didaktische Nullaussage ist,
    weil in einer Struktur wiederum alles sein kann. Du hättest das
    Array moeglichk auch allein (sogar global) definieren können,
    die Struktur hast du ja wirklich nur aus Autoritätsglauben.
    Das Array vorgabe hast du ja ohnehin nur als Eingabe,
    die im wirklichen Leben wahrscheinlich nicht in dieser Form vom Terminal kommen wird.
    Du wirst ja dann die Eingabedaten (die dein Programm ja irgendwann nicht mehr
    aus dem Quelltext beziehen soll) gleich umrechnen und in moeglichk
    speichern, also vorgabe gar nicht brauchen.
    Deshalb hat vorgabe in der Struktur eigentlich nichts zu suchen;
    es hat auch nichts mit dem aktuellen Lösungszustand zu tun.

    So. Nach einigen Edits habe ich mich nun länger mit deiner Hausübung befasst. Ich weise dich darauf hin, dass sie hier keiner für dich machen wird, aber wir dir gerne bei Problemen weiterhelfen. Bis dahin solltest du deinen Code kürzen, damit ihn die anderen schneller verstehen als ich. Da ist noch das unwichtigste, ob du mit chars oder Integer-Bits arbeitest.

    0
  • J

    Vielen vielen dank für diese ausführliche Antwort. Hast dich ja richtig ins Zeug gelegt. Werde deine Tipps und Hinweise morgen umsetzen und melde mich dann wieder. Habe jetzt auch einen Algorithmus herausgefunden um die restlichen Felder des Sudoku zu lösen.

    Das mit der freien Sicht gefällt mir leider auch nicht so, aber leider prüft unser Prof in Form von Testaten jede Woche den aktuellen Wissens- und Verständnisstand ab und verlangt dabei von uns seine Stilvorgaben einzuhalten (damit ers wohl einfacher hat). Diese Testate dienen dazu, dass man erst zur Prüfung zugelassen wird... aber will darauf nicht weiter eingehen.

    Das mit der leeren Anwerisung hab ich jetzt verstanden. Wusste zuerst nicht was du meisnt. Besten dank.
    Das mit den Zeilen kürzen ist mir so gar nicht in den Sinn gekommen. Anfängerfehler eben 😉 Aber super, dass du das gesehen hast. Nur aus Fehlern lernt man ja ...

    Der Vorschlag mit der Speicherung der Möglichkeiten je Feld als Binärzahl ist wirklich gut, werde aber wahrscheinlich dennoch die Speicherung als char beibehalten, da das Programm nicht effizient sein muss und unser Prof sonst im Testat nur dumme Frage stellt(wir müssen das Programm vorstellen, erklären und auf Fragen zum Quelltext antworten können und falls er Veränderungen am Quelltext vornehmen möchte deren Auswirkungen auf das Programm erklären. Falls man dabei nen Fehler macht dann hat man schon halbes Fehltestat und bei mehreren fehlern ist das ein komplettes Fehltestat und man kann es wiederholen. Bei 3 Fehltestaten wird man nicht zur Prüäfung zugelassen. Deswegen halte ich mich da strikt an seine Dummen Regeln. Ist zwar blöd aber nur so kann ich Info bestehen).

    Werde aber für mich persönlich nach dem Testat das Programm mit Speicherung als Binärzahlen umschreiben. Finde das wirklich gut die Idee 😮

    Zu der Eingabe: Das habe ich bisher so gelöst, damit ich nicht bei jeder Ausführung des Programms die Matrix eingeben muss. Das Array vorgabe wird bei fertigem Programm entfernt und eine Eingabesequenz geschrieben, die die Eingabe direkt im Feld moeglichk speichert...

    Jiss

    0
  • C

    Stil ist Schall und Rauch.

    Vielen vielen dank für diese ausführliche Antwort. Hast dich ja richtig ins Zeug gelegt.

    Ich will ja auch sehen, was am Ende rauskommt.

    Werde aber für mich persönlich nach dem Testat das Programm mit Speicherung als Binärzahlen umschreiben. Finde das wirklich gut die Idee

    Weil sie so gut ist, ist sie älter als ich.

    0
  • C

    Werde aber für mich persönlich nach dem Testat das Programm mit Speicherung als Binärzahlen umschreiben. Finde das wirklich gut die Idee

    Noch einmal bedacht: das ist eigentlich nicht nötig, weil ich's schon getan habe.
    Siehe:

    /* so machst du's: */

typedef struct dt_sudoku
{
    char moeglichk[9][9][10];
    /* der Rest ist egal */
} sud;

/* so mach ich's: */

typedef struct dt_sudoku
{
    /* short ist besser als int, hat auch immer mind. 2 Bytes */
    short moeglichk[9][9];
} sud;

/* egal, wie man's macht, man muss nur die drei Makros anpassen ;)
   Wenn ich recht verstanden habe, dann bedeutet '0' bei dir: unmöglich
   und '1': möglich. moeglichk hat in der tiefsten Ebene 10 Elemente,
   also eines zu viel. Afaik ist das nullte bei dir egal.
   Also:
*/

#define MOEGL(POINTER, ZIFFER) \
        (((POINTER)[ZIFFER]) == '1' ? 1 : 0)
/* um ZIFFER moeglich zu machen */
#define SETZEM(POINTER, ZIFFER) \
        ((POINTER)[ZIFFER] = '1')
/* um ZIFFER unmoeglich zu machen */
#define LOESCHEM(POINTER, ZIFFER) \
        ((POINTER)[ZIFFER] = '0')
/* weil die Sache mit ALLEM in der Zuweisung an ein Array nicht geht, 
   mache ich noch ein Makro, um alle M. zu setzen
*/
#define SETZEALLEM(POINTER) \
        { for (int i = 0; i < 10; i++) { (SETZEM(POINTER, i)); } }

/* in meinem Fall (mit ints) muss SETZEALLEM lauten: */
#define SETZEALLEM(INTEGER) \
        ((INTEGER) = 0x0377)

    Nun ist es egal, ob du moeglichk deklarierst als int[][] oder char[][][], wenn du nur mehr die jeweiligen Makros verwendest. Wenn dein Professor fragt, warum du die Makros hast, sagst du einfach: weil's so klarer ist. Und wenn er nicht herschaut, änderst du die Deklaration von moeglichk und nimmst die anderen Makros. Sonst müsste man nichts am Code ändern, wenn du die Makros konsequent verwendet. Ein Aufruf sieht immer so aus:

    MOEGL(sdk->moeglichk[1][2], 5)
/* sieht nach, ob im Feld (1,2) noch 5 möglich ist */

    Wenn du's dann zum Laufen gebracht hast, wär's schön, wenn du mir eine Kopie geben könntest. (Ich brauche nämlich auch einen Sudoku-Löser, den ich verstehe, nur nicht so dringed wie du 🙂 )

    0
Anmelden zum Antworten