Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitca4b75b

Browse files
committed
Update Sudoku.java
1 parentacf5d3f commitca4b75b

File tree

1 file changed

+137
-37
lines changed

1 file changed

+137
-37
lines changed

‎Backtracking/Sudoku.java

Lines changed: 137 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,24 @@
11
packagebacktracking;
22

3+
importjava.util.InputMismatchException;
34
importjava.util.Random;
45
importjava.util.Scanner;
5-
importjava.util.Stack;
6+
importjava.util.Deque;
7+
importjava.util.ArrayDeque;
68

79
publicclassSudoku {
810
privatestaticfinalintN =9;// board size
9-
privatestaticfinalintNsqrt =3;// block size
10-
char[][]board =newchar[N][N];// Sudoku board
11+
privatestaticfinalintNsqrt =(int)Math.sqrt(N);// block size
12+
int[][]board =newint[N][N];// Sudoku board
1113
/*
1214
* level:
1315
* 1 (EASY) - mostly filled board
1416
* 2 (MEDIUM) - halfly filled board
15-
*3 (HARD) - mostly empty board
17+
* (HARD) - mostly empty board
1618
*/
17-
privatestaticfinaldoubleEMPTY_RATIO_EASY =0.25,
19+
privatestaticfinaldoubleEMPTY_RATIO_EASY =0.3,
1820
EMPTY_RATIO_MEDIUM =0.5,
19-
EMPTY_RATIO_HARD =0.75;
21+
EMPTY_RATIO_HARD =0.7;
2022

2123
/**
2224
* construct a partially filled board randomly. Difficulty level is set to default, i.e., 1
@@ -35,21 +37,30 @@ public Sudoku(int level) {
3537
}
3638

3739
/**
38-
* construct a partially filled board with input
40+
* construct a partially filled board with input (2D int matrix)
41+
* @param board - specified input
42+
*/
43+
publicSudoku(int[][]board) {
44+
this.board =board;
45+
System.out.println("Original board:");
46+
printSudoku();
47+
assert(isValid());
48+
}
49+
50+
/**
51+
* construct a partially filled board with input (string array)
3952
* @param board - specified input
4053
*/
4154
publicSudoku(String[]board) {
4255
for(inti=0;i<N;i++) {
4356
String[]str =board[i].split(",");
4457
for(intj=0;j<N;j++) {
45-
this.board[i][j] =str[j].charAt(0);
46-
if(this.board[i][j]=='0') {
47-
this.board[i][j] =0;
48-
}
58+
this.board[i][j] =Integer.parseInt(str[j]);
4959
}
5060
}
5161
System.out.println("Original board:");
5262
printSudoku();
63+
assert(isValid());
5364
}
5465

5566
/**
@@ -60,7 +71,7 @@ public void createRandomSudoku(int level) {
6071
inttotalLocations =N*N,remove =0;
6172

6273
//push all N*N empty spots into the stack
63-
Stack<Integer>emptyLocationList =newStack<>();
74+
Deque<Integer>emptyLocationList =newArrayDeque<>();
6475
for(inti=totalLocations-1;i>=0;i--) {
6576
emptyLocationList.push(i);
6677
}
@@ -132,7 +143,7 @@ private void swap(int[] nums, int i, int j) {
132143
* solve Sudoku main function
133144
*/
134145
publicvoidsolveSudoku() {
135-
Stack<Integer>emptyLocationList =getEmptySpots(0,0);
146+
Deque<Integer>emptyLocationList =getEmptySpots(0,0);
136147
if(!solve(emptyLocationList,false,newRandom())) {
137148
System.out.println("No solution!");
138149
}
@@ -149,18 +160,22 @@ public void solveSudoku() {
149160
* @param rm - Random instance
150161
* @return true if all empty spots are filled
151162
*/
152-
privatebooleansolve(Stack<Integer>emptyLocationList,booleanstartWithRandomInitialValue,Randomrm) {
163+
privatebooleansolve(Deque<Integer>emptyLocationList,booleanstartWithRandomInitialValue,Randomrm) {
153164
if(emptyLocationList.size()==0)returntrue;
165+
/*{
166+
printSudoku();
167+
return false;
168+
}*/
154169
intfirstValue =emptyLocationList.peek();
155170
introw =firstValue/N,col =firstValue%N;
156-
intstartIndex =startWithRandomInitialValue ?rm.nextInt(N)+1 :1;
157-
for(intk=startIndex;k<=N+startIndex;k++) {
171+
intstartValue =startWithRandomInitialValue ?rm.nextInt(N) :0;
172+
for(intk=startValue;k<=N+startValue;k++) {
158173
inttrueValue =k%N +1;
159-
if(isSafe(board,row,col,(char)(trueValue+'0'))) {
160-
board[row][col] =(char)(trueValue+'0');
161-
emptyLocationList.pop();
174+
if(isSafe(board,row,col,trueValue)) {
175+
board[row][col] =trueValue;
176+
emptyLocationList.pop();
162177
if(solve(emptyLocationList,startWithRandomInitialValue,rm))returntrue;
163-
board[row][col] =' ';
178+
board[row][col] =0;
164179
emptyLocationList.push(firstValue);
165180
}
166181
}
@@ -175,7 +190,7 @@ private boolean solve(Stack<Integer> emptyLocationList, boolean startWithRandomI
175190
* @param ch - number to be placed at location (i, j)
176191
* @return true if placing 'ch' at location (i, j) is allowed, otherwise return false
177192
*/
178-
privatebooleanisSafe(char[][]board,inti,intj,charch) {
193+
privatebooleanisSafe(int[][]board,inti,intj,intch) {
179194
for(intk=0;k<N;k++) {
180195
if(board[k][j]==ch)returnfalse;
181196
if(board[i][k]==ch)returnfalse;
@@ -195,8 +210,8 @@ private boolean isSafe(char[][] board, int i, int j, char ch) {
195210
* @param startj - start column index
196211
* @return stack of all empty spots
197212
*/
198-
privateStack<Integer>getEmptySpots(intstarti,intstartj) {
199-
Stack<Integer>emptyLocationList =newStack<>();
213+
privateDeque<Integer>getEmptySpots(intstarti,intstartj) {
214+
Deque<Integer>emptyLocationList =newArrayDeque<>();
200215
for(inti=starti;i<N+starti;i++) {
201216
for(intj=startj;j<N+startj;j++) {
202217
introw =i%N,col =j%N;
@@ -207,33 +222,88 @@ private Stack<Integer> getEmptySpots(int starti, int startj) {
207222
}
208223
returnemptyLocationList;
209224
}
225+
226+
/**
227+
* check if a Sudoku board is valid
228+
* @return true if the board is valid; false if not
229+
*/
230+
publicbooleanisValid() {
231+
for(inti=0;i<N;i++) {
232+
for(intj=0;j<N;j++) {
233+
if(!isValidBlock(0,j,N,j) || !isValidBlock(i,0,i,N))returnfalse;
234+
if(i%Nsqrt==0 &&j%Nsqrt==0 && !isValidBlock(i,j,i+Nsqrt,j+Nsqrt))returnfalse;
235+
}
236+
}
237+
returntrue;
238+
}
239+
/**
240+
* check if a given block defined by start and end row and column index is valid
241+
* @param starti - start row index
242+
* @param startj - start column index
243+
* @param endi - end row index
244+
* @param endj - end column index
245+
* @return true if the block is valid
246+
*/
247+
privatebooleanisValidBlock(intstarti,intstartj,intendi,intendj) {
248+
int[]digits =newint[N];
249+
for(inti=starti;i<endi;i++) {
250+
for(intj=startj;j<endj;j++) {
251+
if(board[i][j]>0 &&board[i][j]<=N && ++digits[board[i][j]-1]>1)returnfalse;
252+
}
253+
}
254+
returntrue;
255+
}
210256

211257
/**
212258
* print Sudoku board
213259
*/
214260
privatevoidprintSudoku() {
261+
System.out.print("╔");
262+
intcol =0;
263+
while(++col<N) {
264+
System.out.print("═══╦");
265+
}
266+
System.out.println("═══╗");
215267
for(inti=0;i<N;i++) {
216-
if(i%3==0) {
217-
if(i==0 ||i==N-1)
218-
System.out.println("╔═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╦═══╗");
219-
else
220-
System.out.println("╠═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╬═══╣");
268+
if(i%Nsqrt==0 &&i>0) {
269+
System.out.print("╠");
270+
col =0;
271+
while(++col<N) {
272+
System.out.print("═══╬");
273+
}
274+
System.out.println("═══╣");
221275
}
222-
else {
223-
System.out.println("╠───┼───┼───╬───┼───┼───╬───┼───┼───╣");
276+
elseif(i>0) {
277+
System.out.print("╠");
278+
col =0;
279+
while(++col<N) {
280+
if(col%Nsqrt==0)System.out.print("───╬");
281+
elseSystem.out.print("───┼");
282+
}
283+
System.out.println("───╣");
224284
}
225285

226286
for(intj=0;j<N;j++) {
227-
if(j%3==0)System.out.print("║ ");
228-
elseSystem.out.print("│ ");
229-
System.out.print(board[i][j] +" ");
287+
if(j%Nsqrt==0)System.out.print("║");
288+
elseSystem.out.print("│");
289+
Stringshow ="";
290+
if(board[i][j]==0)show =" ";
291+
elseif(board[i][j]<10)show =" " +board[i][j] +" ";
292+
elseshow =board[i][j] +" ";
293+
System.out.print(show);
230294
}
231295
System.out.println("║");
232296
}
233-
System.out.println("╚═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╩═══╝");
297+
298+
System.out.print("╚");
299+
col =0;
300+
while(++col<N) {
301+
System.out.print("═══╩");
302+
}
303+
System.out.println("═══╝");
234304
System.out.println();
235305
}
236-
306+
237307
publicstaticvoidmain(String[]args) {
238308

239309
/*
@@ -244,15 +314,45 @@ public static void main(String[] args) {
244314
"0,2,0,1,0,9,0,0,0",
245315
"0,0,7,0,0,0,2,4,0",
246316
"0,6,4,0,1,0,5,9,0",
247-
"0,9,8,0,0,0,3,0,0",
248-
"0,0,0,8,0,3,0,2,0",
317+
"0,9,8,0,0,0,0,0,0",
318+
"0,0,0,8,0,0,0,2,0",
249319
"0,0,0,0,0,0,0,0,6",
250320
"0,0,0,2,7,5,9,0,0",
251321
};
252322
Sudoku q = new Sudoku(board);
253323
q.solveSudoku();
254324
*/
255325

326+
/*
327+
// get the solution of a given board:
328+
Scanner sc = new Scanner(System.in);
329+
int[][] board = new int[N][N];
330+
System.out.println("Type the values line by line and seperated by a space:\n"
331+
+ "Example input:\n"
332+
+ "1 2 3 4 5 6 7 8 9\n"
333+
+ "0 0 0 0 0 0 0 0 0\n"
334+
+ "0 0 0 0 0 0 0 0 0\n"
335+
+ "0 0 0 0 0 0 0 0 0\n"
336+
+ "0 0 0 0 0 0 0 0 0\n"
337+
+ "0 0 0 0 0 0 0 0 0\n"
338+
+ "0 0 0 0 0 0 0 0 0\n"
339+
+ "0 0 0 0 0 0 0 0 0\n"
340+
+ "0 0 0 0 0 0 0 0 0\n");
341+
for(int i=0; i<N; i++) {
342+
for(int j=0; j<N; j++) {
343+
try {
344+
int next = sc.nextInt();
345+
assert(next>=0 && next<=N);
346+
board[i][j] = next;
347+
}
348+
catch(InputMismatchException e) { }
349+
}
350+
}
351+
sc.close();
352+
Sudoku q = new Sudoku(board);
353+
q.solveSudoku();
354+
*/
355+
256356
// generate a random board and get the solution:
257357
Scannersc =newScanner(System.in);
258358
System.out.print("1 - easy\n2 - medium\n3 - hard\nSelect level: ");

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp