Inital commitHEADmaster

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