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 } };Нека създадем метод за решаване () , който приема дъската като входен параметър и итерира през редове, колони и стойности, тествайки всяка клетка за валидно решение:
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 () , който ще провери ограниченията на Sudoku, т.е. ще провери дали редът, колоната и мрежата 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} , където:
- A = {1, 4, 7}
- B = {1, 4}
- C = {4, 5, 7}
- D = {3, 5, 6}
- E = {2, 3, 6, 7}
- F = {2, 7}
Нашата цел е да изберем такива подмножества, че всяко число да е там само веднъж и нито едно да не се повтаря, следователно и името.
We can represent the problem using a matrix, where columns are numbers and rows are sets:
| 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 |Subcollection S* = {B, D, F} is exact cover:
| 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 |Each column has exactly one 1 in all selected rows.
4.2. Algorithm X
Algorithm X is a “trial-and-error approach” to find all solutions to the exact cover problem, i.e. starting with our example collection S = {A, B, C, D, E, F}, find subcollection S* = {B, D, F}.
Algorithm X works as follows:
- 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 anddelete column j from matrix A
- Repeat this algorithm recursively on the reduced matrix A
An efficient implementation of the Algorithm X is Dancing Links algorithm (DLX for short) suggested by Dr. Donald Knuth.
The following solution has been heavily inspired by this Java implementation.
4.3. Exact Cover Problem
First, we need to create a matrix that will represent Sudoku puzzle as an Exact Cover problem. The matrix will have 9^3 rows, i.e., one row for every single possible position (9 rows x 9 columns) of every possible number (9 numbers).
Columns will represent the board (again 9 x 9) multiplied by the number of constraints.
We've already defined three constraints:
- each row will have only one number of each kind
- each column will have only one number of each kind
- each subsection will have only one number of each kind
Additionally, there is implicit fourth constraint:
- only one number can be in a cell
This gives four constraints in total and therefore 9 x 9 x 4 columns in the Exact Cover matrix:
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; }Next, we need to update the newly created board with our initial puzzle layout:
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; }We are ready to move to the next stage now. Let's create two classes that will link our cells together.
4.4. Dancing Node
Dancing Links algorithm operates on a basic observation that following operation on doubly linked lists of nodes:
node.prev.next = node.next node.next.prev = node.prevremoves the node, while:
node.prev = node node.next = noderestores the node.
Each node in DLX is linked to the node on the left, right, up and down.
DancingNode class will have all operations needed to add or remove nodes:
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. Column Node
ColumnNode class will link columns together:
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. Solver
Next, we need to create a grid consisting of our DancingNode and ColumnNode objects:
private ColumnNode makeDLXBoard(boolean[][] grid) { int COLS = grid[0].length; ColumnNode headerNode = new ColumnNode("header"); List 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; }We'll use heuristic search to find columns and return a subset of the matrix:
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; }Finally, we can recursively search for the answer:
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(); } }If there are no more columns, then we can print out the solved Sudoku board.
5. Benchmarks
We can compare those two different algorithms by running them on the same computer (this way we can avoid differences in components, the speed of CPU or RAM, etc.). The actual times will differ from computer to computer.
However, we should be able to see relative results, and this will tell us which algorithm runs faster.
The Backtracking Algorithm takes around 250ms to solve the board.
If we compare this with the Dancing Links, which takes around 50ms, we can see a clear winner. Dancing Links is around five times faster when solving this particular example.
6. Conclusion
В този урок обсъдихме две решения за пъзел судоку с основна Java. Алгоритъмът за обратно проследяване, който е алгоритъм на груба сила, може лесно да реши стандартния пъзел 9 × 9.
Обсъден е и малко по-сложният алгоритъм за танцуващи връзки. И двамата решават най-трудните пъзели за секунди.
И накрая, както винаги, кодът, използван по време на дискусията, може да бъде намерен в GitHub.