diff options
Diffstat (limited to 'projects/project3_kenken/stab2/kenkensolver.java')
| -rw-r--r-- | projects/project3_kenken/stab2/kenkensolver.java | 141 |
1 files changed, 141 insertions, 0 deletions
diff --git a/projects/project3_kenken/stab2/kenkensolver.java b/projects/project3_kenken/stab2/kenkensolver.java new file mode 100644 index 0000000..dd36f5e --- /dev/null +++ b/projects/project3_kenken/stab2/kenkensolver.java @@ -0,0 +1,141 @@ +public class kenkensolver +{ + public static boolean done = false; + public static void main(String args[]) + { + Solver s = new Solver("3x3_1.txt"); + s.printPuzzle(); + KStack stack = new KStack(); + //int[][] implied = s.implyByRows(); + solve(s,stack); + System.out.println(); + s.printPuzzle(); + } + public static void solve(Solver s, KStack k) + { + System.out.println("Attempting to solve:"); + s.printArray(s.puzzle); + System.out.println("Stack is:"); + s.printArray(k.toArray()); + if(s.isSolved()) + { + System.out.println("Done!"); + done = true; + return; + } + else + { + int[][] rows = s.implyByRows(); + if(rows.length > 0) + { + //System.out.println("Implying by rows because imply returned "); + //s.printArray(rows); + for(int[] i : rows) + { + k.push(i); + } + solve(s,k); + return; + } + else + { + int[][] cols = s.implyByCols(); + if(cols.length > 0) + { + for(int[] i : cols) + { + k.push(i); + } + solve(s,k); + return; + } + else + { + int[][] cage = s.implyByCages(); + if(cage.length > 0) + { + for(int[] i : cage) + { + k.push(i); + } + solve(s,k); + return; + } + else + {//We have implyed by rows, cols, and cages, now we just have to guess. + //Fist, find the first(from top left) spot in the puzzle that's still 0 + int lastx = -1; + int lasty = -1; + search: + for(int x = 0; x < s.size; x++) + { + for(int y = 0; y < s.size;y++) + { + if(s.puzzle[x][y] == 0) + { + lastx = x; + lasty = y; + System.out.println("Attempting to guess number for (" + x + "," + y + ")"); + break search; + } + } + } + boolean[] possibilities = s.getPossibilities(lastx,lasty); + int numpossible = 0; + for(boolean b : possibilities) + { + if(b) + numpossible++; + } + if(numpossible > 0) + { + int[] guess = new int[4]; + for(int i = 0; i < possibilities.length && !done; i++) + { + System.out.println("Unable to imply a solution for (" + lastx + "," + lasty + ") guessing:"); + s.printArray(possibilities); + if(possibilities[i]) + { + if(i == possibilities.length-1) + { + guess[0] = 0; + } + else + { + guess[0] = 1; + } + guess[1] = lastx; + guess[2] = lasty; + guess[3] = i+1; + k.push(guess); + s.put(lastx,lasty,i+1); + solve(s,k); + } + } + } + else + { + //We have exhusted all possibilities for this square + System.out.println("\nExhausted possibilities.. backtracking\n"); + while(k.getLength() > 0 && k.peek()[0] == 0 && !done) //While implied stuff is still on top + { + int[] thisitem = k.pop(); + System.out.println("Removeing:"); + s.printArray(thisitem); + s.remove(thisitem[1],thisitem[2]); + } + //And pop the last guess + int[] lastguess = k.pop(); + System.out.println("Removeing:"); + s.printArray(lastguess); + s.remove(lastguess[1],lastguess[2]); + System.out.println("Done backtracking"); + return; + } + } + } + } + } + //System.out.println("Something has gone horribly wrong!"); + } +}
\ No newline at end of file |