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]

[NicNacMan]

hi, erstmal danke für die vorschläge.

also, wenn ich das alles richtig verstanden habe, dürfte das auch dann kein problem mehr sein,
verschieden schwere rätsel zu lösen/erstellen (bei denen ja nur verschieden viele zahlen fehlen).
mein problem ist jetzt nur, das rechnen mit den bitcodierten Cardinals.
shl sagt mir zwar was (du hattest das glaube ich auch schon ein paar mal im form erklärt), aber benutzt hab ich das nie . naja, aber das werde ich dann jetzt mal ändern.

edit: so, hab noch n bisschen rum probiert:

Delphi-Quellcode:

var
  Field   : Array [1..9, 1..9] of TField  // record mit possible(Cardinal) und current(0..9)
  Row, Col: Array [1..9] of Cardinal;
  Block   : Array [1..3, 1..3] of Cardinal;

{...}

procedure OnFieldChange(Sender: TObject);
begin
  with TSudokuField(Sender) do
    begin
      Field[Xpos, Ypos].Current := Value;
      Col[Xpos] := Col[Xpos] and (1 shl oldValue);
      Col[Xpos] := Col[Xpos] or (1 shl Value);

      Row[Ypos] := Row[Ypos] and (1 shl oldValue);
      Row[Ypos] := Row[Ypos] or (1 shl Value);

      {...}
    end;
end;

funktioniert nur noch nicht so richtig: das löschen mit and funzt nicht richtig, obwohl es eigentlich so richtig sein müsste, oder?

naja, morgen gehts weiter...

nicnacman

[negaH]

 Row[Ypos] := Row[Ypos] and [b]not[/b] (1 shl oldValue); Gruß Hagen

[NicNacMan]

ah thx,
jetzt gehts.

aber was ist, wenn ich aus einer zeile, spalte, einem block einen wert lösche, der dort mehrmals enthalten ist.
dann fehlt er in der variable, ist aber in wirklichkeit noch da.

müsste ich dann bei jeder änderung die felder der betreffenden zeile, spalte, des blocks neu einlesen

Delphi-Quellcode:

Row[y] := 0;
for i := 1 to 9 do
  Row[y] := Row[y] or (1 shl Field[i, y].Current);

oder gibts da noch ne schönere möglichkeit?

nicnacman

[sECuRE]

Hi,

mmh, ihr wisst aber schon, dass gerade schwere Sudokus nicht einfach über das Ausschlussverfahren gelöst werden können?

Kann auch sein, dass ich mich täusche, ich durchschaue den Lösungsansatz, den ihr momentan benutzt, nicht ganz. Vielleicht kann einer ja mal einen kompletten Sourcecode posten?

cu

[NicNacMan]

die schweren rätsel sind ja nur schwer, weil man sich ein paar mal entscheiden muss, welche zahl man nimmt. aber nur ein weg ist richtig.
darum hat mein programm ja auch noch schwierigkeiten damit.
aber bei negahs vorschlag werden alle kombinationsmöglichkeiten gefunden,
da von der jeweiligen ausgangs situation rekursiv alle möglichkeiten durchgegangen werden.
(soweit ich das verstanden habe^^)
werde meinen code auch hier wieder posten, wenn er n bisschen aussagekräftiger ist.
im moment bastel ich aber noch an der rekursiven funktion.

nicnacman

[hflick]

Jesper Högström hat eine Variante entwickelt. Vielleicht kannst Du dort ein paar Dinge "abgucken", falls noch erforderlich

(google besser nach Jesper Hogstrom)

--
Holger

[NicNacMan]

thx, hab auf der suche nach jesper hogstrom auch noch ein paar andere seiten gute gefunden (wen s interessiert):
http://www.scanraid.com/sudoku.htm
http://www.urbanrim.org.uk/sudoku.htm
http://users.pandora.be/vandenberghe...html?how2solve

is natürlich klar, dass sich noch mehr leute damit befasst haben, aber das das sooo viele sind...
das demotiviert jetzt n bisschen, aber ich werd trotzdem weiter machen
hab ja jetzt einige neue lösungsmethoden (x-wing, swordfish, burma, ...) entdeckt.

ich weiß aber noch nicht, wie ich mit den bitcodierten cardinals schnittmengen rausbekommen kann.
bzw wie ich zählen kann wieviele werte enthalten sind, ohne eine schleife durchlaufen zu lassen.
mit anderen worten ich kann die "boolscher algebra" noch nicht so richtig anwenden (hab aber auch noch nicht danach gesucht).

gn8, nicnacman

[negaH]

Zitat:

ich weiß aber noch nicht, wie ich mit den bitcodierten cardinals schnittmengen rausbekommen kann.

Schnittmenge = A and B; also eine UND Verknüpfung aller Bits, übrig bleiben alle Bits die in allen Werten gesetzt sind. Vergleichbar mit Sets -> [A] * [B] in PASCAL.
Unions, Vereinigungsmenge = A or B; das Resultat enthält alle Bits die in A wie auch B gesetzt sind.

Zitat:

bzw wie ich zählen kann wieviele werte enthalten sind, ohne eine schleife durchlaufen zu lassen.

Bits zählen. Man kann dies per Schleife, per Lookup Tabelle oder per Berechnungenen machen. Suche mal nach BitCount, CountsOfBits(), BitWeigth(), Hamming Distance etc.

Willst du testen ob nur 1 Bit in deinen cardinals gesetzt ist so geht dies mit

if (A <> 0) and (A and (A -1) = 0) then Willst du das MSB eines Cardinals ermitteln dann mit

 t := A and -A; Gruß Hagen

[NicNacMan]

sooooo,

erstmal danke für die weiteren tipps.

ich hab in den letzten tagen nochmal komplett von vorne angefangen.
die felder sind jetzt auch schon zur designtime da, und können eigene hintergrundbilder speichern.
ein problem war, dass die 0 (wenn kein wert angegeben ist) im cardinal ja als 1 steht (1 shl 0 = 1)
daraufhin funktioniert das zählen der werte auch nicht.
und das löschen mit "and not" funktioniert auch nicht, wenn ein wert mehrmals in einer zeile/spalte/einem block enthalten ist.
hab mich jetzt so entschieden, dass beim ändern (per hand) alle werte neu eingelesen werden
und geprüft wird, welche werte noch möglich sind, ohne für zeilen/spalten/blöcke variablen anzulegen, die nur aktualisiert werden.
den algortihmus will ich dann so machen, dass zuerst alle werte in eine variable kopiert werden, um damit zu arbeiten, und danach wieder zurück, damit nicht nach jedem schritt alles neu gezeichnet wird.
das kann aber noch ein paar tage (wochen^^) dauern.

hier erstmal der vorläufigen code:

[Grishnak]

Ich habe mich ebenfalls an einem (Multi-)Sudoku-Solver versucht. Das Programm errechnet per Backtrac(k)ing alle möglichen Lösungen.

WICHTIG: bei (fast) leerem Feld nicht auf 'Lösen' drücken, da das Programm dann alle möglichen Sudokus ermitteln wird!

Mit Links-Click werden Zahlen gesetzt, mit Rechts-Click gelöscht.

Nach dem Lösen, kann man sich alle Lösungen über den ScrollBar anzeigen lassen.

Eine Erweiterung zum Sudoku-Generator folgt...