Solver

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

Re: Solver

Post by Manfred » Thursday 18. November 2010, 13:21

Ich habe die Fehler gefunden. Hier ist der neue Code in C':

private bool notStr8t(int row, int col)
{
int i, iR=-1, iC=-1;

for (i = 0; i < RSnum; i++) // find Index of Street in Row
if (row == RStreet[i, 0] && col >= RStreet[i, 1] &&
col < RStreet[i, 2])
{ iR = i; break; }
if (iR >= 0) if (col == RStreet[iR, 2] -1)
if (checkStr8t(true, row, iR)) return (true); // no Street

for (i = 0; i < CSnum; i++) // find Index of Street in Col
if (col == CStreet[i, 0] && row >= CStreet[i, 1] &&
row < CStreet[i, 2]) { iC = i; break; }
if (iC >= 0) if (row == CStreet[iC, 2] - 1)
if (checkStr8t(false, col, iC)) return (true); // no Street

return (false); // means: it is a legal Street
}

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; // clear seq
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++) // Set the Sequence Matrix
{
if (Rows) i1 = Math.Abs(f[RC, j]); else i1 = Math.Abs(f[j, RC]);
seq[i1] = true;
}
anf = 0;
for (j = 1; j < 10; j++) if (seq[j]) { anf = j; break; } // Find Start
for (j = anf; j < anf + len; j++) if (!seq[j]) return (true); // Found Hole
if (!DEBUGstr8ts) return (false);
nDEBUGstr++; tws.Write(nDEBUGstr); tws.Write(';');
if (Rows)
{
for (i = 0; i < iRC; i++) tws.Write(';');
for (j = RStreet[iRC, 1]; j < RStreet[iRC,2]; j++)
tws.Write(Math.Abs(f[RStreet[iRC, 0], j]));
tws.Write(';');
}
else
{
for (i = 0; i < RSnum; i++) tws.Write(';');
for (i = 0; i < iRC; i++) tws.Write(';');
for (j = CStreet[iRC, 1]; j < CStreet[iRC, 2]; j++)
tws.Write(Math.Abs(f[j, CStreet[iRC, 0]]));
tws.Write(';');
}
tws.WriteLine();
return (false);
}

private void iterate(int row, int col)
{
int i1, j; bool vorhanden;
for (i1 = 1; i1 < 10; i1++) // new Digit
{
if (f[row, col] < 0) i1 = -f[row, col]; // Block or Preset
if (i1 != 10) // not Block
{
vorhanden = false; // Rows unique?
for (j = row - 1; j >= 0; j--)
if (i1 == Math.Abs(f[j, col]))
{ vorhanden = true; break; }
for (j = row + 1; j < 9; j++)
if (i1 == -f[j, col])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

vorhanden = false; // Cols unique?
for (j = col - 1; j >= 0; j--)
if (i1 == Math.Abs(f[row, j]))
{ vorhanden = true; break; }
for (j = col + 1; j < 9; j++)
if (i1 == -f[row, j])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

if (f[row, col] >= 0) f[row, col] = i1; // Set the Test-Digit
else i1 = 9; // Preset
if (DEBUG) fToFeld();
if (notStr8t(row, col)) // no Hole in Street?
{ if (f[row, col] >= 0) f[row, col] = 11; continue; }
}

if (!CFIRST)
{
if (col < 8) iterate(row, col + 1); //recursive
if (row < 8) iterate(row + 1, 0); //recursive
}
else
{
if (row < 8) iterate(row + 1, col); //recursive
if (col < 8) iterate(0, col + 1); //recursive
}
if (row < 8 || col < 8)
{
if (nSol > 0) break;
if (f[row, col] < 0) i1 = 9; // Preset
else if (i1 == 9) f[row, col] = 11; // Marker for Debugging
continue;
}
fToFeld(); nSol++; return; // found Solution
}
}

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

Re: Solver

Post by Manfred » Thursday 18. November 2010, 13:41

Anmerkungen zu meinem Code:

1. Dies ist ein "dummes" Brute-Force Modul für mein ansonsten deduktiv logisches Solver-Programm. Es scheint bei allen Str8ts eine Lösung zu finden, allerdings mit stark unterschiedlichen Lösungszeiten:

Extr01 0:01:26,780
Extr02 0:04:14,593
Extr03 0:15:34,546
Extr04 0:00:42,968
Extr05 0:00:12,125
Extr06 0:10:30,687
Extr07 0:00:02,310
Extr08 0:03:37,640
Extr09 0:00:02,828
Extr10 0:00:05,375
Extr11 0:01:38,765
Extr12 0:02:13,310
Extr13 0:00:11,312
Extr14 6:19:08,468 (!)
Extr15 0:00:00,484 (!)
Extr16 0:04:04,375
Extr17 0:00:40,125
Extr18 0:00:21,609
Extr19 0:00:39,187
Extr20 0:22:41,930
Extr21 0:00:04,150

bei einem 3 GHz Single-CPU Prozessor. Wenn man Reihen und Spalten vertauscht (CFIRST: ich vertausche nur die Reihenfolge der Iterationen), dann entstehen z. T. dramatische Zeitunterschiede. Es werden ja einfach ALLE möglichen Zahlenkombinationen durch-iteriert. Entweder man fängt mit Reihen oder mit Spalten an. Dann werden Ziffern-Wiederholungen ausgeschaltet und die vorher schon gespeicherten "Strassen" auf "Löcher" untersucht. Bei Extr14 sieht man schön, dass diese Strategie nicht besonders "intelligent" ist. Bei Extr15 lohnt sich dieses Modul aber wieder.

2. Die Subroutine "iterate" wird rekursiv verwendet. Mit ein wenig Nachdenken werdet Ihr sehen, dass damit alle Zahlenkombinationen erreicht werden können, für Reihen und für Spalten.

3. Ich habe mit DEBUGstr8ts noch eine Datei erzeugt, die man in Excel oder Access einlesen und analysieren kann. Das erleichtert die Fehlersuche ganz erheblich und lässt mit nDEBUGstr einen Haltepunkt für den Debugger setzen. Es sind ja hier häufig mehrere Millionen Strassen zu analysieren.

Wenn jemand mir noch einen Tipp geben will: bitte melden! Jetzt werde ich wieder über deduktive Logik nachdenken. Übrigens: meine Str8ts löse ich nach wie vor alle per Pencilling, ohne Computer. Das Programmieren mache ich nur zum Spass.

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

Re: Solver

Post by Manfred » Monday 22. November 2010, 03:44

Bei der Einführung von "Column first" (CFIRST) ist mir jetzt doch noch ein Fehler unterlaufen. Die rekursiv aufgerufene "iterate" Subroutine muss also so aussehen:

private void iterate(int row, int col)
{
int i1, j; bool vorhanden;
for (i1 = 1; i1 < 10; i1++) // new Digit
{
if (f[row, col] < 0) i1 = -f[row, col]; // Block or Preset
if (i1 != 10) // not Block
{
vorhanden = false; // Rows unique?
for (j = row - 1; j >= 0; j--)
if (i1 == Math.Abs(f[j, col]))
{ vorhanden = true; break; }
for (j = row + 1; j < 9; j++)
if (i1 == -f[j, col])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

vorhanden = false; // Cols unique?
for (j = col - 1; j >= 0; j--)
if (i1 == Math.Abs(f[row, j]))
{ vorhanden = true; break; }
for (j = col + 1; j < 9; j++)
if (i1 == -f[row, j])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

if (f[row, col] >= 0) f[row, col] = i1; // Set the Test-Digit
else i1 = 9; // Preset
//if (DEBUG) fToFeld();
if (notStr8t(row, col)) // no Hole in Street?
{ if (f[row, col] >= 0) f[row, col] = 11; continue; }
if (DEBUG && printFeld[row, col])
{
fToFeld();
printFeld[row, col] = false;
}
}

if (!CFIRST && col < 8) iterate(row, col + 1); //recursive
if (CFIRST && row < 8) iterate(row + 1, col); //recursive
if ((!CFIRST && col < 8) || (CFIRST && row < 8))
{
if (nSol > 0) break;
if (f[row, col] < 0) i1 = 9;
else if (i1 == 9) f[row, col] = 11;
continue;
}
if (!CFIRST && row < 8) iterate(row + 1, 0); //recursive
if (CFIRST && col < 8) iterate(0, col + 1); //recursive
if ((!CFIRST && row < 8) || (CFIRST && col < 8))
{
if (nSol > 0) break;
if (f[row, col] < 0) i1 = 9;
else if (i1 == 9) f[row, col] = 11;
continue;
}

fToFeld(); nSol++;
buttonWrong_Check();
return; // found Solution
}
}

Tut mir leid, für alle, die das schon ausprobiert haben. Die Endstatements nach der rekursiven Iteration waren falsch sortiert für die CFIRST-Bedingung.

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

new Compartment check

Post by Manfred » Sunday 5. December 2010, 10:46

... as indicated in the main Extreme page of today, this is my new module for the compartment check. First, why is it needed?
Think of a situation, where the candidates are as follows:
34567, 34567, 67, 67, 67.
The compartment has the length of 5, and a street 23456 or 45678 could possibly been built, but we are analyzing now the above mentioned situation. I did not find any easy method for the program, to decide, that there is no possibilty to form a street. So I decided to build a pointer vector to point to those cells:
Assume a compartment of length 3, then there are 3-factorial (6) possibilities to look at these cells:
123, 132, 213, 231, 312, 321
In order to avoid Sorting, you look at the cells through this pointing vector, and try to form a gapless continuing street, like "567". If you are successfull, you remember these candidates in the "canStreet" vector for each cell, and you look now at the "mustStreet" vector, if there is already any street overlapping, and you delete those candidates in "mustStreet", where there is no overlapping.
As indicated in the above 5-length street, you must shift your analyze-window through all possible spreads:
12345, 23456, 34567, 45678, 56789
In this case, the start (anfang) is 1, 2, 3, 4, 5, and the length (lg) is 5.
The calculation of the "Sort"-pointing vector can be done by a self-calling (recursive) subroutine, called by:
MatrixIterate(0, anfang, lg); // Anstoss
anfang == Startindex of first cell, and lg == length of Street.

private void MatrixIterate(int it, int anfang, int lg)
{
int i, i1, j, j1, j2; bool OK, vorhanden;
for (i1 = 0; i1 < lg; i1++) // set Pointer Vector
{
vorhanden = false; // unique?
for (j = it - 1; j >= 0; j--)
if (i1 == mIt[j])
{ vorhanden = true; break; }
if (vorhanden) continue;
mIt[it] = i1; // found next Pointer Digit

if (it < lg - 1)
{
MatrixIterate(it + 1, anfang, lg); // recursive
continue;
}

for (i = 1; i < 11 - lg; i++)
{
OK = true;
for (j = 0; j < lg; j++) // test for Holes
{
j1 = mIt[j] + anfang;
j2 = j + i;
if (!Matrix[j1, j2]) { OK = false; break; }
}
if (!OK) continue;
for (j = 0; j < lg; j++) // found, fill canStreet
{
j1 = mIt[j] + anfang;
j2 = j + i;
canStreet[j1, j2] = true;
if (firstMust) mustStreet[j2] = true;
}
if (!firstMust) // fill mustStreet
{
for (j = 1; j < i; j++) mustStreet[j] = false;
for (j = i + lg; j < 10; j++) mustStreet[j] = false;
}
firstMust = false;
}
}
}

Happy programming!

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

neuer Compartment Check

Post by Manfred » Sunday 5. December 2010, 13:41

... hier noch einmal das Ganze in Deutsch:
... wie in meinem Beitrag im englischen Extreme Forum angekündigt, erkläre ich also hier mein neues Modul compartment check.
Stellen Sie sich folgende Kandidaten in 5 Zellen vor:
34567, 34567, 67, 67, 67.
Diese leichte Beispiel kann man gleich erkennen, es gibt aber sehr unübersichtliche Beiträge. Diese Straße hat die Länge 5 und eine Straße mit 23456 oder 45678 könnten vielleicht gebaut werden, wenn noch weitere Kandidate vorhanden sind, aber hier beschränken wir uns ja auf obiges Beispiel. Ich habe bisher keine einfache Methode gefunden, um bei solchen Situationen programmiert festzustellen, dass hier die Straße 34567 nicht gebaut werden kann und damit die Kandidaten 3 oder 4 jedenfalls wegfallen werden. Deswegen habe ich mich entschieden, einen Vektor zu schaffen, der als Zeiger das "Sortieren" der Zellen in alle möglichen Reihenfolgen erlauben soll. Dann kann ich einfach die Möglichkeiten der aufsteigenden Reihen auf Lücken überprüfen.
Wenn Sie mal annehmen, dass wir eine 3-er Strasse untersuchen, dann würde dieser Vektor nacheinander so aussehen:
123, 132, 213, 231, 312, 321
Das sind 3-Fakultät (6) Permutationen. Um jetzt das Sortieren zu vermeiden, benutze ich diesen Vektor als Zeiger auf die unbewegten Zellen. Jetzt versuchen wir, eine kontinuierliche Straße, z. B. "567" zu bilden. Wenn das gelingt, dann speichern wir diese Kandidaten in der Matrix "canStreet" für jede Zelle. Dann wird der "mustStreet" Vektor angesehen, ob da bereits überlappende Straßen festgehalten wurden. Wo keine Überlappung ist, werden die Kandidaten gestrichen. Wie oben bei der 5-er Straße bereits angedeutet, muss ein "Fenster" über den Zahlenraum geschoben werden. z. B.:
12345, 23456, 34567, 45678, 56789
In diesem Fall wäre also der Anfang 1, 2, 3, 4 oder 5 und die Länge lg wäre 5.
Die Berechnung des "Sortierungsvektors", der eigentlich nur ein Zeiger ist, wird über eine sich selbst aufrufende, also rekursive Subroutine erledigt, die folgendermaßen gestartet wird:
MatrixIterate (0, anfang, lg);
[und dann folgt der Programmiercode in C-Sharp, C#]

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

Re: Solver

Post by Jens » Monday 6. December 2010, 16:21

@neuer Compartment Check:
Dein Beitrag scheint revolutionär zu sein, vor allem wie Du die sehr schwierige Matrizenrechnung hier einsetzt. Schade, leider kann ich Dir nicht folgen, weil ich (noch) nicht über C# verfüge und auch in der Mathematik nicht sattelfest genug bin.
Aber ich sehe, das Beispiel "34567, 34567, 67, 67, 67" kann nicht richtig gehen, es humpelt ein wenig, weil die drei Zellen 67, 67, 67 zusammen mindestens drei Kandidaten brauchen, aber tatsächlich nur über zwei Kandidaten verfügen. Du schreibst weiter "Diese Straße hat die Länge 5 und eine Straße mit 23456 oder 45678 könnten vielleicht gebaut werden, wenn noch weitere Kandidate vorhanden sind", nehme ich an, die weiteren Kandidaten 2 und 8 sollen da noch irgendwo hineingesetzt werden. Dann kann es natürlich weitergehen.
Gruß von Jens

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

@Jens: neuer Compartment Check

Post by Manfred » Monday 6. December 2010, 18:24

Hallo Jens, danke für Deinen Beitrag. Deine Vermutung ist richtig. Die neuen Kandidaten 2 oder 8 würden erst nach Verschiebung des Zahlenfensters nach unten oder oben zum Tragen kommen. Dann könnte die Reihe z. B. so aussehen: "45678, 45678, 678, 678, 678" bei Verschiebung des Fensters nach oben. Dann würden die 8-er Kandidaten (angenommen, es gibt sie!) sichtbar werden und die 3-er verschwinden. Hier wäre dann eine Schlaglochlose Strasse "45678" möglich. Das Behandeln der "naked Pairs" 67+67 hatte ich tatsächlich ins Auge gefasst, aber schließlich war die Permutation einfacher zu programmieren. Ich weiß auch nicht, ob ich damit wirklich ALLE Kombinationen erfassen würde. Das ist aber zur Elimination der "sicheren" Kandidaten in anderen Compartments derselben Reihe oder Spalte notwendig.

Ein nach unten verschobenes Zahlen-Fenster würde vermutlich gar keine Strassse finden können. Aber da habe ich nicht wirklich darüber nachgedacht. Es sollte nur ein einfaches Beispiel sein. Komplexe Beispiele sind leider nicht so übersichtlich. Wahrscheinlich findet ein Mensch sie auch deshalb nicht so einfach. Theoretisch müssten wir das alles auch ohne Computer "sehen".

An C# (C-Sharp) kommst Du ganz einfach über Microsofts Seite: http://www.microsoft.com/germany/expres ... ndows.aspx. Das ist ganz kostenlos.

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

Brute Force Batch-program

Post by Manfred » Tuesday 28. December 2010, 11:29

As promised, this is the comand-line version of my Brute-Force module in C-Sharp:

using System;
using System.IO;

namespace BFStr8ts
{
class Program
{
static bool CFIRST = false;
static int CSnum = 0, RSnum = 0, nSol = 0;
static int[,] CStreet = new int[36, 3]; // Index, col, anfang, ende
static int[,] RStreet = new int[36, 3]; // Index, row, anfang, ende
static int[,] RQuerSum = new int[9, 10]; // Row, Candidate
static int[,] CQuerSum = new int[9, 10]; // Col, Candidate
static int[,] ZellSum = new int[9, 9]; // row, col
static int[,] f = new int[9, 9];
static string timeDiff, RCF = "RF";
static string[,] feld = new string[9, 9];
static TextWriter tw, log;
static TextReader tr;

static void StrassenRows()
{
int anfang = 0, ende = 9, row, col, j, Laenge;
int Digit;
RSnum = 0;
for (row = 0; row < 9; row++) // alle Reihen
{ // Reihen
anfang = 0;
for (col = 0; col < 8; col++) // suche Reihe nach rechts
{ // Spalten
Digit = f[row, col]; // suche Anfang
if (col == 0 && Digit >= 0)
anfang = 0; // kein Block oder Sperre am Anfang
else if (Digit < 0) anfang = col + 1;

ende = 9; // falls kein Endblock
for (j = col + 1; j < 9; j++)
{
Digit = f[row, j];
if (Digit < 0) { ende = j; break; }
}

Laenge = ende - anfang; // Strasse gefunden
if (Laenge == 0) continue; // zwei Blocks
RStreet[RSnum, 0] = row;
RStreet[RSnum, 1] = anfang;
RStreet[RSnum, 2] = ende;
RSnum++;
col = ende - 1;
} // Spalten
} // Reihen
} // Sub

static void StrassenCols()
{
int anfang = 0, ende = 9, row, col, j, Laenge;
int Digit;
CSnum = 0;
for (col = 0; col < 9; col++) // alle Spalten
{ // Spalten
anfang = 0;
for (row = 0; row < 8; row++) // suche Spalte nach unten
{ // Reihen
Digit = f[row, col]; // suche Anfang
if (row == 0 && Digit >= 0)
anfang = 0; // kein Block oder Sperre am Anfang
else if (Digit < 0) anfang = row + 1;

ende = 9; // falls kein Endblock
for (j = row + 1; j < 9; j++)
{
Digit = f[j, col];
if (Digit < 0) { ende = j; break; }
}

Laenge = ende - anfang; // Strasse gefunden
if (Laenge == 0) continue; // zwei Blocks
CStreet[CSnum, 0] = col;
CStreet[CSnum, 1] = anfang;
CStreet[CSnum, 2] = ende;
CSnum++;
row = ende - 1;
} // Spalten
} // Reihen
} // Sub

static bool isStr8t(int row, int col)
{
int i, iR = -1, iC = -1;

for (i = 0; i < RSnum; i++) // find Index of Street in Row
if (row == RStreet[i, 0] && col >= RStreet[i, 1] &&
col < RStreet[i, 2])
{ iR = i; break; }
if (iR >= 0) if (col == RStreet[iR, 2] - 1)
if (!checkStr8t(true, row, iR)) return (false); // no Street

for (i = 0; i < CSnum; i++) // find Index of Street in Col
if (col == CStreet[i, 0] && row >= CStreet[i, 1] &&
row < CStreet[i, 2]) { iC = i; break; }
if (iC >= 0) if (row == CStreet[iC, 2] - 1)
if (!checkStr8t(false, col, iC)) return (false); // no Street

return (true); // a legal Street
}

static 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; // clear seq
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++) // Set the Sequence Matrix
{
if (Rows) i1 = Math.Abs(f[RC, j]); else i1 = Math.Abs(f[j, RC]);
seq[i1] = true;
}
anf = 0;
for (j = 1; j < 10; j++) if (seq[j]) { anf = j; break; } // Find Start
for (j = anf; j < anf + len; j++) if (!seq[j]) return (false); // Found Hole
return (true);
}

static void iterate(int row, int col)
{
int i1, j; bool vorhanden;
for (i1 = 1; i1 < 10; i1++) // new Digit
{
if (f[row, col] < 0) i1 = -f[row, col]; // Block or Preset
if (i1 != 10) // not Block
{
vorhanden = false; // Rows unique?
for (j = row - 1; j >= 0; j--)
if (i1 == Math.Abs(f[j, col]))
{ vorhanden = true; break; }
for (j = row + 1; j < 9; j++)
if (i1 == -f[j, col])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

vorhanden = false; // Cols unique?
for (j = col - 1; j >= 0; j--)
if (i1 == Math.Abs(f[row, j]))
{ vorhanden = true; break; }
for (j = col + 1; j < 9; j++)
if (i1 == -f[row, j])
{ vorhanden = true; break; }
if (vorhanden)
{
if (i1 == 9) f[row, col] = 11;
if (f[row, col] < 0) i1 = 9;
continue;
}

if (f[row, col] >= 0) f[row, col] = i1; // Set the Test-Digit
else i1 = 9; // Preset
if (!isStr8t(row, col)) // no Hole in Street?
{ if (f[row, col] >= 0) f[row, col] = 11; continue; }
}

if (!CFIRST && col < 8) iterate(row, col + 1); // recursive
if (CFIRST && row < 8) iterate(row + 1, col); // recursive
if ((!CFIRST && col < 8) || (CFIRST && row < 8))
{
if (nSol > 0) break;
if (f[row, col] < 0) i1 = 9;
else if (i1 == 9) f[row, col] = 11;
continue;
}
if (!CFIRST && row < 8) iterate(row + 1, 0); // recursive
if (CFIRST && col < 8) iterate(0, col + 1); // recursive
if ((!CFIRST && row < 8) || (CFIRST && col < 8))
{
if (nSol > 0) break;
if (f[row, col] < 0) i1 = 9;
else if (i1 == 9) f[row, col] = 11;
continue;
}

nSol++;
return; // found Solution
}
}

static void BruteForce()
{
DateTime oldDate = DateTime.Now, newDate; TimeSpan ts;
oldDate = DateTime.Now;

nSol = 0;
iterate(0, 0);

newDate = DateTime.Now;
ts = newDate - oldDate;
timeDiff = ts.Hours.ToString() + ':' + ts.Minutes.ToString() + ':' +
ts.Seconds.ToString() + ',' + ts.Milliseconds.ToString();
}

static void StuartIn()
{
int i, j; string sFile;
sFile = tr.ReadToEnd();
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
f[i, j] = sFile[36 + i*9 + j] - 48;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
if (sFile[117 + i * 9 + j] == '0' && f[i,j] == 0)
{ f[i, j] = 0; feld[i, j] = "123456789"; }
if (sFile[117 + i * 9 + j] == '0' && f[i, j] != 0)
{ f[i, j] = f[i, j]; feld[i, j] = f[i, j].ToString(); }
if (sFile[117 + i * 9 + j] == '1' && f[i, j] == 0)
{ f[i, j] = -10; feld[i, j] = "0"; }
if (sFile[117 + i * 9 + j] == '1' && f[i, j] > 0)
{ f[i, j] = -f[i, j]; feld[i, j] = f[i, j].ToString(); }
}

StrassenRows();
StrassenCols();
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++) if (f[i, j] > 0) f[i, j] = -f[i, j];
}

static void StuartOut()
{
int i, j;
tw.Write(@"http://www.str8ts.com/str8ts.htm?bd=");
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
if (f[i, j] != -10) tw.Write(Math.Abs(f[i, j]));
else tw.Write(0);
}
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
if (feld[i, j][0] == '-' || f[i, j] == -10) tw.Write('1');
else tw.Write('0');
}
}

static void Main(string[] args)
{
string sStuart, sStuart2;
CFIRST = false; RCF = "RF";
DirectoryInfo di2 = new DirectoryInfo(".");
sStuart = di2.FullName + @"\Stuart.str";
if (args.Length > 0) sStuart = args[0] + ".str";
if (args.Length > 1)
{
RCF = args[1];
if (args[1] == "CF") CFIRST = true;
}
FileInfo fi = new FileInfo(sStuart);
if (!fi.Exists) return;
tr = new StreamReader(sStuart, System.Text.Encoding.Default);
fi = new FileInfo("Extreme.csv");
if (!fi.Exists)
{
log = new StreamWriter("Extreme.csv", false, System.Text.Encoding.Default);
log.WriteLine("File;R/C;Time");
}
else
log = new StreamWriter("Extreme.csv", true, System.Text.Encoding.Default);
StuartIn();
tr.Close();

BruteForce();

sStuart2 = di2.FullName + @"\Stuart.sol";
if (args.Length > 0) sStuart2 = args[0] + "RF.sol";
if (args.Length > 1)
{
sStuart2 = args[0] + args[1] + ".sol";
if (args[1] == "CF") CFIRST = true;
}
fi = new FileInfo(sStuart2);
tw = new StreamWriter(sStuart2, false, System.Text.Encoding.Default);
StuartOut();
tw.WriteLine();
tw.WriteLine(timeDiff);
log.WriteLine(sStuart + ";" + RCF + ";" + timeDiff);
tw.Close(); log.Close();
}
}

}

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

Brute Force Batch-program

Post by Manfred » Tuesday 28. December 2010, 11:43

Some explanations:

StrassenRows and StrassenCols calculate all straits for Rows and Columns. iterate is the main recursive routine to iterate through all possible Digit-Combinations. notStr8t and checkStr8t test, if there is a Hole in a Strait, and if it is legal. The switch CFIRST controls, if iterate goes Row by Row to the right or Column by Column downwards. BruteForce controls iterate and takes timings. StuartIn and StuartOut read the input file and write the resulting solution in to a file. The format is the comand string, which you get free of charge, when you push the solver button to get the Stuart-Solver. You can take the comand string from *.sol and paste it to a Browser, and Mr. Stuarts solver will say "Thats it! All done". Main is the startup program, manages files and the commandline arguments, and calls BruteForce. Thats it. Have fun.

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

Brute Force Batch

Post by Manfred » Tuesday 28. December 2010, 13:25

... und hier noch einmal in Deutsch:

StrassenRows und StrassenCols errechnen alle "Straits" für Reihen und Spalten . "iterate" ist das zentrale rekursive Unterprogramm, um durch die möglichen Ziffernfolgen zu iterieren. "notStr8t" und "checkStr8t" überprüfen, ob es einer Strait ein "Schlagloch" gibt und ob es den Regeln entspricht. Der Schalter CFIRST legt fest, ob die Iteration Reihe für Reihe, zunächst nach links, oder Spalte für Spalte, also zunächst nach unten, durchgeführt werden soll. Das ist manchmal viel günstiger. "BruteForce" steuert "iterate" und nimmt die Zeit. "StuartIn" und "StuartOut" lesen die Eingabedatei und schreiben die Lösungsdatei. Das Format ist identisch mit der Browser-Eingabezeile, die Sie erhalten, wenn Sie auf den "Solver"-Knopf drücken. Ebenfalls kann das Ergebnis in der "*.sol"-Datei kopiert und in die Browser-Zeile eingefügt werden. Dann sagt Ihnen der Stuart-Solver: "Thats it! All done". "Main" ist das Start-Programm, das die Dateien und die Argumente des Aufrufs verwaltet und bearbeitet. Es ruft dann das "BruteForce" Unterprogramm. Das war's. Viel Spass.

Post Reply