Sudoku

[NicNacMan]

hi,

diese sudoku rätsel aus japan dürften inzwischen bekannt sein
(sonst einfach mal googlen Sudoku).

ich hab mich mal an einem kleinen prog versucht, das diese rätsel lösen soll.
die einfachen schafft es ohne probleme, aber bei den schweren,
wo sich die möglichen wege verzweigen muss man immer noch per hand nachhelfen.
da werde ich mich aber demnächst nochmal dran versuchen.

würde mich über verbesserungsvorschläge zu funktionen,
design, aber auch zum code freuen.

thx nicnacman

[edit]
ich hab nur eine komponente verwendet: RakUndoRedo
für die rückgängig funktion
[/edit]

[Flocke]

Zitat von negaH:

Viel interessanter dürfte es nun sein Sudoku Games per Machine zu erzeugen. Dabei aber nicht wie fast alle Programme per Zufall ein Game zu erzeugen und es dann so lange zu reduzieren wie es nur eine Lösung gibt. Sondern eben gezielt schwierige Games zu konstruieren.

Da hab' ich auch schon drüber nachgedacht

Mein Ansatz wäre:
1. Fange an mit einem leeren Brett (Spielnummer = 0, Faktor = 1)
2. Zähle die Anzahl der möglichen Züge (Anzahl)
3. Wähle einen dieser Züge per Zufall und setze die Zahl (Spielnummer = Spielnummer + Faktor * Zug, Faktor = Faktor * Anzahl)
4. Vereinfache die erhaltene Stellung rein logisch (Verfahren je nach gewähltem Schwierigkeitsgrad)
5. Wenn es noch freie Felder gibt, dann fahre fort mit (2)
6. Fertig. Das nach (3) erhaltene Brett ist ein Rätsel mit genau einer Lösung, die vollkommen logisch ermittelt werden kann (hat man ja gerade in (4) getan).

Je nach Schwierigkeitsgrad kann man bei (4) unterschiedlich komplizierte Verfahren einsetzen (Hidden pairs / Pointing pairs / etc.).

Will man ein Spiel aus der Nummer wiederherstellen, dann nimmt man bei (3) einfach keine Zufallszahl sondern (Zug = Spielnummer mod Anzahl, Spielnummer = Spielnummer div Anzahl).

Hatte allerdings noch nicht die Zeit, dass mal in der Realität auszuprobieren.

[negaH]

@Flocke:

das ist mein bisheriger Ansatz und setzt eben auch voraus das man alle bekannten Tricks implementiert hat. Schaut man sich aber alle diese Tricks an so kann man sie in wenige Gruppen einteilen. Die meisten schwierigen Tricks basieren aber immer auf der kombinatorischen Analyse, sprich Entscheidungsketten und deren Beweis per Kontradiktion. Algorithmisch heist das das man per Program einen Entscheidungsbaum benutzt der lange Ketten bildet die sich in den meisten Fällen gegenseitig ausschließen. Das Trial & Error Verfahren ist im Grunde so ein Ding, halt rekursiv und nur auf ein Teilproblem beschränkt.

Klar per Trial & Error kann jeder selbst mit der simpelsten Lösung, so wie igel457, selbst mit einem ziemlich schlechtem Source das Problem lösen, heutige Computer sind eben leistungsstark.

Um aber für den Menschen anspruchsvolle Games zu erzeugen muß der Computer auf logisch lösbaren Kombinationen aufbauen.

Schade das ich keine Zeit habe. Und bisher wüsste ich auch nicht mit welchen Datenstrukturen so ein Entscheidungsbaum aufzubauen wäre. Es gibt aber zb. bei der Entwicklung mit FPGA per VHDL Synthesetools die per mathematischen Verfahren riesige Matrizen von boolschen Formeln auf ein Minimum reduzieren können. Das entstehende Resultat aus logischen Verknüpfungen repräsentiert dann den Source des VHDLs und wird in die FPGA Hardware gepresst. Auf grund meiner Erfahrungen muß ich sagen das diese Sythesetools super Arbeit leisten und oft hochkomplexe boolsche Formeln auf unerwartete Weise reduzieren. Eventuell müsste man sich mal in diese Richtung orientieren.

Gruß Hagen

[Amateurprofi]

Nachdem das Thema Sudoku, so scheint es, in aller Munde ist, möchte ich Euch auch meine Version nicht vorenthalten. Sicherlich nicht perfekt aber ....

[Thanatos81]

//Edit

Bitte löschen, sollte eine PN werden

[JJAnke88]

Hallo, ich habe mich selbst auch einmal an einem Sudoku-Programm versucht

Allerdings habe ich Probleme bei der Überprüfung ob eine Zufallszahl in dem Quadrat
schon vorkommt..

Vielleicht könnt ihr mir ja helfen..

MFG

Edit:

Ich habe einen Kommentar an die Stelle gesetzt wo ich hilfe brauche^^

EDIT 2: KEINER eine Idee?

[Filestricker]

@NicNacMan:
Folgendes Problem bei deinem Progrämmchen. Die internationalen Sudoku-Standards (jaja, gibt es nicht, aber ich kenne sie so, deswegen muss das ja stimmen, oder? ) sehen vor, dass die Diagonalen ebenfalls die übliche Vorschrift (jede Zahl von 1-9 genau einmal enthalten) erfüllen müssen. Oder liege ich da falsch? Zumindest die Rätsel, die ich kenne, waren so aufgebaut. Ansonsten . Kann mir vielleicht jemand auch ein Programm mit Quellcode geben, das genau das Gegenteil macht, also nicht das Rätsel löst, sondern eins erstellt, das lösbar ist?

Vielen Dank schonmal für eure vielen Antworten...

[Matze]

Hallo JJAnke88, herzlich Willkommen!

Da in dieser Rubrik ein Programm vorgestellt wird, wäre es gut, wenn du Fragen zur eigenen Umsetzung in einer entsprechenden Delphi-Sparte posten würdest (Multimedia). Das Programm aus dem ersten Beitrag ist übrigens Open-Source, evtl. kannst du dort schon eine mögliche Umsetzung für dein Problem finden.

[Christian V.]

@JJAnke88
Ich habe dir die paar Zeilen geschrieben die dir gefehlt haben. Ich habe mir dann deinen restlichen Source noch schnell angeschaut, und bim beim Überprüfen des Quadrates auf Richtigkeit nicht drausgekomen, und habe mir das mal angeschaut. jedefalls enthielt der HilfArray nicht die von dir benötigten Informationen, deshalb habe ich das auch noch umgeschrieben.(Nebenbei noch den Quelltext an dem ich arbeiten usste umformatiert, ich hoffe du kannst ihn so nicht schlechter lesen , ne echt, an dem musst du arbeiten, das sieht ja schrecklich aus). So müsste die Funktion(pruf) funktionieren.(Ich habe nur die Funktion für die Quadranten angeschaut und umgeschrieben. Ich denke der Rest funktioniert.)
Zudem wäre eine Fehlermeldung hilfreich, die Sagt an welcher Stelle der Fehler liegt. Allerdings musst du dich nun mit einem neuen Problem herumschlagen: Es werden nicht Alle Felder ausgefüllt wenn ich auf NewGame drücke, die hälfte der Felder bleibt leer.

Delphi-Quellcode:

function CHECK(XKORD,YKORD,AZAHL: BYTE): BOOLEAN;
var qx,qy,temp,i,i2: BYTE;
begin
  CHECK := TRUE;
  {REIHE}
  for I:=1 to 9 do begin
    if  I <> XKORD then begin
      if Sudoku[I,Ykord] = AZAHL then begin
        CHECK := FALSE;
        Exit;
      end;
    end;
  end;
{SPALTE}
  for I:= 1 to 9 do begin
    if I <> Ykord then begin
      if Sudoku[Xkord,i] = AZAHL then begin
           CHECK := FALSE;
        EXIT;
      end;
    end;
  end;
{QUADRAT}
  qx:=(xKord-1) div 3 +1;
  qy:=(yKord-1) div 3 +1;
  for i:= 1 to 3 do begin
    for i2:= 1 to 3 do begin
      if Sudoku[(qx-1)*3+i,(qy-1)*3+i2]=AZahl then begin
        check:=false;
        exit;
      end;
    end;
  end;
end;

///////////////////////////////////////////////////////////////
procedure tform1.pruf;
var
    i,j,x,y,z: BYTE;
    rechts,unten,xkord,ykord: BYTE;
    hilfe : ARRAY[1..9] OF BYTE;
    n,m : BYTE;
begin
  // Initalisierung
  dzahl := FALSE;
  xkord := 1;
  ykord := 1;
  z:= 0;
  //REIHE
  for y:= 1 to 9 do begin
    for i:=1 to 9 do begin
      for j:=1 to 9 do begin
        if j<>i then begin
          if Zahl[i,y]=Zahl[j,y] then begin
            dzahl := true;
            doppelt;
            exit;
          end;
        end;
      end;
    end;
  end;
  //SPALTE
  for x:= 1 to 9 do begin
    for i:= 1 to 9 do begin
      for j:= 1 to 9 do begin
        if i<> j then begin
          if Zahl[x,i] = Zahl[x,j] then begin
            dzahl := true;
            doppelt;
            exit;
          end;
        end;
      end;
    end;
  end;
  //Quadrate
  for rechts := 1 to 3 do begin
    for unten := 1 to 3 do begin
      for x:= 1 to 3 do begin
        for y:= 1 to 3 do begin
          case rechts of
            1 : xkord := x;
            2 : xkord := x+3;
            3 : xkord := x+6;
          end;
          case unten of
            1 : ykord := y;
            2 : ykord := y+3;
            3 : ykord := y+6;
          end;
          for m:= 1 to 3 do begin
            for n:= 1 to 3 do begin
              if (m<>x)OR (n<>y) then begin
                if Zahl[xKord,yKord]=Zahl[(rechts-1)*3+m,(unten-1)*3+n] then begin
                  dzahl := true;
                  doppelt;
                  exit;
                end;
              end;
            end;
          end;
        end;
      end;
    end;
  end;
if dzahl = false then showmessage('Ihre Lösung ist richtig');
end;

Und Bitte halte in Zukunft deinen Quelltext Ordentlicher. Dazu gehört ordentlich Einrücken, und die Begins(Ja, ich weiss, die kann man in bestimmten Fällen weglassen, ist ja ne supersache, aber nicht ÜBERALL WOS NUR GEHT. Das macht den Code sehr schwer Nachvollziehbar wenn überall die end's Fehlen bei for-schleifen.)
Das nächste: hast du den Code eigentlich blind eingetippt? Ohne einmal auf den Monitor zu schauen? Sonst wäre dir sicher aufgefallen, dass du CAPSLOCK eingeschaltet hattes. Der Compiler macht sich daraus zwar keinen Unterschied, aber das menschliche Auge schon. Es ist sehr viel angegnehmer wenn man lowercase(ich meine jetzt hier vor allem Sachen wie end for begin, halt alle reserved words) schreibt.

@Filestricker
Schau dir mal meine Unit an die ich in diesem Forum gepostet habe(class TSudoku). Damit kannst du im Prinzip Sudokus erzeugen. Vorgehensweise: Du setzt zu Begin per Zufall ein paar werte so, dass Sie die "Sudoku Regeln" nicht verletzen. Dann rufst du die Backtracking Methode auf. Anschliessend Entfernst du zufällig mehrere Felder so, dass es per Heuristik-Algorithmus noch lösbar ist. Dann hast ud ein "gültiges" Sudoku mit nur einer Lösung.
Ich werde allerdings diese Funktion in nächster Zeit noch hinzufügen, sodass man die Lösungsfunktionen nicht "zweckentfremden"muss.