-
Notifications
You must be signed in to change notification settings - Fork 0
/
SudokuGenerator.java
131 lines (116 loc) · 3.58 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
// Sudoku Project
// November 2017
// Andy Vainauskas
// Reference: https://github.com/SomeKittens/Sudoku-Project/blob/master/SudokuGenerator.java
//
// SudokuGenerator uses an algorithm to generate a new Sudoku
// puzzle depending on the desired difficulty level. The difficulty is
// based upon the number of holes that is generated in the makeHoles() method.
//
import java.util.*;
public class SudokuGenerator {
int[][] board;
public SudokuGenerator() {
board = new int[9][9];
}
// Creates and returns a 2D int array for a new Sudoku puzzle
public int[][] nextBoard(int difficulty)
{
board = new int[9][9];
nextCell(0,0);
makeHoles(difficulty);
return board;
}
// Recursive method that cycles through every possible number to place in a cell.
public boolean nextCell(int x, int y)
{
int nextX = x;
int nextY = y;
int[] toCheck = {1,2,3,4,5,6,7,8,9};
Random random = new Random();
int tmp = 0;
int current = 0;
int top = toCheck.length;
// Randomly selects numbers 1-9 to enter into the puzzle
for(int i = top-1; i > 0; --i)
{
current = random.nextInt(i);
tmp = toCheck[current];
toCheck[current] = toCheck[i];
toCheck[i] = tmp;
}
for(int i = 0; i < toCheck.length; ++i)
{
if(legalMove(x, y, toCheck[i]))
{
board[x][y] = toCheck[i];
if(x == 8)
{
if(y == 8)
return true;
else
{
nextX = 0;
nextY = y + 1;
}
} else {
nextX = x + 1;
}
if(nextCell(nextX, nextY))
return true;
}
}
board[x][y] = 0;
return false;
}
// Determines if the value "current" is allowed to be placed in the puzzle based on the coordinates x and y
private boolean legalMove(int x, int y, int current) {
for(int i=0;i<9;i++) {
if(current == board[x][i])
return false;
}
for(int i=0;i<9;i++) {
if(current == board[i][y])
return false;
}
int cornerX = 0;
int cornerY = 0;
if(x > 2)
if(x > 5)
cornerX = 6;
else
cornerX = 3;
if(y > 2)
if(y > 5)
cornerY = 6;
else
cornerY = 3;
for(int i = cornerX; i < 10 && i < cornerX+3; ++i)
for(int j = cornerY;j < 10 && j < cornerY+3; ++j)
if(current == board[i][j])
return false;
return true;
}
// Randomly assigns a variable amount of blank spaces (int holesToMake) to the board.
public void makeHoles(int holesToMake)
{
/* We define difficulty as follows:
Easy: 32+ clues (49 or fewer holes)
Medium: 27-31 clues (50-54 holes)
Hard: 26 or fewer clues (54+ holes)
*/
double remainingSquares = 81;
double remainingHoles = (double)holesToMake;
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
{
double holeChance = remainingHoles/remainingSquares;
if(Math.random() <= holeChance)
{
board[i][j] = 0;
remainingHoles--;
}
remainingSquares--;
}
}
}