package sudoku3;
// ....67.1..6.1.....2.9.4....683.....259..8..7.4.......8....91.6.........5..452..8.
// check double Hidden Twin found????
/*
36 set 5 @ 2 (Random select); (Hidden Twin [6,7] @ 24,26)
37 set 8 @ 6 (Single [8] at pos)
38 set 7 @ 9 (Random select); (Hidden Twin [6,7] @ 24,26)
maybe we need to keep removed candidaets in upd possibles showhow?
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.concurrent.ThreadLocalRandom;
public class Sudoku3 {
/*
see also: http://www.sudoku.org.pl/solver.html
How to solve?
Assumption:
There are 9*9=81 positions, where we can set digits 1..9.
The value of the digits are stored in an one dimensional array d[].
Free positions are not set and has the value 0.
Rules:
Let's define 3 functions to check if at a given position i
a value could be set:
validRow(i,val)
validCol(i,val)
validBox(i,val)
Strategy:
On a first approach, we could go in sequence for the free positions.
Test all values 1..9, if one could be set.
If so, set value and call function recursive again.
If no set, go back. Exception: last position is set, then we have a solution.
This approach works, but for hard sudokus there are many dead ends,
and CPU time increases to seconds.
Speedup:
It's a good idea, to set those positions first, where only 1 or 2 values are possible.
So we analyse the board first to get the minimum position.
There are 3 returns:
- minimum position found, ok stop to anaylse and return pos
- no position found to set, because reaching dead end, stop and return
- no position found to set, because solved
Once done this simplifys the reursion code also.
Realised speedup is up to 100.
*/
static int d[] = new int[81]; // digits
static ArrayList<Integer>[] possible = (ArrayList<Integer>[]) new ArrayList[81];
static ArrayList<Integer> candidates = new ArrayList(); // 9 positions for row,col or box
static ArrayList<Integer>[] used = (ArrayList<Integer>[]) new ArrayList[10];
// static int locked[][] = new int[54][9]; // 9 Boxes * 6=54 ; 3 check pos + 6 remove Pos
/*
1 2 3 1 4 7 a b c d e f
4 5 6
7 8 9
a
b
c
d
e
f
*/
static long startTime;
static int solNbr = 0;
//static String solution = "no solution found";
static String iniStr;
static Trace trace = null; // trace only good sets, not the reset
static BitSet bit[] = new BitSet[81];
static boolean verbose = false;
static int lvlmincnt = 0;
static int lvlmaxcnt = 99;
static int cntGen = 0;
// CmdLine Options
static boolean gen = false;
static boolean sym = false;
static boolean disp = false;
static boolean html = false;
static boolean lvlmin = false;
static boolean lvlmax = false;
static boolean solve = false;
static boolean inp = false;
static boolean chk = false;
static boolean set = false;
static boolean analyse = false;
static boolean tip = false;
static boolean display = false;
static int genMin = 8; // random generate first n digits
static int genMinSet = 30;
static String fnHTML = "disp.html";
// -------------- display functions ----------------------------------------
static private void print(String s) {
System.out.print(s);
}
static private void println(String s) {
System.out.println(s);
}
static private StringBuffer getPoss(int i, int val) {
StringBuffer sb = new StringBuffer();
sb.append("|");
for (int v = val; v < val + 3; v++) {
if (possible[i].contains(v)) {
sb.append(v + "");
} else {
sb.append(" ");
}
}
return sb;
}
static private String getD() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 81; i++) {
sb.append(d[i]);
}
return sb.toString().replaceAll("0", ".");
}
static private void display() {
updPossible();
StringBuffer sb = new StringBuffer();
sb.append("\t a b c d e f g h i");
String dash = "\t+---+---+---+ +---+---+---+ +---+---+---+\n\t";
for (int y = 0; y < 9; y++) {
if (y % 3 == 0) {
sb.append("\n" + dash);
}
for (int i = y * 9; i < y * 9 + 9; i++) {
sb.append(getPoss(i, 1));
if (i % 3 == 2) {
sb.append("| ");
}
}
sb.append("\n " + (1 + y) + "\t");
for (int i = y * 9; i < y * 9 + 9; i++) {
sb.append(getPoss(i, 4));
if (i % 3 == 2) {
sb.append("| ");
}
}
sb.append("\n\t");
for (int i = y * 9; i < y * 9 + 9; i++) {
sb.append(getPoss(i, 7));
if (i % 3 == 2) {
sb.append("| ");
}
}
sb.append("\n");
sb.append(dash);
}
println(sb.toString());
}
static private void printlnElapsed(String s) {
//hh:min:ss,ms
long mis = (System.nanoTime() - startTime) / 1000 / 1000;
int sec = (int) mis / 1000;
String ms = (mis % 1000) + "";
if (ms.length() < 3) {
ms = "0" + ms;
}
if (ms.length() < 3) {
ms = "0" + ms;
}
String ss = sec % 60 + ";";
if (ss.length() < 3) {
ss = "0" + ss;
}
String mm = (sec / 60) % 60 + ":";
if (mm.length() < 3) {
mm = "0" + mm;
}
String hh = (sec / 3600) + ":";
if (hh.length() < 3) {
hh = "0" + hh;
}
print(hh + mm + ss + ms + "\t" + s + "\n");
/*
requires 60 ms to use first time!!!!!!
println(String.format("%02d", hh) + ":"
+ String.format("%02d", mm) + ":"
+ String.format("%02d", ss) +","
+ String.format("%03d",ms) +"\t"
+ s);
*/
}
static private boolean validRow(int p, int val) {
int pos = p / 9 * 9;
for (int i = 0; i < 9; i++) {
if (d[pos] == val) {
return false;
}
pos++;
}
return true;
}
static private boolean validCol(int p, int val) {
int pos = p % 9;
for (int i = 0; i < 9; i++) {
if (d[pos] == val) {
return false;
}
pos += 9;
}
return true;
}
static private boolean validBox(int p, int val) {
int pos = (p % 9) / 3 * 3 + (p / 27) * 27;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
if (d[pos + x + y * 9] == val) {
return false;
}
}
}
return true;
}
static private boolean canSet(int i, int val) {
return (validRow(i, val) && validCol(i, val) && validBox(i, val));
}
static private void addMsg(int i, int i1, int i2, String msg, int b) {
// trace.add(i, i1, i2, getBoard() + "\n" + msg);
trace.add(i, i1, i2, msg);
bit[i].set(b);
}
private static RetMsg chk() {
RetMsg retMsg = new RetMsg(0, "ok");
for (int i = 0; i < 81; i++) {
retMsg = chk(i);
if (retMsg.ret != 0) {
break;
}
}
return retMsg;
}
private static RetMsg chk(int i) {
// chk each digit set against rules
//
//
RetMsg retMsg = new RetMsg(0, "ok");
//for (int i = 0; i < 81; i++) {
if (d[i] > 0) {// is set
// row
int y = i / 9;
for (int x = 0; x < 9; x++) {
int ii = y * 9 + x;
if (i != ii && d[ii] == d[i]) {
String msg = "\t\tRow=" + y + " chk Error, duplicate value " + d[i] + " @ " + trace.pos(i) + "," + trace.pos(ii); // + "\n\t\t" + disp();
return new RetMsg(-2, msg);
}
}
// col
int x = i % 9;
for (y = 0; y < 9; y++) {
int ii = y * 9 + x;
if (i != ii && d[ii] == d[i]) {
String msg = "\t\tCol " + x + " chk Error, duplicate value " + d[i] + " @ " + trace.pos(i) + "," + trace.pos(ii);// + "\n\t\t" + disp();
return new RetMsg(-2, msg);
}
}
// box
int yt = (i / 27) * 27;
int xt = (i % 9 / 3) * 3;
int ibox = yt + xt;
for (x = 0; x < 3; x++) {
for (y = 0; y < 3; y++) {
int ii = ibox + y * 9 + x;
if (i != ii && d[ii] == d[i]) {
String msg = "\t\tBox" + " chk Error, duplicate value " + d[i] + " @ " + trace.pos(i) + "," + trace.pos(ii);// + "\n\t\t" + disp();
return new RetMsg(-2, msg);
}
}
}
}
return retMsg;
}
static private void isolateSingle(int i, int val) {
//addMsg(i,"isolate Single "+val+" @ "+trace.pos(i),2);
possible[i].clear();
possible[i].add(val);
}
static private Boolean cleanTwin(int cand, int i1, int i2, int v1, int v2, String msg) {
Boolean ret = false; // no cleanup
for (int c = 0; c < 9; c++) {
String valList = "";
int i = candidates.get(cand + c);
if (i != i1 && i != i2) {
for (int v = possible[i].size() - 1; v >= 0; v--) {
int val = possible[i].get(v);
if (val == v1 || val == v2) {
valList += "," + val;
possible[i].remove(new Integer(val));
ret = true; // cleanup done
}
}
}
if (valList.length() > 1) {
valList = valList.substring(1);
addMsg(i, i1, i2, "remove " + valList + " at position " + trace.pos(i) + " \tdue to " + msg, 3);
}
}
return ret; // cleanup done
}
static private Boolean clrRowCol(int i1, int i2, int val, String msg) {
Boolean ret = false; // nothing found
int cand = -2;
if (i2 % 9 == i1 % 9) { // same X => col
cand = 81 + i2 % 9 * 9;
} else if (i2 / 9 == i1 / 9) { // same y => row
cand = i2 / 9 * 9;
}
if (cand >= 0) {
for (int c = 0; c < 9; c++) {
int i = candidates.get(cand + c);
if (i != i1 && i != i2) {
// clear
if (possible[i].contains(val)) {
possible[i].remove(new Integer(val));
addMsg(i, i1, i2, "remove " + val + " at position " + trace.pos(i) + " \tdue to " + msg, 5);
ret = true;
}
}
}
}
return ret;
}
/*--------------------------------------------------------------------------
static private int chkLockedColRow(int cand) {
for (int i = 0; i < 10; i++) {
used[i].clear();
}
int i = -1;
int i1 = -1;
int v1 = -1;
for (int c = 0; c < 9; c++) {
i = candidates.get(cand + c);
for (int v = 0; v < possible[i].size(); v++) {
int val = possible[i].get(v);
used[val].add(i);
}
}
// chk
boolean ok = true;
for (int v = 1; v < 10; v++) {
if (used[v].size() >= 2) {
// all in same Box?
int B = used[i].get(0) % 9 / 3;
for (int b = 1; b < used[i].size(); b++) {
if (B != used[i].get(b) % 9 / 3) {
ok = false;
}
}
if (ok) {
// remBox(B,v);
}
}
}
return -2;
} ------------------------------------------------------------------------*/
static private Boolean chkLockedBox(int cand) {
Boolean ret = false; // nothing found
for (int i = 0; i < 10; i++) {
used[i].clear();
}
int i = -1;
int i1 = -1;
for (int c = 0; c < 9; c++) {
i = candidates.get(cand + c);
for (int v = 0; v < possible[i].size(); v++) {
int val = possible[i].get(v);
used[val].add(i);
}
}
// chk
for (int v = 1; v < 10; v++) {
if (used[v].size() == 2) {
i = used[v].get(0);
i1 = used[v].get(1);
// find Row / col to clear
String msg = "locked " + v + " @ " + trace.pos(i) + "," + trace.pos(i1);
if (clrRowCol(i, i1, v, msg)) {
ret = true;
}
}
}
return ret;
}
static private Boolean chkhiddenTwin(int cand) {
/*
Rule: in a group of candidates
search exactly 2 used values.
If found, isolate.
before: after:
+---+---+---+ +---+---+---+
|12 | | | |1 | | |
|4 6| 6| | |4 | 6| |
| 8 | 8 | | | | 8 | |
+---+---+---+ +---+---+---+
|12 | | | |1 | | |
|4 | | | |4 | | |
| | | | | | | |
+---+---+---+ +---+---+---+
| 2 | | 2 | | 2 | | 2 |
| 6| | 6| | 6| | 6|
| 8 | | | | 8 | | |
+---+---+---+ +---+---+---+
hidden Twin (1,4)
*/
Boolean ret = false; // nothing found
for (int i = 0; i < 10; i++) {
used[i].clear();
}
int i = -1;
int i1 = -1;
int v1 = -1;
for (int c = 0; c < 9; c++) {
i = candidates.get(cand + c);
for (int v = 0; v < possible[i].size(); v++) {
int val = possible[i].get(v);
used[val].add(i);
}
}
// chk
for (int v = 1; v < 10; v++) {
if (used[v].size() == 2) {
if (v1 < 0) {
v1 = v; // first Twin value
i = used[v1].get(0);
i1 = used[v1].get(1);
} else {
if (i == used[v].get(0)
&& i1 == used[v].get(1)) // found hidden Twin
{
// chk if we can remove something first!
if (possible[i].size() > 2 || possible[i1].size() > 2) {
String msg = "";
for (int j = 0; j < possible[i].size(); j++) {
int v0 = possible[i].get(j);
if (v0 != v && v0 != v1) {
msg += "," + v0;
}
}
if (msg.length() > 1) {
msg = msg.substring(1);
msg = "remove " + msg + " at position " + trace.pos(i) + " \tdue to hidden twin [" + v1 + "," + v + "] at positions " + trace.pos(i) + "," + trace.pos(i1);
addMsg(i, i, i1, msg, 4);
}
msg = "";
for (int j = 0; j < possible[i1].size(); j++) {
int v0 = possible[i1].get(j);
if (v0 != v && v0 != v1) {
msg += "," + v0;
}
}
if (msg.length() > 1) {
msg = msg.substring(1);
msg = "remove " + msg + " at position " + trace.pos(i1) + " \tdue to hidden twin [" + v1 + "," + v + "] at positions " + trace.pos(i) + "," + trace.pos(i1);
addMsg(i1, i, i1, msg, 4);
}
possible[i].clear();
possible[i].add(v);
possible[i].add(v1);
possible[i1].clear();
possible[i1].add(v);
possible[i1].add(v1);
ret = true;
}
}
}
}
}
return ret;
}
static private Boolean chkTwin(int cand) {
Boolean ret = false; // nothing found
int i;
int i2 = -1;
for (int c = 0; c < 9; c++) {
i = candidates.get(cand + c);
if (possible[i].size() == 2) {
{
if (i2 < 0) {
i2 = i; //// first twin found, search next
} else {
// second twin found, compare
int v1 = possible[i].get(0);
int v2 = possible[i].get(1);
if (possible[i2].contains(new Integer(v1))
&& possible[i2].contains(new Integer(v2))) {
// great we found a Twin
String dir = "col";
if (cand < 81) {
dir = "row";
}
if (cand > 161) {
dir = "box";
}
String msg = "twin [" + v1 + "," + v2 + "] at positions " + trace.pos(i) + "," + trace.pos(i2) + " in " + dir;
Boolean r = cleanTwin(cand, i, i2, v1, v2, msg);
if (r) {
ret = true;
}
} else {
i2 = i; // maybe next
}
}
}
}
}
return ret;
}
static private RetMsg chkHiddenSingles(int cand) {
RetMsg retMsg = new RetMsg(-1, "nothing found");
int possDig[] = new int[10];
int possNo[] = new int[10];
int i;
for (int c = 0; c < 9; c++) {
i = candidates.get(cand + c);
for (int v = 0; v < possible[i].size(); v++) {
int val = possible[i].get(v);
possDig[val]++;
possNo[val] = i;
}
}
// chk, if there is a Single val in the possDig List
for (int v = 1; v < 10; v++) {
if (possDig[v] == 1) {
i = possNo[v];
int m = cand / 81;
String msgTxt = "row " + trace.pos(i).charAt(1);
if (m == 1) {
msgTxt = "column " + trace.pos(i).charAt(0);
} else if (m == 2) {
msgTxt = "box " + posBox(i);
}
String msg = "hidden single [" + v + "] in " + msgTxt;
retMsg = new RetMsg(i, msg);
isolateSingle(i, v);
return retMsg; // single found
}
}
return retMsg;
}
static private void updPossible() {
for (int i = 0; i < 81; i++) {
possible[i].clear();
if (d[i] == 0) { // no value set till now
for (int val = 1; val < 10; val++) {
if (canSet(i, val)) {
possible[i].add(val);
}
}
}
}
}
static private Boolean SingleChk(ArrayList posList, ArrayList posValue) {
Boolean ret = false;
for (int i = 0; i < 81; i++) {
if (possible[i].size() == 1) {
// Single found
if (posList.indexOf(i) < 0) { // is new
String msg = "single [" + possible[i].get(0) + "] at position " + trace.pos(i);
addMsg(i, -1, -1, msg, 1);
posList.add(i);
posValue.add(possible[i].get(0));
ret = true;
}
}
}
return ret;
}
static private int getMinPos() {
int min = 999;
int pos = -2;
for (int i = 0; i < 81; i++) {
if (d[i] < 1 && possible[i].size() < min) {
min = possible[i].size();
pos = i;
}
}
return pos;
}
static private Boolean HiddenSinglChk(ArrayList posList, ArrayList posValue) {
Boolean ret = false;
for (int c = 0; c < 3 * 9; c++) { // row, col, box
RetMsg retMsg = chkHiddenSingles(c * 9);
if (retMsg.ret >= 0 && posList.indexOf(retMsg.ret) < 0) { // is new
posList.add(retMsg.ret); // one singel found at ret position
posValue.add(possible[retMsg.ret].get(0));
addMsg(retMsg.ret, -1, -1, retMsg.msg, 2);
ret = true;
}
}
return ret;
}
static private void analyse(int lvl, Boolean oneStep) {
// clr
trace.clear();
if (solNbr > 1) {
return;
}
ArrayList<Integer> posList = new ArrayList();
ArrayList<Integer> posValue = new ArrayList();
for (int i = 0; i < 81; i++) {
bit[i] = new BitSet(); //.clear();
} // clear indication 1=Single, 2=HiddenSingle
updPossible();
if (!SingleChk(posList, posValue) // find all Singles
&& !HiddenSinglChk(posList, posValue)) // try to find all hidden singles
{
// Twin Check
Boolean retry = false;
do {
retry = false;
for (int c = 0; c < 3 * 9; c++) { // row, col, box
if (chkTwin(c * 9)) {
retry = true;
}
}
} while (retry);
// hidden Twin Pair
do {
retry = false;
for (int c = 0; c < 3 * 9; c++) { // row, col, box
if (chkhiddenTwin(c * 9)) { // we have removed some, so retry
retry = true;
}
}
} while (retry);
// locked candidate Box
do {
retry = false;
for (int c = 2 * 9; c < 3 * 9; c++) { // box
if (chkLockedBox(c * 9)) {
retry = true;
}
}
} while (retry);
// hope: we find now further SINGLs
SingleChk(posList, posValue);
HiddenSinglChk(posList, posValue);
}
// ------------------ finished at on level -----------------------------
StringBuffer sb = new StringBuffer();
//
// valid chk (solution maybe wrong, if random select fails
Boolean valid = true;
Boolean haveSet = false;
for (int i = 0; i < posList.size(); i++) {
// do set my isolated positions
int pos = posList.get(i);
d[pos] = posValue.get(i);
haveSet = true;
if (chk(pos).ret != 0) {
valid = false;
}
if (valid) {
trace.add(getSetPos(),
lvl + ": "
+ trace.getMsgForPos(pos),
bit[posList.get(i)]);
}
}
int minPos = getMinPos();
if (minPos < 0) {
trace.addSolution(++solNbr, getBoard());
} else {
// --------------- if no set found, try random next --------------------
if (!haveSet) {
// random set
int pmax = possible[minPos].size();
int tryPos[] = new int[10];
for (int p = 0; p < pmax; p++) {
tryPos[p] = possible[minPos].get(p);
}
for (int p = 0; p < pmax; p++) {
int k = tryPos[p];
d[minPos] = k; // set Random
addMsg(minPos, -1, -1,
//getBoard() + "\n\t\t\t\t"
"random " + (p + 1) + "/" + pmax + " set [" + k + "] at position " + trace.pos(minPos),
10);
trace.add(getSetPos(),
lvl + ": "
+ trace.getMsgForPos(minPos),
bit[minPos]);
if (oneStep) {
return;
}
analyse(lvl + 1, oneStep);
d[minPos] = 0; // reset
}
} else {
// --------------- maybe a valid set was done --------------------
if (valid) {
analyse(lvl + 1, oneStep);
}
}
}
// goback
for (int i = 0; i < posList.size(); i++) {
d[posList.get(i)] = 0;
}
}
/*--------------------------------------------------------------------------
static private void addLocked(int b, int start, int ofs, int inc) {
// setOnly
locked[b][0] = start + ofs;
locked[b][1] = start + ofs + inc;
locked[b][2] = start + ofs + inc + inc;
if (ofs == 0) {
for (int i = 3; i < 9; i++) {
locked[b][i] = start + inc * i;
}
} else if (ofs == 6 || ofs == 54) {
for (int i = 0; i < 6; i++) {
locked[b][3 + i] = start + inc * i;
}
} else if (ofs == 3 || ofs == 27) {
for (int i = 0; i < 3; i++) {
locked[b][3 + i] = start + inc * i;
}
for (int i = 6; i < 9; i++) {
locked[b][i] = start + inc * i;
}
}
}
-----------------------------------*/
static private void initBoard(String iniStr) {
solNbr = 0;
for (int i = 0; i < 81; i++) {
if (iniStr.charAt(i) >= '0' && iniStr.charAt(i) <= '9') {
d[i] = new Integer(iniStr.charAt(i) - 48);
} else {
d[i] = 0;
}
possible[i] = new ArrayList<Integer>();
}
}
static private RetMsg init(String ini) {
// locked setup
int b = 0;
/*------------------------------------------------------
for (int i = 0; i < 9; i++) {
// horizontal
addLocked(b++, i * 9, 0, 1);
addLocked(b++, i * 9, 3, 1);
addLocked(b++, i * 9, 6, 1);
// vertical
addLocked(b++, i, 0, 9);
addLocked(b++, i, 27, 9);
addLocked(b++, i, 54, 9);
}
-------------------------------------------------*/
candidates.clear();
// row
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++) {
candidates.add(y * 9 + x);
}
}
// col
for (int x = 0; x < 9; x++) {
for (int y = 0; y < 9; y++) {
candidates.add(y * 9 + x);
}
}
// box
for (int yb = 0; yb < 3; yb++) {
for (int xb = 0; xb < 3; xb++) {
int ibox = xb * 3 + yb * 27;
for (int y = 0; y < 3; y++) {
for (int x = 0; x < 3; x++) {
candidates.add(ibox + x + y * 9);
}
}
}
}
for (int i = 0; i < 10; i++) {
used[i] = new ArrayList<Integer>();
}
iniStr = ini.trim().replace(" ", "").replace(".", "0");
if (iniStr.length() < 81) {
println("no valid number argument, need 81 digits, received length=" + iniStr.length());
System.exit(1);
}
initBoard(iniStr);
return chk();
}
static private int getSetPos() {
int cnt = 0;
for (int i = 0; i < 81; i++) {
if (d[i] > 0) {
cnt++;
}
}
return cnt;
//return 81 - (iniStr.length() - iniStr.replace("0", "").length());
}
static private int getSetPos(String iniStr) {
return 81 - (iniStr.length() - iniStr.replace("0", "").length());
}
static private String getBoard() {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 81; i++) {
if (d[i] == 0) {
sb.append(".");
} else {
sb.append(d[i] + "");
}
}
return sb.toString();
}
static private void addtd(String data, StringBuffer sb) {
// used for header a b c d. 1, 2, 3,.. labels
if (data.charAt(0) > '@') {
sb.append("<td class='row'>" + data + "</td>");
} else {
sb.append("<td class='col'>" + data + "</td>");
}
}
static private String getPos(int p, int i) {
if (possible[p].contains(i)) {
// http://rlhome.noip.me/body/sudoku/index.php
return "<a href='index.php?set=" + p + "&val=" + i + "&show=1&ini=" + getBoard() + "'>" + i + "</a>";
}
return " ";
}
static private void addTD(int i, int idx, StringBuffer sb) {
sb.append("\n<!-- cell " + i + " @ " + trace.pos(i) + " -->\n");
if (idx % 2 == 0) {
sb.append("<td class='inner1'>");
} else {
sb.append("<td class='inner2'>");
}
if (d[i] == 0) {
// allow input
if (inp) {
String style = "style='font-size:x-large; color:green; border:0px none; background-color:transparent;text-align: center;'"
+ " id='" + i + "'"
+ " onkeyup='keyupFunction(" + i + ")' ";
sb.append("<input " + style + " maxlength='1' size='1' type='text' name='lname'>");
} else {
sb.append(getPos(i, 1) + " " + getPos(i, 2) + " " + getPos(i, 3) + "<br>");
sb.append(getPos(i, 4) + " " + getPos(i, 5) + " " + getPos(i, 6) + "<br>");
sb.append(getPos(i, 7) + " " + getPos(i, 8) + " " + getPos(i, 9) + "<br>");
}
//sb.append(" ");
} else {
if (iniStr.charAt(i) == '0') {
sb.append("<div class='bigGray'>");
//sb.append("<b><font size='+3' color='lightgray'>" + d[i] + "</font></b>");
} else {
sb.append("<div class='big'>");
//sb.append("<b><font size='+3' color='black'>" + d[i] + "</font></b>");
}
sb.append(d[i]);
sb.append("</div>");
}
sb.append("</td>");
}
static private String html() {
StringBuffer sb = new StringBuffer();
sb.append("<style>\n"
+ "table {\n"
+ " border:0px solid black;\n"
+ " border-collapse: collapse;\n"
+ "}\n"
+ "a:link {\n"
+ " text-decoration: none;\n"
+ "}\n"
+ "td {\n"
+ " padding: 0px;\n"
+ "}\n"
+ "div.big {\n"
+ " font-size:x-large;\n"
+ " font-weight: bold;\n"
+ " color:black;\n"
+ "}\n"
+ "div.bigGray {\n"
+ " font-size:x-large;\n"
+ " font-weight: bold;\n"
+ " color:gray;\n"
+ "}\n"
+ "td.row {\n"
+ " text-align:center;\n"
+ " border:0px;\n"
+ " color:darkblue;\n"
+ " width:40px;\n"
+ "}\n"
+ "td.col {\n"
+ " text-align:center;\n"
+ " border:0px;\n"
+ " color:darkblue;\n"
+ " width:20px;\n"
+ " height:40px;\n"
+ "}\n"
+ "td.inner1 {\n"
+ " background-color:#FEFEFE;\n"
+ " text-align:center;\n"
+ " border:1px solid black;\n"
+ " line-height: 0.9;\n"
+ " font-size:small;\n"
+ " font-family:'Courier New', Arial;\n"
+ " height:40px;\n"
+ " width:40px;\n"
+ "}\n"
+ "td.inner2 {\n"
+ " background-color:#F0F0F0;\n"
+ " text-align:center;\n"
+ " border:1px solid black;\n"
+ " line-height: 0.9;\n"
+ " font-size:small;\n"
+ " font-family:'Courier New', Arial;\n"
+ " height:40px;\n"
+ " width:40px;\n"
+ "}\n"
+ "</style>\n");
sb.append("\n<script>"
+ "function keyupFunction(id) {\n"
+ " var val = document.getElementById(id).value;\n"
+ " var n=val.length;\n"
+ " if (val>0) {\n"
+ " window.location = 'http://rlhome.noip.me/body/sudoku/index.php?set='+id+'&val='+val+'&ini=" + getBoard() + "'\n"
+ " }\n"
+ "}\n"
+ "</script>\n\n");
sb.append("<table>\n");
// head line a b c ....
sb.append("<tr><td>");
sb.append("<table >\n");
sb.append("<tr><td>");
sb.append("</td></tr></table></td>\n");
char c = 'a';
int row = 1;
for (int j = 0; j < 3; j++) {
sb.append("<td>");
sb.append("<table>\n<tr>");
for (int i = 0; i < 3; i++) {
addtd("" + c++, sb);
}
sb.append("</tr></table>\n");
}
sb.append("\n\n\n\n");
// end of head line a b c ....
for (int idx = 162; idx < candidates.size(); idx++) {
int i = candidates.get(idx);
if (idx % 27 == 0) {
sb.append("<tr>\n");
sb.append("<td><table>");
for (int j = 0; j < 3; j++) {
sb.append("<tr>");
addtd("" + row++, sb);
sb.append("</tr>");
}
sb.append("</table></td>");
}
if (idx % 9 == 0) {
sb.append("<td><table>\n");
}
if (idx % 3 == 0) {
sb.append("<tr>\t");
}
addTD(i, idx, sb);
if (idx % 3 == 2) {
sb.append("</tr>\n");
}
if (idx % 9 == 8) {
sb.append("</table></td>\n");
}
if (idx % 27 == 26) {
sb.append("</tr>\n");
}
}
sb.append("</table>");
file_put_contents(fnHTML, sb.toString());
return "";
}
public static boolean file_put_contents(String filename, String data) {
try {
FileWriter fstream = new FileWriter(filename, false);
BufferedWriter out = new BufferedWriter(fstream);
out.write(data);
out.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
return (true);
}
static private String disp() {
/*
. . 5 . 6 . 1 . .
. 3 . 8 . . . . .
. . . . . . . . .
. . . 2 . . . 8 3
. . 7 . 4 . . . .
. . . . . . . 9 .
. . . . . 1 7 . .
8 . . . . . 2 . .
2 9 . . . . . . .
*/
if (html) {
updPossible();
return html();
}
StringBuffer sb = new StringBuffer();
if (disp || verbose) {
sb.append(" a b c d e f g h i \n");
sb.append(" +-------+-------+-------+\n1 | ");
for (int i = 0; i < 81; i++) {
if (d[i] == 0) {
sb.append(". ");
} else {
sb.append(d[i] + " ");
}
if (i % 3 == 2) {
sb.append("| ");
}
if (i % 27 == 26) {
sb.append("\n +-------+-------+-------+\n");
if (i < 80) {
sb.append(2 + i / 9);
sb.append(" | ");
}
} else if (i % 9 == 8) {
sb.append("\n");
sb.append(2 + i / 9);
sb.append(" | ");
}
}
} else {
return getBoard();
}
if (disp) {
return sb.toString();
}
return "";
}
private static void usage() {
println("valid args are:");
println("<nbrs> \t 9x9 = 81 digits 1..9 or 0/. for unused");
println("-solve \t try to solve a puzzle");
println("-gen \t to generate a puzzle");
println("-tip \t show tip for next position");
println("\nInput options:");
println("-gen <size> \t generate with less than <size> known positions");
println("-inp \t allow input in generated HTML output");
println("-set pos:val \t set val@pos and do a chk if pos is valid");
println("-lvlmin <nbr> \t generate sudoku wich needs at least nbr steps to solve");
println("-lvlmax <nbr> \t generate sudoku wich needs less nbr steps to solve");
println("-sym \t create symmetric puzzles");
println("-test \t solve 100 Sudokus for speed test (init + chk + solve + displ)");
println("\nOuput options:");
println("-chk \t check nbrs are valid");
println("-display \t show it detailed");
println("-disp \t show it");
println("-html <fn> \t create fn as HTML");
println("-verbose \t detailed report and solution hints");
println("-genIni \t show generated Ini only");
System.exit(0);
}
private static int getRnd() {
// 0..80
return ThreadLocalRandom.current().nextInt(0, 81);
}
private static void rndSet(int howMany) {
int cnt = 0;
int maxTry = 10;
int val;
do {
for (int i = 0; i < 81; i++) {
d[i] = 0;
}
iniStr = ".................................................................................";
for (int r = 0; r < howMany; r++) {
int x = getRnd() % 3;
int y = getRnd() % 3;
// only Box0, so there is no illeagal SET possible
int i = x + 9 * y;
if (d[i] == 0) {
cnt = 0;
do {
val = 1 + getRnd() % 9;
cnt++;
} while (!canSet(i, val) && cnt < maxTry);
d[i] = val;
iniStr = iniStr.substring(0, i) + val + iniStr.substring(i + 1);
}
i = 8 - x + (8 - y) * 9; // sym position
cnt = 0;
do {
val = 1 + getRnd() % 9;
cnt++;
} while (!canSet(i, val) && cnt < maxTry);
d[i] = val;
iniStr = iniStr.substring(0, i) + val + iniStr.substring(i + 1);
}
// chk, if valid!
} while (chk().ret != 0); // retry if chk fails
}
private static void rndRemove() {
// find a pos/value
int i;
do {
i = getRnd();
} while (iniStr.charAt(i) == '0');
iniStr = iniStr.substring(0, i) + '0' + iniStr.substring(i + 1);
if (sym) { // another
int x = 8 - (i % 9);
int y = 8 - (i / 9);
i = x + y * 9;
iniStr = iniStr.substring(0, i) + '0' + iniStr.substring(i + 1);
}
}
private static Boolean tryRemove(int genMinSet) {
// just retry (maybe other twin/single could be removed
// -------------- first remove some
do {
rndRemove(); // just remove one/two from iniStr
} while (getSetPos(iniStr) > 50);
initBoard(iniStr);
// -------------- if we fail to solve exit
if (chk().ret != 0) {
return false;
}
// in rare cases we have an initStr, which has NO solution.
// chk() will return ok, but could not be solved!
String lastIni;
int cnt = 0;
int n = 0;
// search with cnt retries ONE Solution with MinSets
do {
lastIni = iniStr; // keep a copy
rndRemove(); // just remove one/two from iniStr
initBoard(iniStr);
analyse(0, false);
if (solNbr != 1) {
iniStr = lastIni; // restore prev and retry
}
n = getSetPos();
} while (++cnt < 24 && (solNbr != 1 || n >= genMinSet));
if (solNbr > 1 || n >= genMinSet) {
return false;
}
if (verbose) {
println("solNbr=" + solNbr + " minSet=" + getSetPos() + " " + getBoard());
}
return true;
//
}
private static String stat() {
/*
int n = 0;
for (int i = 0; i < 81; i++) {
if (d[i] > 0) {
n++;
}
}
*/
String br;
if (html) {
br = "<br>";
} else {
br = "\n\t\t";
}
return ("start=" + (81 - trace.getN())
+ "; " + trace.getCntList()
// + "; generate retries=" + cntGen
+ br);
}
private static String generate() {
boolean fnd = false;
cntGen = 0;
trace = new Trace();
do {
rndSet(genMin);
if (init(iniStr).ret == 0) {
solNbr = 0;
analyse(0, false); // solve it first
if (solNbr > 0) {
do {
iniStr = trace.getSolution();
} while (!tryRemove(genMinSet));
// min iniStr found which has 1 solution, solve it
initBoard(iniStr);
int n = getSetPos();
if (n < genMinSet) {
trace = new Trace();
analyse(0, false);
cntGen++;
// report good ones only
if (solNbr == 1 && trace.isInLvl(lvlmincnt, lvlmaxcnt)) {
fnd = true;
}
}
}
}
} while (!fnd);
return iniStr.replace("0", ".");
}
public static String posBox(int i) {
int x = i % 9;
int y = i / 9;
int xS = x - (x % 3);
int xE = xS + 2;
int yS = y - (y % 3);
int yE = yS + 2;
char cS = (char) ('a' + xS);
char cE = (char) ('a' + xE);
return cS + "" + (yS + 1) + "-" + cE + "" + (yE + 1);
}
//------------------ M A I N ---------------------------------
public static void main(String[] args) {
startTime = System.nanoTime();
String valPos = "0@0";
String ini = "";
if (args.length < 1) {
usage();
} else {
for (int i = 0; i < args.length; i++) {
if (args[i].length() > 80) {
ini = args[i].trim().replace(" ", "");
} else if (args[i].contentEquals("-gen")) {
gen = true;
if (args.length > i + 1) {
if (args[i + 1].charAt(0) != '-') {
genMinSet = new Integer(args[++i]);
}
}
} else if (args[i].contentEquals("-verbose")) {
verbose = true;
} else if (args[i].contentEquals("-solve")) {
solve = true;
} else if (args[i].contentEquals("-sym")) {
sym = true;
} else if (args[i].contentEquals("-tip")) {
tip = true;
} else if (args[i].contentEquals("-disp")) {
disp = true;
} else if (args[i].contentEquals("-html")) {
html = true;
if (args.length > i + 1) {
if (args[i + 1].charAt(0) != '-') {
fnHTML = args[++i];
}
}
} else if (args[i].contentEquals("-inp")) {
inp = true;
} else if (args[i].contentEquals("-chk")) {
chk = true;
} else if (args[i].contentEquals("-set")) {
set = true;
if (args.length > i + 1) {
if (args[i + 1].charAt(0) != '-') {
valPos = args[++i];
}
}
} else if (args[i].contentEquals("-lvlmin")) {
lvlmin = true;
if (args.length > i + 1) {
if (args[i + 1].charAt(0) != '-') {
lvlmincnt = new Integer(args[++i]);
}
}
} else if (args[i].contentEquals("-lvlmax")) {
lvlmax = true;
if (args.length > i + 1) {
if (args[i + 1].charAt(0) != '-') {
lvlmaxcnt = new Integer(args[++i]);
}
}
} else if (args[i].contentEquals("-display")) {
display = true;
} else if (args[i].contentEquals("-test")) {
trace = new Trace();
ini = "..5.6.1.. .3.8.............. ...2...83..7.4...........9. .....17..8.....2..29.......";
for (int t = 0; t < 100; t++) {
init(ini);
analyse(0, false);
}
printlnElapsed("end of test");
System.exit(0);
} else {
println("unknown argument ='" + args[i] + "'\n\n");
usage();
}
}
}
if (set) {
RetMsg retMsg = init(ini);
if (retMsg.ret == 0) {
// valPos = 3@60 d[60]=3;
String tmp[] = valPos.split("@");
if (tmp.length == 2) {
int val = new Integer(tmp[0]);
int pos = new Integer(tmp[1]);
d[pos] = val;
ini = getBoard();
retMsg = chk(pos);
if (retMsg.ret != 0) {
// println(retMsg.msg);
chk = false; // no more checks
}
}
} else {
//println(retMsg.msg);
chk = false;
}
}
if (chk) {
init(ini);
trace = new Trace();
analyse(0, false);
if (trace.getSolNbr() == 1) {
println("ok");
} else if (trace.getSolNbr() > 1) {
println("not unique!");
} else {
println("no solution found!");
}
init(ini);
} else if (gen) {
ini = generate();
printlnElapsed("Sudoku is generated\n\t\t" + stat() + ini);
} else {
if (init(ini).ret == 0) {
trace = new Trace();
if (tip) {
analyse(0, true);
}
if (solve) {
analyse(0, false);
initBoard(trace.getSolution());
solNbr = trace.getSolNbr();
if (solNbr > 1) {
printlnElapsed("not unique!\t");
} else if (solNbr < 1) {
printlnElapsed("no solution!\t");
} else {
printlnElapsed(trace.getSolution() + "\n\t\t" + stat());
}
}
} else {
printlnElapsed("Error!\n" + chk().msg);
}
}
if (disp) {
println(disp());
}
if (display) {
display();
}
if (verbose || tip) {
//println(trace.getShortList(tip));
if (!tip) {
println("no\tstep\tset\t\texplain");
println("-----------------------------------------------------------");
}
print(trace.getList(tip));
}
}
}