Ich hab mich nebenbei immer mal wieder ein bisschen mit meinem Solver beschäftigt und geprüft, ob ich noch irgendetwas optimieren kann.
Und gerade ist mir ein “Durchbruch” gelungen:
Puzzles: 49151
Solved: 49151
Duration: 76682ms
Total steps: 293398034
Alle 49.151 Sudokus in nur 77 Sekunden!
Der Trick: ich habe die Auswahlstrategie für den nächsten Eintrag verbessert. Dabei habe ich mich an die Auswahlstrategie des Algorithm X im Originalpaper (Seite 6) gehalten. Warum ich das vorher nicht drin hatte, weiß ich nicht - denn die Zählung wie viele Einträge in der Spalte sind, hatte ich bereits bei anderen Optimierungsversuchen umgesetzt.
So sieht mein Solver jetzt aus:
[spoiler]```package com.byte_welt.sudoku;
import java.util.ArrayList;
import java.util.List;
/**
-
User: Christian
-
Date: 20.07.13
-
Time: 13:48
*/
public class SudokuExactCover implements Sudoku {
private final int fixed;
private final MatrixEntry head;
private final List solution;
private long steps = 0;
private final int blockWidth;
private final int totalWidth;
private final int fieldCount;public SudokuExactCover(int[][] sudoku, int blockWidth) {
this.blockWidth = blockWidth;
totalWidth = blockWidth * blockWidth;
fieldCount = totalWidth * totalWidth;if (sudoku.length != totalWidth) throw new IllegalArgumentException("sudoku must be a " + totalWidth + "x" + totalWidth + " array"); for (int[] row : sudoku) if (row.length != totalWidth) throw new IllegalArgumentException("sudoku must be a " + totalWidth + "x" + totalWidth + " array"); solution = new ArrayList<>(fieldCount); head = generateMatrix(); extractFixed(sudoku); fixed = solution.size(); countRows();}
private void countRows() {
MatrixEntry p = head.getRight();
while (p != head) {
p.countRows();
p = p.getRight();
}
}private void extractFixed(int[][] sudoku) {
MatrixEntry p = head;
for (int i = 0; i < 3 * fieldCount; i++)
p = p.getRight();for (int col = 0; col < totalWidth; col++) { for (int row = 0; row < totalWidth; row++) { p = p.getRight(); if (sudoku[row][col] == 0) continue; MatrixEntry s = p.get(row, sudoku[row][col] - 1); s.removeEntry(); solution.add(s); } }}
private MatrixEntry generateMatrix() {
MatrixEntry head = new MatrixEntry();
List headers = generateHeaders(head);for (int number = 0; number < totalWidth; number++) { for (int row = 0; row < totalWidth; row++) { for (int col = 0; col < totalWidth; col++) { MatrixEntry h = headers.get(number * totalWidth + col); MatrixEntry entryCol = new MatrixEntry(col, row, number, h); h.insertAbove(entryCol); h = headers.get(fieldCount + number * totalWidth + row); MatrixEntry entryRow = new MatrixEntry(col, row, number, h); h.insertAbove(entryRow); h = headers.get(2 * fieldCount + number * totalWidth + col / blockWidth * blockWidth + row / blockWidth); MatrixEntry entryBlock = new MatrixEntry(col, row, number, h); h.insertAbove(entryBlock); h = headers.get(3 * fieldCount + col * totalWidth + row); MatrixEntry entryField = new MatrixEntry(col, row, number, h); h.insertAbove(entryField); entryCol.setLeft(entryField); entryCol.setRight(entryRow); entryRow.setLeft(entryCol); entryRow.setRight(entryBlock); entryBlock.setLeft(entryRow); entryBlock.setRight(entryField); entryField.setLeft(entryBlock); entryField.setRight(entryCol); } } } return head;}
private List generateHeaders(MatrixEntry head) {
List headers = new ArrayList<>(4 * fieldCount);
for (int i = 0; i < 4 * fieldCount; i++) {
MatrixEntry entry = new MatrixEntry();
head.insertBefore(entry);
headers.add(entry);
}
return headers;
}@Override
public boolean solve() {
steps = 0;MatrixEntry p = selectNextColumn(); while (head.getRight() != head) { p = p.getLower(); steps++; if (p.getCol() != -1) { solution.add(p); if (p.removeEntry()) { p = selectNextColumn(); } else { p = backtrack(); } } else { if (solution.size() == fixed) return false; p = backtrack(); } } return true;}
private MatrixEntry selectNextColumn() {
MatrixEntry p = head.getRight();
MatrixEntry bestMatch = p;
int bestRowCount = p.getRowCount();
while (p != head) {
if (p.getRowCount() < bestRowCount) {
bestRowCount = p.getRowCount();
bestMatch = p;
}
p = p.getRight();
}
return bestMatch;
}private MatrixEntry backtrack() {
MatrixEntry entry = solution.remove(solution.size() - 1);
entry.reinsert();return entry;}
@Override
public long getSteps() {
return steps;
}@Override
public String toString() {
int[][] field = new int[totalWidth][totalWidth];
for (MatrixEntry entry : solution) {
field[entry.getRow()][entry.getCol()] = entry.getValue() + 1;
}
String result = “”;
for (int row = 0; row < totalWidth; row++) {
for (int col = 0; col < totalWidth; col++) {
if (col > 0) result += " ";
if (totalWidth > 9 && field[row][col] <= 9) result += " “;
result += field[row][col];
if ((col + 1) % blockWidth == 0 && col + 1 < totalWidth) result += " |”;
}
result += "
";
if ((row + 1) % blockWidth == 0 && row + 1 < totalWidth) {
for (int col = 0; col < totalWidth; col++) {
if (col > 0) result += “-”;
if (totalWidth > 9) result += “-”;
result += “-”;
if ((col + 1) % blockWidth == 0 && col + 1 < totalWidth) result += “-+”;
}
result += "
";
}
}
return result;
}
}```
/**
* User: Christian
* Date: 20.07.13
* Time: 17:43
*/
class MatrixEntry {
private final int row;
private final int col;
private final MatrixEntry columnHeader;
private MatrixEntry left;
private MatrixEntry right;
private MatrixEntry upper;
private MatrixEntry lower;
private int value;
MatrixEntry() {
row = -1;
col = -1;
value = -1;
left = this;
right = this;
upper = this;
lower = this;
columnHeader = this;
}
MatrixEntry(int col, int row, int value, MatrixEntry columnHeader) {
this.row = row;
this.col = col;
this.columnHeader = columnHeader;
this.value = value;
}
void insertBefore(MatrixEntry entry) {
entry.right = this;
entry.left = left;
left.right = entry;
left = entry;
}
public void insertAbove(MatrixEntry entry) {
entry.lower = this;
entry.upper = upper;
upper.lower = entry;
upper = entry;
}
public void setLeft(MatrixEntry left) {
this.left = left;
}
public MatrixEntry getRight() {
return right;
}
public void setRight(MatrixEntry right) {
this.right = right;
}
MatrixEntry get(int row, int value) {
MatrixEntry result = this.columnHeader;
// Endlosschleife, falls row nicht gefunden wird
while (result.row != row || result.value != value) {
result = result.lower;
}
return result;
}
private boolean removeRow() {
boolean result = true;
MatrixEntry p = this.right;
while (p != this) {
p.upper.lower = p.lower;
p.lower.upper = p.upper;
p.columnHeader.value--;
if (p.columnHeader.value == 0) result = false;
p = p.right;
}
return result;
}
private boolean removeCol() {
boolean result = true;
columnHeader.left.right = columnHeader.right;
columnHeader.right.left = columnHeader.left;
MatrixEntry p = this.lower;
while (p != this) {
if (p != columnHeader)
if (!p.removeRow()) result = false;
p = p.lower;
}
return result;
}
boolean removeEntry() {
boolean result = true;
MatrixEntry p = this;
do {
if (!p.removeCol()) result = false;
p = p.right;
} while (p != this);
return result;
}
MatrixEntry getLower() {
return lower;
}
private void reinsertRow() {
MatrixEntry p = this.right;
while (p != this) {
p.upper.lower = p;
p.lower.upper = p;
p.columnHeader.value++;
p = p.right;
}
}
private void reinsertCol() {
columnHeader.left.right = columnHeader;
columnHeader.right.left = columnHeader;
MatrixEntry p = this.lower;
while (p != this) {
if (p != columnHeader)
p.reinsertRow();
p = p.lower;
}
}
void reinsert() {
MatrixEntry p = this;
do {
p.reinsertCol();
p = p.right;
} while (p != this);
}
int getCol() {
return col;
}
int getRow() {
return row;
}
int getValue() {
return value;
}
int countRows() {
int result = 0;
MatrixEntry p = columnHeader.lower;
while (p != columnHeader) {
result++;
p = p.lower;
}
columnHeader.value = result;
return result;
}
int getRowCount() {
return columnHeader.getValue();
}
}```[/spoiler]
Zum ursprünglichen Solver hat sich eigentlich nicht viel geändert. Ich habe die Methode selectNextColumn() extrahiert und dann etwas erweitert, sodass dort die bessere Auswahlstrategie umgesetzt ist. Die Methode eleminateOnes konnte ich deshalb ebenfalls weglassen - sie ist nur ein Spezialfall, der im Allgemeinen genauso schnell abgearbeitet wird.
Ein Preprocessing bringt dabei übrigens keine Vorteile mehr, weil der Algorithmus hidden singles, naked singles und holes sofort erkennt: dies sind die Spalten in der Matrix, die nur einen Eintrag haben.
Mal im Ernst: In der C-Variante stehen ein paar mehr Kommentare, was er denn da eigentlich macht. Und „natürlich“ ist es viel schneller, wenn man nur auf rohen int-Arrays rumhantiert, statt tausende „new MatrixEntry“-Objekte zu erstellen etc.