Buat Pemecah Sudoku di Java

1. Ikhtisar

Pada artikel ini, kita akan melihat teka-teki Sudoku dan algoritma yang digunakan untuk memecahkannya.

Selanjutnya, kami akan menerapkan solusi di Java. Solusi pertama adalah serangan brute-force sederhana. Yang kedua akan menggunakan teknik Dancing Links.

Ingatlah bahwa fokus kita akan fokus pada algoritma dan bukan pada desain OOP.

2. Puzzle Sudoku

Sederhananya, Sudoku adalah teka-teki penempatan angka kombinatorial dengan kisi sel 9 x 9 yang sebagian diisi dengan angka dari 1 hingga 9. Tujuannya adalah untuk mengisi bidang kosong yang tersisa dengan sisa angka sehingga setiap baris dan kolom hanya akan memiliki satu jumlah masing-masing jenis.

Terlebih lagi, setiap 3 x 3 sub-bagian grid tidak boleh memiliki nomor yang diduplikasi juga. Tingkat kesulitan secara alami meningkat dengan jumlah bidang kosong di setiap papan.

2.1. Papan Tes

Untuk membuat solusi kami lebih menarik dan untuk memvalidasi algoritme, kami akan menggunakan papan "sudoku tersulit di dunia", yaitu:

8 . . . . . . . . . . 3 6 . . . . . . 7 . . 9 . 2 . . . 5 . . . 7 . . . . . . . 4 5 7 . . . . . 1 . . . 3 . . . 1 . . . . 6 8 . . 8 5 . . . 1 . . 9 . . . . 4 . .

2.2. Papan Terselesaikan

Dan, untuk merusak solusi dengan cepat - teka-teki yang diselesaikan dengan benar akan memberi kita hasil sebagai berikut:

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. Algoritma Mundur

3.1. pengantar

Algoritma mundur mencoba memecahkan teka-teki dengan menguji setiap sel untuk solusi yang valid.

Jika tidak ada pelanggaran batasan, algoritme pindah ke sel berikutnya, mengisi semua solusi potensial dan mengulangi semua pemeriksaan.

Jika ada pelanggaran, maka itu menambah nilai sel. Setelah nilai sel mencapai 9, dan masih terjadi pelanggaran maka algoritme kembali ke sel sebelumnya dan meningkatkan nilai sel tersebut.

Ia mencoba semua solusi yang mungkin.

3.2. Larutan

Pertama-tama, mari kita definisikan papan kita sebagai larik bilangan bulat dua dimensi. Kami akan menggunakan 0 sebagai sel kosong kami.

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

Mari buat metode Solving () yang mengambil papan sebagai parameter input dan melakukan iterasi melalui baris, kolom dan nilai yang menguji setiap sel untuk solusi yang valid:

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

Metode lain yang kami butuhkan adalah metode isValid () , yang akan memeriksa kendala Sudoku, yaitu, memeriksa apakah baris, kolom, dan grid 3 x 3 valid:

private boolean isValid(int[][] board, int row, int column) { return (rowConstraint(board, row) && columnConstraint(board, column) && subsectionConstraint(board, row, column)); }

Ketiga pemeriksaan ini relatif serupa. Pertama, mari kita mulai dengan pemeriksaan baris:

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

Selanjutnya, kami menggunakan kode yang hampir identik untuk memvalidasi kolom:

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

Selanjutnya, kita perlu memvalidasi sub-bagian 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; }

Akhirnya, kita membutuhkan metode 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; }

Sekali, semua yang dilakukan metode isValid () hanya dapat mengembalikan true .

Kami hampir siap untuk menguji solusinya sekarang. Algoritma selesai. Namun, ini hanya mengembalikan true atau false .

Oleh karena itu, untuk memeriksa papan secara visual, kita hanya perlu mencetak hasilnya. Tampaknya, ini bukan bagian dari algoritme.

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

Kami telah berhasil menerapkan algoritme mundur yang memecahkan teka-teki Sudoku!

Jelas, ada ruang untuk perbaikan karena algoritme secara naif memeriksa setiap kemungkinan kombinasi berulang kali (meskipun kami tahu solusi tertentu tidak valid).

4. Tautan Menari

4.1. Cover yang Tepat

Mari kita lihat solusi lain. Sudoku dapat digambarkan sebagai masalah Exact Cover, yang dapat direpresentasikan oleh matriks insiden yang menunjukkan hubungan antara dua objek.

Misalnya, jika kita mengambil angka dari 1 sampai 7 dan kumpulan himpunan S = {A, B, C, D, E, F} , di mana:

  • A = {1, 4, 7}
  • B = {1, 4}
  • C = {4, 5, 7}
  • D = {3, 5, 6}
  • E = {2, 3, 6, 7}
  • F = {2, 7}

Tujuan kami adalah memilih subset sedemikian rupa sehingga setiap nomor hanya ada sekali dan tidak ada yang diulang, maka namanya.

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:

  1. If the matrix A has no columns, the current partial solution is a valid solution;

    terminate successfully, otherwise, choose a column c (deterministically)

  2. Choose a row r such that Ar, c = 1 (nondeterministically, i.e., try all possibilities)
  3. Include row r in the partial solution
  4. 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

  5. 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.prev

removes the node, while:

node.prev = node node.next = node

restores 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

Dalam tutorial ini, kita telah membahas dua solusi teka-teki sudoku dengan inti Java. Algoritma backtracking, yang merupakan algoritma brute-force, dapat memecahkan teka-teki standar 9 × 9 dengan mudah.

Algoritma Dancing Links yang sedikit lebih rumit telah dibahas juga. Keduanya memecahkan teka-teki tersulit dalam hitungan detik.

Terakhir, seperti biasa, kode yang digunakan selama diskusi dapat ditemukan di GitHub.