Sudoku Probleme generieren

  • Sudoku Probleme generieren

    Hallo ich mache gerade ein Projekt in C. Es geht darum Sudoku's zu erstellen. Ich weiß, dass ich dass irgendwie über Backtracking machen muss. Habe aber keine Ahnung wie ich das machen soll.

    Kann mir da jemand helfen?

    Mein Lösungsansatz sah wie folgt aus, hängt sich aber natürlich dann irgendwann auf.

    Ein Auszug:

    Quellcode

    1. printf("Alles auf Null Setzen ...\n");
    2. for(j=0;j<9;j++) for(i=0;i<9;i++) s_matrix [j][i] = 0;
    4. printf("Starte Erstellung ...\n");
    6. srand( (unsigned)time( NULL ) );
    7. for(Laufzahl=1;Laufzahl!=10;Laufzahl++)
    8. {
    9. for(Verteilt=0;Verteilt!=9;)
    10. {
    11. j = (((double) rand() / (double) RAND_MAX) * 9 + 0);
    12. i = (((double) rand() / (double) RAND_MAX) * 9 + 0);
    13. printf("l%d\tv%d\tz%d\ts%d\n",Laufzahl,Verteilt,j,i);
    15. check = (s_matrix [j][i]); //Ist das Feld schon belegt (alle Felder sind von vorne mit "0" belegt)
    16. if ( check == 0 ) check = test_ispalte(&s_matrix[0][i],Laufzahl); //Test Spalte (Funktion) wenn "0" dann OK
    17. if ( check == 0 ) check = test_jzeile(&s_matrix[j][0],Laufzahl); //Test Zeile (Funktion) wenn "0" dann OK
    18. if ( check == 0 ) check = test_box(&s_matrix[0][0],j,i,Laufzahl); //Test 3*3Feld (Funktion) wenn "0" dann OK
    20. if ( check == 0) // Wenn alles OK dann setzen
    21. {
    22. s_matrix [j][i] = Laufzahl;
    23. Verteilt++;
    24. }
    25. }
    26. }
    Alles anzeigen

  • Ich weis nicht obs dir hilft, aber ich hab mal ein Programm zum automatischen Lösen geschrieben.
    Kannst wenn du willst jedenfalls die Überprüfung übernehmen, ob eine Zahl für das Feld zulässig ist

    Quellcode

    1. // Copyright Christoph Egger
    2. //Berechnet eine Mögliche Lösung für das Sudoku
    3. //Als eingabe wird eine Textdatei mit 9 Zeilen zu je 9 Zahlen mit ' ' als
    4. //Abstand angenommen, 0 steht für ein Leeres Feld
    5. #include <stdio.h>
    11. bool step(int feld[9][9], int filled, int searchdepth, char* filename);
    12. inline void get_next_empty(int* posx, int* posy, int feld[9][9]);
    13. void print_solution(int feld[9][9]);
    14. inline bool test_feld(int feld[9][9]);
    15. void save_solution(int feld[9][9], char* filename);
    17. int main()
    18. {
    19. char buffer[255];
    20. int feld[9][9];
    21. int filled = 0;
    22. int searchdepth = 0;
    23. printf("Dateiname des zu lösenden Sudokus eingeben!\n");
    24. scanf("%s", buffer);
    25. printf("\n\n");
    27. searchdepth = 10000;
    29. FILE* theFile = fopen(buffer,"r");
    30. if(theFile == NULL)
    31. {
    32. return -1;
    33. }
    35. for (int z = 0; z < 9; z++)
    36. {
    37. for(int s = 0; s < 9; s++)
    38. {
    39. fscanf(theFile, "%d", &feld[z][s]);
    40. if (feld[z][s] != 0) filled++;
    41. }
    42. }
    43. fclose(theFile);
    45. return step(feld, filled, searchdepth, buffer);
    46. }
    48. bool step(int feld[9][9], int filled, int searchdepth, char* filename)
    49. {
    50. static int iteration = 0;
    51. static bool printed = false;
    52. if(++iteration > searchdepth)
    53. {
    54. print_solution(feld);
    55. printf("Zu viele Durchläufe nötig!\n");
    56. return false;
    57. }
    59. int posx;
    60. int posy;
    63. get_next_empty(&posx, &posy, feld);
    65. if (posx == -1 || posy == -1)
    66. {
    67. printf("SuDoKu nach %d durchläufen gelöst:\n\n", iteration);
    68. print_solution(feld);
    69. save_solution(feld, filename);
    70. return true;
    71. }
    74. filled++;
    76. for (int i = 1; i < 10; i++)
    77. {
    78. feld[posx][posy] = i;
    79. if (test_feld(feld))
    80. {
    81. if (step(feld, filled, searchdepth, filename))
    82. return true;
    83. else
    84. {
    86. }
    87. }
    88. }
    90. feld[posx][posy] = 0;
    92. if (!printed)
    93. {
    94. print_solution(feld);
    95. printed = true;
    96. }
    98. return false;
    99. }
    101. inline void get_next_empty(int* posx, int* posy, int feld[9][9])
    102. {
    103. *posx = -1;
    104. *posy = -1;
    106. for (int x = 0; x < 9; x++)
    107. {
    108. for (int y = 0; y < 9; y++)
    109. {
    110. if (feld[x][y] == 0)
    111. {
    112. *posx = x;
    113. *posy = y;
    114. break;
    115. }
    116. }
    117. if(*posx != -1) break;
    118. }
    119. }
    121. inline bool test_feld(int feld[9][9])
    122. {
    123. bool first = true;
    124. int zff;
    125. int x;
    126. int y;
    129. //Zeilen
    130. for (zff = 1; zff < 10; zff++)
    131. {
    132. for (y = 0; y < 9; y++)
    133. {
    134. for (x = 0; x < 9; x++)
    135. {
    136. if (feld[x][y]==zff)
    137. {
    138. if (first)
    139. {
    140. first = false;
    141. }
    142. else
    143. {
    144. return false;
    145. }
    146. }
    147. }
    148. first = true;
    149. }
    150. }
    152. first = true;
    154. //Spalten
    155. for (zff = 1; zff < 10; zff++)
    156. {
    157. for (x = 0; x < 9; x++)
    158. {
    159. for (y = 0; y < 9; y++)
    160. {
    161. if (feld[x][y]==zff)
    162. {
    163. if (first)
    164. {
    165. first = false;
    166. }
    167. else
    168. {
    169. return false;
    170. }
    171. }
    172. }
    173. first = true;
    174. }
    175. }
    177. //Quadrate
    178. int x2, y2;
    180. for (zff = 1; zff < 10; zff++)
    181. {
    182. for (x2 = 0; x2 < 3; x2++)
    183. {
    184. for (y2 = 0; y2 < 3; y2++)
    185. {
    186. first = true;
    187. for (x = 0; x < 3; x++)
    188. {
    189. for (y = 0; y < 3; y++)
    190. {
    191. if (feld[x + (x2 * 3)][y + (y2 * 3)]==zff)
    192. {
    193. if (first)
    194. {
    195. first = false;
    196. }
    197. else
    198. {
    199. return false;
    200. }
    201. }
    202. }
    203. }
    204. }
    205. }
    206. }
    207. return true;
    208. }
    210. void print_solution(int feld[9][9])
    211. {
    212. for (int i = 0; i < 9; i++)
    213. {
    214. printf("%d %d %d %d %d %d %d %d %d\n", feld[i][0], feld[i][1], feld[i][2], feld[i][3], feld[i][4], feld[i][5], feld[i][6], feld[i][7], feld[i][8]);
    215. }
    216. printf("\n\n");
    217. }
    219. void save_solution(int feld[9][9], char* filename)
    220. {
    221. char newFilename[255];
    222. sprintf(newFilename, "%s.solution", filename);
    223. FILE* theFile = fopen(newFilename,"w");
    224. if(theFile == NULL)
    225. {
    226. printf("Fehler beim Speichern!");
    227. }
    228. for (int i = 0; i < 9; i++)
    229. {
    230. fprintf(theFile, "%d %d %d %d %d %d %d %d %d\n", feld[i][0], feld[i][1], feld[i][2], feld[i][3], feld[i][4], feld[i][5], feld[i][6], feld[i][7], feld[i][8]);
    231. }
    232. fprintf(theFile, "\n\n");
    233. }
    Alles anzeigen

  • OK DANKE!

    Danke für deine Antwort, das hilft mir schon etwas weiter.

    :!: Ich wußte gar nicht das es in C bool gibt, gibt es doch auch nicht oder. C verwendet für

    Quellcode

    1. false = 1;
    2. true = 0;


    :?: Kannst du mir noch erklären wo und wie du jetzt Backtracking benutzt und was die Funktion inline bool test_feld(int feld[9][9]) eigentlich macht, steig ich irgendwie net so ganz dahinter?! Und was bedeutet inline?

  • also genau das was ich hier tue:

    Quellcode

    1. check = (s_matrix [j][i]); //Ist das Feld schon belegt (alle Felder sind von vorne mit "0" belegt)
    2. if ( check == 0 ) check = test_ispalte(&s_matrix[0][i],Laufzahl); //Test Spalte (Funktion) wenn "0" dann OK
    3. if ( check == 0 ) check = test_jzeile(&s_matrix[j][0],Laufzahl); //Test Zeile (Funktion) wenn "0" dann OK
    4. if ( check == 0 ) check = test_box(&s_matrix[0][0],j,i,Laufzahl); //Test 3*3Feld (Funktion) wenn "0" dann OK

  • Hm ein Sudoku ist doch ne Frage der Intelligenz, das heisst, man kann es maschinell nur durch ausprobieren lösen ? Wie ineffektiv 8)

    Nee - ma ne andere Frage:
    Also so ein olles Rätsel erstellen ist ja nicht das Problem nur, man trägt in
    jede Zeile oder Spalte die Ziffern von 1 bis 9 ein und muss diese dann nicht-identisch permutieren lol eine S9-Gruppe ? ;)

    Die Frage ist: wieviele Möglichkeiten gibt es denn ? sind das etwa (9 ! ) *(8 !) * (7 !) ... * (2 !) ? Weil aus der Eindeutigkeit könnte man dann errechnen, wieviele Ziffern man HÖCHSTENS weglassen kann, damit das Rätsel noch eindeutig bleibt ? Oder halt wiviele Ziffern noch dastehen dürfen, damit es eindeutig lösbar ist - muss es ja, sonst isses ja langweilig ;)

  • Zumindest kommt man durch ausprobieren 100%ig auf eine Lösung.

    Hier mal zu deiner Frage zur Anzahl der Möglichkeiten:

    http://de.wikipedia.org/wiki/Sudoku
    Die Zahl der möglichen 9 × 9-Sudokus beträgt nach Berechnung von Bertram Felgenhauer (im Jahr 2005) 6.670.903.752.021.072.936.960. Diese Zahl ist gleich 9! · 722 · 27 · 27.704.267.971, der letzte Faktor ist eine Primzahl.

    Durch triviale Umformung kann diese Konstante in die Finis-Normalform überführt werden, die in diesem Fall sogar einer Primfaktorzerlegung gleich kommt: 7 · 5 · 38 · 220 · 27.704.267.971. Die Zahl wurde unabhängig davon durch Ed Russell bestätigt. Nach Ed Russell und Frazer Jarvis gibt es 5.472.730.538 Möglichkeiten bei Berücksichtigung von Symmetrien. Die Zahl gültiger 16 × 16-Sudokus ist unbekannt.

  • Aber einen Tipp wie ich das ganze jetzt machen kann hat keiner? Oder soll ich einfach die frage nochmal eindeutig formulieren.

    Ich möchte gerne erklärt haben wie ich Sudokurätsel erstellen kann. Dabei ist mir nicht wichtig wie viele Felder ich maximal freilassen darf oder in welcher Anordnung diese zu einander stehen. Mir geht es darum zufällige ausgefüllte Felder zu erstellen, die dann weiter verarbeitet werden können.

    Wie kann ich das machen?

  • Try and Error. Besetze die Felder irgendwie zufällig (aber zulässig) und probier am Schluss ob der PC es selber Lösen kann. Was genialeres würde mir da auch nicht einfallen.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]