ToyCode/Soduku.java at master · NEUGWB/ToyCode · GitHub

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
public class Soduku {
	public int a[][];
	public int t = 0;
	public boolean solved = false;
	public void solve(){
		t++;
		int i=0, j=0;
		for (i = 0; i < 9; i++){
			for (j = 0; j < 9; j++){
				if (a[i][j] == 0){
					for (int k = 1; k <= 9; k++){
						a[i][j] = k;
						if (legal(i, j)){
							solve();
							if (solved)
								return;
						}
					}
					a[i][j] = 0;
					return;

				}
			}
		}
		if (i == 9 && j == 9)
			solved = true;
	}
	public boolean legal(int i, int j){
		// line
		{
			int ii = i;
			for (int jj = 0; jj < 9; jj++){
				if (a[ii][jj] != 0 &&
						jj != j && a[i][j] == a[ii][jj]){
					return false;
				}
			}
		}
		//colume
		{
			int jj = j;
			for (int ii = 0; ii < 9; ii++){
				if (a[ii][jj] != 0 &&
						ii != i && a[i][j] == a[ii][jj]){
					return false;
				}
			}
		}

		//cube
		{
			int ib = i-i%3, jb = j-j%3;
			int ie = ib+3, je = jb+3;
			for (int ii = ib; ii < ie; ii++){
				for (int jj = jb; jj < je; jj++){
					if (a[ii][jj] != 0 &&
							(ii!=i || jj!=j) && a[i][j] == a[ii][jj]){
						return false;
					}
				}
			}
		}
		return true;
	}

	public void print(){
		for (int i = 0; i < 9; i++){
			for (int j = 0; j < 9; j++){
				System.out.print(a[i][j]);
			}
			System.out.println();
		}

		System.out.print(t);
	}
	public static void main(String argc[]) {
		int a[][] = {
				{8,0,0,0,0,0,0,0,0},
				{0,0,3,6,0,0,0,0,0},
				{0,7,0,0,9,0,2,0,0},
				{0,5,0,0,0,7,0,0,0},
				{0,0,0,0,4,5,7,0,0},
				{0,0,0,1,0,0,0,3,0},
				{0,0,1,0,0,0,0,6,8},
				{0,0,8,5,0,0,0,1,0},
				{0,9,0,0,0,0,4,0,0}
		};

		/*int a[][] = {
				{8,1,2,7,5,3,6,4,9},
				{9,4,3,6,8,2,1,7,5},
				{3,7,5,4,9,1,2,8,3},
				{1,5,4,2,3,7,8,9,6},
				{3,6,9,8,4,5,7,2,1},
				{2,8,7,1,6,9,5,3,4},
				{5,2,1,9,7,4,3,6,8},
				{4,3,8,5,2,6,9,1,7},
				{7,9,6,3,1,8,4,5,2}
		};*/

		Soduku s = new Soduku();
		s.a = a;
		s.solve();
		/*s.legal(1, 2);
		for (int i = 0; i< 9; i++)
			for (int j = 0; j < 9; j++){
				if (!s.legal(i, j)){
					System.out.println("error" + i + j);
				}
			}*/
		s.print();
	}
}