Inital commitHEADmaster

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