Создайте решатель судоку на Java

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 2

3. Алгоритм возврата

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. Точная обложка

Давайте посмотрим на другое решение. Судоку можно описать как задачу точного покрытия , которая может быть представлена матрицей инцидентности, показывающей отношения между двумя объектами.

Например, если взять числа от 1 до 7 и совокупность множеств S = {A, B, C, D, E, F} , где:

• А = {1, 4, 7}
• В = {1, 4}
• С = {4, 5, 7}
• Д = {3, 5, 6}
• Е = {2, 3, 6, 7}
• Ф = {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 представляет собой «метод проб и ошибок» для поиска всех решений проблемы точного покрытия, т. е. начиная с нашего примера коллекции S = {A, B, C, D, E, F} , найдите подколлекцию S* = { Б, Д, Ф}.

Алгоритм X работает следующим образом:

1. Если матрица A не имеет столбцов, текущее частичное решение является допустимым решением;

   завершиться успешно, в противном случае выбрать столбец c (детерминировано)

2. Выберите строку r такую, что Ar , c = 1 (недетерминировано, т. е. попробуйте все возможности ) ``

3. Включите строку r в частичное решение

4. Для каждого столбца j такого, что Ar , j = 1, для каждой строки i такой, что A i , `j` = 1, удалить строку `i` из матрицы `A` и удалить столбец `j` `из` матрицы `A` ``

   ``

5. Повторите этот алгоритм рекурсивно на уменьшенной матрице 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. Танцующий узел

Алгоритм Dancing Links работает на основе базового наблюдения, что следующая операция над двусвязными списками узлов:

node.prev.next = node.next
node.next.prev = node.prev

удаляет узел, а:

node.prev = node
node.next = node

восстанавливает узел.

Каждый узел в DLX связан с узлом слева, справа, вверху и внизу.

Класс DancingNode будет иметь все операции, необходимые для добавления или удаления узлов:

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;
    }
}

4.5. Узел столбца

Класс ColumnNode свяжет столбцы вместе:

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();
    }
}

4.6. Решатель

Далее нам нужно создать сетку, состоящую из наших объектов DancingNode и ColumnNode :

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;
}

Мы будем использовать эвристический поиск, чтобы найти столбцы и вернуть подмножество матрицы:

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. Оба решают самые сложные головоломки за считанные секунды.

Наконец, как всегда, код, использованный во время обсуждения, можно найти на GitHub .