Solver

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Solver

Post by Manfred » Thursday 7. October 2010, 18:17

Mit diesem Thema möchte ich gerne über programmierte Löser diskutieren. Ulrich hatte mir geschrieben:
Monday 4-Oct-2010

... by: Ulrich
@Manfred: EXCEL & C: Sounds interesting. I use EXCEL and VB. Maybe, you can contct me by pm via the german str8ts forum in order to have some exchange of experience.

Mein Programm ist also in C# geschrieben und nutzt .NET mit dem Visual C# VCSExpress. Die Bedienoberfläche ist wie folgt:

[img]c:\str8ts\interface.jpg[/img]

und in Excel sieht das dann wie folgt aus:

[img]c:\str8ts\excel.jpg[/img]

Bei Path, File und Sheet gibt man die Excel-Datei und den Folder an. Mit "load Excel" wird Excel geladen und sichtbar gemacht. Mit "Excel to C#" läd sich C# das Problem in den internen Speicher, wobei eine spezielle Formatierung verlangt wird, die im Folder "Str8ts" als Template vorliegt und kopiert werden muss.

Leider habe ich nicht herausgefunden, wie man mit C#-Fernsteuerung die Hintergrundfarbe abfragen kann. Deshalb die spezielle Formatierung (Bold, Italic, etc.). In der internen Tabelle werden die Vorgaben durch deren Ziffer, schwarze leere Zellen als Null und schwarze Vorgaben als Minus Ziffer gespeichert. Leere weisse Zellen werden mit den Kandidaten 1..9 gefüllt. Außerdem werden die Strassen in 2 Matrizen (Row und Column) gespeichert, damit man sie später leicht finden kann. Die Log-Einträge ab Reihe 20 werden gelöscht.

Mit "Processing" startet eine unendliche Schleife, die dann endet, wenn keine Änderungen von den Strategien gemeldet wurden. Die Strategien können ein- und ausgeschaltet werden. Sie sind:

1. Primitive Löschung der Vorgaben oder später dann Lösungziffern (naked Singles) bei den Kandidaten der entsprechenden Reihen und Spalten.

2. "Spread" soll heissen, dass von den naked Singles entsprechend der Strassen-Länge Kandidaten gelöscht werden, die davor oder danach sind: Pro Strasse durch alle Singles.

3. "Neighbors" soll heißen, es wird jeder Kandidat in jeder Strasse untersucht, ob er mindestens eine durchgehende Strasse mit seinen Kandidaten-Nachbarn in dieser Strasse bilden kann. Falls nicht, wird er gelöscht.

4. "Naked" umfasst naked Twins (oder Pairs), Triples, Quads, etc. Sie werden pro Reihe, bzw. Spalte untersucht und von den anderen Zellen ausgeschlossen.

5. "Hidden" habe ich noch nicht geschrieben. Ich sehe noch keine Strategie, bei der ich sinnvoll hidden Singles erkenne, die sicher in der späteren Lösungs-Strasse vorkommen müssen und deshalb als Lösungsziffer eingetragen werden können. Was ich mir vorstelle ist, dass ich mir von Strategie 3 (Nachbarn) alle möglichen Lösungsstrings geben lasse und die überlagere, sodass eine verkürzte, aber notwendige Lösungs-Reihe entseht, wo man dann Hidden Singles suchen könnte... Hat jemand eine bessere Idee?

Nun noch einmal zu Strategie 3 (Nachbarn): Ich lasse ein "Fenster" über alle Kandidaten einer Strasse gleiten und untersuche die n mal n-Matrix auf Machbarkeit einer lückenlosen Strasse. Was ist aber, wenn folgendes eintritt:

8 8 x 8 8 8
7 7 x 7 7 7
6 6 x
x x 5 x x x
4 4 x
3 3 x
E3 E4 E5 E6 E7 E8

Untersucht werden soll Kandidat "5" in der Zelle E5. Offensichtlich kann mit den Nachbarn E3, E4, E6, E7 und E8 keine geschlossene 6er-Strasse (3,4,5,6,7,8) gebildet werden. Aber wie kann ich das sicher im Programm erkennen?

Die 5 müsste hier in E5 gelöscht werden, falls sie nicht in einem anderen Rollfenster (z. B. 1-6, 2-7, 4-9) doch eine geschlossene Strasse bilden kann.

An den Quersummen geht es nicht, die scheinen ausreichend zu sein. Alle Permutationen möchte ich nicht durchgehen müssen. Ein Ansatz wäre: "Naked Pairs" (Triples, Quads,...) erkennen und deren andere Kandidaten in der Submenge löschen. Damit würden dann Quersummen Null entstehen, die als Lücke erkannt werden könnten... Hat jemand eine bessere Idee?

Viel Spass beim Nachdenken, Manfred

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Re: Solver

Post by Manfred » Thursday 7. October 2010, 18:23

PS: Wie kriege ich hier Bilder rein?

User avatar
Ulrich
Posts: 86
Joined: Monday 24. May 2010, 20:05
Location: Region Augsburg München

Re: Solver

Post by Ulrich » Saturday 9. October 2010, 11:25

Bilder: als Dateianhang hochladen, dann in Text einfügen.
Ulrich
Str8ts addicted

User avatar
Ulrich
Posts: 86
Joined: Monday 24. May 2010, 20:05
Location: Region Augsburg München

Re: Solver

Post by Ulrich » Saturday 9. October 2010, 11:43

Mein aktueller Status: ich habe alle naked- und alle hidden-Fälle programmiert. Für die hidden ist einfach nur wichtig, dass die Strategie sich nur auf "sichere" Kandidaten beziehen kann, also die Ziffern, die in einer Straße vorkommen müssen.
Dann ist's relativ einfach. Beispiel Hidden pair.

Schleife über alle Zeilen.
Schleife über alle sicheren Ziffern der Zeile.
Wenn Ziffer genau zweimal vorkommt, merken.
Ende der Schleife über Ziffern.
Schleife über die gemerkten Ziffern.
Schleife über die weiteren gemerkten Ziffern.
Kommen beide in den gleichen zwei Spalten vor? wenn ja: hidden pair gefunden. Andere Zellkandidaten in den Zellen des hidden pair löschen.
Das gleiche nochmal über die Spalten.
Fertig.

Ich hoffe, die etwas improvisierte Beschreibung ist ausreichend verständlich.

Noch nicht zufrieden bin ich mit meiner Programmierung der gestrandeten Ziffern. Bisher betrachte ich nur die Straßen, in denen die zu prüfende Ziffer steht. Auch da gibt es noch Fälle die nicht erkannt werden. Aber auch dann, wenn wegen anderer Straßen bei drei Straßen in der Zeile oder Spalte eine Ziffer nicht möglich ist, klappt das noch nicht befriedigend.

Beispiel für das Problem innerhalb einer Straße: 145 - 2345 - 456

Mein Programm erkennt nicht, dass die 1 entfällt, weil die 2 und die 3 existieren. Es erkennt nicht, dass die erforderlichen Ziffern in nur einer Zelle stecken.
Manfred, kannst du das besser?
Ulrich
Str8ts addicted

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Re: Solver

Post by Manfred » Sunday 10. October 2010, 06:08

@Ulrich: Du formulierst genau auch mein Problem. Meine Lösung ist z. Zt. folgende:

Ich lagere die Analyse auf Subroutine rund um eine boolsche 9x9 Matrix M aus. Die sieht dann mit Deinem Beispiel folgendermassen aus:

[100110],[01110],[000111]

Da Deine Strasse die Länge 3 hat, brauchen wir nicht mehr Positionen. Die 1 (true) steht für das Vorhandensein der Ziffern 1 bis 9. Deine höchste Ziffer ist 6. Die Längssummen der Strasse sind [343] und die Quersummen [111331]. Das bringt uns zunächst nicht weiter, da alle Ziffern vorkommen und auch keine der 3 Zellen leer ist.

Jetzt gehe ich jeden Kandidaten durch, beispielsweise die 2 aus Zelle 2. Damit entfällt die Zelle 2 selbst als Analyseobjekt, alle anderen Kandidate der Zelle 2 werden Null: [010000]. Damit ergibt sich eine neue Quersumme für alle betrachteten Zellen: [110221].

Jetzt kann ich mein Anlalysefenster die Ziffern hoch gehen lassen: 1-3, 2-4. Die Strassen 3-5 und 4-6 betrachten wir jezt nicht, es geht ja um die 2. Bereits beim Fenster 1-3 ergibt sich eine Quersumme von [110], das kann keine Strasse ergeben. Eine Strasse ergäbe sich für [456], aber die betrachten wir jetzt nicht, wir sind ja bei Ziffer 2 von Zelle 2. Da jetzt auch Fenster 2 die Quersumme [101] ergibt, also keine Strasse möglich ist, ist klar dass die Ziffer 2 aus allen Kandidatenlisten der 3 Zellen entfernt werden kann.

Mit der 2 aus Zelle 2 ist nichts zu machen. Mein Programm würde also Dein Problem erkennen. Aber eben nicht das Problem, das ich beim ersten Beitrag formuliert habe:

[111111], [111111],[001000],[000011],[000011],[000011]
bei Analyse der 3 aus Zelle 3. Selbst wenn ich die 3 aus den anderen Zellen entferne:
[110111], [110111],[001000],[000011],[000011],[000011]
bleibt die Quersumme größer Null für alle Kandidatenziffern.

Auch hier kann man keine Strasse definieren, aber wie erkenne ich das? Ich würde z. Zt. die 3 aus Zelle 3 weiterleben lassen und nicht streichen.

Übrigens: ich wohne auch im Münchener Großraum: 82024 Taufkirchen.

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Bilder meines Solvers

Post by Manfred » Sunday 10. October 2010, 11:35

Hier sind jetzt meine 2 erwähnten Bilder:

Image
Image

Jens
Posts: 418
Joined: Sunday 25. July 2010, 14:55
Location: München

Re: Solver

Post by Jens » Monday 11. October 2010, 17:06

@Manfred: Da Excel und Str8ts mit vertauschten Koordinaten arbeiten und es für mich unmöglich ist, die Zellbezeichnungen simultan zu übersetzen, bitte ich Dich, die Vorgaben in Ex15 genauso einzusetzen wie es die Str8ts-Zelladresse erfordert. Unter Berücksichtigung der von Dir vorgestellten vereinfachten Inhalts-Kodierung der Zellen (leere schwarze Zellen sind gleich Null, gefüllte schwarze Zellen sind Negativ) sind die Vorgaben von Ex15 folgendermaßen:

a1=0, a4=7, a5=0, a7=1, a8=3, b4=0, c1=7, c2=8, c5=4, c5=0, d2=5, d6=0, d8=2, e2=0, e3=-1, e7=0, e8=0, f4=-9, f7=6, g4=0, g9=5, h1=2, h6=0, j5=0 und j9=0.

Nach der Eingabe erscheint die Str8ts-Matrix zwar als gespiegelt, aber alle Zelladressen stimmen überein und eignen sich, um auf dieser Basis Lösungsstrategien zu diskutieren. Die einfachen Orientierungshilfen links, rechts, oben und unten gelten dann natürlich nicht mehr und das "rechte obere Viertel" wird dann leider "linkes unteres Viertel."

Zu Deiner Denksportaufgabe, einen vernünftigen Weg zum Suchen von HIDDEN SINGLES zu finden, möchte ich Dich bitten, Dein Beispiel zur Fragestellung noch besser darzustellen, so daß man die Frage ohne Hyperintelligenz verstehen kann.
Gruß von Jens

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Re: Solver

Post by Manfred » Tuesday 12. October 2010, 05:36

@Jens:
Danke, dass Du Dir die Arbeit gemacht hast. Die Vorgabewerte liest mein Programm direkt aus Excel ein, das muss ich nicht noch einmal eingeben. Das werde ich jetzt nicht überprüfen. Der Vorteil von Excel ist ja, dass man alles schön graphisch überprüfen kann. Auch die Zwischenergebnisse werden laufend in Excel dargestellt und können schrittweise angehalten werden.

Wie Du aus meinen beiden Graphiken entnehmen kannst, gibt es einen Schalter, der die Darstellung des Lösungsweges in Excel- oder in Stuart-Notation erlaubt. Auch das ist längst gelöst. Im englischen Extreme Forum habe ich ja auch beide Notationen schon benutzt und angegeben.

Die Darstellung meiner Suche nach Hidden Singles werde ich demnächst lösen und dann einfach den Code veröffentlichen oder genau beschreiben. Ich glaube, mein Ansatz wird zum Ziel führen. Ich habe jetzt nur wenig Zeit, da meine 2 Enkel erst 4 Monate, bzw. 4 Jahre alt sind und viel Zuwendung beanspruchen (die ich Ihnen nur allzu gerne zukommen lasse

Hier ist schon mal der Code für die von mir beschriebene Spezial-Matrix für die Nachbarsuche:

private void MatrixInit(int lg)
{
int i, j;
for (i = 0; i < lg; i++)
for (j = 0; j < lg; j++)
Matrix[i, j] = false;
}

private void MatrixSet(int x, int y)
{
Matrix[x, y] = true;
}

private bool MatrixOK(int lg)
{
int i, j;
bool[] x = new bool[9], y = new bool[9];
for (i = 0; i < lg; i++) x = false;
for (j = 0; j < lg; j++) y[j] = false;
for (i = 0; i < lg; i++)
for (j = 0; j < lg; j++)
if (Matrix[i, j]) {x = true; y[j] = true;}
for (i = 0; i < lg; i++) if (x == false) return (false);
for (j = 0; j < lg; j++) if (y[j] == false) return (false);
return (true);
}

Benutzt wird sie dann in etwa so:

for (i1 = a; i1 < a + n; i1++) //a = Fensteranfang, n = Anzahl der notwendigen Fenster
{ // maximaler SpannenAnfang um testCH (bzw. str8tsI)
MatrixInit(lg);
for (j = anfang; j < ende; j++)
{ // ein Strasse
if (j == i) { MatrixSet(i - anfang, str8tsI - i1); continue; }
if (Rows) Text = feld[row, j]; else Text = feld[j, col]; // Rows zeigt, ob gerade eine Reihe
for (l = i1; l < i1 + lg; l++) // oder Spalte untersucht wird
{ // ein Segment
if (l == str8tsI) continue;
c = false;
str8tsCH = System.Convert.ToChar(l + 48);
if (Rows) c = Exists(row, j, str8tsCH);
else c = Exists(j, col, str8tsCH);
if (c)
{ MatrixSet(j - anfang, l - i1); }
} // ein Segment

} // eine Strasse
if (MatrixOK(lg)) return (1);

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Re: Solver

Post by Manfred » Wednesday 20. October 2010, 07:50

Zu meinem Beitrag vom 7.10.:
Jetzt habe ich endlich die Abfrage der Hintergrundfarbe herausgefunden und muss mich nicht auf die Font-Abfrage beschränken. Damit kann man auch testweise "Guess"-Tests z. B. in Rot eintragen:

private void Laden()
{
// feld laden
int row, col, i;
bool cellBlack;
for (row = 0; row < 9; row++)
for (col = 0; col < 9; col++)
{
range = (Excel.Range)worksheet.Cells[row + offsetRread, col + offsetCread];
cellBlack = (double)range.Interior.Color == 0.0;
if (!cellBlack && range.Value2 != null) feld[row, col] = System.Convert.ToString(range.Value2); //Kandidaten
if (!cellBlack && range.Value2 == null) feld[row, col] = "123456789"; //frei
if (cellBlack && range.Value2 != null) feld[row, col] = String.Concat("-", System.Convert.ToString(range.Value2)); //Sperre oder Vorgabe
if (cellBlack && range.Value2 == null) feld[row, col] = "0"; //Block
setFeld(row, col);
}
for (i = 20; i <= iLog; i++)
{
range = (Excel.Range)worksheet.Cells[i, 1];
range.Clear();
}
iLog = 20;
labelWrong.Text = "NO";
}

Die Hintergrundfarbe einer Zelle wird also mit .Interior.Color abgefragt. Wer hätte das gedacht?

Am Schluss der Leseroutine (von Excel in die Matrix feld) lösche ich noch den "Log"-Bereich, wenn man z. B. mehrere Tests hintereinander durchführen will. "feld" ist übrigens ein String (Zeichenkette). Das fand ich besser als Integer, da man beim Debuggen schneller die Kandidaten erkennen kann. Nachteil: Man muss von Zeit zu Zeit zwischen Character und Ziffer hin- und her konvertieren.

Manfred
Posts: 16
Joined: Wednesday 6. October 2010, 18:15
Location: 82024 Taufkirchen
Contact:

Re: Solver

Post by Manfred » Friday 12. November 2010, 10:43

Hier ist der Horror eines jeden deduktiven Logikers: Meine Brute-Force Lösungstaste.
Die Matrizen RStreet und CStreet wurden bei der Aufnahme der Aufgabenstellung von Excel schon eingefüllt: 1. Paramter: Index, 2. Paramter: 0 für die Reihe (oder Spalte), 1 für den Anfangsindex und 2 für den Endindex plus 1.
feld enthält die Aufgabe als String, f als Integer. fToFeld überführt dann f in feld und macht das Ergebnis in Excel sichtbar.
Damit kann JEDES Str8ts in Sekunden gelöst werden, d. h. bei einem einzigen bestimmten Str8ts findet dieses Programm keine Lösung. Vielleicht will mir jemand beim Fehlersuchen helfen? nSol gibt die Zahl der gefundenen Lösungen, falls größer 1.

private bool notStr8t(int row, int col)
{
int i, iR=-1, iC=-1; bool full;
bool[] seq = new bool[18];

for (i = 0; i < RSnum; i++)
if (row == RStreet[i, 0] && col >= RStreet[i, 1] &&
col < RStreet[i, 2]) { iR = i; break; }
full = true;
for (i = col + 1; i < RStreet[iR, 2]; i++)
if (f[row, i] >= 0) { full = false; break; }
if (full) if (checkStr8t(true, row, iR)) return (true);

for (i = 0; i < CSnum; i++)
if (col == CStreet[i, 0] && row >= CStreet[i, 1] &&
row < CStreet[i, 2]) { iC = i; break; }
full = true;;
for (i = row + 1; i < CStreet[iC, 2]; i++)
if (f[i, col] >= 0) { full = false; break; }
if (full) if(checkStr8t(false, col, iC)) return(true);

return (false);
}

private bool checkStr8t(bool Rows, int RC, int iRC)
{
int i, j, i1, anf, sAnf, sEnd, len;
bool[] seq = new bool[18];
for (i = 0; i < 18; i++) seq = false;
if (Rows) {sEnd = RStreet[iRC, 2]; sAnf = RStreet[iRC, 1];}
else {sEnd = CStreet[iRC, 2]; sAnf = CStreet[iRC, 1];}
len = sEnd - sAnf;
for (j = sAnf; j < sEnd; j++)
{
if (Rows) i1 = f[RC, j]; else i1 = f[j, RC];
if (i1 < 0) i1 = -i1;
seq[i1] = true;
}
anf = 0;
for (j = 0; j < 9; j++) if (seq[j]) { anf = j; break; }
for (j = anf; j < anf + len; j++) if (!seq[j]) return (true);
return (false);
}

private void iterate(int row, int col)
{
int i1, j; bool vorhanden;
if (f[row, col] >= 0)
for (i1 = 1; i1 < 10; i1++) // neuer Wert
{
vorhanden = false;
for (j = row - 1; j >= 0; j--)
if (i1 == f[j, col] || i1 == -f[j, col])
{ vorhanden = true; break; }
for (j = row; j < 9; j++)
if (i1 == -f[j, col])
{ vorhanden = true; break; }
if (vorhanden) continue;

vorhanden = false;
for (j = col - 1; j >= 0; j--)
if (i1 == f[row, j] || i1 == -f[row, j])
{ vorhanden = true; break; }
for (j = col; j < 9; j++)
if (i1 == -f[row, j])
{ vorhanden = true; break; }
if (vorhanden) continue;

f[row, col] = i1;
if (DEBUG) fToFeld();
if (notStr8t(row, col)) { f[row, col] = 0; continue; }
if (col < 8) { iterate(row, col + 1); continue; }
if (row < 8) { iterate(row + 1, 0); continue; }
fToFeld(); nSol++;
}
else
{
if (col < 8) { iterate(row, col + 1); return; }
if (row < 8) { iterate(row + 1, 0); return; }
fToFeld(); nSol++;
}
}

private void fToFeld()
{
int i, j;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
if (f[i,j] >= 0) feld[i, j] = f[i, j].ToString();
}
Einfuegen();
}

private void BruteForce_Click(object sender, EventArgs e)
{
nSol = 0;
iterate(0, 0);
if (DEBUG) fToFeld();
}

Post Reply