Problem im Umgang mit Sets

[Salazriel]

Also einen schönen guten Abend erstmal.

Ich möchte als Projektarbeit für die Schule ein Sudoku-Generator und -Löser programmieren. Der Ansatz beim Lösen ist dabei folgender: in einem leeren Sodoku könnte in jedem Feld jede Zahl stehen, sprich die 'FeldMenge' jeder Zelle ist [1,2,3,4,5,6,7,8,9]. Ist aber z.B. in der Zeile eine 1, so wird aus den FeldMengen der restlichen 8 Zellen dieser Zeile die 1 gelöscht, Spalten und Blöcke analog. Nach Eingabe des Sudokus (Generator verschiebe ich erstmal in die Zukunft ^^) soll das Programm die FeldMengen der einzelnen Zellen reduzieren, wenn sie nur noch aus einer Zahl besteht, so wird diese Zahl in die Zelle geschrieben und die FeldMengen der Zeile, der Spalte und des Blockes werden wieder verkleinert. Irgendwann müsste das Sudoku gelöst sein.
Auf dem Formular liegen zwei Instanzen von TStringGrid, Nr.1 ist 9x9 und soll das Sudoku darstellen, Nr.2 gibt die RestMenge der angeklickten Zelle aus (wird dann verborgen, ist eigentlich nur zur Überprüfung da).

Delphi-Quellcode:

type
  Zahlen = Set of 1..9; //Menge der Zahlen, die in einem Feld stehen könnten

var
  Form1: TForm1;
  FeldMenge: Array [0..8,0..8] of Zahlen;


implementation

{$R *.dfm}

procedure TForm1.FormKeyPress(Sender: TObject; var Key: Char);
begin
If (Key in ['1'..'9']) and Stringgrid1.focused
then                     //dient der Eingabe der Zahlen in das gewählte Feld
  begin
  StringGrid1.cells[StringGrid1.col,StringGrid1.row]:=Key;
  RestMengeNeuZuOrdnen(strtoint(Key));
  end;

end;

procedure TForm1.FormCreate(Sender: TObject);
var i,j:integer;
begin
For i:=0 to 8 do
  For j:=0 to 8 do
    FeldMenge[i,j]:=[1,2,3,4,5,6,7,8,9]    //in jedem Feld kann
                                          // zu Beginn jede Zahl stehen
end;



procedure TForm1.StringGrid1Click(Sender: TObject);
begin
RestMengeAnzeigen;
end;



procedure TForm1.RestMengeNeuZuordnen(EingegebeneZahl:integer);
var NeueZahl:Zahlen;
    i:integer;
begin
FeldMenge[StringGrid1.col,StringGrid1.row]:=[]; //da bereits eine Zahl drinsteht
For i:=0 to 8 do
    begin
    FeldMenge[StringGrid1.col,i]:=FeldMenge[StringGrid1.col,i]-NeueZahl;
    FeldMenge[i,StringGrid1.row]:=FeldMenge[i,StringGrid1.row]-NeueZahl;
//Die Zahl aus den Restmengen der Zellen der gleichen Spalte und Zeile löschen)
    end;


end;

procedure TForm1.RestMengeAnzeigen;
var RestMengeDerZelle:Zahlen;
begin
RestMengeDerZelle:=FeldMenge[StringGrid1.col,StringGrid1.row];

If 1 in RestMengeDerZelle then Stringgrid2.Cells[0,0]:='1';
If 2 in RestMengeDerZelle then Stringgrid2.Cells[1,0]:='2';
If 3 in RestMengeDerZelle then Stringgrid2.Cells[2,0]:='3';
If 4 in RestMengeDerZelle then Stringgrid2.Cells[0,1]:='4';
If 5 in RestMengeDerZelle then Stringgrid2.Cells[1,1]:='5';
If 6 in RestMengeDerZelle then Stringgrid2.Cells[2,1]:='6';
If 7 in RestMengeDerZelle then Stringgrid2.Cells[0,2]:='7';
If 8 in RestMengeDerZelle then Stringgrid2.Cells[1,2]:='8';
If 9 in RestMengeDerZelle then Stringgrid2.Cells[2,2]:='9';
//geht das irgendwie eleganter ?

StringGrid1.SetFocus;
end;

end.

Das Problem: es funktioniert nicht! Gebe ich z.B. in [0,0] eine Zahl ein und klicke auf [0,1], so zeigt er mir als FeldMenge [1,2,5,6] an -unabhängig von der eingegebenen Zahl. Klicke ich nun auf ein Feld, das nicht in der selben Spalte oder Zeile liegt, so gibt er mir [1,2,3,4,5,6,7,8,9] aus, was ja auch stimmt.
Klicke ich dann aber wieder auf [0,1], so gibt er mir wieder [1,2,3,4,5,6,7,8,9] aus!


Ich weiß ehrlich gesagt überhaupt nicht, wo mein Fehler liegt und ich wäre für jede Hilfe sehr dankbar!

[Amateurprofi]

Zitat von Salazriel:

Delphi-Quellcode:

procedure TForm1.RestMengeNeuZuordnen(EingegebeneZahl:integer);
var NeueZahl:Zahlen;
    i:integer;
begin
FeldMenge[StringGrid1.col,StringGrid1.row]:=[]; //da bereits eine Zahl drinsteht
For i:=0 to 8 do
    begin
    FeldMenge[StringGrid1.col,i]:=FeldMenge[StringGrid1.col,i]-NeueZahl;
    FeldMenge[i,StringGrid1.row]:=FeldMenge[i,StringGrid1.row]-NeueZahl;
//Die Zahl aus den Restmengen der Zellen der gleichen Spalte und Zeile löschen)
    end;
end;

NeueZahl hat einen undefinierten Zustand, also reduzierst du deine Sets um undefinierte Mengen.
So sollte es funktionieren.

Delphi-Quellcode:

procedure TMain.RestMengeNeuZuordnen(EingegebeneZahl:integer);
var NeueZahl:Zahlen;
    i:integer;
begin
   FeldMenge[StringGrid1.col,StringGrid1.row]:=[]; //da bereits eine Zahl drinsteht
   For i:=0 to 8 do begin
      FeldMenge[StringGrid1.col,i]:=FeldMenge[StringGrid1.col,i]-[EingegebeneZahl];
      FeldMenge[i,StringGrid1.row]:=FeldMenge[i,StringGrid1.row]-[EingegebeneZahl];
      //Die Zahl aus den Restmengen der Zellen der gleichen Spalte und Zeile löschen)
   end;
end;

Zitat von Salazriel:

Delphi-Quellcode:

procedure TForm1.RestMengeAnzeigen;
var RestMengeDerZelle:Zahlen;
begin
RestMengeDerZelle:=FeldMenge[StringGrid1.col,StringGrid1.row];
If 1 in RestMengeDerZelle then Stringgrid2.Cells[0,0]:='1';
If 2 in RestMengeDerZelle then Stringgrid2.Cells[1,0]:='2';
If 3 in RestMengeDerZelle then Stringgrid2.Cells[2,0]:='3';
If 4 in RestMengeDerZelle then Stringgrid2.Cells[0,1]:='4';
If 5 in RestMengeDerZelle then Stringgrid2.Cells[1,1]:='5';
If 6 in RestMengeDerZelle then Stringgrid2.Cells[2,1]:='6';
If 7 in RestMengeDerZelle then Stringgrid2.Cells[0,2]:='7';
If 8 in RestMengeDerZelle then Stringgrid2.Cells[1,2]:='8';
If 9 in RestMengeDerZelle then Stringgrid2.Cells[2,2]:='9';
//geht das irgendwie eleganter ?
StringGrid1.SetFocus;
end;

Du schreibst Zahlen in die Zellen, aber wenn eine Zahl nicht in der Menge enthalten ist, löscht du sie nicht aus der Anzeige.
So sollte es funktionieren.

Delphi-Quellcode:

procedure TMain.RestMengeAnzeigen;
var RestMengeDerZelle:Zahlen;
   r,c,n:integer;
begin
   RestMengeDerZelle:=FeldMenge[StringGrid1.col,StringGrid1.row];
   for r:=0 to 2 do
      for c:=0 to 2 do begin
         n:=r*3+c+1;
         if n in RestMengeDerZelle then Stringgrid2.Cells[c,r]:=chr(n+48)
            else Stringgrid2.Cells[c,r]:='';
      end;
   StringGrid1.SetFocus;
end;

Du weißt aber, daß du die Zahlen nicht nur in gleichen Zeilen und Spalten entfernen mußt sondern auch im jeweiligen 3x3-Block?

Und ansonsten schau mal hier: Uni-Wien

[Salazriel]

Ok Riesendank erstmal, du hast mir wirklich geholfen, ich dachte nämlich das ich die Funktionsweise von Sets irgendwie missverstanden habe (und das mit den Blocks habe ich erst später integriert, aber wenn nicht mal die Zeilen und Spalten funktionieren... ^^).
Nun ist das Programm soweit, dass man Zahlen eingeben kann und die RestMengen der Zeile, Spalte und des Blocks entsprechend reduziert werden. Nun soll das Programm erkennen, das die RestMenge nur aus einer Zahl besteht und diese dann in die Zelle schreiben.

Günstig wäre eine Funktion, die die Größe eines Sets ausgibt, wenn diese 1 ist, könnte man die FeldMenge der Zelle, in der die FeldMenge im Rahmen von RestMengeNeuZuordnen verändert wird, auf den Inhalt von 1..9 untersuchen und (es gibt ja nur eins) das Ergebnis dann in die entsprechende Zelle schreiben.
Ums kurz zu machen: So eine Funktion ist mir unbekannt.

Mein alternativer Lösungsansatz dazu ist jedoch etwas arg 'holprig'.

Untersuche die FeldMenge jeder Zelle, deren FeldMenge im Rahmen von RestMengeNeuZuordnen verändert wird, auf das Beinhalten von einer Zahl und das Nichtbeinhalten der anderen Zahlen, wenn das zutrifft, gib die beinhaltete Zahl aus.
Das Problem liegt dabei bei "auf das Beinhalten von einer Zahl und das Nichtbeinhalten der anderen Zahlen", hier fällt mir nur

Delphi-Quellcode:

For i:=1 to 9 do
  If (i in FeldMenge[x,y]) and not (((i+1) mod 9) in FeldMenge[x,y]) and not (((i+2) mod 9) in FeldMenge[x,y]){.....
  ....} and not (((i+8) mod 9) in FeldMenge[x,y]) then GibZahlaus ;

Das muss doch eleganter gehen!

[Amateurprofi]

Zitat von Salazriel:

Delphi-Quellcode:

For i:=1 to 9 do
  If (i in FeldMenge[x,y]) and not (((i+1) mod 9) in FeldMenge[x,y]) and not (((i+2) mod 9) in FeldMenge[x,y]){.....
  ....} and not (((i+8) mod 9) in FeldMenge[x,y]) then GibZahlaus ;

Das muss doch eleganter gehen!

Ja, das geht deutlich eleganter, vor allem schneller, ist aber etwas tricky und nicht beliebig auf ähnliche Probleme übertragbar.

Delphi-Quellcode:

function SingleValueInSet(v:zahlen):integer;
begin
   result:=0;
   if (Word(v)>0) and (Word(v) and (Word(v)-1) = 0) then // dann ist nur ein Wert im Set
      while not odd(word(v)) do begin
         inc(result);
         Word(v):=Word(v) shr 1;
      end;
end;

Der erste Teil (Prüfung ob nur ein Bit im Set gesetzt ist) stammt nicht von mir (von negah).

Und die folgende Assembler Version dürfte erheblich schneller sein.

Delphi-Quellcode:

function ASingleValueInSet(v:zahlen):integer;
asm
      movzx edx,ax     // v auf Cardinal erweitert in EDX
      bsf   eax,edx    // Index des untersten gesetzten Bits in EAX
      bsr   edx,edx    // Index des obersten gesetzten Bits in EDX
      xor   edx,eax    // Wenn mehrere Bits gesetzt sind (oder keins, oder Bit 0), ist ZF=1
      jz    @end       // Nur 1 Bit gesetzt, (EAX enthält den Wert) oder keins oder Bit 0 (und EAX ist 0)
      xor   eax,eax    
@end:
end;

[himitsu]

Zitat von Amateurprofi:

Delphi-Quellcode:

function SingleValueInSet(v:zahlen):integer;
begin
   result:=0;
   if (Word(v)>0) and (Word(v) and (Word(v)-1) = 0) then // dann ist nur ein Wert im Set
      while not odd(word(v)) do begin
         inc(result);
         Word(v):=Word(v) shr 1;
      end;
end;

Bei dieser Art der Typkonvertierung muß man nur aufpassen.
Also der neue Typ muß genaudo groß sein, wie das Set, sonst meckert der Compiler.

Set = 1 Byte > Byte
Set = 2 Byte > Word
Set = 4 Byte > LongWord
...

Hier stimmt das Word aber > 10 Werte / 8 Bit = 1,25 = 2 Byte

Und das Verfahren ist dort etwas erklärt
http://www.delphipraxis.net/internal...ight=countbits

[alzaimar]

Du willst also prüfen, ob in der Menge nur eine Zahl enthalten ist, oder wie?
If Menge = [Zahl] Then Oder

Delphi-Quellcode:

For i:=1 to 9 do if Menge=[i] Then 
  Showmessage(Format('%d ist als einziges in der Menge enthalten',[i]));

[Amateurprofi]

Zitat von himitsu:

Zitat von Amateurprofi:

Delphi-Quellcode:

function SingleValueInSet(v:zahlen):integer;
begin
   result:=0;
   if (Word(v)>0) and (Word(v) and (Word(v)-1) = 0) then // dann ist nur ein Wert im Set
      while not odd(word(v)) do begin
         inc(result);
         Word(v):=Word(v) shr 1;
      end;
end;

Bei dieser Art der Typkonvertierung muß man nur aufpassen.
Also der neue Typ muß genaudo groß sein, wie das Set, sonst meckert der Compiler.

Set = 1 Byte > Byte
Set = 2 Byte > Word
Set = 4 Byte > LongWord
...

Hier stimmt das Word aber > 9 Werte / 8 Bit = 1,125 = 2 Byte

Deshalb schrieb ich ja "ist aber etwas tricky und nicht beliebig auf ähnliche Probleme übertragbar".
Aber deine Rechnung 9 Werte/ 8 Bit = 1.125 = 2 Byte stimmt so nicht ganz.
In diesem Fall sind es 10 Bits (0..9). Mir war aufgefallen, daß bei diesem Set of 1..9 die 1 nicht etwa Bit 0 belegt (wie ich erwartet hätte) sondern Bit 1.
Wie der Compiler wann wieviel Platz reserviert ist mir im Moment noch nicht ganz klar.
Zum Beispiel
type zahlen=Set of 8..16; braucht 2 Bytes
type zahlen=Set of 7..16; braucht 4 Bytes
type zahlen=Set of 15..16; braucht 2 Bytes
aber : type zahlen=Set of 254..255; braucht 1 Byte
Alles Delphi 2005. Mag sein; andere Versionen compilieren das anders.
Vielleicht kennt ja jemand die genauen "Spielregeln" und erklärt sie.

[himitsu]

Zitat:

Wie der Compiler wann wieviel Platz reserviert ist mir im Moment noch nicht ganz klar.

Das ist wohl ein Problem der Optimierung.

Immerhin gibst du bei diesen Sets die Werte des zugehörigen Enum-Typs vor.

Delphi-Quellcode:

type x = Set of 15..16; 

type z = 15..16;
  x = Set of z; 

type z = (a=15, b=16);
  x = Set of z;

Da kann es sein, daß der Compiler bei einigen Varianten auf eine Umrechnung verzichtet und sich so beim Vergleich der Sets etwas arbeit erspart?

Diese automatisch generierten Sets sind halt immer etwas anfällig.

Delphi-Quellcode:

// 1 Byte
type z = (a=0, b=1);
  x = Set of z;

// 2 Byte
type z = (a=14, b=15);
  x = Set of z;

Und dann kommen da auch ab und zu noch andere Faktoren ins Spiel.

Delphi-Quellcode:

type x = (a, b);
  {$MINENUMSIZE 2}
  z = (c, d);

x = 1 Byte
z = 2 Byte

[edit]
Zitat-, statt Delphi-Tags

[Salazriel]

Da ich mit dem Umgang mit Bits und dem Assembler überhaupt nicht auskenne (ist ja noch im Rahmen des Schulunterrichts ^^ )habe ich es so gemacht wie "alzaimar" es vorgeschlagen hat, auch wenn ich es für Trickserei ohne Ende halte und selbst drauf hätte kommen können.
So weit funktionierts jetzt, Sudokus die "sehr einfach" sind, können sogar schon komplett gelöst werden.
http://www.hib-wien.at/leute/wurban/..._strategie.pdf @amateurprofi danke für den link
Der offizielle Begriff dafür ist wohl Naked Singles. Jetzt möchte ich mindestens noch die Hidden Singles integrieren.
Mein Ansatz dafür wäre der, dass (am Beispiel einer Zeile):
Man nehme die FeldMenge einer Zelle und ziehe davon die FeldMengen aller anderen Zellen dieser Zeile ab, besteht diese reduzierte RestMenge aus genau einer Zahl, so muss diese Zahl in dieser Zelle stehen.
Über die Umsetzung des Ansatzes bin ich ehrlich gesagt recht stolz, hat mich doch einiges an Denkarbeit gekostet ^^

Delphi-Quellcode:

procedure TForm1.HiddenSingles;
var i,Spalte,Zeile,Anfangszelle,Verschiebung:integer;
    RestMenge:Zahlen;
begin
//Zeilenweise
For Zeile:=0 to 8 do
  For Anfangszelle:=0 to 8 do
    begin
    RestMenge:=FeldMenge[Anfangszelle,Zeile];
    For Verschiebung:=1 to 8 do
      begin
      RestMenge:=RestMenge-FeldMenge[(Anfangszelle+Verschiebung) mod 9,Zeile];
      For i:=1 to 9 do
        If RestMenge=[i]
        then
          begin
          StringGrid1.cells[Anfangszelle,Zeile]:=Inttostr(i);
          RestMengeNeuZuOrdnen(i,Anfangszelle,Zeile);
          end;
      end;
    end;
//Spaltenweise

//Blockweise
end;


procedure TForm1.RestMengeNeuZuordnen(EingegebeneZahl,Spalte,Zeile:integer);
var i:integer;
begin
FeldMenge[Spalte,Zeile]:=[]; //da bereits eine Zahl drinsteht
For i:=0 to 8 do
    begin
    FeldMenge[Spalte,i]:=FeldMenge[Spalte,i]-[EingegebeneZahl];
    FeldMenge[i,Zeile]:=FeldMenge[i,Zeile]-[EingegebeneZahl];
//Die Zahl aus den Restmengen der Zellen der gleichen Spalte und Zeile löschen)
    end;

Block.x:=1+(Spalte div 3);
Block.y:=1+(Zeile div 3);
RestMengenDerZellenDesBlocksNeuZuordnen(EingegebeneZahl,Block.x,Block.y);

NakedSingles;
HiddenSingles;
end;

Aber: es funktioniert nicht -.-
Mal ganz davon abgesehen, dass ich meinen Fehler nicht finde, ist das Programm nun iwie in der Lage, sehr schnell (komplett gelöste) Sudokus zu erstellen (einfach in einen Block die Zahlen von 1-9 eintippen)

Ich bin 'etwas' verwirrt ^^

[Salazriel]

wirklich keiner eine idee?