-
Notifications
You must be signed in to change notification settings - Fork 0
/
SudokuGenerator.java
90 lines (69 loc) · 2.57 KB
/
SudokuGenerator.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
package sudoku;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
public class SudokuGenerator {
public SudokuPuzzle generateRandomSudoku(SudokuPuzzleType puzzleType) {
SudokuPuzzle puzzle = new SudokuPuzzle(puzzleType.getRows(), puzzleType.getColumns(), puzzleType.getBoxWidth(), puzzleType.getBoxHeight(), puzzleType.getValidValues());
SudokuPuzzle copy = new SudokuPuzzle(puzzle);
Random randomGenerator = new Random();
List<String> notUsedValidValues = new ArrayList<String>(Arrays.asList(copy.getValidValues()));
for(int r = 0;r < copy.getNumRows();r++) {
int randomValue = randomGenerator.nextInt(notUsedValidValues.size());
copy.makeMove(r, 0, notUsedValidValues.get(randomValue), true);
notUsedValidValues.remove(randomValue);
}
backtrackSudokuSolver(0, 0, copy);
int numberOfValuesToKeep = (int)(0.22222*(copy.getNumRows()*copy.getNumRows()));
for(int i = 0;i < numberOfValuesToKeep;) {
int randomRow = randomGenerator.nextInt(puzzle.getNumRows());
int randomColumn = randomGenerator.nextInt(puzzle.getNumColumns());
if(puzzle.isSlotAvailable(randomRow, randomColumn)) {
puzzle.makeMove(randomRow, randomColumn, copy.getValue(randomRow, randomColumn), false);
i++;
}
}
return puzzle;
}
private boolean backtrackSudokuSolver(int r,int c,SudokuPuzzle puzzle) {
//If the move is not valid return false
if(!puzzle.inRange(r,c)) {
return false;
}
//if the current space is empty
if(puzzle.isSlotAvailable(r, c)) {
//loop to find the correct value for the space
for(int i = 0;i < puzzle.getValidValues().length;i++) {
//if the current number works in the space
if(!puzzle.numInRow(r, puzzle.getValidValues()[i]) && !puzzle.numInCol(c,puzzle.getValidValues()[i]) && !puzzle.numInBox(r,c,puzzle.getValidValues()[i])) {
//make the move
puzzle.makeMove(r, c, puzzle.getValidValues()[i], true);
//if puzzle solved return true
if(puzzle.boardFull()) {
return true;
}
//go to next move
if(r == puzzle.getNumRows() - 1) {
if(backtrackSudokuSolver(0,c + 1,puzzle)) return true;
} else {
if(backtrackSudokuSolver(r + 1,c,puzzle)) return true;
}
}
}
}
//if the current space is not empty
else {
//got to the next move
if(r == puzzle.getNumRows() - 1) {
return backtrackSudokuSolver(0,c + 1,puzzle);
} else {
return backtrackSudokuSolver(r + 1,c,puzzle);
}
}
//undo move
puzzle.makeSlotEmpty(r, c);
//backtrack
return false;
}
}