<%@ page import="jakarta.servlet.jsp.JspWriter" %> <%@ page import="java.util.*" %> <%! boolean english = false; class Comparer implements java.util.Comparator { public int compare(Object obj1, Object obj2) { Set s1 = (Set) obj1; Iterator it1 = s1.iterator(); int first = 0; while (it1.hasNext()) { first = (first * 10) + ((Integer) it1.next()).intValue() + 1; } Set s2 = (Set) obj2; Iterator it2 = s2.iterator(); int second = 0; while (it2.hasNext()) { second = (second * 10) + ((Integer) it2.next()).intValue() + 1; } return first - second; } } class Context { private boolean solveAll; private boolean solveUntilInteresting; private boolean interesting; private int noOfSolutions; private JspWriter jspWriter; int recursions = 0; int deductions = 0; Cell[][] board; int remaining; boolean reduced; } class Cell { int row; int col; int square; int value; String color; Set candidates; public Cell(int row, int col, int value) { this.row = row; this.col = col; this.square = (row / 3) * 3 + (col / 3); this.value = value; this.candidates = null; this.color = null; } public String toString() { return "(" + (row + 1) + "," + (col + 1) + ")"; } } private String squareNo(int square) { if (english) { switch (square) { case 0: return "the upper left square"; case 1: return "the upper middle square"; case 2: return "the upper right square"; case 3: return "the middle left square"; case 4: return "the middle square"; case 5: return "the middle right square"; case 6: return "the lower left square"; case 7: return "the lower middle square"; case 8: return "the lower right square"; } } else { switch (square) { case 0: return "kvadratet øverst til venstre"; case 1: return "kvadratet øverst i midten"; case 2: return "kvadratet øverst til højre"; case 3: return "kvadratet i midten til venstre"; case 4: return "kvadratet i midten"; case 5: return "kvadratet i midten til højre"; case 6: return "kvadratet nederst til venstre"; case 7: return "kvadratet nederst i midten"; case 8: return "kvadratet nederst til højre"; } } return "error"; } private void display(Context context, String txt) { try { context.jspWriter.println(txt); context.jspWriter.println("
"); } catch (Exception e) { } } private String displaySetPlusOne(Set set) { Set tmp = new HashSet(); Iterator it = set.iterator(); while (it.hasNext()) { int i = ((Integer) it.next()).intValue() + 1; tmp.add(new Integer(i)); } return tmp.toString(); } private void printCandidates(Context context, Set candidates) throws Exception { context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println(""); context.jspWriter.println("

"); if (candidates.contains(new Integer(1))) { context.jspWriter.print("1"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(2))) { context.jspWriter.print("2"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(3))) { context.jspWriter.print("3"); } context.jspWriter.println("
"); if (candidates.contains(new Integer(4))) { context.jspWriter.print("4"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(5))) { context.jspWriter.print("5"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(6))) { context.jspWriter.print("6"); } context.jspWriter.println("
"); if (candidates.contains(new Integer(7))) { context.jspWriter.print("7"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(8))) { context.jspWriter.print("8"); } context.jspWriter.println("	"); if (candidates.contains(new Integer(9))) { context.jspWriter.print("9"); } context.jspWriter.println("

"); } private void displayBoard(Context context) { try { context.jspWriter.println(""); context.jspWriter.print(""); context.jspWriter.println(""); for (int i = 0; i < 9; i++) { context.jspWriter.println(""); context.jspWriter.print(""); for (int j = 0; j < 9; j++) { context.jspWriter.print(""); context.board[i][j].color = null; if (j % 3 == 2) { context.jspWriter.print(""); } else { context.jspWriter.print(""); } } context.jspWriter.println(""); if (i % 3 == 2) { context.jspWriter.print(""); context.jspWriter.println(""); } else { context.jspWriter.print(""); context.jspWriter.println(""); } } context.jspWriter.println("

"); context.jspWriter.println("

"); if (context.board[i][j].value != 0) { context.jspWriter.print(context.board[i][j].value); } else { printCandidates(context, context.board[i][j].candidates); } context.jspWriter.println("

"); context.jspWriter.println("

"); context.jspWriter.flush(); } catch (Exception e) { e.printStackTrace(); } } private void displaySolution(Context context) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { context.board[i][j].color = "lightgreen"; } } if (english) { display(context, "

Solution found

"); } else { display(context, "

Løsning fundet

"); } displayBoard(context); } private void clearBoardColors(Context context) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { context.board[i][j].color = null; } } } private Cell getEmptyCellWithLeastCandidates(Context context) { Cell candidateCell = null; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (context.board[i][j].value == 0) { context.board[i][j].candidates = getCandidatesBySudokuRule(context, i, j); if (context.board[i][j].candidates.size() == 1) { if (!context.solveAll) { clearBoardColors(context); List all = getAllCellsInRow(context, i); for (int k = 0; k < 9; k++) { ((Cell) all.get(k)).color = "yellow"; } all = getAllCellsInColumn(context, j); for (int k = 0; k < 9; k++) { ((Cell) all.get(k)).color = "yellow"; } all = getAllCellsInSquare(context, ((i / 3) * 3) + (j / 3)); for (int k = 0; k < 9; k++) { ((Cell) all.get(k)).color = "yellow"; } displayBoard(context); } context.board[i][j].color = "green"; if (english) { display(context, "After removing candidates from the same row, column and square, there is a naked single in" + context.board[i][j] + " : " + context.board[i][j].candidates.toArray()[0]); } else { display(context, "Efter at have fjernet alle værdier fra samme række, søjle og kvadrat er der kun en mulig værdi for " + context.board[i][j] + " : " + context.board[i][j].candidates.toArray()[0]); } return context.board[i][j]; } } } } do { context.reduced = false; for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = testForSingleCandidate(context, getEmptyCellsInRow(context, i), getAllCellsInRow(context, i), " række " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = testForSingleCandidate(context, getEmptyCellsInColumn(context, i), getAllCellsInColumn(context, i), " søjle " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = testForSingleCandidate(context, getEmptyCellsInSquare(context, i), getAllCellsInSquare(context, i), squareNo(i))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceBySingleRowInSquare(context, getEmptyCellsInSquare(context, i), getAllCellsInSquare(context, i), squareNo(i))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceBySingleColumnInSquare(context, getEmptyCellsInSquare(context, i), getAllCellsInSquare(context, i), squareNo(i))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceBySingleSquare(context, getEmptyCellsInRow(context, i), getAllCellsInRow(context, i), " række " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceBySingleSquare(context, getEmptyCellsInColumn(context, i), getAllCellsInColumn(context, i), " søjle " + (i + 1))) != null) { return candidateCell; } } if ((candidateCell = reduceByDualLaser(context)) != null) { return candidateCell; } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceByCandidateCardinality(context, getEmptyCellsInRow(context, i), getAllCellsInRow(context, i), " række " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceByCandidateCardinality(context, getEmptyCellsInColumn(context, i), getAllCellsInColumn(context, i), " søjle " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceByCandidateCardinality(context, getEmptyCellsInSquare(context, i), getAllCellsInSquare(context, i), squareNo(i))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceHidden(context, getEmptyCellsInRow(context, i), getAllCellsInRow(context, i), " række " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceHidden(context, getEmptyCellsInColumn(context, i), getAllCellsInColumn(context, i), " søjle " + (i + 1))) != null) { return candidateCell; } } for (int i = 0; !context.reduced && i < 9; i++) { if ((candidateCell = reduceHidden(context, getEmptyCellsInSquare(context, i), getAllCellsInSquare(context, i), squareNo(i))) != null) { return candidateCell; } } if (!context.reduced) { if ((candidateCell = reduceByLockedCandidateInIntersectionInRows(context)) != null) { return candidateCell; } } if (!context.reduced) { if ((candidateCell = reduceByLockedCandidateInIntersectionInColumns(context)) != null) { return candidateCell; } } if (!context.reduced) { if ((candidateCell = reduceByColouring(context)) != null) { return candidateCell; } } if (!context.reduced) { if ((candidateCell = reduceByCandidateChain(context)) != null) { return candidateCell; } } } while (context.reduced); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (context.board[i][j].value == 0) { if (candidateCell == null || context.board[i][j].candidates.size() < candidateCell.candidates.size()) { candidateCell = context.board[i][j]; } } } } return candidateCell; } private Set getUnionOfCandidates(List cells) { Iterator it = cells.iterator(); Set union = new HashSet(); while (it.hasNext()) { Cell cell = (Cell) it.next(); union.addAll(cell.candidates); } return union; } private Cell reduceBySingleRowInSquare(Context context, List cells, List all, String origin) { Set union = getUnionOfCandidates(cells); Iterator it = union.iterator(); while (it.hasNext()) { Integer candidate = ((Integer) it.next()); Set rows = new HashSet(); Cell cell; int row = 0; Iterator it1 = cells.iterator(); while (it1.hasNext()) { cell = (Cell) it1.next(); if (cell.candidates.contains(candidate)) { rows.add(new Integer(cell.row)); row = cell.row; } } if (rows.size() == 1) { List cellsInRow = getEmptyCellsInRow(context, row); Iterator it2 = cellsInRow.iterator(); while (it2.hasNext()) { cell = (Cell) it2.next(); if (!cells.contains(cell) && cell.candidates.contains(candidate)) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { for (int i = 0; i < 9; i++) { if (all.contains(context.board[row][i])) { context.board[row][i].color = "yellow"; } } cell.color = "red"; displayBoard(context); context.interesting = true; } cell.candidates.remove(candidate); if (english) { display(context, candidate + " is the only possible candidate in row " + (row + 1) + " in " + origin); display(context, "Thus " + candidate + " is not a candidate in " + cell); } else { display(context, candidate + " optræder kun som mulig værdi i række " + (row + 1) + " i " + origin); display(context, "Derfor kan " + candidate + " fjernes som mulig værdi fra " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } return null; } private Cell reduceBySingleColumnInSquare(Context context, List cells, List all, String origin) { Set union = getUnionOfCandidates(cells); Iterator it = union.iterator(); while (it.hasNext()) { Integer candidate = ((Integer) it.next()); Set cols = new HashSet(); Cell cell; int col = 0; Iterator it1 = cells.iterator(); while (it1.hasNext()) { cell = (Cell) it1.next(); if (cell.candidates.contains(candidate)) { cols.add(new Integer(cell.col)); col = cell.col; } } if (cols.size() == 1) { List cellsInColumn = getEmptyCellsInColumn(context, col); Iterator it2 = cellsInColumn.iterator(); while (it2.hasNext()) { cell = (Cell) it2.next(); if (!cells.contains(cell) && cell.candidates.contains(candidate)) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { for (int i = 0; i < 9; i++) { if (all.contains(context.board[i][col])) { context.board[i][col].color = "yellow"; } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(candidate); if (english) { display(context, candidate + " is the only possible candidate in column " + (col + 1) + " in " + origin); display(context, "Thus " + candidate + " is not a candidate in " + cell); } else { display(context, candidate + " optræder kun som mulig værdi i søjle " + (col + 1) + " i " + origin); display(context, "Derfor kan " + candidate + " fjernes som mulig værdi fra " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } return null; } private Cell reduceBySingleSquare(Context context, List cells, List all, String origin) { Set union = getUnionOfCandidates(cells); Iterator it = union.iterator(); while (it.hasNext()) { Integer candidate = ((Integer) it.next()); Set squares = new HashSet(); Cell cell; int square = 0; Iterator it1 = cells.iterator(); while (it1.hasNext()) { cell = (Cell) it1.next(); if (cell.candidates.contains(candidate)) { squares.add(new Integer((cell.row / 3) * 3 + (cell.col / 3))); square = (cell.row / 3) * 3 + (cell.col / 3); } } if (squares.size() == 1) { List cellsInSquare = getEmptyCellsInSquare(context, square); Iterator it2 = cellsInSquare.iterator(); while (it2.hasNext()) { cell = (Cell) it2.next(); if (!cells.contains(cell) && cell.candidates.contains(candidate)) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { List allCellsInSquare = getAllCellsInSquare(context, square); for (int i = 0; i < 9; i++) { Cell tmp = ((Cell) all.get(i)); if (allCellsInSquare.contains(tmp)) { tmp.color = "yellow"; } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(candidate); if (english) { display(context, candidate + " is the only possible candidate in " + squareNo(square) + " in " + origin); display(context, "Thus " + candidate + " is not a candidate in " + cell); } else { display(context, candidate + " optræder kun som mulig værdi i " + squareNo(square) + " i " + origin); display(context, "Derfor kan " + candidate + " fjernes som mulig værdi fra " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } return null; } private Cell reduceByDualLaserInCols(Context context, int laser1, int laser2, int target) { List emptyCellsInLaser1 = getEmptyCellsInSquare(context, laser1); Set possibleCandidatesInLaser1 = getUnionOfCandidates(emptyCellsInLaser1); Iterator iter = possibleCandidatesInLaser1.iterator(); while (iter.hasNext()) { Integer candidate = (Integer) iter.next(); Set cols = new HashSet(); Iterator iter1 = getEmptyCellsInSquare(context, laser1).iterator(); while (iter1.hasNext()) { Cell cell = (Cell) iter1.next(); if (cell.candidates.contains(candidate)) { cols.add(new Integer(cell.col)); } } if (cols.size() != 2) { return null; } List emptyCellsInLaser2 = getEmptyCellsInSquare(context, laser2); Iterator iter2 = emptyCellsInLaser2.iterator(); Set possibleCandidatesInLaser2 = getUnionOfCandidates(emptyCellsInLaser2); if (!possibleCandidatesInLaser2.contains(candidate)) { return null; } while (iter2.hasNext()) { Cell cell = (Cell) iter2.next(); if (cell.candidates.contains(candidate)) { cols.add(new Integer(cell.col)); } } if (cols.size() != 2) { return null; } List emptyCellsInTarget = getEmptyCellsInSquare(context, target); Set possibleCandidatesInTarget = getUnionOfCandidates(emptyCellsInTarget); if (!possibleCandidatesInTarget.contains(candidate)) { return null; } Iterator iter3 = emptyCellsInTarget.iterator(); while (iter3.hasNext()) { Cell cell = (Cell) iter3.next(); if (cell.candidates.contains(candidate) && cols.contains(new Integer(cell.col))) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator iter4 = emptyCellsInLaser1.iterator(); while (iter4.hasNext()) { Cell tmp = (Cell) iter4.next(); if (tmp.candidates.contains(candidate)) { tmp.color = "yellow"; } } Iterator iter5 = emptyCellsInLaser2.iterator(); while (iter5.hasNext()) { Cell tmp = (Cell) iter5.next(); if (tmp.candidates.contains(candidate)) { tmp.color = "yellow"; } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(candidate); if (english) { display(context, candidate + " appears only as candidate in the 2 columns " + displaySetPlusOne(cols) + " in " + squareNo(laser1) + " and " + squareNo(laser2)); display(context, "Thus " + candidate + " is not a candidate in " + cell); } else { display(context, candidate + " optræder kun som kandidat i de 2 søjler " + displaySetPlusOne(cols) + " i " + squareNo(laser1) + " og " + squareNo(laser2)); display(context, "Derfor kan " + candidate + " fjernes som mulig værdi fra " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } return null; } private Cell reduceByDualLaserInRows(Context context, int laser1, int laser2, int target) { List emptyCellsInLaser1 = getEmptyCellsInSquare(context, laser1); Set possibleCandidatesInLaser1 = getUnionOfCandidates(emptyCellsInLaser1); Iterator iter = possibleCandidatesInLaser1.iterator(); while (iter.hasNext()) { Integer candidate = (Integer) iter.next(); Set rows = new HashSet(); Iterator iter1 = getEmptyCellsInSquare(context, laser1).iterator(); while (iter1.hasNext()) { Cell cell = (Cell) iter1.next(); if (cell.candidates.contains(candidate)) { rows.add(new Integer(cell.row)); } } if (rows.size() != 2) { return null; } List emptyCellsInLaser2 = getEmptyCellsInSquare(context, laser2); Iterator iter2 = emptyCellsInLaser2.iterator(); Set possibleCandidatesInLaser2 = getUnionOfCandidates(emptyCellsInLaser2); if (!possibleCandidatesInLaser2.contains(candidate)) { return null; } while (iter2.hasNext()) { Cell cell = (Cell) iter2.next(); if (cell.candidates.contains(candidate)) { rows.add(new Integer(cell.row)); } } if (rows.size() != 2) { return null; } List emptyCellsInTarget = getEmptyCellsInSquare(context, target); Set possibleCandidatesInTarget = getUnionOfCandidates(emptyCellsInTarget); if (!possibleCandidatesInTarget.contains(candidate)) { return null; } Iterator iter3 = emptyCellsInTarget.iterator(); while (iter3.hasNext()) { Cell cell = (Cell) iter3.next(); if (cell.candidates.contains(candidate) && rows.contains(new Integer(cell.row))) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator iter4 = emptyCellsInLaser1.iterator(); while (iter4.hasNext()) { Cell tmp = (Cell) iter4.next(); if (tmp.candidates.contains(candidate)) { tmp.color = "yellow"; } } Iterator iter5 = emptyCellsInLaser2.iterator(); while (iter5.hasNext()) { Cell tmp = (Cell) iter5.next(); if (tmp.candidates.contains(candidate)) { tmp.color = "yellow"; } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(candidate); if (english) { display(context, candidate + " appears only as candidate in the 2 rows " + displaySetPlusOne(rows) + " in " + squareNo(laser1) + " and " + squareNo(laser2)); display(context, "Thus " + candidate + " is not a candidate in " + cell); } else { display(context, candidate + " optræder kun som kandidat i de 2 rækker " + displaySetPlusOne(rows) + " i " + squareNo(laser1) + " og " + squareNo(laser2)); display(context, "Derfor kan " + candidate + " fjernes som mulig værdi fra " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } return null; } private Cell reduceByDualLaser(Context context) { Cell cell; if ((cell = reduceByDualLaserInRows(context, 0, 1, 2)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 0, 2, 1)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 1, 2, 0)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 3, 4, 5)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 3, 5, 4)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 4, 5, 3)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 6, 7, 8)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 6, 8, 7)) != null) { return cell; } if ((cell = reduceByDualLaserInRows(context, 7, 8, 6)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 0, 3, 6)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 0, 6, 3)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 3, 6, 0)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 1, 4, 7)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 1, 7, 4)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 4, 7, 1)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 2, 5, 8)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 2, 8, 5)) != null) { return cell; } if ((cell = reduceByDualLaserInCols(context, 5, 8, 2)) != null) { return cell; } return null; } private Set getPermutationsOfSize(int k, List cells) { Set permutations = new HashSet(); if (k == 1) { for (int i = 0; i < cells.size(); i++) { Set permutation = new HashSet(); permutation.add(cells.get(i)); permutations.add(permutation); } } else { Set oneLess = getPermutationsOfSize(k - 1, cells); Iterator it = oneLess.iterator(); while (it.hasNext()) { Set permOneLess = (Set) it.next(); for (int i = 0; i < cells.size(); i++) { Set permutation = clone(permOneLess); permutation.add(cells.get(i)); if (permutation.size() == k) { permutations.add(permutation); } } } } return permutations; } private Cell reduceByCandidateCardinality(Context context, List cells, List all, String origin) { for (int i = 2; i < cells.size() - 1; i++) { Set permutations = getPermutationsOfSize(i, cells); Iterator it = permutations.iterator(); while (it.hasNext() && !context.reduced) { Set union = new HashSet(); Set permutation = (Set) it.next(); Iterator it1 = permutation.iterator(); while (it1.hasNext()) { Cell cell = (Cell) it1.next(); union.addAll(cell.candidates); } if (union.size() == permutation.size()) { for (int j = 0; j < cells.size(); j++) { Cell cell = (Cell) cells.get(j); clearBoardColors(context); Set test = clone(cell.candidates); if (!permutation.contains(cell) && test.removeAll(union)) { display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator it2 = permutation.iterator(); while (it2.hasNext()) { ((Cell) it2.next()).color = "yellow"; } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.removeAll(union); if (english) { display(context, "The " + permutation.size() + " positions " + permutation + " reserves together the " + union.size() + " candidates " + union); display(context, "Thus the values " + union + " are not candidates for " + cell + ", leaving only " + cell.candidates + " as candidates for " + cell); } else { display(context, "De " + permutation.size() + " positioner " + permutation + " beslaglægger tilsammen alle de " + union.size() + " mulige værdier " + union); display(context, "Derfor kan værdierne " + union + " ikke benyttes i " + cell + ", hvorefter kun " + cell.candidates + " er mulige værdier i " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } } return null; } private Set getCandidateCombinations(Set candidates) { Set combinations = new TreeSet(new Comparer()); if (candidates.size() == 1) { combinations.add(new TreeSet(new Comparer())); combinations.add(cloneTreeSet(candidates)); } else { Iterator it = candidates.iterator(); Integer firstCandidate = (Integer) it.next(); candidates.remove(firstCandidate); Set oneLess = getCandidateCombinations(candidates); it = oneLess.iterator(); while (it.hasNext()) { Set combOneLess = (Set) it.next(); Set s1 = clone(combOneLess); combinations.add(s1); Set s2 = clone(combOneLess); s2.add(firstCandidate); combinations.add(s2); } } return combinations; } private Cell reduceHidden(Context context, List cells, List all, String origin) { if (cells.size() < 4) { return null; } Set union = new HashSet(); for (int i = 0; i < cells.size(); i++) { Cell cell = (Cell) cells.get(i); union.addAll(cell.candidates); } Set permutations = getCandidateCombinations(clone(union)); Iterator it = permutations.iterator(); while (it.hasNext() && !context.reduced) { Set permutation = (Set) it.next(); Set hiddenIn = new HashSet(); if (permutation.size() > 1) { boolean possibleHidden = true; int completelyContained = 0; for (int i = 0; i < cells.size(); i++) { Cell cell = (Cell) cells.get(i); if (cell.candidates.containsAll(permutation)) { completelyContained++; hiddenIn.add(cell); continue; } Set tmp = clone(cell.candidates); if (permutation.containsAll(tmp) || tmp.removeAll(permutation)) { possibleHidden = false; break; } } if (possibleHidden && completelyContained == permutation.size()) { for (int j = 0; j < cells.size(); j++) { Cell cell = (Cell) cells.get(j); if (cell.candidates.containsAll(permutation) && cell.candidates.size() > permutation.size()) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { for (int k = 0; k < 9; k++) { ((Cell) all.get(k)).color = "yellow"; } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.retainAll(permutation); if (english) { display(context, "The " + permutation.size() + " candidates " + permutation + " are only candidates in " + origin + " in the " + hiddenIn.size() + " positions " + hiddenIn); display(context, "Thus other candidates in " + cell + " can be removed, leaving only " + cell.candidates + " as candidates for " + cell); } else { display(context, "De " + permutation.size() + " værdier " + permutation + " optræder kun som mulige værdier i " + origin + " i de " + hiddenIn.size() + " positioner " + hiddenIn); display(context, "Derfor kan andre mulige værdier udelukkes i " + cell + ", hvorefter kun " + cell.candidates + " er mulige værdier i " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } } return null; } private Cell reduceByLockedCandidateInIntersectionInRows(Context context) { Set all = new HashSet(); for (int i = 0; i < 9; i++) { all.add(new Integer(i)); } Set permutations = getCandidateCombinations(all); Iterator it1 = permutations.iterator(); while (it1.hasNext() && !context.reduced) { Set rows = (Set) it1.next(); if (rows.size() > 1 && rows.size() < 7) { for (int i = 1; i < 10; i++) { Integer singleCandidate = new Integer(i); Iterator it2 = rows.iterator(); Set possibleColumns = new HashSet(); boolean possible = true; while (it2.hasNext() && possible) { int row = ((Integer) it2.next()).intValue(); for (int j = 0; j < 9; j++) { if (context.board[row][j].value == singleCandidate.intValue()) { possible = false; } else if (context.board[row][j].value == 0 && context.board[row][j].candidates.contains(singleCandidate)) { possibleColumns.add(new Integer(j)); } } } if (possible && possibleColumns.size() == rows.size()) { Iterator it3 = possibleColumns.iterator(); while (it3.hasNext()) { int col = ((Integer) it3.next()).intValue(); for (int j = 0; j < 9; j++) { if (!rows.contains(new Integer(j)) && context.board[j][col].value == 0 && context.board[j][col].candidates.contains(singleCandidate)) { Cell cell = context.board[j][col]; clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator it6 = rows.iterator(); while (it6.hasNext()) { int irow = ((Integer) it6.next()).intValue(); for (int k = 0; k < 9; k++) { if (context.board[irow][k].value == 0 && context.board[irow][k].candidates.contains(singleCandidate)) { context.board[irow][k].color = "yellow"; } } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(singleCandidate); if (english) { display(context, "In the " + rows.size() + " rows " + displaySetPlusOne(rows) + " the candidate " + singleCandidate + " is only possible for the " + possibleColumns.size() + " columns " + displaySetPlusOne(possibleColumns)); display(context, "Thus " + singleCandidate + " is not a candidate for " + cell); } else { display(context, "I de " + rows.size() + " rækker " + displaySetPlusOne(rows) + " optræder " + singleCandidate + " kun som mulig værdi i de " + possibleColumns.size() + " søjler " + displaySetPlusOne(possibleColumns)); display(context, "Derfor kan " + singleCandidate + " ikke være en mulig værdi i " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } } } } return null; } private Cell reduceByLockedCandidateInIntersectionInColumns(Context context) { Set all = new HashSet(); for (int i = 0; i < 9; i++) { all.add(new Integer(i)); } Set permutations = getCandidateCombinations(all); Iterator it1 = permutations.iterator(); while (it1.hasNext() && !context.reduced) { Set cols = (Set) it1.next(); if (cols.size() > 1 && cols.size() < 7) { for (int i = 0; i < 9; i++) { Integer singleCandidate = new Integer(i); Iterator it2 = cols.iterator(); Set possibleRows = new HashSet(); boolean possible = true; while (it2.hasNext() && possible) { int col = ((Integer) it2.next()).intValue(); for (int j = 0; j < 9; j++) { if (context.board[j][col].value == singleCandidate.intValue()) { possible = false; } else if (context.board[j][col].value == 0 && context.board[j][col].candidates.contains(singleCandidate)) { possibleRows.add(new Integer(j)); } } } if (possible && possibleRows.size() == cols.size()) { Iterator it3 = possibleRows.iterator(); while (it3.hasNext()) { int row = ((Integer) it3.next()).intValue(); for (int j = 0; j < 9; j++) { if (!cols.contains(new Integer(j)) && context.board[row][j].value == 0 && context.board[row][j].candidates.contains(singleCandidate)) { Cell cell = context.board[row][j]; clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator it6 = cols.iterator(); while (it6.hasNext()) { int icol = ((Integer) it6.next()).intValue(); for (int k = 0; k < 9; k++) { if (context.board[k][icol].value == 0 && context.board[k][icol].candidates.contains(singleCandidate)) { context.board[k][icol].color = "yellow"; } } } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(singleCandidate); if (english) { display(context, "In the " + cols.size() + " columns " + displaySetPlusOne(cols) + " the candidate " + singleCandidate + " is only possible for the " + possibleRows.size() + " rows " + displaySetPlusOne(possibleRows)); display(context, "Thus " + singleCandidate + " is not a candidate for " + cell); } else { display(context, "I de " + cols.size() + " søjler " + displaySetPlusOne(cols) + " optræder " + singleCandidate + " kun som mulig værdi i de " + possibleRows.size() + " rækker " + displaySetPlusOne(possibleRows)); display(context, "Derfor kan " + singleCandidate + " ikke være en mulig værdi i " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } } } } } return null; } private Cell reduceByCandidateChain(Context context) { List twoCandidateCells = getEmptyCellsWithTwoCandidates(context); Iterator it1 = twoCandidateCells.iterator(); while (it1.hasNext()) { Cell cell = (Cell) it1.next(); List start = new ArrayList(); start.add(cell); Iterator it2 = cell.candidates.iterator(); Integer n1 = (Integer) it2.next(); Integer n2 = (Integer) it2.next(); Cell candidateCell; if ((candidateCell = tryCandidateChain(context, start, n1, n2, twoCandidateCells)) != null) { return candidateCell; } if ((candidateCell = tryCandidateChain(context, start, n2, n1, twoCandidateCells)) != null) { return candidateCell; } } return null; } private boolean lockingCells(Cell a, Cell b) { return a.row == b.row || a.col == b.col || a.square == b.square; } private void displayChain(Context context, List chain, Integer startNumber, Cell cell) { clearBoardColors(context); display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll || context.solveUntilInteresting) { Iterator it1 = chain.iterator(); while (it1.hasNext()) { Cell tmp = (Cell) it1.next(); tmp.color = "yellow"; } context.interesting = true; cell.color = "red"; displayBoard(context); } cell.candidates.remove(startNumber); if (english) { display(context, "The " + chain.size() + " positions " + chain + " locks as a chain the candidate " + startNumber); display(context, "Thus " + startNumber + " is not a possible value for " + cell); } else { display(context, "De " + chain.size() + " celler " + chain + " låser som kæde værdien " + startNumber); display(context, "Derfor kan " + startNumber + " ikke være en mulig værdi i " + cell); } context.reduced = true; if (!context.solveAll) { displayBoard(context); } } private Cell testChained(Context context, List chain, Integer startNumber) { Cell first = (Cell) chain.get(0); Cell head = (Cell) chain.get(chain.size() - 1); Cell cell = context.board[first.row][head.col]; if (cell.value == 0 && cell.candidates.contains(startNumber)) { displayChain(context, chain, startNumber, cell); if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } cell = context.board[head.row][first.col]; if (cell.value == 0 && cell.candidates.contains(startNumber)) { displayChain(context, chain, startNumber, cell); if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } if (first.square == head.square) { List emptyCellsInSquare = getEmptyCellsInSquare(context, first.square); for (int i = 0; i < emptyCellsInSquare.size(); i++) { cell = (Cell) emptyCellsInSquare.get(i); if (cell != first && cell != head && cell.candidates.contains(startNumber)) { displayChain(context, chain, startNumber, cell); if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } else { List emptyCellsInSquare = getEmptyCellsInSquare(context, first.square); for (int i = 0; i < emptyCellsInSquare.size(); i++) { cell = (Cell) emptyCellsInSquare.get(i); if (cell != first && (cell.col == head.col || cell.row == head.row) && cell != head && cell.candidates.contains(startNumber)) { displayChain(context, chain, startNumber, cell); if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } emptyCellsInSquare = getEmptyCellsInSquare(context, head.square); for (int i = 0; i < emptyCellsInSquare.size(); i++) { cell = (Cell) emptyCellsInSquare.get(i); if (cell != first && (cell.col == first.col || cell.row == first.row) && cell != first && cell.candidates.contains(startNumber)) { displayChain(context, chain, startNumber, cell); if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } } } } return null; } private Cell tryCandidateChain(Context context, List start, Integer startNumber, Integer chainNumber, List twoCandidateCells) { Cell first = (Cell) start.get(0); Cell head = (Cell) start.get(start.size() - 1); Iterator it1 = twoCandidateCells.iterator(); while (it1.hasNext()) { Cell next = (Cell) it1.next(); if (!start.contains(next) && lockingCells(head, next) && next.candidates.contains(chainNumber)) { Cell candidateCell; Set candidates = clone(next.candidates); candidates.remove(chainNumber); Iterator it2 = candidates.iterator(); Integer nextChainNumber = (Integer) it2.next(); start.add(next); if (!lockingCells(first, next) && candidates.contains(startNumber)) { // possible chain if ((candidateCell = testChained(context, start, startNumber)) != null) { return candidateCell; } } if ((candidateCell = tryCandidateChain(context, start, startNumber, nextChainNumber, twoCandidateCells)) != null) { return candidateCell; } start.remove(next); } } return null; } private Cell testForColour(Context context, List colouredCells, Integer candidate) { if (colouredCells.size() <= 2) { return null; } Cell head = (Cell) colouredCells.get(colouredCells.size() - 1); for (int i = 0; i < colouredCells.size() - 1; i++) { Cell other = (Cell) colouredCells.get(i); if (lockingCells(other, head) && other.color.equals(head.color)) { // conflict on actual colour - must be other for (int j = 0; j < colouredCells.size() - 1; j++) { Cell cell = (Cell) colouredCells.get(j); if (!cell.color.equals(head.color)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the same colour, thus the opposite colour must be correct in " + cell); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har samme farve og udelukker hinanden. Altså må den modsatte farve være den rigtige farve i " + cell); } if (!context.solveAll) { displayBoard(context); } cell.candidates = new HashSet(); cell.candidates.add(candidate); return cell; } } } if (!other.color.equals(head.color)) { // one of them is right. Candidate can be removed in locking points Cell cell = context.board[other.row][head.col]; if (!colouredCells.contains(cell) && cell.value == 0 && cell.candidates.contains(candidate)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); cell.color = "red"; displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the different colours.Thus the candidate " + candidate + " is not possible in the interjection " + cell); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har forskellig farve. Derfor kan " + candidate + " ikke optræde i krydspunktet " + cell); } cell.candidates.remove(candidate); context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } else { return null; } } cell = context.board[head.row][other.col]; if (!colouredCells.contains(cell) && cell.value == 0 && cell.candidates.contains(candidate)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); cell.color = "red"; displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the different colours.Thus the candidate " + candidate + " is not possible in the interjection " + cell); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har forskellig farve. Derfor kan " + candidate + " ikke optræde i krydspunkt " + cell); } cell.candidates.remove(candidate); context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } else { return null; } } if (other.square == head.square) { List emptyCellsInSquare = getEmptyCellsInSquare(context, other.square); for (int j = 0; j < emptyCellsInSquare.size(); j++) { cell = (Cell) emptyCellsInSquare.get(j); if (!colouredCells.contains(cell) && cell != head && cell.candidates.contains(candidate)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); cell.color = "red"; displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the different colours.Thus the candidate " + candidate + " is not possible " + cell + " as it is in the same square as " + other + " and" + head); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har forskellig farve. Derfor kan " + candidate + " ikke optræde i " + cell + " da det er i samme kvadrat som " + other + " og " + head); } cell.candidates.remove(candidate); context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } else { return null; } } } } else { // not same square List emptyCellsInSquare = getEmptyCellsInSquare(context, other.square); for (int j = 0; j < emptyCellsInSquare.size(); j++) { cell = (Cell) emptyCellsInSquare.get(j); if (!colouredCells.contains(cell) && (cell.row == head.row || cell.col == head.col) && cell != head && cell.candidates.contains(candidate)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); cell.color = "red"; displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the different colours.Thus the candidate " + candidate + " is not possible " + cell + " as it is in the same square as " + other + " and negates with " + head); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har forskellig farve. Derfor kan " + candidate + " ikke optræde i " + cell + " da det er i samme kvadrat som " + other + " og udelukker " + head); } cell.candidates.remove(candidate); context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } else { return null; } } } emptyCellsInSquare = getEmptyCellsInSquare(context, head.square); for (int j = 0; j < emptyCellsInSquare.size(); j++) { cell = (Cell) emptyCellsInSquare.get(j); if (!colouredCells.contains(cell) && (cell.row == other.row || cell.col == other.col) && cell != other && cell.candidates.contains(candidate)) { if (!context.solveAll) { display(context, ""); display(context, ""); display(context, ""); cell.color = "red"; displayBoard(context); context.interesting = true; } if (english) { display(context, "The coloured positions excludes pairwise the candidate " + candidate); display(context, other + " og " + head + " has the different colours.Thus the candidate " + candidate + " is not possible " + cell + " as it is in the same square as " + head + " and negates with " + other); } else { display(context, "De farvede celler udelukker parvist hinanden for kandidaten " + candidate); display(context, other + " og " + head + " har forskellig farve. Derfor kan " + candidate + " ikke optræde i " + cell + " da det er i samme kvadrat som " + head + " og udelukker " + other); } cell.candidates.remove(candidate); context.reduced = true; if (!context.solveAll) { displayBoard(context); } if (cell.candidates.size() == 1) { if (english) { display(context, "That leaves only one candidate for " + cell + ":" + cell.candidates.toArray()[0]); } else { display(context, "Herefter er der kun en mulig værdi for " + cell + ":" + cell.candidates.toArray()[0]); } return cell; } else { return null; } } } } } } return null; } private Cell colourPairs(Context context, List colouredCells, Integer candidate) { Cell head = (Cell) colouredCells.get(colouredCells.size() - 1); String nextColour = "green".equals(head.color) ? "yellow" : "green"; List list = getEmptyCellsInRow(context, head.row); int noOfCellsWithCandidate = 0; Cell next = null; for (int i = 0; i < list.size(); i++) { Cell cell = (Cell) list.get(i); if (!colouredCells.contains(cell) && cell.candidates.contains(candidate)) { noOfCellsWithCandidate++; next = cell; } } if (noOfCellsWithCandidate == 1) { next.color = nextColour; colouredCells.add(next); Cell cell = testForColour(context, colouredCells, candidate); if (context.reduced) { return cell; } cell = colourPairs(context, colouredCells, candidate); if (context.reduced) { return cell; } } list = getEmptyCellsInColumn(context, head.col); noOfCellsWithCandidate = 0; next = null; for (int i = 0; i < list.size(); i++) { Cell cell = (Cell) list.get(i); if (!colouredCells.contains(cell) && cell.candidates.contains(candidate)) { noOfCellsWithCandidate++; next = cell; } } if (noOfCellsWithCandidate == 1) { next.color = nextColour; colouredCells.add(next); Cell cell = testForColour(context, colouredCells, candidate); if (context.reduced) { return cell; } cell = colourPairs(context, colouredCells, candidate); if (context.reduced) { return cell; } } list = getEmptyCellsInSquare(context, head.square); noOfCellsWithCandidate = 0; next = null; for (int i = 0; i < list.size(); i++) { Cell cell = (Cell) list.get(i); if (!colouredCells.contains(cell) && cell.candidates.contains(candidate)) { noOfCellsWithCandidate++; next = cell; } } if (noOfCellsWithCandidate == 1) { next.color = nextColour; colouredCells.add(next); Cell cell = testForColour(context, colouredCells, candidate); if (context.reduced) { return cell; } cell = colourPairs(context, colouredCells, candidate); if (context.reduced) { return cell; } } return null; } private Cell reduceByColouring(Context context) { List emptyCells = getAllEmptyCells(context); for (int i = 0; i < emptyCells.size(); i++) { Cell emptyCell = (Cell) emptyCells.get(i); Iterator iterator = emptyCell.candidates.iterator(); while (iterator.hasNext()) { Integer candidate = (Integer) iterator.next(); clearBoardColors(context); emptyCell.color = "green"; List colouredCells = new ArrayList(); colouredCells.add(emptyCell); Cell cell = colourPairs(context, colouredCells, candidate); if (cell != null) { return cell; } } } clearBoardColors(context); return null; } private Cell testForSingleCandidate(Context context, List cells, List all, String origin) { for (int i = 0; i < cells.size(); i++) { Cell cell = (Cell) cells.get(i); Set possibleSingleCandidate = clone(cell.candidates); for (int j = 0; j < cells.size(); j++) { if (i != j) { possibleSingleCandidate.removeAll(((Cell) cells.get(j)).candidates); } } ; if (possibleSingleCandidate.size() == 1) { display(context, ""); display(context, ""); display(context, ""); if (!context.solveAll) { for (int k = 0; k < 9; k++) { ((Cell) all.get(k)).color = "yellow"; } displayBoard(context); } display(context, "I " + origin + " optræder " + possibleSingleCandidate + " kun som mulig værdi i " + cell); cell.candidates = possibleSingleCandidate; cell.color = "green"; return cell; } } return null; } private Set clone(Set set) { Set tmp = new HashSet(); Iterator it = set.iterator(); while (it.hasNext()) { tmp.add(it.next()); } return tmp; } private Set cloneTreeSet(Set set) { Set tmp = new TreeSet(new Comparer()); Iterator it = set.iterator(); while (it.hasNext()) { tmp.add(it.next()); } return tmp; } private List getEmptyCellsWithTwoCandidates(Context context) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (context.board[i][j].value == 0 && context.board[i][j].candidates.size() == 2) { tmp.add(context.board[i][j]); } } } return tmp; } private List getAllEmptyCells(Context context) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (context.board[i][j].value == 0) { tmp.add(context.board[i][j]); } } } return tmp; } private List getEmptyCellsInRow(Context context, int row) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { if (context.board[row][i].value == 0) { tmp.add(context.board[row][i]); } } return tmp; } private List getEmptyCellsInColumn(Context context, int col) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { if (context.board[i][col].value == 0) { tmp.add(context.board[i][col]); } } return tmp; } private List getEmptyCellsInSquare(Context context, int square) { int innesquarerow = square / 3; int innesquarecol = square % 3; List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { int row = (innesquarerow * 3) + i / 3; int col = (innesquarecol * 3) + i % 3; if (context.board[row][col].value == 0) { tmp.add(context.board[row][col]); } } return tmp; } private List getAllCellsInRow(Context context, int row) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { tmp.add(context.board[row][i]); } return tmp; } private List getAllCellsInColumn(Context context, int col) { List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { tmp.add(context.board[i][col]); } return tmp; } private List getAllCellsInSquare(Context context, int square) { int innesquarerow = square / 3; int innesquarecol = square % 3; List tmp = new ArrayList(); for (int i = 0; i < 9; i++) { int row = (innesquarerow * 3) + i / 3; int col = (innesquarecol * 3) + i % 3; tmp.add(context.board[row][col]); } return tmp; } private boolean validateBoard(Context context) { for (int i = 0; i < 9; i++) { List all = getAllCellsInRow(context, i); Set values = new HashSet(); for (int k = 0; k < 9; k++) { Cell cell = (Cell) all.get(k); if (cell.value == 0) { return false; } else { values.add(new Integer(cell.value)); } } if (values.size() != 9) { return false; } } for (int i = 0; i < 9; i++) { List all = getAllCellsInColumn(context, i); Set values = new HashSet(); for (int k = 0; k < 9; k++) { Cell cell = (Cell) all.get(k); if (cell.value == 0) { return false; } else { values.add(new Integer(cell.value)); } } if (values.size() != 9) { return false; } } for (int i = 0; i < 9; i++) { List all = getAllCellsInSquare(context, i); Set values = new HashSet(); for (int k = 0; k < 9; k++) { Cell cell = (Cell) all.get(k); if (cell.value == 0) { return false; } else { values.add(new Integer(cell.value)); } } if (values.size() != 9) { return false; } } return true; } private Set getCandidatesBySudokuRule(Context context, int row, int col) { Set candidates = new HashSet(); for (int i = 1; i <= 9; i++) { candidates.add(new Integer(i)); } int innesquarerow = row / 3; int innesquarecol = col / 3; for (int i = 0; i < 9; i++) { candidates.remove(new Integer(context.board[row][i].value)); candidates.remove(new Integer(context.board[i][col].value)); int irow = (innesquarerow * 3) + i / 3; int icol = (innesquarecol * 3) + i % 3; candidates.remove(new Integer(context.board[irow][icol].value)); } ; return candidates; } private void reduceBySudokuRule(Context context) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (context.board[i][j].value == 0) { context.board[i][j].candidates = getCandidatesBySudokuRule(context, i, j); } } } } private void solve(Context context) throws Exception { if (context.noOfSolutions >= 2) { return; } display(context, "
"); if (english) { display(context, "

Solving sudoku, " + context.remaining + " remaning

"); } else { display(context, "

Løser sudoku, mangler at udfylde " + context.remaining + " positioner

"); } context.recursions++; Cell next = getEmptyCellWithLeastCandidates(context); if (next.candidates.size() == 0) { if (english) { display(context, "Sudoku not solvable for " + next); } else { display(context, "Sudoku kan ikke løses for positionen " + next); } displayBoard(context); return; } else if (next.candidates.size() == 1) { context.deductions++; if (!context.solveAll || context.solveUntilInteresting) { java.util.Iterator it = next.candidates.iterator(); int value = ((Integer) it.next()).intValue(); context.jspWriter.println(""); next.value = value; context.remaining--; reduceBySudokuRule(context); if (!context.solveAll && context.interesting) { return; } } } else { if (!context.solveAll) { if (english) { display(context, "I'm out of ideas. Guess on a value in " + next + " from the possible candidates " + next.candidates); } else { display(context, "Jeg er vist løbet tør for ideer. Vælg en værdi i " + next + " med de mulige værdier " + next.candidates); } displayBoard(context); return; } else { if (english) { display(context, "I'm out of ideas. I'll try all values in " + next + " with the possible candidates " + next.candidates); } else { display(context, "Jeg er vist løbet tør for ideer. Jeg prøver alle værdier i " + next + " med de mulige værdier " + next.candidates); } displayBoard(context); } } java.util.Iterator it = next.candidates.iterator(); boolean firstIteraton = true; while (it.hasNext()) { if (!firstIteraton) { display(context, ""); if (english) { display(context, "

Back to position from before guessing

"); display(context, "

Solving sudoku, remaining " + context.remaining + " positiones

"); } else { display(context, "
Tilbage fra trial and error"); display(context, "

Løser sudoku, mangler at udfylde " + context.remaining + " positioner

"); } } else { firstIteraton = false; } next.value = ((Integer) it.next()).intValue(); context.remaining--; if (next.candidates.size() > 1) { if (english) { display(context, "Still missing " + context.remaining + " positiones, and more possibilities available"); display(context, "I'll try if " + next.value + " can be used in " + next + " with the candidates " + next.candidates); } else { display(context, "Der mangler at blive udfyldt " + context.remaining + " positioner, og der er flere muligheder for at fortsætte"); display(context, "Jeg prøver nu om " + next.value + " kan anvendes i " + next + " med de mulige værdier " + next.candidates); } context.jspWriter.flush(); reduceBySudokuRule(context); displayBoard(context); } if (context.remaining == 0) { displaySolution(context); context.noOfSolutions++; next.value = 0; context.remaining++; return; } else { solve(context); next.value = 0; context.remaining++; reduceBySudokuRule(context); } } return; } %> <% if ("ENGLISH".equals(request.getParameter("LANGUAGE"))) { english = true; session.setAttribute("LANGUAGE", "ENGLISH"); } else if ("DANISH".equals(request.getParameter("LANGUAGE"))) { english = false; session.setAttribute("LANGUAGE", "DANISH"); } else { english = "ENGLISH".equals(session.getAttribute("LANGUAGE")); } %> Sudoku

Sudoku

<%if (english) { %> Dansk version <% } else { %> English version <% } %>

<% out.print(""); out.println(""); for (int i = 0; i < 9; i++) { out.println(""); out.print(""); for (int j = 0; j < 9; j++) { out.print(""); if (j % 3 == 2) { out.print(""); } } out.println(""); if (i % 3 == 2) { out.print(""); out.println(""); } } %>

"); out.println("

"); out.print(""); out.println("

"); out.println("

<% if (english) { %> <% } else { %> <% } %>

<% long start = System.currentTimeMillis(); if (request.getParameter("SOLVE")!=null) { System.out.println("Peter " + request.getRemoteHost() + " -requestTime " + new Date(start) + " " + request.getParameter("SOLVE") + request.getParameter("INTEREST") + request.getParameter("NEXT") + request.getParameter("SHOW")); for (int i=0;i<9;i++) { for (int j=0;j<9;j++){ System.out.print(request.getParameter("CELL" + i + j) == null || request.getParameter("CELL" + i + j).length() == 0 ? "0" : request.getParameter("CELL" + i + j)); } System.out.println(); } } Context context = new Context(); context.noOfSolutions = 0; context.recursions = 0; context.deductions = 0; context.jspWriter = out; context.solveAll = false; context.solveUntilInteresting = false; context.interesting = false; if (request.getParameter("NEXT") != null) { context.interesting = true; } else { if (request.getParameter("INTEREST") != null) { context.solveUntilInteresting = true; } else { context.solveAll = true; } } if (request.getParameter("CELL00") != null) { context.board = new Cell[9][9]; context.remaining = 0; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { context.board[i][j] = new Cell(i, j, 0); if (request.getParameter("CELL" + i + j) != null && request.getParameter("CELL" + i + j).length() > 0) { try { context.board[i][j].value = Integer.parseInt(request.getParameter("CELL" + i + j)); } catch (Exception e) { } } else { context.remaining++; } } } if (context.remaining > 64) { if (english) { display(context, "

I need at least 17 values

"); } else { display(context, "

Der skal indtastes mindst 17 startværdier

"); } System.out.println("RequestTime " + start + " finished, executionTime " + (System.currentTimeMillis() - start) + " msek"); return; } if (context.remaining == 0) { if (english) { display(context, "

Sudoku solved

"); } else { display(context, "

Sudoku er løst

"); } displaySolution(context); if (validateBoard(context)) { if (english) { display(context, "

Solution verified

"); } else { display(context, "

Løsning er gyldig

"); } } else { if (english) { display(context, "

Solution not valid

"); } else { display(context, "

Løsning er ikke gyldig

"); } } System.out.println("RequestTime " + start + " finished, executionTime " + (System.currentTimeMillis() - start) + " msek"); return; } reduceBySudokuRule(context); if (request.getParameter("SHOW") != null) { displayBoard(context); } else { if (!context.solveAll) { reduceBySudokuRule(context); } try { solve(context); } catch (Exception e) { display(context, "Fejl " + e.getMessage()); } if (context.solveAll) { display(context, ""); if (english) { display(context, "Result"); } else { display(context, "Resultat"); } display(context, ""); if (context.noOfSolutions == 0) { if (english) { display(context, "

Sudoku not solvable

"); } else { display(context, "

Sudoku kan ikke løses

"); } } else { if (context.noOfSolutions == 1) { if (english) { display(context, "Found one unique solution"); } else { display(context, "Der er fundet en entydig løsning"); } } else { if (english) { display(context, "

Found more than 1 solution - not solving exhaustive

"); } else { display(context, "

Der er fundet mere end 1 løsning - finder ikke alle løsninger

"); } System.out.println("More than 1 solution"); } } } if (english) { display(context, "Time: " + (System.currentTimeMillis() - start) + " millisekunder"); } else { display(context, "Tid: " + (System.currentTimeMillis() - start) + " millisekunder"); } } } if (request.getParameter("SOLVE")!=null) { System.out.println("RequestTime " + new Date(start) + " finished, executionTime " + (System.currentTimeMillis() - start) + " msek"); } %>