java/ch/wlkl/div/Sudoku2.java
package ch.wlkl.div;
import java.util.Arrays;
import ch.wlkl.wsh.Top;
public class Sudoku2 extends Top {
final static int IsSolution = -77;
final static int IsInconsistent = -55;
final static String [] allTasks = {
" 7 92 " +
" 12 " +
" 4 7 " +
" 9 8" +
" 162 3 9 " +
"3 5 " +
" 24 " +
" 9 82" +
"7 6 3 9"
, " 742 " +
" 87 " +
"2 8 9 3" +
" 5 6 2 " +
" 9 8 1 3 " +
" 4 3 6 " +
"9 3 1 7" +
" 14 " +
" 567 "
, " 385" + // tagi 14.1.06 ==> 4 branches, 1 solution
"5 7 9 " +
" 4 52 " +
" 9 5 2 " +
"65 49" +
" 7 1 8 " +
" 63 1 " +
" 8 4 7" +
"129 ",
// "012345678012345678012345678012345678012345678012345678012345678012345678012345678" ,
// "0 1 2 3 4 5 6 7 8"
" 491 5 2 7 6 3 5 7 68 1 3 9 24 6 5 3 4 9 8 6 612 ", // tagi 22.7
" 4 3 1 5 72 975 9 8 53 4 5 947 624338 5 9 1 ",
// "9 7 3 56 7 352 9 8 238 2 34 6 7 1", // 800 evil 200000 L�sungen!
" 2 4 37 59 69 3 18 4 697 2 55 3 24 82 69 1 3 ",
" 632 5 37 261 2 4 5 182 9 9 7 168 2 1 364 ", // tagi 16.9.06
" 6 19 8 5 947 7 5 24 68 9 3 547 7 2 91 3 ", // tagi 10.12 ==> 5 branches!
" 7 3 5 85 9 1 4 8 7 3 1 3 4 7 9 6 2 2 92 3 1 64 5 ", // superieur 4.9.07
" 3 9 4 568 3 7 1 8 4 97 6 5 2 1 1 7 386 2 5 89 ", // superieur 4.9.07
" 8 5 8 7 4 5 1 69 24 6 73 13 2 1 7 3 2 8 4 " // schwer tagi 23.2.08
};
int sols = 0, branches = 0, brMax = 0, brMin = 0;
final char [] chars;
final char [] indexes = new char [256];
final char empty;
final int [] [] constraint;
final int constraintML;
final char [] state;
final long [] sets;
final long setAll;
int complexity = 0;
int coMax = 0;
StringBuffer msg = null;
public Sudoku2() {
int x, y;
chars = "123456789".toCharArray();
empty = ' ';
constraint = new int [27] [9];
for (y=0; y<9; y++) {
for (x=0; x<9; x++) {
constraint[y][x] = 9*y + x;
constraint[9+y][x] = y + 9*x;
}
}
for (int c=18; c<27; c++) {
y = 27 * ((c-18) / 3) + 3 * (c % 3);
for (x=0; x<9; x++) {
constraint[c][x] = y + 9 * (x / 3) + (x % 3);
}
}
state = new char [81];
sets = new long[81];
long a = 0;
Arrays.fill(indexes, (char) 255);
for (x=0; x<chars.length; x++) {
indexes[chars[x]] = (char) x;
a |= 1l << x;
}
setAll = a;
constraintML = 9;
}
public int fillSets() {
int i;
int en = 0;
Arrays.fill(sets, setAll);
for (i=0; i<state.length; i++) {
sets[i] = state[i] == empty ? setAll : (en++ * 0);
}
for (int c=0; c < constraint.length; c++) {
long a = 0;
long r = 0;
for (int d=0; d < constraint[c].length; d++) {
if (state[i = constraint[c] [d]] != empty) {
a = 1l << indexes[state[i]];
if ((a & r) != 0)
return -1;
r |= a;
} else {
}
}
for (int d=0; d < constraint[c].length; d++) {
if (state[i = constraint[c] [d]] == empty) {
if (0 == (sets[i] &= ~ r))
return -1;
}
}
}
return sets.length - en;
}
public String coord(int i) {
return String.valueOf(i/9) + '.' + (i%9);
}
public void msg(String s) {
if (msg != null)
System.out.println(s);
}
public void msgP(String s) {
if (msg != null) {
System.out.println(s + msg);
msg.setLength(0);
}
}
public int set(int i, char v) {
if (state[i] == empty) {
state[i] = v;
if (msg != null)
msg.append(coord(i)).append("->").append(v).append(' ');
return 1;
} else if (state[i] != v) {
// say("conflicting set " + coord(i) + " old " + state[i] + " new " + v);
if (msg != null)
msg.append("conflicting set ").append(coord(i)).append(" old ").append(state[i]).append(" new ").append(v).append(' ');
}
return 0;
}
public int bitCount1() {
int cnt = 0;
for (int i = 0; i < sets.length; i++) {
if (Long.bitCount(sets[i]) == 1)
cnt += set(i, chars[Long.numberOfTrailingZeros(sets[i])]);
}
return cnt;
}
public int singleInConstraint() {
int s;
long a;
int cnt = 0;
for (int c = 0; c < constraint.length; c++) {
long once = 0l;
long twice = 0l;
for (int d=0; d < constraint[c].length; d++) {
twice |= once & sets[s = constraint[c][d]];
once |= sets[s];
}
once &= ~twice;
if (once != 0) {
for (int d=0; d < constraint[c].length; d++) {
if ((a = sets[s = constraint[c][d]] & once) != 0l) {
// if (Long.bitCount(a) != 1) // ==> only possibility for more than 1 digit ==> impossible: set 1 possiblity and fillSets will detect conflict!
// fail("mismatch");
cnt += set(s, chars[Long.numberOfTrailingZeros(a)]);
}
}
}
}
return cnt;
}
public boolean cover(int max) {
long [] stack = new long[constraintML];
long o;
int ix;
int cnt = 0;
for (int [] c: constraint) {
o = 0;
ix = -1;
oneConstraint: while (true) {
if (++ix >= c.length || Long.bitCount(o) >= max) {
while (true) {
if (--ix < 0)
break oneConstraint;
if (stack[ix] != 0)
break;
}
o = stack[ix];
stack[ix] = 0;
} else {
stack[ix] = o;
o |= sets[c[ix]];
if (Long.bitCount(o) == max) {
int k = 0;
for (int s : c)
k += 0 != sets[s] && 0 == (sets[s] & ~o) ? 1 : 0;
if (k == max) {
for (int s : c) {
if (0 != (sets[s] & ~o) && 0 != (sets[s] & o)) {
cnt++;
sets[s] &= ~o;
}
}
} else if (k > max) {
// say("cover conflict");
}
}
}
}
}
return cnt > 0;
}
public boolean coverLEQ(int max) {
for(int m=1; m <= max; m++) {
if (cover(m)) {
msg("covered " + m);
complexity += m * m;
return true;
}
}
return false;
}
public void search() {
int bestIx = -1;
for (int s=0; s<sets.length;s++) {
int b = Long.bitCount(sets[s]);
if (b > 0 && (bestIx < 0 || b < Long.bitCount(sets[bestIx])))
bestIx = s;
}
final int oldCompl = complexity;
long best = sets[bestIx];
char [] copy = state.clone();
branches++;
while (best != 0) {
int i = Long.numberOfTrailingZeros(best);
msg("trying " + branches + ": " + coord(bestIx) + "->" + chars[i]);
if (1 != set(bestIx, chars[i]))
fail("best set");
complexity = 100 + oldCompl;
solve() ;
msg("backtracking " + branches + ": " + coord(bestIx) + "->" + chars[i]);
for (int xx=0; xx < state.length; xx++)
state[xx] = copy[xx];
best &= ~ (1l << i);
}
branches--;
complexity = oldCompl;
}
public void show() {
StringBuffer s = new StringBuffer();
for (int x=0; x<81; x++) {
s.append(state[x]).append(' ');
if ((x % 9) == 8) {
System.out.println(s);
s.setLength(0);
}
}
}
public void solve() {
int cnt;
while (true) {
if ((cnt = fillSets()) < 0) {
return; // failed, it's impossible
} else if (cnt == 0) {
if (++sols == 1 || branches < brMin)
brMin = branches;
if (sols == 1 || branches > brMax)
brMax = branches;
if (sols == 1 || complexity > coMax)
coMax = complexity;
if (msg != null) {
msg("solution " + sols + " with " + branches + " branches");
show();
}
return;
}
while (true) {
if (msg != null)
msg.setLength(0);
if (0 != (cnt = bitCount1())) {
msgP("bitCount1 " + cnt + ": ");
break;
} else if (0 != (cnt = singleInConstraint())) {
msgP("singleInConstraint " + cnt + ": ");
break;
} else if (coverLEQ(8)) {
} else {
search();
return;
}
}
}
}
public void solve(CharSequence s, boolean talky) {
if (state.length != s.length())
fail("length should be " + state.length + " not " + s.length() + " for " + s);
for (int c=0; c < state.length; c ++)
state[c] = s.charAt(c);
coMax = complexity = 0;
msg = talky ? new StringBuffer() : null;
msg("Sudoko2 to solve:");
sols = branches = 0;
if (talky)
show();
solve();
if (sols > 0)
msg("solved search " + sols + " solutions, branches " + brMin + ".." + brMax);
else
msg("no solutions");
}
public void reduce(CharSequence s) {
StringBuffer sBuf = new StringBuffer(s);
char [] back = new char[s.length()];
String best = "";
int bestRed = 0;
int red = 0;
int ix = 0;
solve(s, true);
if (sols != 1) {
say("cannot reduce " + sols + " solutions");
return;
}
int bestCompl = coMax;
bigSearch: while (true) {
if (ix >= state.length) {
ix = state.length;
while (true) {
if (--ix < 0)
break bigSearch;
else if (back[ix] != empty) {
sBuf.setCharAt(ix, back[ix]);
back[ix] = empty;
red--;
break;
}
}
} else if (sBuf.charAt(ix) == empty) {
back[ix] = empty;
} else {
back[ix] = sBuf.charAt(ix);
sBuf.setCharAt(ix, empty);
solve(sBuf, false);
if (sols == 1) {
red++;
if (coMax > bestCompl || (coMax == bestCompl && red > bestRed)) {
say("new bestCompl " + coMax + " red " + red + " back " + new String(back));
bestCompl = coMax;
bestRed = red;
best = sBuf.toString();
}
} else {
sBuf.setCharAt(ix, back[ix]);
back[ix] = empty;
}
}
ix++;
}
if (bestRed == 0) {
say("no reduction possible");
} else {
say("finally best solution complexity " + bestCompl + " red " + bestRed);
solve(best, true);
}
}
public static void main(String [] args) {
Sudoku2 s = new Sudoku2();
// s.reduce(allTasks[allTasks.length-1]);
for (String t: allTasks) {
// s.reduce(t);
s.solve(t, true);
}
}
}