Lösen des Sudoku mit Integer-Programmierung

Ein 9 X9 SUDOKU-Puzzle hat die folgenden Regeln. Jede Zeile und Spalte sollte die Zahlen zwischen 1 und 9 haben und jedes der inneren Kästchen sollte die Zahlen zwischen 1 und 9 haben. Jede Zahl in jeder Spalte und Zeile und in jedem kleinen Kästchen sollte nur einmal vorkommen.

Lassen Sie uns Xijk für alle Werte von I, j und k von 1 bis 9 als 1 definieren. Wenn die Zelle (I, j) die Zahl k enthält, wobei I, j und k alle zwischen 1 und 9 liegen. Hier bezeichnet I die i-te Zeile und j bezeichnet die j-te Spalte und k bezeichnet eine ganze Zahl zwischen 1 und 9. Wenn X134 = 1, bedeutet dies, dass die Zelle (1,3) die Zahl 4 enthält. Dies würde auch bedeuten, dass keines der anderen Elemente von die erste Zeile oder die dritte Spalte mit Ausnahme der Zelle (1,3) kann gleich 4 sein.

Um das SUDOKU zu modellieren, verwenden wir insgesamt 729 Variablen.

Lassen Sie uns nun jede der drei Klassen von Regeln algebraisch formulieren.

Jede Zeile sollte eine Zahl zwischen 1 und 9 genau einmal enthalten.

Für die erste Zeile würde diese Regel als (in der Sprache der Integer-Programmierung als „Constraint“ bezeichnet) erscheinen.

für jedes I von 1 bis 9 und für jedes k von 1 bis 9(I ist eine mathematische Darstellung einer Zählervariablen)

Summe (Xijk) für alle j von 1 bis 9 = 1;

Geschrieben in ausführlicher Form für die 1. Reihe für jede Zahl zwischen 1 und 9

X111 + X121 + X131 + X141 + X151 + X161 + X171 + X181 + X191 = 1.

X112 + X122 + X132 + X142 + X152 + X162 + X172 + X182 + X192 = 1.

X113 + X123 + X133 + X143 + X153 + X163 + X173 + X183 + X193 = 1.

X114 + X124 + X134 + X144 + X154 + X164 + X174 + X184 + X194 = 1.

Diese Gleichungen folgen für Variablen, die mit X115 bis X119 beginnen.

Auf ähnliche Weise formulieren wir Gleichungen für die Regeln jeder Zahl zwischen 1 und 9, die in jeder der 9 Spalten nur einmal vorkommt.

In mathematischer Schreibweise geschrieben,

Summe X für jedes j von 1 bis 9 ( für alle I und k zwischen 1 bis 9 ) = 1

Geschrieben in ausführlicher Form für einige Spalten für jede Zahl zwischen 1 und 9

Spalte 1

X111 + X211 + X311 + X411 + X511 + X611 + X711 + X811 + X911 = 1.

X112 + X212 + X312 + X412 + X512 + X612 + X712 + X812 + X912 = 1.

X113 + X213 + X313 + X413 + X513 + X613 + X713 + X813 + X913 = 1.

Für alle anderen Zahlen 4 bis 9 muss dieser ausgefüllt werden.

Spalte 2

X121 + X221 + X321 + X421 + X521 + X621 + X721 + X821 + X921 = 1.

X122 + X222 + X322 + X422 + X522 + X622 + X722 + X822 + X922 = 1.

X123 + X223 + X323 + X423 + X523 + X623 + X723 + X823 + X923 = 1.

Diese muss für alle anderen Zahlen von 4 bis 9 ausgefüllt werden.

Lassen Sie uns nun die kleinen Kästchen ( 3 x 3 ) insgesamt 9 Quadrate darstellen.

In jedem 3 x 3 Quadrat darf es also nur eine 1 oder 2 oder 3 oder 4 oder 5 oder 6 oder 7 oder 8 oder 9 usw. geben.

Die Zellen befinden sich zwischen Spalten (1 bis 3) und Zeilen (1 bis 3), Spalten (4 bis 6) und Zeilen (1 bis 3) Spalten (7 bis 9) Zeilen (1 bis 3). Auch für den gleichen Satz von Spalten treten sie in den Zeilen (4 bis 6) und (6 bis 9) auf. Also formulieren wir die Gleichungen für nur ein kleines Quadrat zwischen den Spalten (1 bis 3) und den Zeilen (1 bis 3). Die entsprechenden Entscheidungsvariablen für die Ziffer „1“ sind (insgesamt 9)

X111, X121, X131, X211,X221,X231,X311, X321,X331.

Wir formulieren die Gleichung, dass dieses (3 x 3) Quadrat nur eine „1“ enthält.

Die Gleichung lautet also

X111 + X121+ X131 + X211 +X221+ X231+ X311 + X321 + X331 = 1.

Die obige Gleichung würde implizieren, dass nur eine dieser 9 Variablen oder nur eine dieser neun Zellen den Wert 1 annehmen kann.

Entsprechende Einschränkungen müssen für die Ziffer „2“, Ziffer „3“ usw. bis 9 formuliert werden.

Bei ganzzahligen Programmierproblemen sollten zusätzlich zu Gleichungen, die die Randbedingungen beschreiben, auch ganzzahlige Randbedingungen für jede einzelne Variable gelten, so dass man schließlich, wenn das Gleichungssystem gelöst wird, entweder eine 0 oder eine 1 als Lösung für die Variable Xijk . erhält .

Das geometrische Äquivalent eines linearen Programmierproblems mit einer Zielfunktion und einigen Beschränkungen ist nichts anderes als ein dimensionales Polyeder, wobei n die Anzahl der Beschränkungen im Problem darstellt. Normalerweise wird die optimale Lösung an den Ecken des Polytops gefunden, auch die Regeln einiger Verfahren wie SIMPLEX erfordern, dass das Polytop konvex ist, damit man entlang der Kanten von Ecke zu Ecke gehen und die optimale Lösung finden kann.

Das Auferlegen von ganzzahligen Beschränkungen zusätzlich würde bedeuten, dass die optimale Lösung nicht auf den Eckpunkten des Polytops liegt, da eine auf dem Eckpunkt gefundene Lösung möglicherweise keine ganze Zahl ist. Wenn man also berücksichtigt, dass die optimale Lösung 0 oder 1 sein muss, bedeutet dies, dass die Lösung geometrisch irgendwo innerhalb des zulässigen Bereichs des konvexen Polytops und auf einer der vielen Geraden liegt, die aus der Hyperebene äquivalent zu Xi jk mit ganzzahligem Werte.

Beachten Sie, dass die obige Lösung 729 Entscheidungsvariablen und 81 Zeilenbeschränkungen verwendet hat. 81 Spaltenbeschränkungen und 729 kleine quadratische Beschränkungen, insgesamt 901 Beschränkungen. Es kann viele Zielfunktionen geben, aber man kann eine Zielfunktion so formulieren, dass man das Minimum von (Summe aller 729 Variablen) ermittelt. Man kann die Anzahl der Beschränkungen reduzieren, indem man eine gewisse Redundanz findet.

Diese obigen Gleichungen können nicht mit Programmiersprachen wie Visual Basic, Pascal oder C gelöst werden. Integer-Programmierprobleme können mit Optimierungssoftware wie CPLEX-Optimierer, Excel-Add-In zum Lösen von Problemen der linearen Programmierung, Lingo usw. gelöst werden.


Source by Srinivasa Gopal

About admin

Check Also

Kann man Computerprogrammierer werden?

Der Einstieg in die Computerprogrammierung ist lukrativ, da Sie gut bezahlt werden. Obwohl diese Softwarebranche …

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.