Skip to content

Commit 43a4d08

Browse files
pivovaritpivovarit
authored
Sudoku refactor (eugenp#3556)
* BacktrackingAlgorithm refactor * DancingLinks refactor
1 parent bd9a87c commit 43a4d08

5 files changed

Lines changed: 76 additions & 78 deletions

File tree

‎algorithms/src/main/java/com/baeldung/algorithms/sudoku/BacktrackingAlgorithm.java‎

Lines changed: 40 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -3,25 +3,25 @@
33
import java.util.stream.IntStream;
44

55
public class BacktrackingAlgorithm {
6-
7-
private static int BOARD_SIZE = 9;
8-
private static int SUBSECTION_SIZE = 3;
9-
private static int BOARD_START_INDEX = 0;
10-
11-
private static int NO_VALUE = 0;
12-
private static int MIN_VALUE = 1;
13-
private static int MAX_VALUE = 9;
146

15-
public static int[][] board = {
16-
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
17-
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
18-
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
19-
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
20-
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
21-
{ 0, 0, 0, 1, 0, 0, 0, 3, 0 },
22-
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
23-
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
24-
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 }
7+
private static final int BOARD_SIZE = 9;
8+
private static final int SUBSECTION_SIZE = 3;
9+
private static final int BOARD_START_INDEX = 0;
10+
11+
private static final int NO_VALUE = 0;
12+
private static final int MIN_VALUE = 1;
13+
private static final int MAX_VALUE = 9;
14+
15+
private static int[][] board = {
16+
{8, 0, 0, 0, 0, 0, 0, 0, 0},
17+
{0, 0, 3, 6, 0, 0, 0, 0, 0},
18+
{0, 7, 0, 0, 9, 0, 2, 0, 0},
19+
{0, 5, 0, 0, 0, 7, 0, 0, 0},
20+
{0, 0, 0, 0, 4, 5, 7, 0, 0},
21+
{0, 0, 0, 1, 0, 0, 0, 3, 0},
22+
{0, 0, 1, 0, 0, 0, 0, 6, 8},
23+
{0, 0, 8, 5, 0, 0, 0, 1, 0},
24+
{0, 9, 0, 0, 0, 0, 4, 0, 0}
2525
};
2626

2727
public static void main(String[] args) {
@@ -30,7 +30,7 @@ public static void main(String[] args) {
3030
solver.printBoard();
3131
}
3232

33-
public void printBoard() {
33+
private void printBoard() {
3434
for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) {
3535
for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) {
3636
System.out.print(board[row][column] + " ");
@@ -39,17 +39,16 @@ public void printBoard() {
3939
}
4040
}
4141

42-
public boolean solve(int[][] board) {
42+
private boolean solve(int[][] board) {
4343
for (int r = BOARD_START_INDEX; r < BOARD_SIZE; r++) {
4444
for (int c = BOARD_START_INDEX; c < BOARD_SIZE; c++) {
4545
if (board[r][c] == NO_VALUE) {
4646
for (int k = MIN_VALUE; k <= MAX_VALUE; k++) {
4747
board[r][c] = k;
4848
if (isValid(board, r, c) && solve(board)) {
4949
return true;
50-
} else {
51-
board[r][c] = NO_VALUE;
5250
}
51+
board[r][c] = NO_VALUE;
5352
}
5453
return false;
5554
}
@@ -58,16 +57,22 @@ public boolean solve(int[][] board) {
5857
return true;
5958
}
6059

61-
public boolean isValid(int[][] board, int r, int c) {
62-
return (rowConstraint(board, r) &&
63-
columnConstraint(board, c) &&
64-
subsectionConstraint(board, r, c));
60+
private boolean isValid(int[][] board, int r, int c) {
61+
return rowConstraint(board, r) &&
62+
columnConstraint(board, c) &&
63+
subsectionConstraint(board, r, c);
6564
}
6665

6766
private boolean subsectionConstraint(int[][] board, int r, int c) {
6867
boolean[] constraint = new boolean[BOARD_SIZE];
69-
for (int i = (r / SUBSECTION_SIZE) * SUBSECTION_SIZE; i < (r / SUBSECTION_SIZE) * SUBSECTION_SIZE + SUBSECTION_SIZE; i++) {
70-
for (int j = (c / SUBSECTION_SIZE) * SUBSECTION_SIZE; j < (c / SUBSECTION_SIZE) * SUBSECTION_SIZE + SUBSECTION_SIZE; j++) {
68+
int subsectionRowStart = (r / SUBSECTION_SIZE) * SUBSECTION_SIZE;
69+
int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE;
70+
71+
int subsectionColumnStart = (c / SUBSECTION_SIZE) * SUBSECTION_SIZE;
72+
int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE;
73+
74+
for (int i = subsectionRowStart; i < subsectionRowEnd; i++) {
75+
for (int j = subsectionColumnStart; j < subsectionColumnEnd; j++) {
7176
if (!checkConstraint(board, i, constraint, j)) return false;
7277
}
7378
}
@@ -76,28 +81,24 @@ private boolean subsectionConstraint(int[][] board, int r, int c) {
7681

7782
private boolean columnConstraint(int[][] board, int c) {
7883
boolean[] constraint = new boolean[BOARD_SIZE];
79-
for (int i = BOARD_START_INDEX; i < BOARD_SIZE; i++) {
80-
if (!checkConstraint(board, i, constraint, c)) return false;
81-
}
82-
return true;
84+
return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
85+
.allMatch(i -> checkConstraint(board, i, constraint, c));
8386
}
8487

8588
private boolean rowConstraint(int[][] board, int r) {
8689
boolean[] constraint = new boolean[BOARD_SIZE];
87-
for (int i = BOARD_START_INDEX; i < BOARD_SIZE; i++) {
88-
if (!checkConstraint(board, r, constraint, i)) return false;
89-
}
90-
return true;
90+
return IntStream.range(BOARD_START_INDEX, BOARD_SIZE)
91+
.allMatch(i -> checkConstraint(board, r, constraint, i));
9192
}
9293

9394
private boolean checkConstraint(int[][] board, int r, boolean[] constraint, int c) {
94-
if (board[r][c] >= MIN_VALUE && board[r][c] <= MAX_VALUE) {
95-
if (constraint[board[r][c] - 1] == false) {
95+
if (board[r][c] != NO_VALUE) {
96+
if (!constraint[board[r][c] - 1]) {
9697
constraint[board[r][c] - 1] = true;
9798
} else {
9899
return false;
99100
}
100101
}
101102
return true;
102103
}
103-
}
104+
}

‎algorithms/src/main/java/com/baeldung/algorithms/sudoku/ColumnNode.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ class ColumnNode extends DancingNode {
44
int size;
55
String name;
66

7-
public ColumnNode(String n) {
7+
ColumnNode(String n) {
88
super();
99
size = 0;
1010
name = n;

‎algorithms/src/main/java/com/baeldung/algorithms/sudoku/DancingLinks.java‎

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -50,10 +50,9 @@ private ColumnNode selectColumnNodeHeuristic() {
5050

5151
private ColumnNode makeDLXBoard(boolean[][] grid) {
5252
final int COLS = grid[0].length;
53-
final int ROWS = grid.length;
5453

5554
ColumnNode headerNode = new ColumnNode("header");
56-
ArrayList<ColumnNode> columnNodes = new ArrayList<ColumnNode>();
55+
List<ColumnNode> columnNodes = new ArrayList<>();
5756

5857
for (int i = 0; i < COLS; i++) {
5958
ColumnNode n = new ColumnNode(Integer.toString(i));
@@ -62,10 +61,10 @@ private ColumnNode makeDLXBoard(boolean[][] grid) {
6261
}
6362
headerNode = headerNode.R.C;
6463

65-
for (int i = 0; i < ROWS; i++) {
64+
for (boolean[] aGrid : grid) {
6665
DancingNode prev = null;
6766
for (int j = 0; j < COLS; j++) {
68-
if (grid[i][j] == true) {
67+
if (aGrid[j]) {
6968
ColumnNode col = columnNodes.get(j);
7069
DancingNode newNode = new DancingNode(col);
7170
if (prev == null)
@@ -82,21 +81,21 @@ private ColumnNode makeDLXBoard(boolean[][] grid) {
8281
return headerNode;
8382
}
8483

85-
public DancingLinks(boolean[][] cover) {
84+
DancingLinks(boolean[][] cover) {
8685
header = makeDLXBoard(cover);
8786
}
8887

8988
public void runSolver() {
90-
answer = new LinkedList<DancingNode>();
89+
answer = new LinkedList<>();
9190
search(0);
9291
}
9392

94-
public void handleSolution(List<DancingNode> answer) {
93+
private void handleSolution(List<DancingNode> answer) {
9594
int[][] result = parseBoard(answer);
9695
printSolution(result);
9796
}
9897

99-
int size = 9;
98+
private int size = 9;
10099

101100
private int[][] parseBoard(List<DancingNode> answer) {
102101
int[][] result = new int[size][size];
@@ -120,12 +119,12 @@ private int[][] parseBoard(List<DancingNode> answer) {
120119
return result;
121120
}
122121

123-
public static void printSolution(int[][] result) {
122+
private static void printSolution(int[][] result) {
124123
int N = result.length;
125-
for (int i = 0; i < N; i++) {
126-
String ret = "";
124+
for (int[] aResult : result) {
125+
StringBuilder ret = new StringBuilder();
127126
for (int j = 0; j < N; j++) {
128-
ret += result[i][j] + " ";
127+
ret.append(aResult[j]).append(" ");
129128
}
130129
System.out.println(ret);
131130
}

‎algorithms/src/main/java/com/baeldung/algorithms/sudoku/DancingLinksAlgorithm.java‎

Lines changed: 22 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,37 @@
11
package com.baeldung.algorithms.sudoku;
22

3-
import java.util.*;
3+
import java.util.Arrays;
44

55
public class DancingLinksAlgorithm {
6-
private static int BOARD_SIZE = 9;
7-
private static int SUBSECTION_SIZE = 3;
8-
private static int NO_VALUE = 0;
9-
private static int CONSTRAINTS = 4;
10-
private static int MIN_VALUE = 1;
11-
private static int MAX_VALUE = 9;
12-
private static int COVER_START_INDEX = 1;
6+
private static final int BOARD_SIZE = 9;
7+
private static final int SUBSECTION_SIZE = 3;
8+
private static final int NO_VALUE = 0;
9+
private static final int CONSTRAINTS = 4;
10+
private static final int MIN_VALUE = 1;
11+
private static final int MAX_VALUE = 9;
12+
private static final int COVER_START_INDEX = 1;
1313

14-
public static int[][] board = {
15-
{ 8, 0, 0, 0, 0, 0, 0, 0, 0 },
16-
{ 0, 0, 3, 6, 0, 0, 0, 0, 0 },
17-
{ 0, 7, 0, 0, 9, 0, 2, 0, 0 },
18-
{ 0, 5, 0, 0, 0, 7, 0, 0, 0 },
19-
{ 0, 0, 0, 0, 4, 5, 7, 0, 0 },
20-
{ 0, 0, 0, 1, 0, 0, 0, 3, 0 },
21-
{ 0, 0, 1, 0, 0, 0, 0, 6, 8 },
22-
{ 0, 0, 8, 5, 0, 0, 0, 1, 0 },
23-
{ 0, 9, 0, 0, 0, 0, 4, 0, 0 }
24-
};
14+
private static int[][] board = {
15+
{8, 0, 0, 0, 0, 0, 0, 0, 0},
16+
{0, 0, 3, 6, 0, 0, 0, 0, 0},
17+
{0, 7, 0, 0, 9, 0, 2, 0, 0},
18+
{0, 5, 0, 0, 0, 7, 0, 0, 0},
19+
{0, 0, 0, 0, 4, 5, 7, 0, 0},
20+
{0, 0, 0, 1, 0, 0, 0, 3, 0},
21+
{0, 0, 1, 0, 0, 0, 0, 6, 8},
22+
{0, 0, 8, 5, 0, 0, 0, 1, 0},
23+
{0, 9, 0, 0, 0, 0, 4, 0, 0}
24+
};
2525

2626
public static void main(String[] args) {
2727
DancingLinksAlgorithm solver = new DancingLinksAlgorithm();
2828
solver.solve(board);
2929
}
3030

31-
public boolean solve(int[][] board) {
31+
private void solve(int[][] board) {
3232
boolean[][] cover = initializeExactCoverBoard(board);
3333
DancingLinks dlx = new DancingLinks(cover);
3434
dlx.runSolver();
35-
36-
return true;
3735
}
3836

3937
private int getIndex(int row, int col, int num) {
@@ -54,7 +52,7 @@ private boolean[][] createExactCoverBoard() {
5452
}
5553
}
5654
}
57-
55+
5856
// Row constrain.
5957
for (int r = COVER_START_INDEX; r <= BOARD_SIZE; r++) {
6058
for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) {
@@ -74,7 +72,7 @@ private boolean[][] createExactCoverBoard() {
7472
}
7573
}
7674
}
77-
75+
7876
// Subsection constraint
7977
for (int br = COVER_START_INDEX; br <= BOARD_SIZE; br += SUBSECTION_SIZE) {
8078
for (int bc = COVER_START_INDEX; bc <= BOARD_SIZE; bc += SUBSECTION_SIZE) {

‎algorithms/src/main/java/com/baeldung/algorithms/sudoku/DancingNode.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,11 +39,11 @@ void relinkUD() {
3939
this.U.D = this.D.U = this;
4040
}
4141

42-
public DancingNode() {
42+
DancingNode() {
4343
L = R = U = D = this;
4444
}
4545

46-
public DancingNode(ColumnNode c) {
46+
DancingNode(ColumnNode c) {
4747
this();
4848
C = c;
4949
}

0 commit comments

Comments
 (0)