| Why remove all the other values one by one when we know what to assign? |
|---|
def assign(values, s, d):
"Eliminate all the other values (except d) from values[s] and propagate."
if all(eliminate(values, s, d2) for d2 in values[s] if d2 != d):
return values
else:
return False
|
Another aspect of Peter's solution I found obscure was the code at the very end of his eliminate function. It didn't seem to have anything to do with eliminating the value that was being passed in. After studying this code, I realized that he was using a two-pronged approach to propagating constraints.
| What does the code at the end have to do with eliminating d from s? |
|---|
def eliminate(values, s, d):
##Eliminate d from values[s]; propagate when values or places <= 2.
if d not in values[s]:
return values ## Already eliminated
values[s] = values[s].replace(d,'')
if len(values[s]) == 0:
return False ## Contradiction: removed last value
elif len(values[s]) == 1:
## If there is only one value (d2) left in square, remove it from peers
d2, = values[s]
if not all(eliminate(values, s2, d2) for s2 in peers[s]):
return False
## Now check the places where d appears in the units of s
for u in units[s]:
dplaces = [s for s in u if d in values[s]]
if len(dplaces) == 0:
return False
elif len(dplaces) == 1:
# d can only be in one place in unit; assign it there
if not assign(values, dplaces[0], d):
return False
return values
|
The first prong takes each of the known values and assigns them to their respective boxes. As each value is assigned, it is removed as a possibility from its peers. If this in turn solves a box, then that value is assigned in turn, and so on. That's the first prong. The second prong of his constraint-propagation is in the code tucked away at the bottom of the eliminate function. This code looks for unsolved boxes and checks to see if any have a possible value that has been removed from all of the peers in at least one of its units. Say a given box has 1, 3 and 7 as possible values, but one of its units doesn't have 3 as a possible value anywhere else, then that box must hold a 3. I decided to implement the same algorithm Peter was using, but I wanted my code to be more intent-revealing. Instead of mutually recursive assign and eliminate functions, I chose an iterative approach. First I would push all known values as far as I could. Next I would look for uniquely constrained values, all in a loop. Having envisioned the overall goal, I took a step back and began writing tests. I found this approach helped me to define the code as clearly as possible, and overall I am fairly happy with the result. I enjoyed the process of using TDD to solve this problem. Writing the code one test at a time enabled me to do quite a bit of refactoring as I was going along. My solution at the end of this process is below (note that you can pretty much understand exactly how the solution works just by following the tests). By the way, the second part of the constraint propagation does not seem to improve the speed with which puzzles are solved to a great extent, so you can comment out the line below from my code without a noticeable delay. On the other hand, trying to do just a search without any constraint propagation seems to slow things down to a crawl. I allowed the program to run in this configuration for about 5 minutes and was unable to solve the puzzle in 'testSolveWithDepthFirstSearch'. Arguably the only insight required to write a reasonably quick sudoku solver is to remove known values from peers and then do a search if that isn't enough.
| This line can be removed without a very noticeable slowdown |
|---|
setSolvedBoxesInPuzzle(getUniquelySpecifiedBoxes()); |
Incidentally, while I have criticized Peter's code a little, I would like to make it clear that I have nothing but appreciation for Peter putting up his program on the Web. Even though I found a few things confusing, overall it was very helpful to me in writing my own implementation. I don't know much about this kind of stuff and I enjoyed learning a little about Sudoku, Python, AI and general programming by reading Peter's code. In fact, I think his code is quite interesting in the way he uses strings and maps as data structures along with functions like cross and zip to very quickly dispense with the basic housekeeping details of representing sudoku. I noted after I had finished developing my solution that I spend a lot more code on these matters than Peter does. For me personally, TDD was helpful in reaching a working solution. I do think TDD helps to break code down into smaller intention-revealing classes and functions, and this improves overall readability and maintainability.
Feel free to let me know what you think!
package test.sudoku;
import java.util.Arrays;
import java.util.List;
import junit.framework.TestCase;
import src.sudoku.Box;
import src.sudoku.DuplicateBoxesWithSameSolutionException;
import src.sudoku.Puzzle;
public class TestSudoku extends TestCase {
public static void main(String[] args) {
new TestSudoku().testSolveWithDepthFirstSearch();
}
public void testInitialize_Null() {
String initialState = null;
try {
Puzzle solver = new Puzzle(initialState);
fail("should fail");
} catch (RuntimeException e) {
assertEquals("empty input", e.getMessage());
}
}
public void testInitialize_Empty() {
String initialState = "";
try {
Puzzle puzzle = new Puzzle(initialState);
fail("should fail");
} catch (RuntimeException e) {
assertEquals("empty input", e.getMessage());
}
}
public void testInitialize_NotSquare() {
String initialState = "......";
try {
Puzzle puzzle = new Puzzle(initialState);
fail("should fail");
} catch (RuntimeException e) {
assertEquals("invalid input length: 6", e.getMessage());
}
}
public void testInitialize_NoSeededValues() {
String initialState = "....";
Puzzle puzzle = new Puzzle(initialState);
assertEquals(2, puzzle.dimension());
assertEquals(0, puzzle.getSolvedBoxes().size());
}
public void testInitialize_NoSeededValues_Zeros() {
String initialState = "0000";
Puzzle puzzle = new Puzzle(initialState);
assertEquals(2, puzzle.dimension());
assertEquals(0, puzzle.getSolvedBoxes().size());
}
public void testInitialize_NoSeededValues_Dashes() {
String initialState = "----";
Puzzle puzzle = new Puzzle(initialState);
assertEquals(2, puzzle.dimension());
assertEquals(0, puzzle.getSolvedBoxes().size());
}
public void testSolvedValues() {
String initialState = "1234";
Puzzle puzzle = new Puzzle(initialState);
assertEquals(2, puzzle.dimension());
assertEquals(4, puzzle.getSolvedBoxes().size());
assertEquals(1, puzzle.getSolvedValue(0, 0));
assertEquals(2, puzzle.getSolvedValue(0, 1));
assertEquals(3, puzzle.getSolvedValue(1, 0));
assertEquals(4, puzzle.getSolvedValue(1, 1));
}
public void testSolvedValues_SomeValuesMissing() {
String initialState = ".2.4";
Puzzle puzzle = new Puzzle(initialState);
assertEquals(2, puzzle.dimension());
assertEquals(2, puzzle.getSolvedBoxes().size());
assertEquals(2, puzzle.getSolvedValue(0, 1));
assertEquals(4, puzzle.getSolvedValue(1, 1));
}
public void testSolvedValue_Error() {
String initialState = ".2.4";
Puzzle puzzle = new Puzzle(initialState);
try {
puzzle.getSolvedValue(0, 0);
fail("should fail");
} catch (RuntimeException e) {
assertEquals("box: 0, 0 has not been solved", e.getMessage());
}
}
public void testPossibleValues_Tiny() {
Puzzle puzzle = new Puzzle("....");
assertPossibleValues(new int[] { 1, 2 }, puzzle.getPossibleValues(0, 0));
assertPossibleValues(new int[] { 1, 2 }, puzzle.getPossibleValues(0, 1));
assertPossibleValues(new int[] { 1, 2 }, puzzle.getPossibleValues(1, 0));
assertPossibleValues(new int[] { 1, 2 }, puzzle.getPossibleValues(1, 1));
}
public void testPossibleValues_InitiateBoxState() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(5, 6));
}
public void testGetPeers_Unit1() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
List<Box> peers = puzzle.getPeers(0, 0);
assertEquals(20, peers.size());
assertPeer(peers, 0, 1);
assertPeer(peers, 0, 2);
assertPeer(peers, 0, 3);
assertPeer(peers, 0, 4);
assertPeer(peers, 0, 5);
assertPeer(peers, 0, 6);
assertPeer(peers, 0, 7);
assertPeer(peers, 0, 8);
assertPeer(peers, 1, 0);
assertPeer(peers, 2, 0);
assertPeer(peers, 3, 0);
assertPeer(peers, 4, 0);
assertPeer(peers, 5, 0);
assertPeer(peers, 6, 0);
assertPeer(peers, 7, 0);
assertPeer(peers, 8, 0);
assertPeer(peers, 1, 1);
assertPeer(peers, 1, 2);
assertPeer(peers, 2, 1);
assertPeer(peers, 2, 2);
}
public void testGetPeers_Unit6() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
List<Box> peers = puzzle.getPeers(7, 6);
assertEquals(20, peers.size());
assertPeer(peers, 7, 0);
assertPeer(peers, 7, 1);
assertPeer(peers, 7, 2);
assertPeer(peers, 7, 3);
assertPeer(peers, 7, 4);
assertPeer(peers, 7, 5);
assertPeer(peers, 7, 7);
assertPeer(peers, 7, 8);
assertPeer(peers, 0, 6);
assertPeer(peers, 1, 6);
assertPeer(peers, 2, 6);
assertPeer(peers, 3, 6);
assertPeer(peers, 4, 6);
assertPeer(peers, 5, 6);
assertPeer(peers, 6, 6);
assertPeer(peers, 8, 6);
assertPeer(peers, 6, 7);
assertPeer(peers, 6, 8);
assertPeer(peers, 8, 7);
assertPeer(peers, 8, 8);
}
public void testGetPeersInSameRow() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
List<Box> peers = puzzle.getPeersInSameRow(3, 3);
assertEquals(8, peers.size());
assertPeer(peers, 3, 0);
assertPeer(peers, 3, 1);
assertPeer(peers, 3, 2);
assertPeer(peers, 3, 4);
assertPeer(peers, 3, 5);
assertPeer(peers, 3, 6);
assertPeer(peers, 3, 7);
assertPeer(peers, 3, 8);
}
public void testGetPeersInSameColumn() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
List<Box> peers = puzzle.getPeersInSameColumn(3, 4);
assertEquals(8, peers.size());
assertPeer(peers, 0, 4);
assertPeer(peers, 1, 4);
assertPeer(peers, 2, 4);
assertPeer(peers, 4, 4);
assertPeer(peers, 5, 4);
assertPeer(peers, 6, 4);
assertPeer(peers, 7, 4);
assertPeer(peers, 8, 4);
}
public void testGetPeersInSameSubSquare() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
List<Box> peers = puzzle.getPeersInSameSubSquare(3, 4);
assertEquals(8, peers.size());
assertPeer(peers, 3, 3);
assertPeer(peers, 3, 5);
assertPeer(peers, 4, 3);
assertPeer(peers, 4, 4);
assertPeer(peers, 4, 5);
assertPeer(peers, 5, 3);
assertPeer(peers, 5, 4);
assertPeer(peers, 5, 5);
}
private void assertPeer(List<Box> peers, int rowIndex, int columnIndex) {
for (Box box : peers)
if (box.row() == rowIndex && box.column() == columnIndex)
return;
fail("unable to find peer at " + rowIndex + ", " + columnIndex);
}
public void testFindBoxesConstrainedToOnePossibleValue_Row() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
puzzle.getBox(2, 0).copyPossibleValues(Arrays.asList(new Integer[] { 1 }));
puzzle.getBox(2, 1).copyPossibleValues(Arrays.asList(new Integer[] { 2 }));
puzzle.getBox(2, 3).copyPossibleValues(Arrays.asList(new Integer[] { 3 }));
puzzle.getBox(2, 4).copyPossibleValues(Arrays.asList(new Integer[] { 4 }));
puzzle.getBox(2, 5).copyPossibleValues(Arrays.asList(new Integer[] { 5 }));
puzzle.getBox(2, 6).copyPossibleValues(Arrays.asList(new Integer[] { 6 }));
puzzle.getBox(2, 7).copyPossibleValues(Arrays.asList(new Integer[] { 7 }));
puzzle.getBox(2, 8).copyPossibleValues(Arrays.asList(new Integer[] { 8 }));
List<Box> uniquelySpecifiedBoxes = puzzle.getUniquelySpecifiedBoxes();
assertEquals(1, uniquelySpecifiedBoxes.size());
assertSolved(uniquelySpecifiedBoxes.get(0), 2, 2, 9);
}
public void testFindBoxesConstrainedToOnePossibleValue_Column() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
puzzle.getBox(0, 2).copyPossibleValues(Arrays.asList(new Integer[] { 1 }));
puzzle.getBox(1, 2).copyPossibleValues(Arrays.asList(new Integer[] { 2 }));
puzzle.getBox(3, 2).copyPossibleValues(Arrays.asList(new Integer[] { 3 }));
puzzle.getBox(4, 2).copyPossibleValues(Arrays.asList(new Integer[] { 4 }));
puzzle.getBox(5, 2).copyPossibleValues(Arrays.asList(new Integer[] { 5 }));
puzzle.getBox(6, 2).copyPossibleValues(Arrays.asList(new Integer[] { 6 }));
puzzle.getBox(7, 2).copyPossibleValues(Arrays.asList(new Integer[] { 7 }));
puzzle.getBox(8, 2).copyPossibleValues(Arrays.asList(new Integer[] { 8 }));
List<Box> uniquelySpecifiedBoxes = puzzle.getUniquelySpecifiedBoxes();
assertEquals(1, uniquelySpecifiedBoxes.size());
assertSolved(uniquelySpecifiedBoxes.get(0), 2, 2, 9);
}
public void testFindBoxesConstrainedToOnePossibleValue_SubSquare() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
puzzle.getBox(0, 0).copyPossibleValues(Arrays.asList(new Integer[] { 1 }));
puzzle.getBox(0, 1).copyPossibleValues(Arrays.asList(new Integer[] { 2 }));
puzzle.getBox(0, 2).copyPossibleValues(Arrays.asList(new Integer[] { 3 }));
puzzle.getBox(1, 0).copyPossibleValues(Arrays.asList(new Integer[] { 4 }));
puzzle.getBox(1, 1).copyPossibleValues(Arrays.asList(new Integer[] { 5 }));
puzzle.getBox(1, 2).copyPossibleValues(Arrays.asList(new Integer[] { 6 }));
puzzle.getBox(2, 0).copyPossibleValues(Arrays.asList(new Integer[] { 7 }));
puzzle.getBox(2, 1).copyPossibleValues(Arrays.asList(new Integer[] { 8 }));
List<Box> uniquelySpecifiedBoxes = puzzle.getUniquelySpecifiedBoxes();
assertEquals(1, uniquelySpecifiedBoxes.size());
assertSolved(uniquelySpecifiedBoxes.get(0), 2, 2, 9);
}
public void testFindBoxesConstrainedToOnePossibleValue_NoUnitsHave9AsPossibleValue() {
Puzzle puzzle = new Puzzle(get81BlankBoxes());
setPossibleValues(puzzle, new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8 });
puzzle.getBox(2, 2).copyPossibleValues(Arrays.asList(new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }));
List<Box> uniquelySpecifiedBoxes = puzzle.getUniquelySpecifiedBoxes();
assertEquals(1, uniquelySpecifiedBoxes.size());
assertSolved(uniquelySpecifiedBoxes.get(0), 2, 2, 9);
}
private void setPossibleValues(Puzzle puzzle, Integer[] possibleValues) {
for (int rowIndex = 0; rowIndex < puzzle.dimension(); rowIndex++)
for (int columnIndex = 0; columnIndex < puzzle.dimension(); columnIndex++)
puzzle.getBox(rowIndex, columnIndex).copyPossibleValues(Arrays.asList(possibleValues));
}
private void assertSolved(Box box, int rowIndex, int columnIndex, int value) {
assertEquals(rowIndex, box.row());
assertEquals(columnIndex, box.column());
assertTrue("should be solved", box.isSolved());
assertEquals(value, box.getPossibleValues().get(0).intValue());
}
private String get81BlankBoxes() {
return ".................................................................................";
}
public void testRemoveSolvedValuesFromPeers() throws DuplicateBoxesWithSameSolutionException {
String row1 = ".1.......";
String row2 = ".........";
String row3 = ".........";
String row4 = ".........";
String row5 = ".........";
String row6 = ".........";
String row7 = ".........";
String row8 = ".........";
String row9 = ".........";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
puzzle.removeSolvedValuesFromPeers();
assertPossibleValues(new int[] { 1 }, puzzle.getPossibleValues(0, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 0));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 2));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(1, 0));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(1, 2));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(2, 0));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(2, 2));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 3));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 4));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 5));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 6));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 7));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(0, 8));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(1, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(2, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(3, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(4, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(5, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(6, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(7, 1));
assertPossibleValues(new int[] { 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(8, 1));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }, puzzle.getPossibleValues(1, 3));
}
public void testRemoveSolvedValuesFromPeers_NewSolvedValue() throws DuplicateBoxesWithSameSolutionException {
String row1 = ".1.......";
String row2 = ".2.......";
String row3 = ".3.......";
String row4 = ".4.......";
String row5 = ".5.......";
String row6 = ".6.......";
String row7 = ".7.......";
String row8 = ".........";
String row9 = ".9.......";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
puzzle.removeSolvedValuesFromPeers();
assertPossibleValues(new int[] { 8 }, puzzle.getPossibleValues(7, 1));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(6, 0));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(6, 2));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(7, 0));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(7, 2));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(8, 0));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6 }, puzzle.getPossibleValues(8, 2));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 3));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 4));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 5));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 6));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 7));
assertPossibleValues(new int[] { 1, 2, 3, 4, 5, 6, 7, 9 }, puzzle.getPossibleValues(7, 8));
assertPossibleValues(new int[] { 1 }, puzzle.getPossibleValues(0, 1));
assertPossibleValues(new int[] { 2 }, puzzle.getPossibleValues(1, 1));
assertPossibleValues(new int[] { 3 }, puzzle.getPossibleValues(2, 1));
assertPossibleValues(new int[] { 4 }, puzzle.getPossibleValues(3, 1));
assertPossibleValues(new int[] { 5 }, puzzle.getPossibleValues(4, 1));
assertPossibleValues(new int[] { 6 }, puzzle.getPossibleValues(5, 1));
}
private void assertPossibleValues(int[] expectedPossibleValues, Integer[] actualPossibleValues) {
assertEquals("same number of possible values", expectedPossibleValues.length, actualPossibleValues.length);
for (int i = 0; i < expectedPossibleValues.length; i++)
assertEquals("possible value at index " + i, expectedPossibleValues[i], actualPossibleValues[i].intValue());
}
public void testRemoveSolvedValuesFromPeers_ReachContradiction() {
String row1 = ".3.....3.";
String row2 = ".........";
String row3 = ".........";
String row4 = ".........";
String row5 = ".........";
String row6 = ".........";
String row7 = ".........";
String row8 = ".........";
String row9 = ".........";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
try {
puzzle.removeSolvedValuesFromPeers();
fail("should fail");
} catch (DuplicateBoxesWithSameSolutionException e) {
// good
}
}
public void testGetUnsolvedBoxes() {
String initialState = ".2.4";
Puzzle puzzle = new Puzzle(initialState);
List<Box> unsolvedBoxes = puzzle.getUnsolvedBoxes();
assertEquals(2, unsolvedBoxes.size());
assertEquals(0, unsolvedBoxes.get(0).row());
assertEquals(0, unsolvedBoxes.get(0).column());
assertEquals(1, unsolvedBoxes.get(1).row());
assertEquals(0, unsolvedBoxes.get(1).column());
}
public void testSolveByPropagatingKnownValues() throws DuplicateBoxesWithSameSolutionException {
String row1 = "..3.2.6..";
String row2 = "9..3.5..1";
String row3 = "..18.64..";
String row4 = "..81.29..";
String row5 = "7.......8";
String row6 = "..67.82..";
String row7 = "..26.95..";
String row8 = "8..2.3..9";
String row9 = "..5.1.3..";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
puzzle.removeSolvedValuesFromPeers();
assertTrue(puzzle.isSolved());
assertEquals("483921657" + "967345821" + "251876493" + "548132976" + "729564138" + "136798245" + "372689514"
+ "814253769" + "695417382", puzzle.solutionAsSingleString());
}
public void testPropagateConstraints_InsufficientToSolvePuzzle() throws DuplicateBoxesWithSameSolutionException {
String row1 = "4.....8.5";
String row2 = ".3.......";
String row3 = "...7.....";
String row4 = ".2.....6.";
String row5 = "....8.4..";
String row6 = "....1....";
String row7 = "...6.3.7.";
String row8 = "5..2.....";
String row9 = "1.4......";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
boolean solved = puzzle.propagateConstraints(puzzle);
assertFalse(solved);
assertRow(puzzle, 0, new String[] { "4", "1679", "12679", "139", "2369", "269", "8", "1239", "5" });
assertRow(puzzle, 1, new String[] { "26789", "3", "1256789", "14589", "24569", "245689", "12679", "1249",
"124679" });
assertRow(puzzle, 2, new String[] { "2689", "15689", "125689", "7", "234569", "245689", "12369", "12349",
"123469" });
assertRow(puzzle, 3, new String[] { "3789", "2", "15789", "3459", "34579", "4579", "13579", "6", "13789" });
assertRow(puzzle, 4, new String[] { "3679", "15679", "15679", "359", "8", "25679", "4", "12359", "12379" });
assertRow(puzzle, 5, new String[] { "36789", "4", "56789", "359", "1", "25679", "23579", "23589", "23789" });
assertRow(puzzle, 6, new String[] { "289", "89", "289", "6", "459", "3", "1259", "7", "12489" });
assertRow(puzzle, 7, new String[] { "5", "6789", "3", "2", "479", "1", "69", "489", "4689" });
assertRow(puzzle, 8, new String[] { "1", "6789", "4", "589", "579", "5789", "23569", "23589", "23689" });
}
private void assertRow(Puzzle puzzle, int rowIndex, String[] possibleValues) {
for (int columnIndex = 0; columnIndex < possibleValues.length; columnIndex++)
assertPossibleValues(possibleValues[columnIndex], puzzle.getBox(rowIndex, columnIndex));
}
private void assertPossibleValues(String expectedPossibleValues, Box box) {
assertEquals("same number of possible values", expectedPossibleValues.length(), box.numberOfPossibleValues());
String actualPossibleValues = "";
List<Integer> possibleValues = box.getPossibleValues();
for (int actualPossibleValue : possibleValues)
actualPossibleValues += actualPossibleValue;
assertEquals("possible values", expectedPossibleValues, actualPossibleValues);
}
public void testSolveWithDepthFirstSearch() {
String row1 = "4.....8.5";
String row2 = ".3.......";
String row3 = "...7.....";
String row4 = ".2.....6.";
String row5 = "....8.4..";
String row6 = "....1....";
String row7 = "...6.3.7.";
String row8 = "5..2.....";
String row9 = "1.4......";
Puzzle puzzle = new Puzzle(row1 + row2 + row3 + row4 + row5 + row6 + row7 + row8 + row9);
boolean solved = puzzle.solve();
assertTrue("should be solved", solved);
assertEquals("417369825" + "632158947" + "958724316" + "825437169" + "791586432" + "346912758" + "289643571"
+ "573291684" + "164875293", puzzle.solutionAsSingleString());
}
}
|
package src.sudoku;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Puzzle {
List<Box> solvedBoxes = new ArrayList<Box>();
private int dimension;
private Box[][] puzzle;
public Puzzle(String initialState) {
dimension = ((int) Math.sqrt(SudokuUtils.length(initialState)));
validateInputString(initialState);
solvedBoxes = parseSolvedBoxesFromInputString(initialState);
puzzle = initializePuzzle();
setSolvedBoxesInPuzzle(solvedBoxes);
}
public Puzzle(Puzzle anotherPuzzle, Box seededValue) {
dimension = anotherPuzzle.dimension;
solvedBoxes.add(seededValue);
puzzle = initializePuzzle();
copyPossibleValues(anotherPuzzle);
puzzle[seededValue.row()][seededValue.column()] = new Box(dimension, seededValue.row(), seededValue.column(),
seededValue.getSolvedValue());
}
public boolean solve() {
return solve(this);
}
/**
* first eliminate as many possibilities as possible by propagating
* constraints, then try searching.
*
* @param originalPuzzle
* contains the solution to the puzzle at the end
* @return true if this solves the puzzle; false otherwise
*/
public boolean solve(Puzzle originalPuzzle) {
try {
if (propagateConstraints(originalPuzzle))
return true;
} catch (DuplicateBoxesWithSameSolutionException e) {
return false;
}
return search(originalPuzzle);
}
/**
* start by removing all solved values as possibilities from peers. next
* find any boxes where a possible value does not match any possible values
* in at least one of its units, thus solving such boxes; remove these too
* from peers, and so on until this process is exhausted.
*
* @param originalPuzzle
* contains the solution to the puzzle at the end
* @return true if this solves the puzzle; false otherwise
* @throws DuplicateBoxesWithSameSolutionException
* if the same solution shows up in two boxes
*/
public boolean propagateConstraints(Puzzle originalPuzzle) throws DuplicateBoxesWithSameSolutionException {
do {
removeSolvedValuesFromPeers();
if (isSolved()) {
// puzzle has been solved. copy solution into original
originalPuzzle.copyPossibleValues(this);
return true;
}
setSolvedBoxesInPuzzle(getUniquelySpecifiedBoxes());
checkForDuplicates();
} while (solvedBoxes.size() > 0);
return false;
}
/**
* find the unsolved box with the smallest number of possible values. assume
* one of those values is correct and try solving the puzzle. if this
* doesn't work, try the next possible value, etc. until the puzzle is
* solved or all possible values are exhausted (in which case the puzzle
* cannot be solved).
*
* @param originalPuzzle
* contains the solution to the puzzle at the end
* @return true if this solves the puzzle; false otherwise
*/
public boolean search(Puzzle originalPuzzle) {
Box firstUnsolvedBox = min(getUnsolvedBoxes());
for (int possibleValue : firstUnsolvedBox.getPossibleValues()) {
Box seededValue = new Box(dimension(), firstUnsolvedBox.row(), firstUnsolvedBox.column(), possibleValue);
Puzzle copyOfPuzzle = new Puzzle(this, seededValue);
if (copyOfPuzzle.solve(originalPuzzle))
return true;
}
return false;
}
public void checkForDuplicates() throws DuplicateBoxesWithSameSolutionException {
for (int row = 0; row < dimension(); row++)
for (int column = 0; column < dimension(); column++)
if (getBox(row, column).anyPeerHasDuplicateSolvedValue(this))
throw new DuplicateBoxesWithSameSolutionException("reached contradiction");
}
public void removeSolvedValuesFromPeers() throws DuplicateBoxesWithSameSolutionException {
while (solvedBoxes.size() > 0) {
Box solvedBox = solvedBoxes.get(0);
solvedBoxes.addAll(solvedBox.removeSolvedValuesFromPeers(this));
solvedBoxes.remove(0);
}
}
public List<Box> getUniquelySpecifiedBoxes() {
Set<Box> uniquelySpecifiedBoxes = new HashSet<Box>();
for (Box unsolvedBox : getUnsolvedBoxes()) {
int matchFound = 0;
List<Integer> possibleValues = unsolvedBox.getPossibleValues();
for (Integer possibleValue : possibleValues)
for (List<Box> peers : unsolvedBox.getPeersPerUnit(this)) {
if (!doesPossibleValueAppearInAnyPeers(possibleValue, peers)) {
Box solvedBox = new Box(dimension(), unsolvedBox.row(), unsolvedBox.column(), possibleValue);
uniquelySpecifiedBoxes.add(solvedBox);
}
}
}
return new ArrayList<Box>(uniquelySpecifiedBoxes);
}
public List<Box> getUnsolvedBoxes() {
List<Box> unsolvedBoxes = new ArrayList<Box>();
for (int currentRow = 0; currentRow < dimension; currentRow++) {
for (int currentColumn = 0; currentColumn < dimension; currentColumn++) {
Box candidate = getBox(currentRow, currentColumn);
if (!candidate.isSolved())
unsolvedBoxes.add(candidate);
}
}
return unsolvedBoxes;
}
public int dimension() {
return dimension;
}
public List<Box> getSolvedBoxes() {
return solvedBoxes;
}
public int getSolvedValue(int row, int column) {
for (Box box : solvedBoxes) {
if (box.row() == row && box.column() == column)
return box.getSolvedValue();
}
throw new RuntimeException("box: " + row + ", " + column + " has not been solved");
}
public Integer[] getPossibleValues(int row, int column) {
List<Integer> possibleValues = getBox(row, column).getPossibleValues();
return possibleValues.toArray(new Integer[possibleValues.size()]);
}
public boolean isSolved() {
for (int currentRow = 0; currentRow < dimension; currentRow++) {
for (int currentColumn = 0; currentColumn < dimension; currentColumn++) {
Box candidate = getBox(currentRow, currentColumn);
if (!candidate.isSolved())
return false;
}
}
return true;
}
public List<Box> getPeers(int row, int column) {
return getBox(row, column).getPeers(this);
}
public List<Box> getPeersInSameRow(int row, int column) {
return getBox(row, column).getPeersInSameRow(this);
}
public List<Box> getPeersInSameColumn(int row, int column) {
return getBox(row, column).getPeersInSameColumn(this);
}
public List<Box> getPeersInSameSubSquare(int row, int column) {
return getBox(row, column).getPeersInSameSubSquare(this);
}
public Box getBox(int currentrow, int currentcolumn) {
return puzzle[currentrow][currentcolumn];
}
public String solutionAsSingleString() {
String solution = "";
for (int row = 0; row < dimension; row++)
for (int column = 0; column < dimension; column++)
solution += (puzzle[row][column].getSolvedValue());
return solution;
}
private Box min(List<Box> unsolvedBoxes) {
Box boxWithMinimumPossibleValues = null;
for (Box box : unsolvedBoxes) {
if (boxWithMinimumPossibleValues == null
|| box.numberOfPossibleValues() < boxWithMinimumPossibleValues.numberOfPossibleValues())
boxWithMinimumPossibleValues = box;
}
return boxWithMinimumPossibleValues;
}
private boolean doesPossibleValueAppearInAnyPeers(Integer possibleValue, List<Box> peers) {
for (Box peer : peers) {
if (peer.getPossibleValues().contains(possibleValue)) {
return true;
}
}
return false;
}
private void validateInputString(String initialState) {
if (SudokuUtils.isEmpty(initialState))
throw new RuntimeException("empty input");
if (dimension * dimension != SudokuUtils.length(initialState))
throw new RuntimeException("invalid input length: " + SudokuUtils.length(initialState));
}
private Box[][] initializePuzzle() {
Box[][] puzzle = new Box[dimension][dimension];
for (int row = 0; row < dimension; row++)
for (int column = 0; column < dimension; column++)
puzzle[row][column] = new Box(dimension, row, column);
return puzzle;
}
private List<Box> parseSolvedBoxesFromInputString(String initialState) {
List<Box> solvedBoxes = new ArrayList<Box>();
int row = 0;
int column = 0;
for (int i = 0; i < initialState.length(); i++) {
if (Character.isDigit(initialState.charAt(i)) && initialState.charAt(i) != '0') {
int currentValue = Character.getNumericValue(initialState.charAt(i));
Box box = new Box(dimension, row, column);
box.setValue(currentValue);
solvedBoxes.add(box);
}
column = ++column % dimension;
if (column == 0)
row++;
}
return solvedBoxes;
}
private void setSolvedBoxesInPuzzle(List<Box> solvedBoxes) {
this.solvedBoxes = solvedBoxes;
for (Box solvedBox : solvedBoxes)
puzzle[solvedBox.row()][solvedBox.column()] = solvedBox;
}
private void copyPossibleValues(Puzzle anotherPuzzle) {
for (int row = 0; row < dimension; row++) {
for (int column = 0; column < dimension; column++) {
Box box = getBox(row, column);
box.copyPossibleValues(anotherPuzzle.getBox(row, column).getPossibleValues());
}
}
}
}
|
package src.sudoku;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Box {
private List<Integer> possibleValues = new ArrayList<Integer>();
private int row;
private int column;
public Box(int puzzleDimension, int row, int column) {
setRowAndColumn(row, column);
for (int i = 0; i < puzzleDimension; i++)
possibleValues.add(i + 1);
}
public Box(int dimension, int row, int column, int possibleValue) {
setRowAndColumn(row, column);
possibleValues.add(possibleValue);
}
public int numberOfPossibleValues() {
return possibleValues.size();
}
public int row() {
return row;
}
public int column() {
return column;
}
public void setValue(int currentValue) {
possibleValues = new ArrayList<Integer>();
possibleValues.add(currentValue);
}
public void removePossibleValue(int valueToBeRemoved) {
for (int i = 0; i < possibleValues.size(); i++)
if (possibleValues.get(i).intValue() == valueToBeRemoved)
possibleValues.remove(i);
}
public int getSolvedValue() {
return possibleValues.get(0);
}
public boolean isSolved() {
return SudokuUtils.length(possibleValues) == 1;
}
public List<Integer> getPossibleValues() {
return possibleValues;
}
public void copyPossibleValues(List<Integer> possibleValues) {
this.possibleValues = new ArrayList<Integer>();
for (Integer possibleValue : possibleValues)
this.possibleValues.add(possibleValue);
}
public List<Box> getPeers(Puzzle puzzle) {
ArrayList<Box> peers = new ArrayList<Box>();
addUnique(peers, getPeersInSameRow(puzzle));
addUnique(peers, getPeersInSameColumn(puzzle));
addUnique(peers, getPeersInSameSubSquare(puzzle));
return peers;
}
public List<List<Box>> getPeersPerUnit(Puzzle puzzle) {
List<List<Box>> peersPerUnit = new ArrayList<List<Box>>();
peersPerUnit.add(getPeersInSameRow(puzzle));
peersPerUnit.add(getPeersInSameColumn(puzzle));
peersPerUnit.add(getPeersInSameSubSquare(puzzle));
return peersPerUnit;
}
public List<Box> getPeersInSameRow(Puzzle puzzle) {
ArrayList<Box> boxes = new ArrayList<Box>();
for (int currentcolumn = 0; currentcolumn < puzzle.dimension(); currentcolumn++)
boxes.add(puzzle.getBox(row(), currentcolumn));
boxes.remove(this);
return boxes;
}
public List<Box> getPeersInSameColumn(Puzzle puzzle) {
ArrayList<Box> boxes = new ArrayList<Box>();
for (int currentrow = 0; currentrow < puzzle.dimension(); currentrow++)
boxes.add(puzzle.getBox(currentrow, column()));
boxes.remove(this);
return boxes;
}
public List<Box> getPeersInSameSubSquare(Puzzle puzzle) {
List<Box> boxes = new ArrayList<Box>();
int subSquares = (int) Math.sqrt(puzzle.dimension());
int startingsSubSquareRow = (row() / subSquares) * subSquares;
int startingSubSquareColumn = (column() / subSquares) * subSquares;
int endingSubSquarerow = startingsSubSquareRow + subSquares;
int endingSubSquarecolumn = startingSubSquareColumn + subSquares;
for (int row = startingsSubSquareRow; row < endingSubSquarerow; row++)
for (int column = startingSubSquareColumn; column < endingSubSquarecolumn; column++)
boxes.add(puzzle.getBox(row, column));
boxes.remove(this);
return boxes;
}
public List<Box> removeSolvedValuesFromPeers(Puzzle puzzle) throws DuplicateBoxesWithSameSolutionException {
List<Box> newSolvedBoxes = new ArrayList<Box>();
List<Box> peers = getUnsolvedPeers(puzzle);
for (Box peer : peers) {
peer.removePossibleValue(getSolvedValue());
if (peer.isSolved())
newSolvedBoxes.add(peer);
}
puzzle.checkForDuplicates();
return newSolvedBoxes;
}
public List<Box> getUnsolvedPeers(Puzzle puzzle) {
List<Box> peers = getPeers(puzzle);
for (Iterator<Box> iter = peers.iterator(); iter.hasNext();) {
Box peer = iter.next();
if (peer.isSolved())
iter.remove();
}
return peers;
}
public boolean anyPeerHasDuplicateSolvedValue(Puzzle puzzle) {
List<Box> peers = getPeers(puzzle);
for (Box peer : peers) {
if (peer.hasSameSolvedValue(this)) {
return true;
}
}
return false;
}
public boolean equals(Object o) {
Box anotherBox = (Box) o;
return row == anotherBox.row && column == anotherBox.column;
}
public int hashCode() {
return ("" + row + "/" + column).hashCode();
}
public String toString() {
String asString = "" + row + ":" + column + "[";
for (int possibleValue : possibleValues) {
asString += possibleValue;
}
asString += "]";
return asString;
}
private boolean hasSameSolvedValue(Box box) {
if (!isSolved() || !box.isSolved())
return false;
return getSolvedValue() == box.getSolvedValue();
}
private void setRowAndColumn(int row, int column) {
this.row = row;
this.column = column;
}
private void addUnique(ArrayList<Box> peers, List<Box> peersInSameRow) {
for (Box peer : peersInSameRow)
if (!peers.contains(peer))
peers.add(peer);
}
}
|
package src.sudoku;
import java.util.List;
public class SudokuUtils {
public static int length(String str) {
return str == null ? 0 : str.length();
}
public static boolean isEmpty(String val) {
return val == null || val.equals("");
}
public static int length(List list) {
return list == null ? 0 : list.size();
}
}
|
package src.sudoku;
public class DuplicateBoxesWithSameSolutionException extends Exception {
public DuplicateBoxesWithSameSolutionException(String message) {
super(message);
}
}
|