diff options
Diffstat (limited to 'projects/project3_kenken/Solver.java')
| -rw-r--r-- | projects/project3_kenken/Solver.java | 173 |
1 files changed, 173 insertions, 0 deletions
diff --git a/projects/project3_kenken/Solver.java b/projects/project3_kenken/Solver.java new file mode 100644 index 0000000..ebdf950 --- /dev/null +++ b/projects/project3_kenken/Solver.java @@ -0,0 +1,173 @@ + + +public class Solver +{ + private int x; + private int y; + private KStack stack; + public Solver() + { + stack = new KStack(); + x = 0; + y = 0; + } + public void solve(KPuzzle puz) + { + puz.printPossibilities(); + boolean[] b = puz.getPossibilities(x,y); + int numlen = 0; + int lastplace = -1; + System.out.println("looking for possibility in (" + x + "," + y + ")"); + for(for int i = 0; i < b.length; i++) + { + if(ba) + { + numlen++; + lastplace = i; + } + } + if(numlen == 1) + { + imply(x,y,lastplace) + } + else + { + for(int i = 0; i < b.length; i++) + { + System.out.println("Scanning: " + (i+1) + " : " + b[i]); + if(b[i]) + { + guess(x,y,i+1); + puz.putNumber(x,y,i+1); + x++; + if(x > puz.size) + { + y++; + x = 0; + } + solve(puz); + int[] arr = stack.pop(); + puz.takeNumber(arr[1],arr[2]); + } + if(numlen == 0) + { + System.out.println("Exhausted possibilities, backtracking"); + return; + } + } + } + if(numlen == 1) + { + System.out.println("implying " + lastplace + " in (" + x + "," + y + ")"); + imply(x,y,lastplace); + puz.putNumber(x,y,lastplace); + } + else if(numlen == 0) + { + //Pop everything to the last guess + System.out.println("Found a cell with no possibilitys, backtracking"); + while(stack.peek()[0] == 1 && stack.getLength() > 1); + { + int[] arr = stack.pop(); + puz.removePossibility(arr[1],arr[2],arr[3]); + } + } + else + { + System.out.println("Guessing " + lastplace + " in (" + x + "," + y + ")"); + guess(x,y,lastplace); + puz.putNumber(x,y,lastplace); + b[lastplace] = false; + } + } + private void guess(int x, int y, int num) + { + int[] item = new int[4]; + item[0] = 1; + item[1] = x; + item[2] = y; + item[3] = num; + stack.push(item); + } + private void imply(int x, int y, int num) + { + int[] item = new int[4]; + item[0] = 0; + item[1] = x; + item[2] = y; + item[3] = num; + stack.push(item); + } + public class KStack + { + private KNode head; + private int length; + public KStack() + { + length = 0; + } + public int[] peek() + { + return head.getData(); + } + public int[] pop() + { + int[] output = head.getData(); + head = head.getNext(); + length--; + return output; + } + public void push(int[] i) + { + head = new KNode(i,head); + length++; + } + public boolean hasNext() + { + return head != null; + } + public int getLength() + { + return length; + } + public String toString() + { + String output = ""; + for(KNode tmp = head; tmp != null; tmp=tmp.getNext()) + { + output += tmp.getData() + " "; + } + return output; + } + /*public int[] toArray() + { + int[] output = new int[length]; + int i = length-1; + for(KNode tmp = head; tmp != null; tmp = tmp.getNext()) + { + output[i] = tmp.getData(); + i--; + } + return output; + }*/ + + } + public class KNode + { + private KNode next = null; + private int[] data; + public KNode(int[] d, KNode n) + { + data = d; + next = n; + } + public int[] getData() + { + return data; + } + public KNode getNext() + { + return next; + } + } +}
\ No newline at end of file |