【独家发布】[Case Study]Solving Sudoku using Java

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1. /**
   
2. * The <code>Sudoku</code> class povides a static <code>main</code>
   
3. * method allowing it to be called from the command line to print the
   
4. * solution to a specified Sudoku problem.  
   
5. *
   
6. * <p>The following is an example of a Sudoku problem:
   
7. *
   
8. * <pre>
   
9. * -----------------------
   
10. * |   8   | 4   2 |   6   |
    
11. * |   3 4 |       | 9 1   |
    
12. * | 9 6   |       |   8 4 |
    
13. *  -----------------------
    
14. * |       | 2 1 6 |       |
    
15. * |       |       |       |
    
16. * |       | 3 5 7 |       |
    
17. *  -----------------------
    
18. * | 8 4   |       |   7 5 |
    
19. * |   2 6 |       | 1 3   |
    
20. * |   9   | 7   1 |   4   |
    
21. *  -----------------------
    
22. * </pre>
    
23. *
    
24. * The goal is to fill in the missing numbers so that
    
25. * every row, column and box contains each of the numbers
    
26. * <code>1-9</code>.  Here is the solution to the
    
27. * problem above:
    
28. *
    
29. * <pre>
    
30. *  -----------------------
    
31. * | 1 8 7 | 4 9 2 | 5 6 3 |
    
32. * | 5 3 4 | 6 7 8 | 9 1 2 |
    
33. * | 9 6 2 | 1 3 5 | 7 8 4 |
    
34. *  -----------------------
    
35. * | 4 5 8 | 2 1 6 | 3 9 7 |
    
36. * | 2 7 3 | 8 4 9 | 6 5 1 |
    
37. * | 6 1 9 | 3 5 7 | 4 2 8 |
    
38. *  -----------------------
    
39. * | 8 4 1 | 9 6 3 | 2 7 5 |
    
40. * | 7 2 6 | 5 8 4 | 1 3 9 |
    
41. * | 3 9 5 | 7 2 1 | 8 4 6 |
    
42. *  -----------------------
    
43. * </pre>
    
44. *
    
45. * Note that the first row <code>187492563</code> contains
    
46. * each number exactly once, as does the first column
    
47. * <code>159426873</code>, the upper-left box
    
48. * <code>187534962</code>, and every other row, column
    
49. * and box.
    
50. *
    
51. * <p>The {@link #main(String[])} method encodes a problem as an array
    
52. * of strings, with one string encoding each constraint in the problem
    
53. * in row-column-value format.  Here is the problem again with
    
54. * the indices indicated:
    
55. *
    
56. * <pre>
    
57. *     0 1 2   3 4 5   6 7 8
    
58. *    -----------------------
    
59. * 0 |   8   | 4   2 |   6   |
    
60. * 1 |   3 4 |       | 9 1   |
    
61. * 2 | 9 6   |       |   8 4 |
    
62. *    -----------------------
    
63. * 3 |       | 2 1 6 |       |
    
64. * 4 |       |       |       |
    
65. * 5 |       | 3 5 7 |       |
    
66. *   -----------------------
    
67. * 6 | 8 4   |       |   7 5 |
    
68. * 7 |   2 6 |       | 1 3   |
    
69. * 8 |   9   | 7   1 |   4   |
    
70. *    -----------------------
    
71. * </pre>
    
72. *
    
73. * The <code>8</code> in the upper left box of the puzzle is encoded
    
74. * as <code>018</code> (<code>0</code> for the row, <code>1</code> for
    
75. * the column, and <code>8</code> for the value).  The <code>4</code>
    
76. * in the lower right box is encoded as <code>874</code>.  
    
77. *
    
78. * <p>The full command-line invocation for the above puzzle is:
    
79. *
    
80. * <pre>
    
81. * % java -cp . Sudoku 018 034 052 076 \
    
82. *                     113 124 169 171 \
    
83. *                     209 216 278 284 \
    
84. *                     332 341 356     \
    
85. *                     533 545 557     \
    
86. *                     608 614 677 685 \
    
87. *                     712 726 761 773 \
    
88. *                     819 837 851 874 \
    
89. * </pre>
    
90. *
    
91. * <p>See <a href="http://en.wikipedia.org/wiki/Sudoku">Wikipedia:
    
92. * Sudoku</a> for more information on Sudoku.
    
93. *
    
94. * <p>The algorithm employed is similar to the standard backtracking
    
95. * <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle">eight
    
96. * queens algorithm</a>.
    
97. *
    
98. * @version 1.0
    
99. * @author <a href="http://www.colloquial.com/carp">Bob Carpenter</a>
    
100. */
     
101. public class Sudoku {
     
102. 
     
103.     /**
     
104.      * Print the specified Sudoku problem and its solution.  The
     
105.      * problem is encoded as specified in the class documentation
     
106.      * above.
     
107.      *
     
108.      * @param args The command-line arguments encoding the problem.
     
109.      */
     
110.     public static void main(String[] args) {
     
111.         int[][] matrix = parseProblem(args);
     
112.         writeMatrix(matrix);
     
113.         if (solve(0,0,matrix))    // solves in place
     
114.             writeMatrix(matrix);
     
115.         else
     
116.             System.out.println("NONE");
     
117.     }
     
118. 
     
119.     static boolean solve(int i, int j, int[][] cells) {
     
120.         if (i == 9) {
     
121.             i = 0;
     
122.             if (++j == 9)
     
123.                 return true;
     
124.         }
     
125.         if (cells[i][j] != 0)  // skip filled cells
     
126.             return solve(i+1,j,cells);
     
127.        
     
128.         for (int val = 1; val <= 9; ++val) {
     
129.             if (legal(i,j,val,cells)) {  
     
130.                 cells[i][j] = val;      
     
131.                 if (solve(i+1,j,cells))  
     
132.                     return true;
     
133.             }
     
134.         }
     
135.         cells[i][j] = 0; // reset on backtrack
     
136.         return false;
     
137.     }
     
138. 
     
139.     static boolean legal(int i, int j, int val, int[][] cells) {
     
140.         for (int k = 0; k < 9; ++k)  // row
     
141.             if (val == cells[k][j])
     
142.                 return false;
     
143. 
     
144.         for (int k = 0; k < 9; ++k) // col
     
145.             if (val == cells[i][k])
     
146.                 return false;
     
147. 
     
148.         int boxRowOffset = (i / 3)*3;
     
149.         int boxColOffset = (j / 3)*3;
     
150.         for (int k = 0; k < 3; ++k) // box
     
151.             for (int m = 0; m < 3; ++m)
     
152.                 if (val == cells[boxRowOffset+k][boxColOffset+m])
     
153.                     return false;
     
154. 
     
155.         return true; // no violations, so it's legal
     
156.     }
     
157. 
     
158.     static int[][] parseProblem(String[] args) {
     
159.         int[][] problem = new int[9][9]; // default 0 vals
     
160.         for (int n = 0; n < args.length; ++n) {
     
161.             int i = Integer.parseInt(args[n].substring(0,1));   
     
162.             int j = Integer.parseInt(args[n].substring(1,2));   
     
163.             int val = Integer.parseInt(args[n].substring(2,3));
     
164.             problem[i][j] = val;
     
165.         }
     
166.         return problem;
     
167.     }
     
168. 
     
169.     static void writeMatrix(int[][] solution) {
     
170.         for (int i = 0; i < 9; ++i) {
     
171.             if (i % 3 == 0)
     
172.                 System.out.println(" -----------------------");
     
173.             for (int j = 0; j < 9; ++j) {
     
174.                 if (j % 3 == 0) System.out.print("| ");
     
175.                 System.out.print(solution[i][j] == 0
     
176.                                  ? " "
     
177.                                  : Integer.toString(solution[i][j]));
     
178.                
     
179.                 System.out.print(' ');
     
180.             }
     
181.             System.out.println("|");
     
182.         }
     
183.         System.out.println(" -----------------------");
     
184.     }
     
185. 
     
186. }

复制代码

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：Case study Solving sudoku study Using following specified solution command example

1. Compiling and Running Sudoku.java
   
2. The following session provides an example of how to compile and run the code (assuming you have the Java developer's kit installed).
   
3. 
   
4. Bob Carpenter@ry /cygdrive/c/mycvs/carp
   
5. $ cd sudoku/
   
6. 
   
7. Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku
   
8. $ ls -l Sudoku.java
   
9. -rwxr-xr-x 1 Bob Carpenter None 5285 Apr 27 23:59 Sudoku.java
   
10. 
    
11. Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku
    
12. $ javac Sudoku.java
    
13. 
    
14. Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku
    
15. $ ls -l Sudoku.class
    
16. -rwxr-xr-x 1 Bob Carpenter None 1600 Apr 28 00:01 Sudoku.class
    
17. 
    
18. Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku
    
19. $ java -cp . Sudoku  014 023 037 069 088 \
    
20. 125 143 211 263 306 342 357 404 427 461 483 \
    
21. 535 544 589 622 673 745 764 805 824 851 862 876
    
22. -----------------------
    
23. |   4 3 | 7     | 9   8 |
    
24. |     5 |   3   |       |
    
25. |   1   |       | 3     |
    
26. -----------------------
    
27. | 6     |   2 7 |       |
    
28. | 4   7 |       | 1   3 |
    
29. |       | 5 4   |     9 |
    
30. -----------------------
    
31. |     2 |       |   3   |
    
32. |       |   5   | 4     |
    
33. | 5   4 |     1 | 2 6   |
    
34. -----------------------
    
35. -----------------------
    
36. | 2 4 3 | 7 1 6 | 9 5 8 |
    
37. | 9 8 5 | 2 3 4 | 7 1 6 |
    
38. | 7 1 6 | 8 9 5 | 3 4 2 |
    
39. -----------------------
    
40. | 6 3 9 | 1 2 7 | 5 8 4 |
    
41. | 4 5 7 | 9 6 8 | 1 2 3 |
    
42. | 8 2 1 | 5 4 3 | 6 7 9 |
    
43. -----------------------
    
44. | 1 6 2 | 4 7 9 | 8 3 5 |
    
45. | 3 7 8 | 6 5 2 | 4 9 1 |
    
46. | 5 9 4 | 3 8 1 | 2 6 7 |
    
47. -----------------------
    
48. 
    
49. Bob Carpenter@ry /cygdrive/c/mycvs/carp/sudoku
    
50. $

复制代码

1. import java.util.Scanner;
   
2. 
   
3. public class Solver {
   
4.      
   
5.     private static int[][] board = new int[9][9];
   
6.      
   
7.     public static void main(String[] args) {
   
8.      
   
9.     Scanner keyboard = new Scanner(System.in);
   
10.      
    
11.     System.out.println("Welcome to the sudoku solver!");
    
12.     System.out.println("Type inital values separated by spaces, \nwith zeros for blank spots.");
    
13.      
    
14.     for(int y = 0; y < 9; y++) {
    
15.         System.out.print("Enter row values: ");
    
16.         for(int x = 0; x < 9; x++) {
    
17.         board[x][y] = keyboard.nextInt();
    
18.         }
    
19.         keyboard.nextLine();
    
20.     }
    
21.      
    
22.     System.out.println("Initial state: ");
    
23.     printBoard();
    
24. 
    
25.     solve(0, 0);
    
26. 
    
27.     System.out.println("Solved state: ");
    
28.     printBoard();
    
29.     }
    
30. 
    
31.     public static void solve(int x, int y) {
    
32.     // find next open cell
    
33.     int[] nextOpenCell = findOpenCell(x, y);
    
34.     if(nextOpenCell == null) return;
    
35.     int xPos = nextOpenCell[0];
    
36.     int yPos = nextOpenCell[1];
    
37.      
    
38.     System.out.println("xPos: " + xPos + " yPos: " + yPos); // check...
    
39. 
    
40.     // attempt to fill
    
41.     for(int currentNumber = fillCell(1, xPos, yPos); currentNumber != -1;
    
42.         currentNumber = fillCell(currentNumber+1, xPos, yPos)) {
    
43. 
    
44.         if(xPos >= 8)
    
45.         solve(0, yPos+1);
    
46.         else
    
47.         solve(xPos+1, yPos);
    
48.         if(finished()) return;
    
49.     }
    
50.     }
    
51. 
    
52.     public static int fillCell(int val, int x, int y) {
    
53.         if(val > 9) return -1;
    
54.     if(checkRow(val, x) && checkColumn(val, y) && checkBox(val, x, y)) {
    
55.         board[x][y] = val;
    
56.         return val;
    
57.     }
    
58.     return fillCell(val+1, x, y);
    
59.     }
    
60. 
    
61.     public static boolean checkRow(int val, int x) {
    
62.     for(int i = 0; i < 9; i++) {
    
63.         if(board[x][i] == val) return false;
    
64.     }
    
65.     return true;
    
66.     }
    
67. 
    
68.     public static boolean checkColumn(int val, int y) {
    
69.     for(int i = 0; i < 9; i++) {
    
70.         if(board[i][y] == val) return false;
    
71.     }
    
72.     return true;
    
73.     }
    
74. 
    
75.     public static boolean checkBox(int val, int x, int y) {
    
76. 
    
77.     // find 3x3's upper right x/ys
    
78.     int i = (x / 3) * 3;
    
79.     int j = (y / 3) * 3;
    
80. 
    
81.     // check each cell in the 3x3
    
82.     for(int row = i; row < i+3; row++) {
    
83.         for(int column = j; column < j+3; column++) {
    
84.         if(board[row][column] == val) return false;
    
85.         }
    
86.     }
    
87.     return true;
    
88.     }
    
89. 
    
90.     public static void printBoard() {
    
91.     for(int y = 0; y < 9; y++) {
    
92.         if(y%3 == 0) System.out.println("");
    
93.         for(int x = 0; x < 9; x++) {
    
94.         if(x%3 == 0) System.out.print("  ");
    
95.         if(board[x][y] == 0)
    
96.             System.out.print("_ ");
    
97.         else
    
98.             System.out.print(board[x][y] + " ");
    
99.         }
    
100.         System.out.println("");
     
101.     }
     
102.     }
     
103. 
     
104.     public static int[] findOpenCell(int x, int y) {
     
105.     for(int column = y; column < 9; column++) {
     
106.         for(int row = x; row < 9; row++) {
     
107.         if(board[row][column] == 0) {
     
108.             return new int[] {row, column};
     
109.         }
     
110.         }
     
111.     }
     
112.     return null;
     
113.     }
     
114. 
     
115.     public static boolean finished() {
     
116.     for(int row = 0; row < 9; row++) {
     
117.         for(int column = 0; column < 9; column++) {
     
118.         if(board[row][column] == 0)
     
119.             return false;
     
120.         }
     
121.     }
     
122.     return true;
     
123.     }
     
124. }

复制代码

https://coderanch.com/t/601344/java/java/Sudoku-Solving-Java-Program

谢谢分享