«1. Обзор
В этой статье мы рассмотрим головоломку судоку и алгоритмы, используемые для ее решения.
Далее мы реализуем решения на Java. Первым решением будет простая атака грубой силы. Второй будет использовать технику Dancing Links.
Давайте помнить, что основное внимание мы будем уделять алгоритмам, а не дизайну ООП.
2. Головоломка судоку
Проще говоря, судоку представляет собой комбинаторную головоломку с размещением чисел с сеткой 9 x 9 ячеек, частично заполненную числами от 1 до 9. Цель состоит в том, чтобы заполнить оставшиеся пустые поля остальными числами. числа так, чтобы в каждой строке и столбце было только одно число каждого вида.
Более того, в каждом подразделе сетки 3 x 3 не может быть дублированного числа. Уровень сложности естественным образом повышается с увеличением количества пустых полей на каждой доске.
2.1. Тестовая доска
Чтобы сделать наше решение более интересным и проверить алгоритм, мы собираемся использовать «самую сложную в мире доску судоку», а именно:
8 . . . . . . . .
. . 3 6 . . . . .
. 7 . . 9 . 2 . .
. 5 . . . 7 . . .
. . . . 4 5 7 . .
. . . 1 . . . 3 .
. . 1 . . . . 6 8
. . 8 5 . . . 1 .
. 9 . . . . 4 . .2.2. Решенная доска
И, чтобы быстро испортить решение – правильно решенная головоломка даст нам следующий результат:
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 23. Алгоритм поиска с возвратом
3.1. Введение
Алгоритм поиска с возвратом пытается решить головоломку, проверяя каждую ячейку на наличие правильного решения.
Если нарушения ограничений нет, алгоритм переходит к следующей ячейке, заполняет все возможные решения и повторяет все проверки.
Если есть нарушение, то увеличивается значение ячейки. Как только значение ячейки достигает 9, и все еще есть нарушение, алгоритм возвращается к предыдущей ячейке и увеличивает значение этой ячейки.
Пробует все возможные решения.
3.2. Решение
Прежде всего, давайте определим нашу доску как двумерный массив целых чисел. Мы будем использовать 0 в качестве нашей пустой ячейки.
int[][] board = {
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 3, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 }
};Давайте создадим методsolve(), который принимает доску в качестве входного параметра и выполняет итерацию по строкам, столбцам и значениям, проверяя каждую ячейку на наличие допустимого решения:
private boolean solve(int[][] board) {
for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
if (board[row][column] == NO_VALUE) {
for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
board[row][column] = k;
if (isValid(board, row, column) && solve(board)) {
return true;
}
board[row][column] = NO_VALUE;
}
return false;
}
}
}
return true;
}Еще один метод, который нам нужен, это isValid (), который будет проверять ограничения судоку, т. е. проверять правильность строки, столбца и сетки 3 x 3:
private boolean isValid(int[][] board, int row, int column) {
return (rowConstraint(board, row)
&& columnConstraint(board, column)
&& subsectionConstraint(board, row, column));
}Эти три проверки относительно похожи. Во-первых, давайте начнем с проверки строк:
private boolean rowConstraint(int[][] board, int row) {
boolean[] constraint = new boolean[BOARD_SIZE];
return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
.allMatch(column -> checkConstraint(board, row, constraint, column));
}Затем мы используем почти идентичный код для проверки столбца:
private boolean columnConstraint(int[][] board, int column) {
boolean[] constraint = new boolean[BOARD_SIZE];
return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
.allMatch(row -> checkConstraint(board, row, constraint, column));
}Кроме того, нам нужно проверить подраздел 3 x 3:
private boolean subsectionConstraint(int[][] board, int row, int column) {
boolean[] constraint = new boolean[BOARD_SIZE];
int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
if (!checkConstraint(board, r, constraint, c)) return false;
}
}
return true;
}Наконец, нам нужен метод checkConstraint():
boolean checkConstraint(
int[][] board,
int row,
boolean[] constraint,
int column) {
if (board[row][column] != NO_VALUE) {
if (!constraint[board[row][column] - 1]) {
constraint[board[row][column] - 1] = true;
} else {
return false;
}
}
return true;
}После того, как все, что сделано, метод isValid() может просто вернуть true.
Теперь мы почти готовы протестировать решение. Алгоритм выполнен. Однако он возвращает только true или false.
Поэтому для визуальной проверки платы нам нужно просто распечатать результат. Видимо, это не часть алгоритма.
private void printBoard() {
for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
System.out.print(board[row][column] + " ");
}
System.out.println();
}
}Мы успешно реализовали алгоритм поиска с возвратом, который решает головоломку Судоку!
Очевидно, есть место для улучшений, так как алгоритм наивно проверяет каждую возможную комбинацию снова и снова (даже если мы знаем, что конкретное решение неверно).
4. Танцующие ссылки
4.1. Exact Cover
Давайте рассмотрим другое решение. Судоку можно описать как задачу точного покрытия, которая может быть представлена матрицей инцидентности, показывающей отношения между двумя объектами.
Например, если взять числа от 1 до 7 и набор множеств S = {A, B, C, D, E, F}, где:
-
A = {1, 4, 7} B = {1, 4} C = {4, 5, 7} D = {3, 5, 6} E = {2, 3, 6, 7} F = {2, 7}
Наша цель — выбрать такие подмножества, что каждое число встречается только один раз и ни одно не повторяется, отсюда и название.
Мы можем представить задачу с помощью матрицы, где столбцы — числа, а строки — множества:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |Подколлекция S* = {B, D, F} является точным покрытием:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |Каждый столбец имеет ровно одну единицу во всех выбранных строках.
4.2. Алгоритм X
Алгоритм X представляет собой «метод проб и ошибок» для нахождения всех решений проблемы точного покрытия, т. е. начиная с нашего примера набора S = {A, B, C, D, E, F}, найти подколлекцию S* = {B, D, F}.
Алгоритм X работает следующим образом:
- If the matrix A has no columns, the current partial solution is a valid solution;
terminate successfully, otherwise, choose a column c (deterministically) - Choose a row r such that Ar, c = 1 (nondeterministically, i.e., try all possibilities)
- Include row r in the partial solution
- For each column j such that Ar, j = 1, for each row i such that Ai, j = 1,
delete row i from matrix A and delete column j from matrix A - Repeat this algorithm recursively on the reduced matrix A
«Эффективной реализацией алгоритма X является алгоритм Dancing Links (сокращенно DLX), предложенный доктором Дональдом Кнутом.
Следующее решение было сильно вдохновлено этой реализацией Java.
4.3. Задача о точном покрытии
Во-первых, нам нужно создать матрицу, которая будет представлять головоломку Судоку как задачу о точном покрытии. Матрица будет иметь 9 ^ 3 строки, т. Е. По одной строке для каждой возможной позиции (9 строк x 9 столбцов) каждого возможного числа (9 чисел).
Столбцы будут представлять доску (снова 9 x 9), умноженную на количество ограничений.
Мы уже определили три ограничения:
-
в каждой строке будет только одно число каждого вида в каждом столбце будет только одно число каждого вида в каждом подразделе будет только одно число каждого вида
Кроме того, является неявным четвертым ограничением:
-
в ячейке может быть только одно число
Это дает всего четыре ограничения и, следовательно, 9 x 9 x 4 столбца в матрице точного покрытия:
private static int BOARD_SIZE = 9;
private static int SUBSECTION_SIZE = 3;
private static int NO_VALUE = 0;
private static int CONSTRAINTS = 4;
private static int MIN_VALUE = 1;
private static int MAX_VALUE = 9;
private static int COVER_START_INDEX = 1;private int getIndex(int row, int column, int num) {
return (row - 1) * BOARD_SIZE * BOARD_SIZE
+ (column - 1) * BOARD_SIZE + (num - 1);
}private boolean[][] createExactCoverBoard() {
boolean[][] coverBoard = new boolean
[BOARD_SIZE * BOARD_SIZE * MAX_VALUE]
[BOARD_SIZE * BOARD_SIZE * CONSTRAINTS];
int hBase = 0;
hBase = checkCellConstraint(coverBoard, hBase);
hBase = checkRowConstraint(coverBoard, hBase);
hBase = checkColumnConstraint(coverBoard, hBase);
checkSubsectionConstraint(coverBoard, hBase);
return coverBoard;
}
private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) {
for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) {
for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) {
for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) {
for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) {
int index = getIndex(row + rowDelta, column + columnDelta, n);
coverBoard[index][hBase] = true;
}
}
}
}
}
return hBase;
}
private int checkColumnConstraint(boolean[][] coverBoard, int hBase) {
for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) {
for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
int index = getIndex(row, column, n);
coverBoard[index][hBase] = true;
}
}
}
return hBase;
}
private int checkRowConstraint(boolean[][] coverBoard, int hBase) {
for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) {
for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
int index = getIndex(row, column, n);
coverBoard[index][hBase] = true;
}
}
}
return hBase;
}
private int checkCellConstraint(boolean[][] coverBoard, int hBase) {
for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) {
for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) {
int index = getIndex(row, column, n);
coverBoard[index][hBase] = true;
}
}
}
return hBase;
}
private boolean[][] initializeExactCoverBoard(int[][] board) {
boolean[][] coverBoard = createExactCoverBoard();
for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
int n = board[row - 1][column - 1];
if (n != NO_VALUE) {
for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
if (num != n) {
Arrays.fill(coverBoard[getIndex(row, column, num)], false);
}
}
}
}
}
return coverBoard;
}~~ ~ Затем нам нужно обновить только что созданную доску с нашим первоначальным макетом головоломки:
Теперь мы готовы перейти к следующему этапу. Давайте создадим два класса, которые будут связывать наши ячейки вместе.
4.4. Танцующий узел
node.prev.next = node.next
node.next.prev = node.prevАлгоритм танцующих ссылок основан на основном наблюдении, что следующая операция над двусвязным списком узлов:
node.prev = node
node.next = nodeудаляет узел, а:
восстанавливает узел.
Каждый узел в DLX связан с узлом слева, справа, вверху и внизу.
class DancingNode {
DancingNode L, R, U, D;
ColumnNode C;
DancingNode hookDown(DancingNode node) {
assert (this.C == node.C);
node.D = this.D;
node.D.U = node;
node.U = this;
this.D = node;
return node;
}
DancingNode hookRight(DancingNode node) {
node.R = this.R;
node.R.L = node;
node.L = this;
this.R = node;
return node;
}
void unlinkLR() {
this.L.R = this.R;
this.R.L = this.L;
}
void relinkLR() {
this.L.R = this.R.L = this;
}
void unlinkUD() {
this.U.D = this.D;
this.D.U = this.U;
}
void relinkUD() {
this.U.D = this.D.U = this;
}
DancingNode() {
L = R = U = D = this;
}
DancingNode(ColumnNode c) {
this();
C = c;
}
}Класс DancingNode будет иметь все операции, необходимые для добавления или удаления узлов:
4.5. Узел столбца
class ColumnNode extends DancingNode {
int size;
String name;
ColumnNode(String n) {
super();
size = 0;
name = n;
C = this;
}
void cover() {
unlinkLR();
for (DancingNode i = this.D; i != this; i = i.D) {
for (DancingNode j = i.R; j != i; j = j.R) {
j.unlinkUD();
j.C.size--;
}
}
}
void uncover() {
for (DancingNode i = this.U; i != this; i = i.U) {
for (DancingNode j = i.L; j != i; j = j.L) {
j.C.size++;
j.relinkUD();
}
}
relinkLR();
}
}Класс ColumnNode свяжет столбцы вместе:
4.6. Решатель
private ColumnNode makeDLXBoard(boolean[][] grid) {
int COLS = grid[0].length;
ColumnNode headerNode = new ColumnNode("header");
List<ColumnNode> columnNodes = new ArrayList<>();
for (int i = 0; i < COLS; i++) {
ColumnNode n = new ColumnNode(Integer.toString(i));
columnNodes.add(n);
headerNode = (ColumnNode) headerNode.hookRight(n);
}
headerNode = headerNode.R.C;
for (boolean[] aGrid : grid) {
DancingNode prev = null;
for (int j = 0; j < COLS; j++) {
if (aGrid[j]) {
ColumnNode col = columnNodes.get(j);
DancingNode newNode = new DancingNode(col);
if (prev == null) prev = newNode;
col.U.hookDown(newNode);
prev = prev.hookRight(newNode);
col.size++;
}
}
}
headerNode.size = COLS;
return headerNode;
}Далее нам нужно создать сетку, состоящую из наших объектов DancingNode и ColumnNode:
private ColumnNode selectColumnNodeHeuristic() {
int min = Integer.MAX_VALUE;
ColumnNode ret = null;
for (
ColumnNode c = (ColumnNode) header.R;
c != header;
c = (ColumnNode) c.R) {
if (c.size < min) {
min = c.size;
ret = c;
}
}
return ret;
}Мы будем использовать эвристический поиск, чтобы найти столбцы и вернуть подмножество матрицы:
private void search(int k) {
if (header.R == header) {
handleSolution(answer);
} else {
ColumnNode c = selectColumnNodeHeuristic();
c.cover();
for (DancingNode r = c.D; r != c; r = r.D) {
answer.add(r);
for (DancingNode j = r.R; j != r; j = j.R) {
j.C.cover();
}
search(k + 1);
r = answer.remove(answer.size() - 1);
c = r.C;
for (DancingNode j = r.L; j != r; j = j.L) {
j.C.uncover();
}
}
c.uncover();
}
}Наконец , мы можем рекурсивно искать ответ:
Если столбцов больше нет, то мы можем распечатать решенную доску судоку.
5. Контрольные показатели
Мы можем сравнить эти два разных алгоритма, запустив их на одном компьютере (таким образом мы сможем избежать различий в компонентах, скорости ЦП или ОЗУ и т. д.). Фактическое время будет отличаться от компьютера к компьютеру.
Однако мы должны иметь возможность видеть относительные результаты, и это скажет нам, какой алгоритм работает быстрее.
Алгоритм возврата занимает около 250 мс, чтобы решить доску.
Если мы сравним это с Dancing Links, который занимает около 50 мс, мы увидим явного победителя. Dancing Links примерно в пять раз быстрее при решении этого конкретного примера.
6. Заключение
В этом уроке мы обсудили два решения головоломки судоку с ядром Java. Алгоритм поиска с возвратом, который представляет собой алгоритм грубой силы, может легко решить стандартную головоломку 9×9.
Также обсуждался чуть более сложный алгоритм Dancing Links. Оба решают самые сложные головоломки за считанные секунды.