1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.myfaces.tobago.example.demo.sudoku;
21
22 import org.slf4j.Logger;
23 import org.slf4j.LoggerFactory;
24
25 import java.lang.invoke.MethodHandles;
26 import java.util.ArrayList;
27 import java.util.BitSet;
28 import java.util.List;
29 import java.util.Random;
30 import java.util.Stack;
31
32
33
34
35
36
37 public class Sudoku {
38
39 private static final Logger LOG = LoggerFactory.getLogger(MethodHandles.lookup().lookupClass());
40
41 private static final Random RANDOM = new Random(System.currentTimeMillis());
42
43 private byte[] field;
44 private Stack<Byte> undefined;
45
46 private int depth;
47 private int maxDepth;
48
49 public Sudoku() {
50 field = new byte[]{
51 0, 1, 2, 3, 4, 5, 6, 7, 8,
52 -1, -1, -1, -1, -1, -1, -1, -1, -1,
53 -1, -1, -1, -1, -1, -1, -1, -1, -1,
54
55 -1, -1, -1, -1, -1, -1, -1, -1, -1,
56 -1, -1, -1, -1, -1, -1, -1, -1, -1,
57 -1, -1, -1, -1, -1, -1, -1, -1, -1,
58
59 -1, -1, -1, -1, -1, -1, -1, -1, -1,
60 -1, -1, -1, -1, -1, -1, -1, -1, -1,
61 -1, -1, -1, -1, -1, -1, -1, -1, -1,
62 };
63 final RandomList randomList = new RandomList((byte) 81);
64 randomList.removeSmallest(9);
65 depth = 9;
66 undefined = randomList.asStack();
67
68 }
69
70 public Sudoku(final byte[] field) {
71 this.field = field;
72
73 }
74
75 public Result solve() {
76 if (undefined.isEmpty()) {
77 LOG.debug("--------------- result ");
78 LOG.debug(this.toString());
79 LOG.debug("--------------- result ");
80 return Result.UNIQUE;
81 }
82 final byte position = undefined.pop();
83 final RandomList list = new RandomList((byte) 9);
84 boolean foundOne = false;
85 while (!list.isEmpty()) {
86 field[position] = list.next();
87
88
89 if (checkRules()) {
90
91 final Result result = solve2();
92 switch (result) {
93 case ERROR:
94 break;
95 case MULTIPLE:
96 return Result.MULTIPLE;
97 case UNIQUE:
98 if (foundOne) {
99 return Result.MULTIPLE;
100 } else {
101 foundOne = true;
102 }
103 break;
104 default:
105 assert false;
106 }
107 }
108 }
109 undefined.push(position);
110 field[position] = -1;
111
112 return Result.ERROR;
113 }
114
115 private Result solve2() {
116 depth++;
117 if (depth > maxDepth) {
118 maxDepth = depth;
119 LOG.debug("new max depth: " + maxDepth);
120 }
121 final Result result = solve();
122 depth--;
123 return result;
124 }
125
126
127 private boolean checkRules() {
128 return checkRowRules() && checkColumnRules() && checkSquareRules();
129 }
130
131 protected boolean checkRowRules() {
132 for (int i = 0; i < 9; i++) {
133 final BitSet xxx = new BitSet();
134 for (int j = 0; j < 9; j++) {
135 final byte value = field[i * 9 + j];
136 if (value != -1) {
137 if (xxx.get(value)) {
138
139 return false;
140 }
141 xxx.set(value);
142 }
143 }
144 }
145 return true;
146 }
147
148 protected boolean checkColumnRules() {
149 for (int i = 0; i < 9; i++) {
150 final BitSet xxx = new BitSet();
151 for (int j = 0; j < 9; j++) {
152 final byte value = field[j * 9 + i];
153 if (value != -1) {
154 if (xxx.get(value)) {
155
156 return false;
157 }
158 xxx.set(value);
159 }
160 }
161 }
162 return true;
163 }
164
165 protected boolean checkSquareRules() {
166 for (int i = 0; i < 9; i++) {
167 final BitSet xxx = new BitSet();
168 for (int j = 0; j < 9; j++) {
169 final int i1 = (i % 3) * 3 + i / 3 * 27 + j % 3 + j / 3 * 9;
170 final byte value = field[i1];
171 if (value != -1) {
172 if (xxx.get(value)) {
173
174 return false;
175 }
176 xxx.set(value);
177 }
178 }
179 }
180 return true;
181 }
182
183 public static void main(final String[] args) {
184 LOG.debug("" + new RandomList((byte) 9).list);
185 final Sudoku sudoku = new Sudoku();
186 LOG.debug("---------------------------------------------------------------------------------------------");
187 final Result result = sudoku.solve();
188 LOG.debug("" + result);
189 LOG.debug("---------------------------------------------------------------------------------------------");
190 LOG.debug("" + sudoku);
191 }
192
193 @Override
194 public String toString() {
195 final StringBuilder builder = new StringBuilder();
196 for (int i = 0; i < field.length; i++) {
197 if (field[i] == -1) {
198 builder.append('-');
199 } else {
200 builder.append(field[i] + 1);
201 }
202 if (i % 9 != 8) {
203 builder.append(' ');
204 } else {
205 builder.append('\n');
206 }
207 }
208 return builder.toString();
209 }
210
211
212
213
214 private static class RandomList {
215
216 private byte n;
217 private List<Byte> list;
218
219 private RandomList(final byte n) {
220 this.n = n;
221 list = new ArrayList<>(n);
222 shuffle();
223 }
224
225 public void shuffle() {
226 final List<Byte> temp = new ArrayList<>(n);
227 for (byte i = 0; i < n; i++) {
228 temp.add(i, i);
229 }
230 for (byte i = n; i > 0; i--) {
231 final byte index = (byte) RANDOM.nextInt(i);
232 list.add(temp.remove(index));
233 }
234 }
235
236 public byte next() {
237 return list.remove(0);
238 }
239
240 public boolean isEmpty() {
241 return list.isEmpty();
242 }
243
244 public Stack<Byte> asStack() {
245 final Stack<Byte> stack = new Stack<>();
246 stack.addAll(list);
247 return stack;
248 }
249
250 public void removeSmallest(final int m) {
251 for (byte i = 0; i < m; i++) {
252 list.remove((Byte) i);
253 }
254 }
255 }
256
257 private enum Result {
258 UNIQUE,
259 MULTIPLE,
260 ERROR
261 }
262 }