- import java.util.Scanner;
- public class Sudoku2 {
- private static boolean isValid(int[][] sudo, int x, int y) {
- boolean valid = true;
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- boolean condition = false;
- condition = (i == x) || (j == y);//same row or same column
- condition = condition || ((i / 3 == x / 3) && (j / 3 == y / 3));//same square
- condition = condition && !((i == x) && (j == y));
- if (condition && sudo[i][j] == sudo[x][y]) {
- valid = false;
- }
- }
- }
- return valid;
- }
- private static boolean findAnswer(int[][] sudo, int i, int j) {
- if (i >= 9 || j >= 9) return true;
- if (sudo[i][j] != 0) {//如果当前格子是已经填过的,直接进入下一个
- if (j < 8) {
- return findAnswer(sudo, i, j + 1);
- } else {
- return findAnswer(sudo, i + 1, 0);
- }
- }
- boolean result = false;
- int k = 1;
- for (k = 1; k <= 9; k++) {//依次检验1-9看是否符合
- sudo[i][j] = k;
- if (isValid(sudo, i, j)) {
- if (j < 8) {
- result = findAnswer(sudo, i, j + 1);
- } else {
- result = findAnswer(sudo, i + 1, 0);
- }
- }
- if (result) {//如果已经找到正解了不要在循环下去,不过这样只能找到一个答案
- break;
- }
- }
- if (k > 9 && !result) {//如果1-9都不符合,说明之前的格子有填错的,回溯,要把当前格子重置为0,一开始忘了这步导致debug了好久
- sudo[i][j] = 0;//no answer, reset to 0 before backward....
- }
- return result;
- }
- private static void output(int[][] sudo) {
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- System.out.printf("%d ", sudo[i][j]);
- }
- System.out.println();
- }
- }
- public static void main(String[] args) {
- int[][] sudo = new int[9][9];
- Scanner in = new Scanner(System.in);
- for (int i = 0; i < 9; i++) {
- for (int j = 0; j < 9; j++) {
- sudo[i][j] = in.nextInt();
- }
- }
- long start = System.nanoTime();
- findAnswer(sudo, 0, 0);
- System.out.printf("Sudoku2 takes time:%.2f\\n", (System.nanoTime() - start) / 1E9);
- output(sudo);
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/210120148614.html
来源: http://www.codesnippet.cn/detail/210120148614.html