ساخت برنامه حل سودوکو در جاوا — از صفر تا صد

1int[][] board = {
2  { 8, 0, 0, 0, 0, 0, 0, 0, 0 },
3  { 0, 0, 3, 6, 0, 0, 0, 0, 0 },
4  { 0, 7, 0, 0, 9, 0, 2, 0, 0 },
5  { 0, 5, 0, 0, 0, 7, 0, 0, 0 },
6  { 0, 0, 0, 0, 4, 5, 7, 0, 0 },
7  { 0, 0, 0, 1, 0, 0, 0, 3, 0 },
8  { 0, 0, 1, 0, 0, 0, 0, 6, 8 },
9  { 0, 0, 8, 5, 0, 0, 0, 1, 0 },
10  { 0, 9, 0, 0, 0, 0, 4, 0, 0 } 
11};

1private boolean solve(int[][] board) {
2    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
3        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
4            if (board[row][column] == NO_VALUE) {
5                for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
6                    board[row][column] = k;
7                    if (isValid(board, row, column) && solve(board)) {
8                        return true;
9                    }
10                    board[row][column] = NO_VALUE;
11                }
12                return false;
13            }
14        }
15    }
16    return true;
17}

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

1private boolean rowConstraint(int[][] board, int row) {
2    boolean[] constraint = new boolean[BOARD_SIZE];
3    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
4      .allMatch(column -> checkConstraint(board, row, constraint, column));
5}

1private boolean columnConstraint(int[][] board, int column) {
2    boolean[] constraint = new boolean[BOARD_SIZE];
3    return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
4      .allMatch(row -> checkConstraint(board, row, constraint, column));
5}

1private boolean subsectionConstraint(int[][] board, int row, int column) {
2    boolean[] constraint = new boolean[BOARD_SIZE];
3    int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE;
4    int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
5 
6    int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE;
7    int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
8 
9    for (int r = subsectionRowStart; r < subsectionRowEnd; r++) {
10        for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) {
11            if (!checkConstraint(board, r, constraint, c)) return false;
12        }
13    }
14    return true;
15}

1boolean checkConstraint(
2  int[][] board, 
3  int row, 
4  boolean[] constraint, 
5  int column) {
6    if (board[row][column] != NO_VALUE) {
7        if (!constraint[board[row][column] - 1]) {
8            constraint[board[row][column] - 1] = true;
9        } else {
10            return false;
11        }
12    }
13    return true;
14}

1private void printBoard() {
2    for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
3        for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
4            System.out.print(board[row][column] + " ");
5        }
6        System.out.println();
7    }
8}

1  | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
2A | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
3B | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
4C | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
5D | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
6E | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
7F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

1private boolean[][] createExactCoverBoard() {
2    boolean[][] coverBoard = new boolean
3      [BOARD_SIZE * BOARD_SIZE * MAX_VALUE]
4      [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS];
5 
6    int hBase = 0;
7    hBase = checkCellConstraint(coverBoard, hBase);
8    hBase = checkRowConstraint(coverBoard, hBase);
9    hBase = checkColumnConstraint(coverBoard, hBase);
10    checkSubsectionConstraint(coverBoard, hBase);
11     
12    return coverBoard;
13}
14 
15private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) {
16    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) {
17        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) {
18            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
19                for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) {
20                    for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) {
21                        int index = getIndex(row + rowDelta, column + columnDelta, n);
22                        coverBoard[index][hBase] = true;
23                    }
24                }
25            }
26        }
27    }
28    return hBase;
29}
30 
31private int checkColumnConstraint(boolean[][] coverBoard, int hBase) {
32    for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) {
33        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
34            for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
35                int index = getIndex(row, column, n);
36                coverBoard[index][hBase] = true;
37            }
38        }
39    }
40    return hBase;
41}
42 
43private int checkRowConstraint(boolean[][] coverBoard, int hBase) {
44    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) {
45        for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
46            for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
47                int index = getIndex(row, column, n);
48                coverBoard[index][hBase] = true;
49            }
50        }
51    }
52    return hBase;
53}
54 
55private int checkCellConstraint(boolean[][] coverBoard, int hBase) {
56    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
57        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) {
58            for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) {
59                int index = getIndex(row, column, n);
60                coverBoard[index][hBase] = true;
61            }
62        }
63    }
64    return hBase;
65}

1private boolean[][] initializeExactCoverBoard(int[][] board) {
2    boolean[][] coverBoard = createExactCoverBoard();
3    for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) {
4        for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) {
5            int n = board[row - 1][column - 1];
6            if (n != NO_VALUE) {
7                for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
8                    if (num != n) {
9                        Arrays.fill(coverBoard[getIndex(row, column, num)], false);
10                    }
11                }
12            }
13        }
14    }
15    return coverBoard;
16}

1node.prev.next = node.next
2node.next.prev = node.prev

1node.prev = node
2node.next = node

1class DancingNode {
2    DancingNode L, R, U, D;
3    ColumnNode C;
4 
5    DancingNode hookDown(DancingNode node) {
6        assert (this.C == node.C);
7        node.D = this.D;
8        node.D.U = node;
9        node.U = this;
10        this.D = node;
11        return node;
12    }
13 
14    DancingNode hookRight(DancingNode node) {
15        node.R = this.R;
16        node.R.L = node;
17        node.L = this;
18        this.R = node;
19        return node;
20    }
21 
22    void unlinkLR() {
23        this.L.R = this.R;
24        this.R.L = this.L;
25    }
26 
27    void relinkLR() {
28        this.L.R = this.R.L = this;
29    }
30 
31    void unlinkUD() {
32        this.U.D = this.D;
33        this.D.U = this.U;
34    }
35 
36    void relinkUD() {
37        this.U.D = this.D.U = this;
38    }
39 
40    DancingNode() {
41        L = R = U = D = this;
42    }
43 
44    DancingNode(ColumnNode c) {
45        this();
46        C = c;
47    }
48}

1class ColumnNode extends DancingNode {
2    int size;
3    String name;
4 
5    ColumnNode(String n) {
6        super();
7        size = 0;
8        name = n;
9        C = this;
10    }
11 
12    void cover() {
13        unlinkLR();
14        for (DancingNode i = this.D; i != this; i = i.D) {
15            for (DancingNode j = i.R; j != i; j = j.R) {
16                j.unlinkUD();
17                j.C.size--;
18            }
19        }
20    }
21 
22    void uncover() {
23        for (DancingNode i = this.U; i != this; i = i.U) {
24            for (DancingNode j = i.L; j != i; j = j.L) {
25                j.C.size++;
26                j.relinkUD();
27            }
28        }
29        relinkLR();
30    }
31}

1private ColumnNode makeDLXBoard(boolean[][] grid) {
2    int COLS = grid[0].length;
3 
4    ColumnNode headerNode = new ColumnNode("header");
5    List<ColumnNode> columnNodes = new ArrayList<>();
6 
7    for (int i = 0; i < COLS; i++) {
8        ColumnNode n = new ColumnNode(Integer.toString(i));
9        columnNodes.add(n);
10        headerNode = (ColumnNode) headerNode.hookRight(n);
11    }
12    headerNode = headerNode.R.C;
13 
14    for (boolean[] aGrid : grid) {
15        DancingNode prev = null;
16        for (int j = 0; j < COLS; j++) {
17            if (aGrid[j]) {
18                ColumnNode col = columnNodes.get(j);
19                DancingNode newNode = new DancingNode(col);
20                if (prev == null) prev = newNode;
21                col.U.hookDown(newNode);
22                prev = prev.hookRight(newNode);
23                col.size++;
24            }
25        }
26    }
27 
28    headerNode.size = COLS;
29 
30    return headerNode;
31}

1private ColumnNode selectColumnNodeHeuristic() {
2    int min = Integer.MAX_VALUE;
3    ColumnNode ret = null;
4    for (
5      ColumnNode c = (ColumnNode) header.R; 
6      c != header; 
7      c = (ColumnNode) c.R) {
8        if (c.size < min) {
9            min = c.size;
10            ret = c;
11        }
12    }
13    return ret;
14}

1private void search(int k) {
2    if (header.R == header) {
3        handleSolution(answer);
4    } else {
5        ColumnNode c = selectColumnNodeHeuristic();
6        c.cover();
7 
8        for (DancingNode r = c.D; r != c; r = r.D) {
9            answer.add(r);
10 
11            for (DancingNode j = r.R; j != r; j = j.R) {
12                j.C.cover();
13            }
14 
15            search(k + 1);
16 
17            r = answer.remove(answer.size() - 1);
18            c = r.C;
19 
20            for (DancingNode j = r.L; j != r; j = j.L) {
21                j.C.uncover();
22            }
23        }
24        c.uncover();
25    }
26}