📄 solver.java
字号:
{
if( (n/3)*3 == except) continue; // skip numbers in the same block
if( posVals[row][n][num] == 1)
{
posVals[row][n][num] = 0;
posVals[row][n][0]--;
posValsChanged = true;
}
// CONSTS.log("remain: " + posVals[row][n]);
}
// if ( posibleValsChanged) CONSTS.log( "removeNum " + num + " FromRow " + row + posibleValsToString());
return posValsChanged;
}
private boolean removeNumFromCol(int num, int col, int except)
{
boolean posValsChanged = false;
// CONSTS.log("removeNum " + num + " FromCol " + col);
for (int n = 0; n < 9; n++)
{
if( (n/3)*3 == except) continue; // skip numbers in the same block
if( posVals[n][col][num] == 1)
{
posVals[n][col][num] = 0;
posVals[n][col][0]--;
posValsChanged = true;
}
// CONSTS.log("remain: " + posVals[n][col]);
}
// if ( posValsChanged) CONSTS.log( "removeNum " + num + " FromCol " + col + posibleValsToString());
return posValsChanged;
}
private boolean removeNumFromBox(int num, int i, int j, int excludeRow, int excludeCol)
{
boolean posValsChanged = false;
for(int x = i - i%3; x < i - i%3 + 3; x++)
{
if( x == excludeRow) continue;
for(int y = j - j%3; y < j - j%3 + 3; y++)
{
if( y == excludeCol || posVals[x][y][num] == 0) continue;
posVals[x][y][num] = 0;
posVals[x][y][0]--;
posValsChanged = true;
}
}
// if ( posibleValsChanged) CONSTS.log( "removeNumFromBox " + posibleValsToString());
return posValsChanged;
}
protected void fillPosVals()
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (matriu[i][j] >= 1)
{
posVals[i][j][0] = -matriu[i][j]; // we store the value
// but with minus signal
} else
{
posVals[i][j][0] = 9; // maximum posible values
for (int n = 1; n <= 9; n++)
{
posVals[i][j][n] = 1;
for (int x = 0; x < 9; x++)
{
if ( matriu[i][x] == n ||
matriu[x][j] == n ||
matriu[(i/3) * 3 + (x/3)][(j/3) * 3 + (x%3)] == n)
{
posVals[i][j][n] = 0; // no posible value
posVals[i][j][0]--;
break;
}
}
}
}
}
}
}
protected void loopAllStg()
{
boolean changed = true;
Hashtable auxCache = new Hashtable();
String key = null;
Integer diff = null;
while( changed && filled < 81)
{
// key = matriuToKey( matriu);
// diff = (Integer )cache.get( key);
// if( diff != null)
// {
// CONSTS.log("found in cache:\n" + key + " Diff: " + diff + "\n");
// difficulty += diff.intValue();
// if( difficulty >= 0) filled = 81;
// break;
// }
// else
// {
// auxCache.put( key, new Integer( -difficulty));
// }
changed = true;
if( !applyStrategy_1())
if( !applyStrategy_2())
if( !applyStrategy_3_locked_candidates_1())
if( !applyStrategy_4_locked_candidates_2())
if( !applyStrategy_5_naked_pairs())
if( !applyStrategy_6_hidden_pairs())
if( !applyStrategy_8_naked_triples_B())
if( !applyStrategy_9_hidden_triples())
changed = false;
}
if( filled < 81) difficulty = -10000;
// Enumeration k = auxCache.keys();
// while ( k.hasMoreElements())
// {
// key = (String )k.nextElement();
// cache.put( key, new Integer( ((Integer )auxCache.get(key)).intValue() + difficulty ));
// //CONSTS.log("Added to cache:\n" + key + "Diff: " + cache.get(key) + "\n");
// }
}
public int[][] getMatriu()
{
return matriu;
}
public int getFilled()
{
return filled;
}
public String toString()
{
return matriuToString( matriu);
}
public String posibleValsToString()
{
StringBuffer res = new StringBuffer();
res.append("\n-----------------------------------------------------\n");
for (int i = 0; i < 9; i++)
{
for (int subLine = 0; subLine < 3; subLine++)
{
for (int j = 0; j < 9; j++)
{
for (int subCol = 0; subCol < 3; subCol++)
{
int num = subLine*3 + subCol + 1;
if( posVals[i][j][num] == 1)
{
res.append( num);
}
else
{
res.append(" ");
}
}
res.append(" | ");
}
res.append("\n");
}
res.append("-----------------------------------------------------\n");
}
return res.toString();
}
private boolean checkGroupForNakedPairs(int[][] group)
{
boolean posibleValsChanged = false;
boolean found;
int par1, par2;
for (int n = 0; n < 9; n++)
{
if (group[n][0] == 2)
{
for (int m = n + 1; m < 9; m++)
{
if (group[m][0] == 2)
{
found = true;
par1 = par2 = 0;
for (int k = 1; k <= 9; k++)
{
if (group[n][k] != group[m][k]) // check if is the
// same pair
{
found = false;
break;
}
else if( group[n][k] == 1)
{
if( par1 == 0) par1 = k;
else par2 = k;
}
}
if ( found) // Pair found -> remove pair from other
// cells
{
// CONSTS.log( "Naked pair found " + par1 + " " + par2);
for (int x = 0; x < group.length; x++)
{
if (x != n && x != m)
{
if( group[x][par1] == 1)
{
group[x][par1] = 0;
group[x][0]--;
posibleValsChanged = true;
// CONSTS.log( "Naked pair. pos removed: " + par1);
}
if( group[x][par2] == 1)
{
group[x][par2] = 0;
group[x][0]--;
posibleValsChanged = true;
// CONSTS.log( "Naked pair. pos removed: " + par2);
}
}
}
}
}
}
}
}
return posibleValsChanged;
}
/**
* posVals should be initialized before with method fillPosVals
*
*/
protected int findAllSols( int level, boolean checkOnlyUninicity)
{
int row = -1;
int col = -1;
for (int i = 0; i < 9; i++) // search pos with less posible values
{
for (int j = 0; j < 9; j++)
{
if (posVals[i][j][0] == 0) return 0; // no solution
if (posVals[i][j][0] > 0 // (we ignore solved cells)
&& (row == -1 || posVals[i][j][0] < posVals[row][col][0]))
{
row = i;
col = j;
}
}
}
if (row == -1) return 1; // solution found
int sols = 0; // number of solutions
int numPosVals = posVals[row][col][0];
for (int num = 1; num <= 9; num++)
{
if (posVals[row][col][num] != 1)
continue;
posVals[row][col][0] = -num;
for (int i = 0; i < 9; i++)
{
int[] aux = posVals[row][i];
if (aux[0] >= 0 && aux[num] == 1)
{
aux[0]--;
aux[num] = level;
}
aux = posVals[i][col];
if (aux[0] >= 0 && aux[num] == 1)
{
aux[0]--;
aux[num] = level;
}
aux = posVals[(row / 3) * 3 + (i / 3)][(col / 3) * 3 + (i % 3)];
if (aux[0] >= 0 && aux[num] == 1)
{
aux[0]--;
aux[num] = level;
}
}
sols += findAllSols(level - 1, checkOnlyUninicity);
for (int i = 0; i < 9; i++)
{
int[] aux = posVals[row][i];
if (aux[0] >= 0 && aux[num] == level)
{
aux[0]++;
aux[num] = 1;
}
aux = posVals[i][col];
if (aux[0] >= 0 && aux[num] == level)
{
aux[0]++;
aux[num] = 1;
}
aux = posVals[(row / 3) * 3 + (i / 3)][(col / 3) * 3 + (i % 3)];
if (aux[0] >= 0 && aux[num] == level)
{
aux[0]++;
aux[num] = 1;
}
}
if ( checkOnlyUninicity && sols > 1)
{
break; // with 2 or more solutions finish
}
}
posVals[row][col][0] = numPosVals;
return sols;
}
protected int calcDifficulty()
{
loopAllStg();
CONSTS.log( strategiesUsed + " difficulty " + difficulty);
return difficulty;
}
protected void resetCache()
{
if( cache == null) cache = new Hashtable();
else cache.clear();
}
public void clearVal(int i, int j)
{
int num = matriu[i][j];
if( num <= 0 )
throw new RuntimeException("Cant clearVal " + num);
matriu[i][j] = 0;
filled--;
// fillPosVals(); // TODO: optimize
// Arrays.fill( posVals[i][j], 1);
// posVals[i][j][0] = 9;
// for (int n = 0; n < 9; n++)
// {
// if( n != j)
// {
// if( matriu[i][n] > 0 && posVals[i][j][matriu[i][n]] == 1)
// {
// posVals[i][j][matriu[i][n]] = 0;
// posVals[i][j][0]--;
// }
// else if ( posVals[i][n][num] == 1)
// {
// posVals[i][n][num] = 0;
// posVals[i][n][0]--;
// }
// }
//
// if( n != i)
// {
// if( matriu[n][j] > 0 && posVals[i][j][matriu[n][j]] == 1)
// {
// posVals[i][j][matriu[n][j]] = 0;
// posVals[i][j][0]--;
// }
// else if ( posVals[n][j][num] == 1)
// {
// posVals[n][j][num] = 0;
// posVals[n][j][0]--;
// }
// }
//
// int boxi = (i/3)*3 + (n/3);
// int boxj = (j/3)*3 + (n%3);
// if( boxi != i || boxj != j)
// {
// if( matriu[boxi][boxj] > 0 && posVals[i][j][matriu[boxi][boxj]] == 1)
// {
// posVals[i][j][matriu[boxi][boxj]] = 0;
// posVals[i][j][0]--;
// }
// else if ( posVals[boxi][boxj][num] == 1)
// {
// posVals[boxi][boxj][num] = 0;
// posVals[boxi][boxj][0]--;
// }
// }
// }
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -