diff options
Diffstat (limited to 'projects/project3_kenken')
95 files changed, 5041 insertions, 0 deletions
diff --git a/projects/project3_kenken/Cell.java b/projects/project3_kenken/Cell.java new file mode 100644 index 0000000..b9966cf --- /dev/null +++ b/projects/project3_kenken/Cell.java @@ -0,0 +1,30 @@ +public class Cell +{ + int x,y; + int num; + public Cell(int x, int y) + { + this.x = x; + this.y = y; + } + public int getX() + { + return x; + } + public int getY() + { + return y; + } + public void setNum(int num) + { + this.num = num; + } + public int getNum() + { + return num; + } + public String toString() + { + return "Cell:(" + x + "," + y + ")=" + num; + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/KCage.java b/projects/project3_kenken/KCage.java new file mode 100644 index 0000000..dc3642c --- /dev/null +++ b/projects/project3_kenken/KCage.java @@ -0,0 +1,200 @@ + +public class KCage +{ + Cell[] cells; + int targetnumber; + Operator operator; + public KCage() + { + + } + public KCage(int tn,Operator op,Cell[] c) + { + cells = c; + targetnumber = tn; + operator = op; + } + public int getNumCells() + { + return cells.length; + } + public int getTargNumber() + { + return targetnumber; + } + public Operator getOperator() + { + return operator; + } + public Cell getCell(int i) + { + return cells[i]; + } + public boolean[] getPossibilitiesForOthers(int num) + { + boolean[] output = new boolean[num]; + if(operator == Operator.MINUS) + { + for(int i = 1; i < num; i++) + { + for(int j = 1; j < num; j++) + { + if(i-j == targetnumber || j-i == targetnumber) + { + output[i] = true; + output[j] = true; + } + } + } + } + if(operator == Operator.DIVIDE) + { + for(int i = 1; i < num; i++) + { + for(int j = 1; j < num; j++) + { + if(i/(j*1.0) == targetnumber || j/(i*1.0) == targetnumber) + { + output[i] = true; + output[j] = true; + } + } + } + } + if(operator == Operator.PLUS) + { + for(int i = 0; i < num*cells.length; i++) + { + + } + int sum = 0; + for(Cell c : cells) + { + + } + } + return output; + } + public boolean test(int xn, int yn, int num) + { + for(Cell c : cells) + { + if(c.getX() == xn && c.getY() == yn) + { + if(operator == Operator.PLUS) + { + int sum = 0; + for(Cell c2 : cells) + { + sum += c2.getNum(); + } + sum += num; + if(sum == targetnumber) + { + return true; + } + else + { + return false; + } + } + else if(operator == Operator.MINUS) + { + Cell thiscell; + Cell thatcell; + if(c == cells[0]) + { + thiscell = cells[0]; + thatcell = cells[1]; + } + else + { + thatcell = cells[0]; + thiscell = cells[1]; + } + if(thiscell.getNum() == 0 || thatcell.getNum() == 0) + { + return true; + } + if(thatcell.getNum() - num == targetnumber || num - thatcell.getNum() == targetnumber) + { + return true; + } + else + { + return false; + } + } + else if(operator == Operator.MULTIPLY) + { + int product = 1; + for(Cell c2 : cells) + { + if(c2.getNum() != 0) + product *= c2.getNum(); + } + product *= num; + if(product <= targetnumber) + { + return true; + } + else + { + return false; + } + } + else if(operator == Operator.DIVIDE) + { + Cell thiscell; + Cell thatcell; + if(c == cells[0]) + { + thiscell = cells[0]; + thatcell = cells[1]; + } + else + { + thatcell = cells[0]; + thiscell = cells[1]; + } + if(thiscell.getNum() == 0 || thatcell.getNum() == 0) + { + return true; + } + if((thatcell.getNum()*1.0)/num == targetnumber || (num*1.0)/thatcell.getNum() == targetnumber) + { + return true; + } + else + { + return false; + } + } + else if(operator == Operator.NONE) + { + if(num == targetnumber) + { + return true; + } + else + { + return false; + } + } + } + } + return false; + } + public String toString() + { + String output = "Cage(" + targetnumber + "," + operator + "){\n\t\t"; + if(cells.length == 0) + return output+"}"; + output += cells[0]; + for(int i = 1; i < cells.length; i++) + { + output += ",\n\t\t"+cells[i]; + } + return output + "\n\t}"; + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/KPuzzle b/projects/project3_kenken/KPuzzle new file mode 100644 index 0000000..e29ee65 --- /dev/null +++ b/projects/project3_kenken/KPuzzle @@ -0,0 +1 @@ +public class KPuzzle
\ No newline at end of file diff --git a/projects/project3_kenken/KPuzzle.java b/projects/project3_kenken/KPuzzle.java new file mode 100644 index 0000000..41af390 --- /dev/null +++ b/projects/project3_kenken/KPuzzle.java @@ -0,0 +1,264 @@ +import java.util.Scanner; +import java.io.*; + +public class KPuzzle +{ + //a 2-d array of the cages, cages that are more than 1 square will have alieases on all of the squares. + KCage[] p;//The puzzle + int size; + boolean[] p2; //The possiblilities for every square - 3D + public KPuzzle() + { + + } + public KPuzzle(String filename) + { + parsePuzzle(filename); + makePossible(); + checkCages(); + } + private void checkCages() + { + for(int i = 0; i < p.length; i++) + { + KCage c = p[i]; + if(c.getNumCells() == 1) + { + Cell cell = c.getCell(0); + this.putNumber(cell.getX(),cell.getY(),c.getTargNumber()); + System.out.println("After putting " + c.getTargNumber() + " into (" + cell.getX() + "," + cell.getY() + ") Possibilities are:"); + this.printPossibilities(); + return; + } + } + } + public Cell getCell(int x, int y) + { + KCage k = p[y*size + x]; + for(int i = 0; i < k.getNumCells();i++) + { + Cell c = k.getCell(i); + if(c.getX() == x && c.getY() == y) + { + return c; + } + } + return null; + } + public boolean isComplete() + { + for(int i = 0; i < size; i++) + { + for(int j = 0; j < size; j++) + { + int possibilitiesForCell = 0; + for(int k = 0; k < size; k++) + { + if(p2[(i*size*size)+(j*size)+k]) + { + possibilitiesForCell++; + } + } + if(possibilitiesForCell != 1) + { + return false; + } + } + } + return true; + } + public boolean[] getPossibilities(int xn, int yn) + { + boolean[] output = new boolean[size]; + for(int i = 0; i < size; i++) + { + output[i] = p2[(yn*size*size)+(xn*size)+i]; + } + return output; + } + public void removePossibility(int xn, int yn, int num) + { + p2[(yn*size*size)+(xn*size)+num-1] = false; + } + public void addPossibility(int xn, int yn, int num) + { + p2[(yn*size*size)+(xn*size)+num-1] = true; + } + public void putNumber(int xn, int yn, int num) + { + System.out.println("putting " + num + " in (" + xn + "," + yn + ")"); + for(int y = 0; y < size; y++) + { + for(int z = 0; z < size; z++) + { + if(z == num-1) + { + //System.out.println("Setting (" + xn + "," + y + "," + z + ") to false"); + p2[(y*size*size)+(xn*size)+z] = false; + } + } + } + for(int x = 0; x < size; x++) + { + for(int z = 0; z < size; z++) + { + if(z == num-1) + p2[(yn*size*size)+(x*size)+z] = false; + } + } + for(int z = 0; z < size; z++) + { + p2[(yn*size*size)+(xn*size)+z] = false; + } + System.out.println("Setting (" + xn + "," + yn + "," + (num-1) + ") to true"); + p2[(yn*size*size)+(xn*size)+num-1] = true; + } + public void takeNumber(int xn, int yn) + { + int thisnum = -1; + for(int z = 0; z < size; z++) + { + if(p2[(yn*size*size)+(xn*size)+z]) + thisnum = z; + } + if(thisnum == -1) + { + System.out.println("I couldn't find a number there!"); + return; + } + for(int y = 0; y < size; y++) + { + for(int z = 0; z < size; z++) + { + if(z == thisnum) + { + System.out.println("Setting (" + xn + "," + y + "," + z + ") to true"); + p2[(y*size*size)+(xn*size)+z] = true; + } + } + } + for(int x = 0; x < size; x++) + { + for(int z = 0; z < size; z++) + { + if(z == thisnum) + p2[(yn*size*size)+(x*size)+z] = true; + } + } + for(int z = 0; z < size; z++) + { + p2[(yn*size*size)+(xn*size)+z] = true; + } + } + public void printPossibilities() + { + for(int y = 0; y < size; y++) + { + for(int x = 0; x < size; x++) + { + System.out.print("Possibilities for (" + x + "," + y + ") are: "); + for(int z = 0; z < size; z++) + { + if(p2[(y*size*size)+(x*size)+z]) + { + System.out.print(z+1); + } + } + System.out.println(""); + } + } + } + private void makePossible() + { + p2 = new boolean[size*size*size]; + //System.out.println("Makeing possibilities:"); + for(int i = 0; i < size; i++) + { + for(int j = 0; j < size; j++) + { + for(int k = 0; k < size; k++) + { + p2[(i*size*size)+(j*size)+k] = true; + //System.out.print(p2[(i*size*size)+(j*size)+k] + " "); + } + //System.out.print("\t"); + } + //System.out.println(""); + } + } + private void parsePuzzle(String filename) + { + Scanner s = null; + try + { + s = new Scanner(new FileInputStream(filename)); + } + catch (Exception e) + { + System.out.println("Something went terribly wrong!\n" + e); + } + size = Integer.parseInt(s.nextLine().replaceAll("\n","")); + p = new KCage[size*size]; + //System.out.println("Puzzle size: " + size + " Cages: " + p.length); + for(int i = 0; s.hasNextLine();i++) + { + String t1 = s.nextLine(); + //System.out.println("Praseing: " + t1); + String[] t2 = t1.split(","); + //System.out.println("Parts length: " + t2.length); + if(t2.length > 1) + { + Cell[] allcells = new Cell[Integer.parseInt(t2[2])]; + for(int j = 0; j < Integer.parseInt(t2[2]);j++) + { + String[] coords = s.nextLine().split(","); + allcells[j] = new Cell(Integer.parseInt(coords[0]),Integer.parseInt(coords[1])); + } + for(Cell c : allcells) + { + p[c.getY()*size + c.getX()] = new KCage(Integer.parseInt(t2[0]),getOp(t2[1]),allcells); + } + //p[i] = new KCage(Integer.parseInt(t2[0]),getOp(t2[1]),allcells); + //System.out.println("Created " + p[i]); + } + } + } + public KCage getCage(int i) + { + return p[i]; + } + public int getNumCages() + { + return p.length; + } + public String toString() + { + String output = "Puzzle{\n\t"; + if(p.length == 0) + return output+"}"; + output += p[0]; + for(int i = 1; i < p.length; i++) + { + output += ",\n\t"+p[i]; + } + return output + "\n}"; + } + private static Operator getOp(String s) + { + switch(s) + { + case "+": + return Operator.PLUS; + case "-": + return Operator.MINUS; + case "*": + return Operator.MULTIPLY; + case "/": + return Operator.DIVIDE; + case " ": + return Operator.NONE; + default: + return Operator.NULL; + } + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/Operator.java b/projects/project3_kenken/Operator.java new file mode 100644 index 0000000..5facf0e --- /dev/null +++ b/projects/project3_kenken/Operator.java @@ -0,0 +1,4 @@ +public enum Operator +{ + PLUS,MINUS,MULTIPLY,DIVIDE,NULL,NONE +}
\ No newline at end of file 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 diff --git a/projects/project3_kenken/images/3x3_1.jpg b/projects/project3_kenken/images/3x3_1.jpg Binary files differnew file mode 100644 index 0000000..764f9a3 --- /dev/null +++ b/projects/project3_kenken/images/3x3_1.jpg diff --git a/projects/project3_kenken/images/3x3_1_solution.jpg b/projects/project3_kenken/images/3x3_1_solution.jpg Binary files differnew file mode 100644 index 0000000..2514be0 --- /dev/null +++ b/projects/project3_kenken/images/3x3_1_solution.jpg diff --git a/projects/project3_kenken/images/3x3_2.jpg b/projects/project3_kenken/images/3x3_2.jpg Binary files differnew file mode 100644 index 0000000..c06f1d0 --- /dev/null +++ b/projects/project3_kenken/images/3x3_2.jpg diff --git a/projects/project3_kenken/images/3x3_2_solution.jpg b/projects/project3_kenken/images/3x3_2_solution.jpg Binary files differnew file mode 100644 index 0000000..0396e3f --- /dev/null +++ b/projects/project3_kenken/images/3x3_2_solution.jpg diff --git a/projects/project3_kenken/images/3x3_3.jpg b/projects/project3_kenken/images/3x3_3.jpg Binary files differnew file mode 100644 index 0000000..3dd4691 --- /dev/null +++ b/projects/project3_kenken/images/3x3_3.jpg diff --git a/projects/project3_kenken/images/3x3_3_solution.jpg b/projects/project3_kenken/images/3x3_3_solution.jpg Binary files differnew file mode 100644 index 0000000..5b3049c --- /dev/null +++ b/projects/project3_kenken/images/3x3_3_solution.jpg diff --git a/projects/project3_kenken/images/4x4_1.jpg b/projects/project3_kenken/images/4x4_1.jpg Binary files differnew file mode 100644 index 0000000..1a4d971 --- /dev/null +++ b/projects/project3_kenken/images/4x4_1.jpg diff --git a/projects/project3_kenken/images/4x4_1_solution.jpg b/projects/project3_kenken/images/4x4_1_solution.jpg Binary files differnew file mode 100644 index 0000000..fbdc213 --- /dev/null +++ b/projects/project3_kenken/images/4x4_1_solution.jpg diff --git a/projects/project3_kenken/images/4x4_2.jpg b/projects/project3_kenken/images/4x4_2.jpg Binary files differnew file mode 100644 index 0000000..60c64d3 --- /dev/null +++ b/projects/project3_kenken/images/4x4_2.jpg diff --git a/projects/project3_kenken/images/4x4_2_solution.jpg b/projects/project3_kenken/images/4x4_2_solution.jpg Binary files differnew file mode 100644 index 0000000..aa6e135 --- /dev/null +++ b/projects/project3_kenken/images/4x4_2_solution.jpg diff --git a/projects/project3_kenken/images/4x4_3.jpg b/projects/project3_kenken/images/4x4_3.jpg Binary files differnew file mode 100644 index 0000000..60076ec --- /dev/null +++ b/projects/project3_kenken/images/4x4_3.jpg diff --git a/projects/project3_kenken/images/4x4_3_solution.jpg b/projects/project3_kenken/images/4x4_3_solution.jpg Binary files differnew file mode 100644 index 0000000..85bd8c0 --- /dev/null +++ b/projects/project3_kenken/images/4x4_3_solution.jpg diff --git a/projects/project3_kenken/images/5x5_1.jpg b/projects/project3_kenken/images/5x5_1.jpg Binary files differnew file mode 100644 index 0000000..c9e7cb7 --- /dev/null +++ b/projects/project3_kenken/images/5x5_1.jpg diff --git a/projects/project3_kenken/images/5x5_1_solution.jpg b/projects/project3_kenken/images/5x5_1_solution.jpg Binary files differnew file mode 100644 index 0000000..5cefef4 --- /dev/null +++ b/projects/project3_kenken/images/5x5_1_solution.jpg diff --git a/projects/project3_kenken/images/5x5_2.jpg b/projects/project3_kenken/images/5x5_2.jpg Binary files differnew file mode 100644 index 0000000..4651465 --- /dev/null +++ b/projects/project3_kenken/images/5x5_2.jpg diff --git a/projects/project3_kenken/images/5x5_2_solution.jpg b/projects/project3_kenken/images/5x5_2_solution.jpg Binary files differnew file mode 100644 index 0000000..b8c71a5 --- /dev/null +++ b/projects/project3_kenken/images/5x5_2_solution.jpg diff --git a/projects/project3_kenken/images/5x5_3.jpg b/projects/project3_kenken/images/5x5_3.jpg Binary files differnew file mode 100644 index 0000000..cce77bb --- /dev/null +++ b/projects/project3_kenken/images/5x5_3.jpg diff --git a/projects/project3_kenken/images/5x5_3_solution.jpg b/projects/project3_kenken/images/5x5_3_solution.jpg Binary files differnew file mode 100644 index 0000000..64d90bd --- /dev/null +++ b/projects/project3_kenken/images/5x5_3_solution.jpg diff --git a/projects/project3_kenken/images/6x6_1.jpg b/projects/project3_kenken/images/6x6_1.jpg Binary files differnew file mode 100644 index 0000000..8f03d5c --- /dev/null +++ b/projects/project3_kenken/images/6x6_1.jpg diff --git a/projects/project3_kenken/images/6x6_1_solution.jpg b/projects/project3_kenken/images/6x6_1_solution.jpg Binary files differnew file mode 100644 index 0000000..1b9f1d1 --- /dev/null +++ b/projects/project3_kenken/images/6x6_1_solution.jpg diff --git a/projects/project3_kenken/images/6x6_2.jpg b/projects/project3_kenken/images/6x6_2.jpg Binary files differnew file mode 100644 index 0000000..2dad139 --- /dev/null +++ b/projects/project3_kenken/images/6x6_2.jpg diff --git a/projects/project3_kenken/images/6x6_2_solution.jpg b/projects/project3_kenken/images/6x6_2_solution.jpg Binary files differnew file mode 100644 index 0000000..e0c87e9 --- /dev/null +++ b/projects/project3_kenken/images/6x6_2_solution.jpg diff --git a/projects/project3_kenken/images/7x7_1.jpg b/projects/project3_kenken/images/7x7_1.jpg Binary files differnew file mode 100644 index 0000000..7ed98a0 --- /dev/null +++ b/projects/project3_kenken/images/7x7_1.jpg diff --git a/projects/project3_kenken/images/7x7_1_solution.jpg b/projects/project3_kenken/images/7x7_1_solution.jpg Binary files differnew file mode 100644 index 0000000..bec6b7a --- /dev/null +++ b/projects/project3_kenken/images/7x7_1_solution.jpg diff --git a/projects/project3_kenken/images/7x7_2.jpg b/projects/project3_kenken/images/7x7_2.jpg Binary files differnew file mode 100644 index 0000000..d3e7e3b --- /dev/null +++ b/projects/project3_kenken/images/7x7_2.jpg diff --git a/projects/project3_kenken/images/7x7_2_solution.jpg b/projects/project3_kenken/images/7x7_2_solution.jpg Binary files differnew file mode 100644 index 0000000..ed35a9b --- /dev/null +++ b/projects/project3_kenken/images/7x7_2_solution.jpg diff --git a/projects/project3_kenken/images/8x8_1.jpg b/projects/project3_kenken/images/8x8_1.jpg Binary files differnew file mode 100644 index 0000000..573259a --- /dev/null +++ b/projects/project3_kenken/images/8x8_1.jpg diff --git a/projects/project3_kenken/images/8x8_1_solution.jpg b/projects/project3_kenken/images/8x8_1_solution.jpg Binary files differnew file mode 100644 index 0000000..50d1d53 --- /dev/null +++ b/projects/project3_kenken/images/8x8_1_solution.jpg diff --git a/projects/project3_kenken/images/8x8_2.jpg b/projects/project3_kenken/images/8x8_2.jpg Binary files differnew file mode 100644 index 0000000..db8829a --- /dev/null +++ b/projects/project3_kenken/images/8x8_2.jpg diff --git a/projects/project3_kenken/images/8x8_2_solution.jpg b/projects/project3_kenken/images/8x8_2_solution.jpg Binary files differnew file mode 100644 index 0000000..ddd423d --- /dev/null +++ b/projects/project3_kenken/images/8x8_2_solution.jpg diff --git a/projects/project3_kenken/images/9x9_1.jpg b/projects/project3_kenken/images/9x9_1.jpg Binary files differnew file mode 100644 index 0000000..bda6fb8 --- /dev/null +++ b/projects/project3_kenken/images/9x9_1.jpg diff --git a/projects/project3_kenken/images/9x9_1_solution.jpg b/projects/project3_kenken/images/9x9_1_solution.jpg Binary files differnew file mode 100644 index 0000000..c20f72f --- /dev/null +++ b/projects/project3_kenken/images/9x9_1_solution.jpg diff --git a/projects/project3_kenken/images/9x9_2.jpg b/projects/project3_kenken/images/9x9_2.jpg Binary files differnew file mode 100644 index 0000000..53c8b10 --- /dev/null +++ b/projects/project3_kenken/images/9x9_2.jpg diff --git a/projects/project3_kenken/images/9x9_2_solution.jpg b/projects/project3_kenken/images/9x9_2_solution.jpg Binary files differnew file mode 100644 index 0000000..0b41dad --- /dev/null +++ b/projects/project3_kenken/images/9x9_2_solution.jpg diff --git a/projects/project3_kenken/images/9x9_3.jpg b/projects/project3_kenken/images/9x9_3.jpg Binary files differnew file mode 100644 index 0000000..82d231b --- /dev/null +++ b/projects/project3_kenken/images/9x9_3.jpg diff --git a/projects/project3_kenken/images/9x9_3_solution.jpg b/projects/project3_kenken/images/9x9_3_solution.jpg Binary files differnew file mode 100644 index 0000000..638f2bd --- /dev/null +++ b/projects/project3_kenken/images/9x9_3_solution.jpg diff --git a/projects/project3_kenken/kenkensolver.java b/projects/project3_kenken/kenkensolver.java new file mode 100644 index 0000000..8a8e70c --- /dev/null +++ b/projects/project3_kenken/kenkensolver.java @@ -0,0 +1,14 @@ +public class kenkensolver +{ + public static void main(String[] args) + { + KPuzzle p = new KPuzzle("./puzzle_files/3x3_3.txt"); + //System.out.println("Puzzle is: " + p); + //p.takeNumber(0,0); + System.out.println("\n\n\n"); + Solver s = new Solver(); + //p.printPossibilities(); + //stack = new KStack(); + s.solve(p); + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/project3_kenken.pdf b/projects/project3_kenken/project3_kenken.pdf Binary files differnew file mode 100644 index 0000000..8ec834e --- /dev/null +++ b/projects/project3_kenken/project3_kenken.pdf diff --git a/projects/project3_kenken/puzzle_files/3x3_1.txt b/projects/project3_kenken/puzzle_files/3x3_1.txt new file mode 100644 index 0000000..b23e027 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/3x3_1.txt @@ -0,0 +1,17 @@ +3 +5 +3, ,1 +0,0 +6,*,2 +0,1 +1,1 +2,/,2 +0,2 +1,2 +2,/,2 +1,0 +2,0 +2,-,2 +2,1 +2,2 + diff --git a/projects/project3_kenken/puzzle_files/3x3_2.txt b/projects/project3_kenken/puzzle_files/3x3_2.txt new file mode 100644 index 0000000..2556aa6 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/3x3_2.txt @@ -0,0 +1,17 @@ +3 +5 +2, ,1 +0,0 +9,*,3 +0,1 +0,2 +1,2 +2,-,2 +1,0 +2,0 +2,/,2 +1,1 +2,1 +2, ,1 +2,2 + diff --git a/projects/project3_kenken/puzzle_files/3x3_3.txt b/projects/project3_kenken/puzzle_files/3x3_3.txt new file mode 100644 index 0000000..a844c5b --- /dev/null +++ b/projects/project3_kenken/puzzle_files/3x3_3.txt @@ -0,0 +1,17 @@ +3 +5 +1,-,2 +0,1 +0,2 +2,-,2 +0,0 +1,0 +2, ,1 +1,1 +3,+,2 +2,0 +2,1 +3,/,2 +1,2 +2,2 + diff --git a/projects/project3_kenken/puzzle_files/4x4_1.txt b/projects/project3_kenken/puzzle_files/4x4_1.txt new file mode 100644 index 0000000..fcd1e9b --- /dev/null +++ b/projects/project3_kenken/puzzle_files/4x4_1.txt @@ -0,0 +1,27 @@ +4 +8 +1,-,2 +0,0 +0,1 +1,-,2 +0,2 +1,2 +7,+,2 +1,0 +2,0 +2,/,2 +1,1 +2,1 +8,*,3 +0,3 +1,3 +2,3 +3,-,2 +3,0 +3,1 +2,/,2 +2,2 +3,2 +3, ,1 +3,3 + diff --git a/projects/project3_kenken/puzzle_files/4x4_2.txt b/projects/project3_kenken/puzzle_files/4x4_2.txt new file mode 100644 index 0000000..4b4ddf3 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/4x4_2.txt @@ -0,0 +1,27 @@ +4 +8 +1, ,1 +0,3 +6,*,2 +0,0 +1,0 +3,-,2 +0,1 +1,1 +7,+,2 +0,2 +1,2 +1,-,2 +2,1 +2,2 +3,-,2 +2,0 +3,0 +2,/,2 +3,1 +3,2 +9,+,3 +1,3 +2,3 +3,3 + diff --git a/projects/project3_kenken/puzzle_files/4x4_3.txt b/projects/project3_kenken/puzzle_files/4x4_3.txt new file mode 100644 index 0000000..f80c871 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/4x4_3.txt @@ -0,0 +1,28 @@ +4 +9 +1, ,1 +0,1 +2,/,2 +0,2 +0,3 +6,*,2 +0,0 +1,0 +1,-,2 +1,1 +1,2 +2,-,2 +1,3 +2,3 +3,-,2 +2,0 +3,0 +5,+,2 +2,1 +3,1 +2,/,2 +2,2 +3,2 +4, ,1 +3,3 + diff --git a/projects/project3_kenken/puzzle_files/5x5_1.txt b/projects/project3_kenken/puzzle_files/5x5_1.txt new file mode 100644 index 0000000..cc6ff3f --- /dev/null +++ b/projects/project3_kenken/puzzle_files/5x5_1.txt @@ -0,0 +1,41 @@ +5 +13 +4,-,2 +0,0 +0,1 +2,/,2 +0,2 +1,2 +1,-,2 +0,3 +1,3 +1,-,2 +0,4 +1,4 +1,-,2 +1,0 +2,0 +3,-,2 +2,2 +2,3 +3, ,1 +2,4 +4, ,1 +3,0 +30,*,3 +1,1 +2,1 +3,1 +5,+,2 +4,0 +4,1 +15,*,2 +3,2 +4,2 +3,-,2 +3,3 +4,3 +1,-,2 +3,4 +4,4 + diff --git a/projects/project3_kenken/puzzle_files/5x5_2.txt b/projects/project3_kenken/puzzle_files/5x5_2.txt new file mode 100644 index 0000000..6b8a919 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/5x5_2.txt @@ -0,0 +1,37 @@ +5 +9 +2,/,2 +0,1 +1,1 +1,-,2 +0,2 +1,2 +6,+,3 +0,3 +0,4 +1,4 +15,*,3 +0,0 +1,0 +2,0 +6,*,3 +2,1 +2,2 +3,2 +9,+,3 +1,3 +2,3 +3,3 +4,-,2 +2,4 +3,4 +120,*,4 +3,0 +3,1 +4,0 +4,1 +10,+,3 +4,2 +4,3 +4,4 + diff --git a/projects/project3_kenken/puzzle_files/5x5_3.txt b/projects/project3_kenken/puzzle_files/5x5_3.txt new file mode 100644 index 0000000..e8b97db --- /dev/null +++ b/projects/project3_kenken/puzzle_files/5x5_3.txt @@ -0,0 +1,39 @@ +5 +11 +4,-,2 +0,0 +0,1 +2,/,2 +0,3 +0,4 +30,*,3 +0,2 +1,1 +1,2 +3,-,2 +1,3 +1,4 +1,-,2 +1,0 +2,0 +2,-,2 +2,2 +2,3 +6,+,2 +2,4 +3,4 +12,+,4 +2,1 +3,0 +3,1 +4,0 +5, ,1 +4,1 +11,+,3 +3,2 +3,3 +4,2 +1,-,2 +4,3 +4,4 + diff --git a/projects/project3_kenken/puzzle_files/6x6_1.txt b/projects/project3_kenken/puzzle_files/6x6_1.txt new file mode 100644 index 0000000..07d23b0 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/6x6_1.txt @@ -0,0 +1,56 @@ +6 +17 +2,/,2 +0,4 +0,5 +9,+,3 +0,0 +0,1 +1,1 +24,*,2 +0,2 +1,2 +6,*,2 +0,3 +1,3 +8,+,2 +1,4 +1,5 +2,/,2 +1,0 +2,0 +4, ,1 +2,1 +3,/,2 +2,3 +2,4 +4,-,2 +2,2 +3,2 +1,-,2 +3,3 +3,4 +2,/,2 +2,5 +3,5 +13,+,3 +3,0 +3,1 +4,0 +1,-,2 +4,3 +4,4 +1, ,1 +4,5 +13,+,3 +4,1 +5,0 +5,1 +10,+,3 +4,2 +5,2 +5,3 +1,-,2 +5,4 +5,5 + diff --git a/projects/project3_kenken/puzzle_files/6x6_2.txt b/projects/project3_kenken/puzzle_files/6x6_2.txt new file mode 100644 index 0000000..8a4a11b --- /dev/null +++ b/projects/project3_kenken/puzzle_files/6x6_2.txt @@ -0,0 +1,55 @@ +6 +16 +3,-,2 +0,2 +0,3 +3,-,2 +0,0 +1,0 +2,-,2 +0,1 +1,1 +1,-,2 +1,2 +1,3 +720,*,4 +0,4 +0,5 +1,4 +1,5 +12,+,3 +2,0 +2,1 +2,2 +5,-,2 +2,3 +2,4 +4,-,2 +3,1 +3,2 +12,*,3 +2,5 +3,4 +3,5 +3,/,2 +3,0 +4,0 +3,-,2 +3,3 +4,3 +2,-,2 +4,4 +4,5 +60,*,3 +4,1 +5,0 +5,1 +2,-,2 +4,2 +5,2 +1,-,2 +5,3 +5,4 +1, ,1 +5,5 + diff --git a/projects/project3_kenken/puzzle_files/7x7_1.txt b/projects/project3_kenken/puzzle_files/7x7_1.txt new file mode 100644 index 0000000..fd59a27 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/7x7_1.txt @@ -0,0 +1,73 @@ +7 +21 +3, ,1 +0,1 +3,-,2 +0,2 +0,3 +30,*,3 +0,0 +1,0 +1,1 +13,+,3 +0,4 +1,3 +1,4 +60,*,3 +0,5 +0,6 +1,5 +2,-,2 +2,0 +2,1 +5,-,2 +1,2 +2,2 +28,*,2 +2,4 +2,5 +1,-,2 +1,6 +2,6 +1,-,2 +3,1 +3,2 +3,+,2 +2,3 +3,3 +4,-,2 +3,5 +3,6 +18,+,3 +3,0 +4,0 +4,1 +3,/,2 +4,2 +4,3 +11,+,2 +3,4 +4,4 +10,+,3 +4,5 +4,6 +5,5 +9,+,3 +5,0 +5,1 +6,0 +70,*,3 +5,2 +6,1 +6,2 +2,-,2 +5,3 +6,3 +3,/,2 +5,4 +6,4 +15,+,3 +5,6 +6,5 +6,6 + diff --git a/projects/project3_kenken/puzzle_files/7x7_2.txt b/projects/project3_kenken/puzzle_files/7x7_2.txt new file mode 100644 index 0000000..e3d03e9 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/7x7_2.txt @@ -0,0 +1,74 @@ +7 +22 +120,*,3 +0,1 +0,2 +0,3 +6,-,2 +0,4 +0,5 +2,/,2 +0,0 +1,0 +12,+,3 +1,1 +1,2 +1,3 +6, ,1 +1,4 +2,-,2 +0,6 +1,6 +5,-,2 +2,0 +2,1 +2,/,2 +2,3 +2,4 +7,+,3 +1,5 +2,5 +2,6 +10,+,2 +3,0 +3,1 +5,-,2 +3,5 +3,6 +14,+,3 +2,2 +3,2 +4,2 +20,*,3 +3,3 +3,4 +4,4 +3,/,2 +4,5 +4,6 +2,-,2 +4,0 +5,0 +4,-,2 +4,1 +5,1 +7,+,2 +4,3 +5,3 +8,+,2 +6,0 +6,1 +5,-,2 +5,2 +6,2 +16,+,3 +5,4 +6,3 +6,4 +1,-,2 +5,5 +6,5 +2,-,2 +5,6 +6,6 + diff --git a/projects/project3_kenken/puzzle_files/8x8_1.txt b/projects/project3_kenken/puzzle_files/8x8_1.txt new file mode 100644 index 0000000..9a3f5f1 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/8x8_1.txt @@ -0,0 +1,92 @@ +8 +25 +14,+,2 +0,2 +0,3 +3,/,2 +0,6 +0,7 +560,*,4 +0,0 +0,1 +1,0 +1,1 +48,*,3 +0,4 +1,3 +1,4 +5,-,2 +0,5 +1,5 +6,-,2 +1,2 +2,2 +4,-,2 +2,3 +2,4 +12,+,3 +1,6 +2,5 +2,6 +19,+,3 +2,0 +2,1 +3,1 +17,+,4 +1,7 +2,7 +3,6 +3,7 +17,+,3 +3,2 +4,1 +4,2 +3,-,2 +3,3 +4,3 +126,*,3 +3,4 +3,5 +4,4 +6,+,3 +3,0 +4,0 +5,0 +3,+,2 +5,2 +5,3 +6,*,2 +5,1 +6,1 +7,+,2 +6,2 +6,3 +240,*,3 +4,5 +5,5 +6,5 +16,+,4 +4,6 +4,7 +5,6 +6,6 +1,-,2 +5,7 +6,7 +13,+,2 +6,0 +7,0 +1,-,2 +7,1 +7,2 +18,+,4 +5,4 +6,4 +7,3 +7,4 +1, ,1 +7,5 +2,/,2 +7,6 +7,7 + diff --git a/projects/project3_kenken/puzzle_files/8x8_2.txt b/projects/project3_kenken/puzzle_files/8x8_2.txt new file mode 100644 index 0000000..01e6de9 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/8x8_2.txt @@ -0,0 +1,92 @@ +8 +25 +8,+,2 +0,3 +0,4 +6,+,2 +0,0 +1,0 +192,*,3 +0,1 +0,2 +1,1 +14,+,3 +0,5 +1,4 +1,5 +15,+,3 +0,6 +0,7 +1,6 +9,+,3 +1,2 +1,3 +2,3 +1,-,2 +2,4 +2,5 +15,+,2 +2,0 +3,0 +2,/,2 +2,1 +3,1 +9,+,2 +2,2 +3,2 +3,-,2 +4,0 +4,1 +17,+,3 +3,3 +3,4 +4,3 +10,*,3 +3,5 +4,4 +4,5 +6,+,3 +2,6 +3,6 +4,6 +20,+,4 +1,7 +2,7 +3,7 +4,7 +60,*,4 +4,2 +5,0 +5,1 +5,2 +4,/,2 +5,3 +5,4 +2,/,2 +6,0 +6,1 +2,/,2 +5,5 +6,5 +14,+,3 +5,6 +5,7 +6,7 +1,-,2 +7,0 +7,1 +56,*,2 +6,2 +7,2 +90,*,4 +6,3 +6,4 +7,3 +7,4 +5, ,1 +7,5 +168,*,3 +6,6 +7,6 +7,7 + diff --git a/projects/project3_kenken/puzzle_files/9x9_1.txt b/projects/project3_kenken/puzzle_files/9x9_1.txt new file mode 100644 index 0000000..40654c0 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/9x9_1.txt @@ -0,0 +1,119 @@ +9 +35 +2,/,2 +0,0 +1,0 +21,*,3 +0,1 +0,2 +1,2 +7,-,2 +0,3 +0,4 +4,/,2 +1,3 +1,4 +3,-,2 +0,5 +1,5 +1,-,2 +0,6 +0,7 +2,-,2 +1,6 +1,7 +17,+,2 +0,8 +1,8 +14,+,3 +1,1 +2,1 +2,2 +3,-,2 +2,4 +2,5 +2,/,2 +2,3 +3,3 +20,+,3 +2,6 +2,7 +3,6 +3,-,2 +2,8 +3,8 +54,*,3 +3,1 +3,2 +4,1 +4,/,2 +4,2 +4,3 +17,+,2 +4,5 +4,6 +7, ,1 +4,8 +14,+,4 +2,0 +3,0 +4,0 +5,0 +17,+,2 +5,1 +5,2 +23,+,4 +3,4 +3,5 +4,4 +5,4 +3, ,1 +5,5 +160,*,3 +3,7 +4,7 +5,7 +2,-,2 +5,3 +6,3 +8,*,2 +6,4 +6,5 +6,+,3 +5,6 +6,6 +6,7 +3,/,2 +5,8 +6,8 +720,*,4 +6,0 +6,1 +6,2 +7,1 +4,/,2 +7,3 +7,4 +8,-,2 +7,6 +7,7 +4,-,2 +7,0 +8,0 +20,+,3 +7,2 +8,1 +8,2 +8,-,2 +8,3 +8,4 +10,+,2 +7,5 +8,5 +3,/,2 +8,6 +8,7 +2,-,2 +7,8 +8,8 + diff --git a/projects/project3_kenken/puzzle_files/9x9_2.txt b/projects/project3_kenken/puzzle_files/9x9_2.txt new file mode 100644 index 0000000..f6bff8e --- /dev/null +++ b/projects/project3_kenken/puzzle_files/9x9_2.txt @@ -0,0 +1,119 @@ +9 +35 +4,/,2 +0,0 +0,1 +6,-,2 +0,2 +0,3 +5,-,2 +0,7 +0,8 +140,*,3 +1,1 +1,2 +1,3 +18,*,3 +0,4 +1,4 +1,5 +20,+,3 +0,5 +0,6 +1,6 +7,-,2 +1,7 +1,8 +5,-,2 +2,1 +2,2 +5,-,2 +2,4 +2,5 +1620,*,4 +1,0 +2,0 +3,0 +3,1 +5,-,2 +2,3 +3,3 +1,-,2 +3,5 +3,6 +11,+,3 +2,6 +2,7 +3,7 +4,-,2 +2,8 +3,8 +8,-,2 +4,0 +4,1 +10,*,2 +3,2 +4,2 +40,*,2 +3,4 +4,4 +56,*,2 +4,5 +4,6 +2,/,2 +5,0 +5,1 +1,-,2 +4,3 +5,3 +6,-,2 +5,5 +5,6 +2,/,2 +4,7 +5,7 +2,-,2 +4,8 +5,8 +11,+,2 +6,0 +6,1 +6,*,3 +5,2 +6,2 +6,3 +3,-,2 +5,4 +6,4 +252,*,3 +6,6 +6,7 +6,8 +10,+,2 +7,3 +7,4 +1,-,2 +6,5 +7,5 +10,+,2 +7,0 +8,0 +6,-,2 +7,1 +8,1 +48,*,2 +7,2 +8,2 +24,*,2 +8,3 +8,4 +1080,*,4 +7,6 +7,7 +8,5 +8,6 +20,*,3 +7,8 +8,7 +8,8 + diff --git a/projects/project3_kenken/puzzle_files/9x9_3.txt b/projects/project3_kenken/puzzle_files/9x9_3.txt new file mode 100644 index 0000000..8285929 --- /dev/null +++ b/projects/project3_kenken/puzzle_files/9x9_3.txt @@ -0,0 +1,118 @@ +9 +34 +42,*,3 +0,0 +0,1 +0,2 +8, ,1 +0,3 +1,-,2 +0,4 +0,5 +4,-,2 +0,6 +0,7 +2,-,2 +1,6 +1,7 +5,-,2 +0,8 +1,8 +2,/,2 +1,0 +2,0 +6,*,2 +1,1 +2,1 +19,+,4 +1,2 +1,3 +1,4 +2,2 +56,*,3 +1,5 +2,4 +2,5 +2,-,2 +2,6 +2,7 +1,-,2 +3,1 +3,2 +2,/,2 +2,3 +3,3 +7,+,3 +3,4 +3,5 +3,6 +15,+,3 +2,8 +3,7 +3,8 +19,+,3 +3,0 +4,0 +4,1 +240,*,4 +4,2 +4,3 +4,4 +4,5 +2,/,2 +4,6 +4,7 +15,+,5 +5,1 +5,2 +5,3 +5,4 +5,5 +6, ,1 +5,6 +21,*,2 +4,8 +5,8 +8,-,2 +5,0 +6,0 +2,/,2 +6,1 +6,2 +7,-,2 +6,3 +6,4 +2,-,2 +6,5 +6,6 +5,-,2 +5,7 +6,7 +15,+,3 +6,8 +7,7 +7,8 +12,+,3 +7,0 +7,1 +8,0 +72,*,3 +7,2 +8,1 +8,2 +16,+,2 +7,3 +8,3 +13,+,2 +7,4 +8,4 +20,+,3 +7,5 +7,6 +8,5 +3,-,2 +8,6 +8,7 +2, ,1 +8,8 + diff --git a/projects/project3_kenken/stab2/3x3_1.txt b/projects/project3_kenken/stab2/3x3_1.txt new file mode 100644 index 0000000..b23e027 --- /dev/null +++ b/projects/project3_kenken/stab2/3x3_1.txt @@ -0,0 +1,17 @@ +3 +5 +3, ,1 +0,0 +6,*,2 +0,1 +1,1 +2,/,2 +0,2 +1,2 +2,/,2 +1,0 +2,0 +2,-,2 +2,1 +2,2 + diff --git a/projects/project3_kenken/stab2/3x3_2.txt b/projects/project3_kenken/stab2/3x3_2.txt new file mode 100644 index 0000000..2556aa6 --- /dev/null +++ b/projects/project3_kenken/stab2/3x3_2.txt @@ -0,0 +1,17 @@ +3 +5 +2, ,1 +0,0 +9,*,3 +0,1 +0,2 +1,2 +2,-,2 +1,0 +2,0 +2,/,2 +1,1 +2,1 +2, ,1 +2,2 + diff --git a/projects/project3_kenken/stab2/3x3_3.txt b/projects/project3_kenken/stab2/3x3_3.txt new file mode 100644 index 0000000..a844c5b --- /dev/null +++ b/projects/project3_kenken/stab2/3x3_3.txt @@ -0,0 +1,17 @@ +3 +5 +1,-,2 +0,1 +0,2 +2,-,2 +0,0 +1,0 +2, ,1 +1,1 +3,+,2 +2,0 +2,1 +3,/,2 +1,2 +2,2 + diff --git a/projects/project3_kenken/stab2/4x4_1.txt b/projects/project3_kenken/stab2/4x4_1.txt new file mode 100644 index 0000000..fcd1e9b --- /dev/null +++ b/projects/project3_kenken/stab2/4x4_1.txt @@ -0,0 +1,27 @@ +4 +8 +1,-,2 +0,0 +0,1 +1,-,2 +0,2 +1,2 +7,+,2 +1,0 +2,0 +2,/,2 +1,1 +2,1 +8,*,3 +0,3 +1,3 +2,3 +3,-,2 +3,0 +3,1 +2,/,2 +2,2 +3,2 +3, ,1 +3,3 + diff --git a/projects/project3_kenken/stab2/4x4_2.txt b/projects/project3_kenken/stab2/4x4_2.txt new file mode 100644 index 0000000..4b4ddf3 --- /dev/null +++ b/projects/project3_kenken/stab2/4x4_2.txt @@ -0,0 +1,27 @@ +4 +8 +1, ,1 +0,3 +6,*,2 +0,0 +1,0 +3,-,2 +0,1 +1,1 +7,+,2 +0,2 +1,2 +1,-,2 +2,1 +2,2 +3,-,2 +2,0 +3,0 +2,/,2 +3,1 +3,2 +9,+,3 +1,3 +2,3 +3,3 + diff --git a/projects/project3_kenken/stab2/4x4_3.txt b/projects/project3_kenken/stab2/4x4_3.txt new file mode 100644 index 0000000..f80c871 --- /dev/null +++ b/projects/project3_kenken/stab2/4x4_3.txt @@ -0,0 +1,28 @@ +4 +9 +1, ,1 +0,1 +2,/,2 +0,2 +0,3 +6,*,2 +0,0 +1,0 +1,-,2 +1,1 +1,2 +2,-,2 +1,3 +2,3 +3,-,2 +2,0 +3,0 +5,+,2 +2,1 +3,1 +2,/,2 +2,2 +3,2 +4, ,1 +3,3 + diff --git a/projects/project3_kenken/stab2/5x5_1.txt b/projects/project3_kenken/stab2/5x5_1.txt new file mode 100644 index 0000000..cc6ff3f --- /dev/null +++ b/projects/project3_kenken/stab2/5x5_1.txt @@ -0,0 +1,41 @@ +5 +13 +4,-,2 +0,0 +0,1 +2,/,2 +0,2 +1,2 +1,-,2 +0,3 +1,3 +1,-,2 +0,4 +1,4 +1,-,2 +1,0 +2,0 +3,-,2 +2,2 +2,3 +3, ,1 +2,4 +4, ,1 +3,0 +30,*,3 +1,1 +2,1 +3,1 +5,+,2 +4,0 +4,1 +15,*,2 +3,2 +4,2 +3,-,2 +3,3 +4,3 +1,-,2 +3,4 +4,4 + diff --git a/projects/project3_kenken/stab2/5x5_2.txt b/projects/project3_kenken/stab2/5x5_2.txt new file mode 100644 index 0000000..6b8a919 --- /dev/null +++ b/projects/project3_kenken/stab2/5x5_2.txt @@ -0,0 +1,37 @@ +5 +9 +2,/,2 +0,1 +1,1 +1,-,2 +0,2 +1,2 +6,+,3 +0,3 +0,4 +1,4 +15,*,3 +0,0 +1,0 +2,0 +6,*,3 +2,1 +2,2 +3,2 +9,+,3 +1,3 +2,3 +3,3 +4,-,2 +2,4 +3,4 +120,*,4 +3,0 +3,1 +4,0 +4,1 +10,+,3 +4,2 +4,3 +4,4 + diff --git a/projects/project3_kenken/stab2/5x5_3.txt b/projects/project3_kenken/stab2/5x5_3.txt new file mode 100644 index 0000000..e8b97db --- /dev/null +++ b/projects/project3_kenken/stab2/5x5_3.txt @@ -0,0 +1,39 @@ +5 +11 +4,-,2 +0,0 +0,1 +2,/,2 +0,3 +0,4 +30,*,3 +0,2 +1,1 +1,2 +3,-,2 +1,3 +1,4 +1,-,2 +1,0 +2,0 +2,-,2 +2,2 +2,3 +6,+,2 +2,4 +3,4 +12,+,4 +2,1 +3,0 +3,1 +4,0 +5, ,1 +4,1 +11,+,3 +3,2 +3,3 +4,2 +1,-,2 +4,3 +4,4 + diff --git a/projects/project3_kenken/stab2/6x6_1.txt b/projects/project3_kenken/stab2/6x6_1.txt new file mode 100644 index 0000000..07d23b0 --- /dev/null +++ b/projects/project3_kenken/stab2/6x6_1.txt @@ -0,0 +1,56 @@ +6 +17 +2,/,2 +0,4 +0,5 +9,+,3 +0,0 +0,1 +1,1 +24,*,2 +0,2 +1,2 +6,*,2 +0,3 +1,3 +8,+,2 +1,4 +1,5 +2,/,2 +1,0 +2,0 +4, ,1 +2,1 +3,/,2 +2,3 +2,4 +4,-,2 +2,2 +3,2 +1,-,2 +3,3 +3,4 +2,/,2 +2,5 +3,5 +13,+,3 +3,0 +3,1 +4,0 +1,-,2 +4,3 +4,4 +1, ,1 +4,5 +13,+,3 +4,1 +5,0 +5,1 +10,+,3 +4,2 +5,2 +5,3 +1,-,2 +5,4 +5,5 + diff --git a/projects/project3_kenken/stab2/6x6_2.txt b/projects/project3_kenken/stab2/6x6_2.txt new file mode 100644 index 0000000..8a4a11b --- /dev/null +++ b/projects/project3_kenken/stab2/6x6_2.txt @@ -0,0 +1,55 @@ +6 +16 +3,-,2 +0,2 +0,3 +3,-,2 +0,0 +1,0 +2,-,2 +0,1 +1,1 +1,-,2 +1,2 +1,3 +720,*,4 +0,4 +0,5 +1,4 +1,5 +12,+,3 +2,0 +2,1 +2,2 +5,-,2 +2,3 +2,4 +4,-,2 +3,1 +3,2 +12,*,3 +2,5 +3,4 +3,5 +3,/,2 +3,0 +4,0 +3,-,2 +3,3 +4,3 +2,-,2 +4,4 +4,5 +60,*,3 +4,1 +5,0 +5,1 +2,-,2 +4,2 +5,2 +1,-,2 +5,3 +5,4 +1, ,1 +5,5 + diff --git a/projects/project3_kenken/stab2/7x7_1.txt b/projects/project3_kenken/stab2/7x7_1.txt new file mode 100644 index 0000000..fd59a27 --- /dev/null +++ b/projects/project3_kenken/stab2/7x7_1.txt @@ -0,0 +1,73 @@ +7 +21 +3, ,1 +0,1 +3,-,2 +0,2 +0,3 +30,*,3 +0,0 +1,0 +1,1 +13,+,3 +0,4 +1,3 +1,4 +60,*,3 +0,5 +0,6 +1,5 +2,-,2 +2,0 +2,1 +5,-,2 +1,2 +2,2 +28,*,2 +2,4 +2,5 +1,-,2 +1,6 +2,6 +1,-,2 +3,1 +3,2 +3,+,2 +2,3 +3,3 +4,-,2 +3,5 +3,6 +18,+,3 +3,0 +4,0 +4,1 +3,/,2 +4,2 +4,3 +11,+,2 +3,4 +4,4 +10,+,3 +4,5 +4,6 +5,5 +9,+,3 +5,0 +5,1 +6,0 +70,*,3 +5,2 +6,1 +6,2 +2,-,2 +5,3 +6,3 +3,/,2 +5,4 +6,4 +15,+,3 +5,6 +6,5 +6,6 + diff --git a/projects/project3_kenken/stab2/7x7_2.txt b/projects/project3_kenken/stab2/7x7_2.txt new file mode 100644 index 0000000..e3d03e9 --- /dev/null +++ b/projects/project3_kenken/stab2/7x7_2.txt @@ -0,0 +1,74 @@ +7 +22 +120,*,3 +0,1 +0,2 +0,3 +6,-,2 +0,4 +0,5 +2,/,2 +0,0 +1,0 +12,+,3 +1,1 +1,2 +1,3 +6, ,1 +1,4 +2,-,2 +0,6 +1,6 +5,-,2 +2,0 +2,1 +2,/,2 +2,3 +2,4 +7,+,3 +1,5 +2,5 +2,6 +10,+,2 +3,0 +3,1 +5,-,2 +3,5 +3,6 +14,+,3 +2,2 +3,2 +4,2 +20,*,3 +3,3 +3,4 +4,4 +3,/,2 +4,5 +4,6 +2,-,2 +4,0 +5,0 +4,-,2 +4,1 +5,1 +7,+,2 +4,3 +5,3 +8,+,2 +6,0 +6,1 +5,-,2 +5,2 +6,2 +16,+,3 +5,4 +6,3 +6,4 +1,-,2 +5,5 +6,5 +2,-,2 +5,6 +6,6 + diff --git a/projects/project3_kenken/stab2/8x8_1.txt b/projects/project3_kenken/stab2/8x8_1.txt new file mode 100644 index 0000000..9a3f5f1 --- /dev/null +++ b/projects/project3_kenken/stab2/8x8_1.txt @@ -0,0 +1,92 @@ +8 +25 +14,+,2 +0,2 +0,3 +3,/,2 +0,6 +0,7 +560,*,4 +0,0 +0,1 +1,0 +1,1 +48,*,3 +0,4 +1,3 +1,4 +5,-,2 +0,5 +1,5 +6,-,2 +1,2 +2,2 +4,-,2 +2,3 +2,4 +12,+,3 +1,6 +2,5 +2,6 +19,+,3 +2,0 +2,1 +3,1 +17,+,4 +1,7 +2,7 +3,6 +3,7 +17,+,3 +3,2 +4,1 +4,2 +3,-,2 +3,3 +4,3 +126,*,3 +3,4 +3,5 +4,4 +6,+,3 +3,0 +4,0 +5,0 +3,+,2 +5,2 +5,3 +6,*,2 +5,1 +6,1 +7,+,2 +6,2 +6,3 +240,*,3 +4,5 +5,5 +6,5 +16,+,4 +4,6 +4,7 +5,6 +6,6 +1,-,2 +5,7 +6,7 +13,+,2 +6,0 +7,0 +1,-,2 +7,1 +7,2 +18,+,4 +5,4 +6,4 +7,3 +7,4 +1, ,1 +7,5 +2,/,2 +7,6 +7,7 + diff --git a/projects/project3_kenken/stab2/8x8_2.txt b/projects/project3_kenken/stab2/8x8_2.txt new file mode 100644 index 0000000..01e6de9 --- /dev/null +++ b/projects/project3_kenken/stab2/8x8_2.txt @@ -0,0 +1,92 @@ +8 +25 +8,+,2 +0,3 +0,4 +6,+,2 +0,0 +1,0 +192,*,3 +0,1 +0,2 +1,1 +14,+,3 +0,5 +1,4 +1,5 +15,+,3 +0,6 +0,7 +1,6 +9,+,3 +1,2 +1,3 +2,3 +1,-,2 +2,4 +2,5 +15,+,2 +2,0 +3,0 +2,/,2 +2,1 +3,1 +9,+,2 +2,2 +3,2 +3,-,2 +4,0 +4,1 +17,+,3 +3,3 +3,4 +4,3 +10,*,3 +3,5 +4,4 +4,5 +6,+,3 +2,6 +3,6 +4,6 +20,+,4 +1,7 +2,7 +3,7 +4,7 +60,*,4 +4,2 +5,0 +5,1 +5,2 +4,/,2 +5,3 +5,4 +2,/,2 +6,0 +6,1 +2,/,2 +5,5 +6,5 +14,+,3 +5,6 +5,7 +6,7 +1,-,2 +7,0 +7,1 +56,*,2 +6,2 +7,2 +90,*,4 +6,3 +6,4 +7,3 +7,4 +5, ,1 +7,5 +168,*,3 +6,6 +7,6 +7,7 + diff --git a/projects/project3_kenken/stab2/9x9_1.txt b/projects/project3_kenken/stab2/9x9_1.txt new file mode 100644 index 0000000..40654c0 --- /dev/null +++ b/projects/project3_kenken/stab2/9x9_1.txt @@ -0,0 +1,119 @@ +9 +35 +2,/,2 +0,0 +1,0 +21,*,3 +0,1 +0,2 +1,2 +7,-,2 +0,3 +0,4 +4,/,2 +1,3 +1,4 +3,-,2 +0,5 +1,5 +1,-,2 +0,6 +0,7 +2,-,2 +1,6 +1,7 +17,+,2 +0,8 +1,8 +14,+,3 +1,1 +2,1 +2,2 +3,-,2 +2,4 +2,5 +2,/,2 +2,3 +3,3 +20,+,3 +2,6 +2,7 +3,6 +3,-,2 +2,8 +3,8 +54,*,3 +3,1 +3,2 +4,1 +4,/,2 +4,2 +4,3 +17,+,2 +4,5 +4,6 +7, ,1 +4,8 +14,+,4 +2,0 +3,0 +4,0 +5,0 +17,+,2 +5,1 +5,2 +23,+,4 +3,4 +3,5 +4,4 +5,4 +3, ,1 +5,5 +160,*,3 +3,7 +4,7 +5,7 +2,-,2 +5,3 +6,3 +8,*,2 +6,4 +6,5 +6,+,3 +5,6 +6,6 +6,7 +3,/,2 +5,8 +6,8 +720,*,4 +6,0 +6,1 +6,2 +7,1 +4,/,2 +7,3 +7,4 +8,-,2 +7,6 +7,7 +4,-,2 +7,0 +8,0 +20,+,3 +7,2 +8,1 +8,2 +8,-,2 +8,3 +8,4 +10,+,2 +7,5 +8,5 +3,/,2 +8,6 +8,7 +2,-,2 +7,8 +8,8 + diff --git a/projects/project3_kenken/stab2/9x9_2.txt b/projects/project3_kenken/stab2/9x9_2.txt new file mode 100644 index 0000000..f6bff8e --- /dev/null +++ b/projects/project3_kenken/stab2/9x9_2.txt @@ -0,0 +1,119 @@ +9 +35 +4,/,2 +0,0 +0,1 +6,-,2 +0,2 +0,3 +5,-,2 +0,7 +0,8 +140,*,3 +1,1 +1,2 +1,3 +18,*,3 +0,4 +1,4 +1,5 +20,+,3 +0,5 +0,6 +1,6 +7,-,2 +1,7 +1,8 +5,-,2 +2,1 +2,2 +5,-,2 +2,4 +2,5 +1620,*,4 +1,0 +2,0 +3,0 +3,1 +5,-,2 +2,3 +3,3 +1,-,2 +3,5 +3,6 +11,+,3 +2,6 +2,7 +3,7 +4,-,2 +2,8 +3,8 +8,-,2 +4,0 +4,1 +10,*,2 +3,2 +4,2 +40,*,2 +3,4 +4,4 +56,*,2 +4,5 +4,6 +2,/,2 +5,0 +5,1 +1,-,2 +4,3 +5,3 +6,-,2 +5,5 +5,6 +2,/,2 +4,7 +5,7 +2,-,2 +4,8 +5,8 +11,+,2 +6,0 +6,1 +6,*,3 +5,2 +6,2 +6,3 +3,-,2 +5,4 +6,4 +252,*,3 +6,6 +6,7 +6,8 +10,+,2 +7,3 +7,4 +1,-,2 +6,5 +7,5 +10,+,2 +7,0 +8,0 +6,-,2 +7,1 +8,1 +48,*,2 +7,2 +8,2 +24,*,2 +8,3 +8,4 +1080,*,4 +7,6 +7,7 +8,5 +8,6 +20,*,3 +7,8 +8,7 +8,8 + diff --git a/projects/project3_kenken/stab2/9x9_3.txt b/projects/project3_kenken/stab2/9x9_3.txt new file mode 100644 index 0000000..8285929 --- /dev/null +++ b/projects/project3_kenken/stab2/9x9_3.txt @@ -0,0 +1,118 @@ +9 +34 +42,*,3 +0,0 +0,1 +0,2 +8, ,1 +0,3 +1,-,2 +0,4 +0,5 +4,-,2 +0,6 +0,7 +2,-,2 +1,6 +1,7 +5,-,2 +0,8 +1,8 +2,/,2 +1,0 +2,0 +6,*,2 +1,1 +2,1 +19,+,4 +1,2 +1,3 +1,4 +2,2 +56,*,3 +1,5 +2,4 +2,5 +2,-,2 +2,6 +2,7 +1,-,2 +3,1 +3,2 +2,/,2 +2,3 +3,3 +7,+,3 +3,4 +3,5 +3,6 +15,+,3 +2,8 +3,7 +3,8 +19,+,3 +3,0 +4,0 +4,1 +240,*,4 +4,2 +4,3 +4,4 +4,5 +2,/,2 +4,6 +4,7 +15,+,5 +5,1 +5,2 +5,3 +5,4 +5,5 +6, ,1 +5,6 +21,*,2 +4,8 +5,8 +8,-,2 +5,0 +6,0 +2,/,2 +6,1 +6,2 +7,-,2 +6,3 +6,4 +2,-,2 +6,5 +6,6 +5,-,2 +5,7 +6,7 +15,+,3 +6,8 +7,7 +7,8 +12,+,3 +7,0 +7,1 +8,0 +72,*,3 +7,2 +8,1 +8,2 +16,+,2 +7,3 +8,3 +13,+,2 +7,4 +8,4 +20,+,3 +7,5 +7,6 +8,5 +3,-,2 +8,6 +8,7 +2, ,1 +8,8 + diff --git a/projects/project3_kenken/stab2/Constraint.java b/projects/project3_kenken/stab2/Constraint.java new file mode 100644 index 0000000..4d97055 --- /dev/null +++ b/projects/project3_kenken/stab2/Constraint.java @@ -0,0 +1,12 @@ +public class Constraint +{ + public String op; + public Position[] positions; + public int targNumber; + public Constraint(int targNumber,String op,Position[] pos) + { + this.op = op; + positions = pos; + this.targNumber = targNumber; + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/stab2/KNode.java b/projects/project3_kenken/stab2/KNode.java new file mode 100644 index 0000000..e82e0e2 --- /dev/null +++ b/projects/project3_kenken/stab2/KNode.java @@ -0,0 +1,18 @@ +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 diff --git a/projects/project3_kenken/stab2/KStack.java b/projects/project3_kenken/stab2/KStack.java new file mode 100644 index 0000000..613f9f2 --- /dev/null +++ b/projects/project3_kenken/stab2/KStack.java @@ -0,0 +1,54 @@ +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][4]; + int i = length-1; + for(KNode tmp = head; tmp != null; tmp = tmp.getNext()) + { + output[i] = tmp.getData(); + i--; + } + return output; + } + +} diff --git a/projects/project3_kenken/stab2/Position.java b/projects/project3_kenken/stab2/Position.java new file mode 100644 index 0000000..b036299 --- /dev/null +++ b/projects/project3_kenken/stab2/Position.java @@ -0,0 +1,11 @@ +public class Position +{ + public int x; + public int y; + public Position(int x, int y) + { + this.x = x; + this.y = y; + } + +}
\ No newline at end of file diff --git a/projects/project3_kenken/stab2/Solver.java b/projects/project3_kenken/stab2/Solver.java new file mode 100644 index 0000000..18a864b --- /dev/null +++ b/projects/project3_kenken/stab2/Solver.java @@ -0,0 +1,865 @@ +import java.util.Scanner; +import java.io.*; + +public class Solver +{ + public int[][] puzzle; + public Constraint[] constraints; + public int size; + public Solver(String filename) + { + parsePuzzle(filename); + /*puzzle = new int[3][3]; + constraints = new Constraint[5]; + + Position[] p1 = new Position[1]; + p1[0] = new Position(0,0); + constraints[0] = new Constraint(3," ",p1); + + Position[] p2 = new Position[2]; + p2[0] = new Position(1,0); + p2[1] = new Position(1,1); + constraints[1] = new Constraint(6,"*",p2); + + Position[] p3 = new Position[2]; + p3[0] = new Position(2,0); + p3[1] = new Position(2,1); + constraints[2] = new Constraint(2,"/",p3); + + Position[] p4 = new Position[2]; + p4[0] = new Position(0,1); + p4[1] = new Position(0,2); + constraints[3] = new Constraint(2,"/",p4); + + Position[] p5 = new Position[2]; + p5[0] = new Position(1,2); + p5[1] = new Position(2,2); + constraints[4] = new Constraint(2,"-",p5); + + size = puzzle.length; + */ + System.out.println("Everything parsed, data is:"); + System.out.println("Puzzle:"); + printArray(puzzle); + System.out.println("Constraints:"); + printArray(constraints); + System.out.println("size: " + size); + } + private void parsePuzzle(String filename) + { + Scanner s = null; + try + { + s = new Scanner(new FileInputStream(filename)); + } + catch (Exception e) + { + System.out.println("Something went terribly wrong!\n" + e); + } + size = Integer.parseInt(s.nextLine().replaceAll("\n","")); + + puzzle = new int[size][size]; + + constraints = new Constraint[Integer.parseInt(s.nextLine().replaceAll("\n",""))]; + + //System.out.println("Puzzle size: " + size + " Cages: " + p.length); + for(int i = 0; s.hasNextLine();i++) + { + String t1 = s.nextLine(); + System.out.println("Praseing: " + t1); + String[] t2 = t1.split(","); + System.out.println("Parts length: " + t2.length); + if(t2.length > 1) + { + Position[] allcells = new Position[Integer.parseInt(t2[2])]; + for(int j = 0; j < Integer.parseInt(t2[2]);j++) + { + String[] coords = s.nextLine().split(","); + allcells[j] = new Position(Integer.parseInt(coords[1]),Integer.parseInt(coords[0])); + } + constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells); + System.out.println("Created new constraint(" + Integer.parseInt(t2[0]) + "," + t2[1] + ","); + printArray(allcells); + /* + for(Position c : allcells) + { + constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells); + } + */ + //p[i] = new KCage(Integer.parseInt(t2[0]),getOp(t2[1]),allcells); + //System.out.println("Created " + p[i]); + } + } + } + public void put(int x, int y, int num) + { + puzzle[x][y] = num; + } + public int remove(int x, int y) + { + int num = puzzle[x][y]; + puzzle[x][y] = 0; + return num; + } + public boolean[] getPossibilities(int x, int y) + { + boolean[] row = getPossibilitiesByRow(y); + boolean[] col = getPossibilitiesByCol(x); + boolean[] cage = getPossibilitiesByCage(x,y); + boolean[] output = new boolean[size]; + System.out.println("By row:"); + printArray(row); + System.out.println("By col:"); + printArray(col); + System.out.println("By cage:"); + printArray(cage); + for(int i = 0; i < size; i++) + { + if(row[i] && col[i] && cage[i]) + { + output[i] = true; + } + } + System.out.println("Possibilities for (" + x + "," + y + ") are "); + printArray(output); + return output; + } + public boolean[] getPossibilitiesByRow(int row) + { + boolean[] possibs = new boolean[size]; + for(int j = 0; j < size; j++) + {//Set all places is possibs to true + possibs[j] = true; + } + //Find all the possibilities + for(int j = 0; j < size; j++) + { //For every other place + if(puzzle[j][row] != 0) + { + //System.out.println("Setting (" + j + "," + row + "): " + puzzle[j][row] + " to false"); + possibs[puzzle[j][row]-1] = false; + } + } + return possibs; + } + public boolean[] getPossibilitiesByCol(int col) + { + boolean[] possibs = new boolean[size]; + for(int j = 0; j < size; j++) + {//Set all places is possibs to true + possibs[j] = true; + } + //Find all the possibilities + for(int j = 0; j < size; j++) + { //For every other place + if(puzzle[col][j] != 0) + { + //System.out.println("Setting (" + col + "," + j + "): " + puzzle[col][j] + " to false"); + possibs[puzzle[col][j]-1] = false; + } + } + return possibs; + } + public boolean[] getPossibilitiesByCage(int x, int y) + { + //System.out.println("Finding cage possibilities on (" + x + "," + y + ")"); + for(Constraint c : constraints) + { + //System.out.println("Testing a constraint: " + c.op); + for(Position p : c.positions) + { + //System.out.println("Found a position in this constraint: (" + p.x + "," + p.y + ")"); + if(p.x == x && p.y == y) + { + System.out.println("Found cell being talked about."); + //We found the cage that's being talked about + if(c.op.equals("+")) + { + System.out.println("Found op: +"); + return getPossibilitiesByCageAdd(c); + } + else if(c.op.equals("-")) + { + System.out.println("Found op: -"); + return getPossibilitiesByCageSub(c); + } + else if(c.op.equals("*")) + { + System.out.println("Found op: *"); + return getPossibilitiesByCageMul(c); + } + else if(c.op.equals("/")) + { + System.out.println("Found op: /"); + return getPossibilitiesByCageDiv(c); + } + else if(c.op.equals(" ")) + { + System.out.println("Found op: (NONE)"); + boolean[] output = new boolean[size]; + output[c.targNumber-1] = true; + //System.out.println("Returning:"); + //printArray(output); + return output; + } + else + { + System.out.println("Bad operator: (" + c.op + ")"); + return null; + } + } + } + } + System.out.println("Something has gone wrong in getPossibilitiesByCage"); + return null; + } + private boolean[] getPossibilitiesByCageAdd(Constraint c) + { + System.out.println("Getting possibilities for add cage"); + //Try the numbers 1 to size for every square + boolean[] output = new boolean[size]; + int targ = c.targNumber; + //If any of the numbers are already in, subtract them from targ + for(Position p : c.positions) + { + targ -= puzzle[p.x][p.y]; + } + //possibilities are targnumber - 1*# of positions to fill + int numcells = c.positions.length; + int max = targ - numcells; + int min = 1; + for(int i = min; i < max; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageMul(Constraint c) + { + //Numbers can be from 1 to size for this one + //If the target number is odd, only an odd* an odd will work + int targ = c.targNumber; + System.out.println("Getting mul cage possibs:"); + System.out.println("Cage: (" + c.targNumber + "," + c.op); + printArray(c.positions); + //If any of the numbers are already in, divide the target by that. + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + System.out.println("Found a number, useing division shortcut"); + targ /= puzzle[p.x][p.y]; + } + } + boolean[] output = new boolean[size]; + if(c.targNumber % 2 == 1) + { + System.out.println("Found an odd number, useing odd numbers shortcut"); + for(int i = 1; i < size+1; i+= 2) + { + System.out.println("Setting " + i + " to true"); + output[i-1] = true; + } + System.out.println("Returning "); + printArray(output); + return output; + } + for(int i = 1; i < size+1; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageSub(Constraint c) + { + //If one of the items is already in it, find what the other value must be + boolean[] output = new boolean[size]; + int x1 = c.positions[0].x; + int y1 = c.positions[0].y; + int x2 = c.positions[1].x; + int y2 = c.positions[1].y; + if(puzzle[x1][y1] != 0) + { + int onlypossib = 0; + if(c.targNumber > puzzle[x1][y1]) + { + onlypossib = c.targNumber-puzzle[x1][y1]; + } + else if(c.targNumber < puzzle[x1][y1]) + { + onlypossib = puzzle[x1][y1] - c.targNumber; + } + output[onlypossib-1] = true; + return output; + } + if(puzzle[x2][y2] != 0) + { + int onlypossib = 0; + if(c.targNumber>puzzle[x2][y2]) + { + onlypossib = c.targNumber-puzzle[x2][y2]; + } + else if(c.targNumber < puzzle[x2][y2]) + { + onlypossib = puzzle[x2][y2] - c.targNumber; + } + output[onlypossib-1] = true; + return output; + } + //Otherwise, values can be from 1 to targnumber - 2 + for(int i = 1; i < c.targNumber-2; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageDiv(Constraint c) + { + //If one of the items is already in it, find what the other value must be + boolean[] output = new boolean[size]; + int x1 = c.positions[0].x; + int y1 = c.positions[0].y; + int x2 = c.positions[1].x; + int y2 = c.positions[1].y; + if(puzzle[x1][y1] != 0) + { + int onlypossib = c.targNumber/puzzle[x1][y1]; + output[onlypossib-1] = true; + return output; + } + if(puzzle[x2][y2] != 0) + { + int onlypossib = c.targNumber/puzzle[x2][y2]; + output[onlypossib-1] = true; + return output; + } + //Otherwise, values can be from 1 to targnumber + for(int i = 1; i < c.targNumber+1; i++) + { + output[i-1] = true; + } + return output; + } + public boolean isSolved() + { + boolean tr = testRows(); + boolean tc = testCols(); + boolean ta = testCages(); + System.out.println("Checking for solution(Rows: " + tr + ")(Cols: " + tc + ")(Cages: " + ta+"):"); + printArray(puzzle); + if(!testRows() || !testCols() || !testCages()) + { + return false; + } + return true; + } + private boolean testCages() + { + for(Constraint c : constraints) + { + if(!testConstraint(c)) + { + return false; + } + } + return true; + } + private boolean testConstraint(Constraint c) + { + if(c.op.equals("+")) + { + int sum = 0; + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + sum += puzzle[p.x][p.y]; + } + else + { + return false; + } + } + if(sum == c.targNumber) + { + return true; + } + else + { + System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + printArray(c.positions); + return false; + } + } + else if(c.op.equals("-")) + { + Position p1 = c.positions[0]; + Position p2 = c.positions[1]; + if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0) + { + int num1 = puzzle[p1.x][p1.y]; + int num2 = puzzle[p2.x][p2.y]; + if(num1 - num2 == c.targNumber) + { + return true; + } + if(num2 - num1 == c.targNumber) + { + return true; + } + } + else + { + System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + printArray(c.positions); + return false; + } + return false; + } + else if(c.op.equals("*")) + { + int product = 1; + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + product *= puzzle[p.x][p.y]; + } + else + { + return false; + } + } + if(product == c.targNumber) + { + return true; + } + else + { + System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + printArray(c.positions); + System.out.println("Product is " + product); + return false; + } + } + else if(c.op.equals("/")) + { + Position p1 = c.positions[0]; + Position p2 = c.positions[1]; + if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0) + { + double num1 = puzzle[p1.x][p1.y]; + double num2 = puzzle[p2.x][p2.y]; + if(num1 / num2 == c.targNumber) + { + return true; + } + if(num2 / num1 == c.targNumber) + { + return true; + } + } + else + { + System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + printArray(c.positions); + return false; + } + return false; + } + else if(c.op.equals(" ")) + { + int x = c.positions[0].x; + int y = c.positions[0].y; + if(puzzle[x][y] == c.targNumber) + { + return true; + } + else + { + return false; + } + } + System.out.println("Something went wrong in testConstraint"); + return false; + } + private boolean testCols() + { + for(int i = 0; i < size; i++) + { + boolean[] uniqueCols = new boolean[size]; + for(int j = 0; j < size; j++) + { + if(puzzle[i][j] == 0) + { + return false; + } + uniqueCols[puzzle[i][j]-1] = true; + } + for(int j = 0; j < uniqueCols.length; j++) + { + if(!uniqueCols[j]) + { + return false; + } + } + } + //System.out.println("Something went wrong in testCols!"); + return true; + } + private boolean testRows() + { + for(int i = 0; i < size; i++) + { + boolean[] uniqueRows = new boolean[size]; + for(int j = 0; j < size; j++) + { + if(puzzle[j][i] == 0) + { + return false; + } + uniqueRows[puzzle[j][i]-1] = true; + } + for(int j = 0; j < uniqueRows.length; j++) + { + if(!uniqueRows[j]) + { + return false; + } + } + } + //System.out.println("Something went wrong in testRows"); + return true; + } + public int[][] implyByRows() + { + //System.out.println("Implying by rows..."); + int[][][] output = new int[size][4][size]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { + //System.out.println("Calling imply row helper on row " + i); + output[i] = implyByRowsHelper(i); + if(output[i].length > 0) + { + numImplyed++; + } + } + int[][] realoutput = new int[numImplyed][4]; + int j = 0; + for(int i = 0; i < numImplyed;i++) + { + if(output[i].length > 0) + { + realoutput[j] = output[i][0]; + j++; + } + } + return realoutput; + } + public int[][] implyByCols() + { + //System.out.println("Implying by cols..."); + int[][][] output = new int[size][4][size]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { + //System.out.println("Calling imply col helper on col " + i); + output[i] = implyByColsHelper(i); + if(output[i].length > 0) + { + numImplyed++; + } + } + int[][] realoutput = new int[numImplyed][4]; + int j = 0; + for(int i = 0; i < numImplyed;i++) + { + if(output[i].length > 0) + { + realoutput[j] = output[i][0]; + j++; + } + } + return realoutput; + } + public int[][] implyByCages() + { + //System.out.println("Implying by cages"); + int[][][][] output = new int[size][size][4][size]; + int numImplyed = 0; + //We should only be implying ONE number max! + for(int x = 0; x < size; x++) + { + for(int y = 0; y < size; y++) + { + //Scan for a num that has only 1 possibility + output[x][y] = implyByCagesHelper(x,y); + //System.out.println("Attempted to imply by cages on (" + x + "," + y + "):"); + //printArray(output[x][y]); + if(output[x][y].length == 1) + { + //numImplyed++; + //System.out.println("Implything by cage. returning:"); + //printArray(output[x][y]); + return output[x][y]; + } + else + { + //System.out.println("Unable to imply"); + } + } + } + //System.out.println("Unable to imply ANYTHING"); + int[][] realoutput = new int[0][0]; + return realoutput; + /* + int[][] realoutput = new int[1][4]; + int track = 0; + if(output.length == 1) + { + realoutput[0] = output[x][y][0]; + return realoutput; + } + */ + } + public int[][] implyByCagesHelper(int x, int y) + { + int[][] realoutput = new int[size][4]; + //System.out.println("Implying on cage(" + x + "," + y + ")"); + int[][] output = new int[size][4]; + if(puzzle[x][y] != 0) + { + //This square already has a number in it. + } + else + { + boolean[] possibs = getPossibilitiesByCage(x,y); + //System.out.println("Got possibilities:"); + //printArray(possibs); + int j = 0; + int numtrue = 0; + for(boolean b : possibs) + { + if(b) + { + numtrue++; + } + } + if(numtrue == 1) + { + for(int i = 0; i < possibs.length;i++) + { + if(possibs[i]) + { + realoutput = new int[1][4]; + puzzle[x][y] = i+1; + realoutput[j][0] = 0; + realoutput[j][1] = x; + realoutput[j][2] = y; + realoutput[j][3] = i; + return realoutput; + } + } + } + } + return realoutput; + } + private int[][] implyByRowsHelper(int row) + { + //System.out.println("Implying on row " + row); + //boolean[] places = new boolean[size]; + //Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num) + //this method may output more than 1 implyed number. + int[][] output = new int[size][4]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { //For each square + //This place already has something + if(puzzle[i][row] != 0) + { + //System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]); + } + else + { + boolean[] possibs = getPossibilitiesByRow(row); + //System.out.println("Possibilities for (" + i + "," + row + ") are:"); + printArray(possibs); + //Find out how many possibilites for this place is true + int numtrue = 0; + int lasttrue = 0; + for(int j = 0; j < size;j++) + { + if(possibs[j]) + { + numtrue++; + lasttrue = j+1; + } + } + if(numtrue == 1) + { + puzzle[i][row] = lasttrue; + output[numImplyed][0] = 0; + output[numImplyed][1] = i; + output[numImplyed][2] = row; + output[numImplyed][3] = lasttrue; + numImplyed++; + } + } + } + //System.out.println("First output is : "); + //printArray(output); + int[][] realoutput = new int[numImplyed][4]; + for(int i = 0; i < numImplyed; i++) + { + realoutput[i] = output[i]; + } + //System.out.println("Real output is : "); + //printArray(realoutput); + return realoutput; + } + private int[][] implyByColsHelper(int col) + { + // System.out.println("Implying on row " + row); + //boolean[] places = new boolean[size]; + //Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num) + //this method may output more than 1 implyed number. + int[][] output = new int[size][4]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { //For each square + //This place already has something + if(puzzle[col][i] != 0) + { + //System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]); + } + else + { + boolean[] possibs = getPossibilitiesByCol(col); + //System.out.println("Possibilities for (" + col + "," + i + ") are:"); + //printArray(possibs); + //Find out how many possibilites for this place is true + int numtrue = 0; + int lasttrue = 0; + for(int j = 0; j < size;j++) + { + if(possibs[j]) + { + numtrue++; + lasttrue = j+1; + } + } + if(numtrue == 1) + { + puzzle[col][i] = lasttrue; + output[numImplyed][0] = 0; + output[numImplyed][1] = col; + output[numImplyed][2] = i; + output[numImplyed][3] = lasttrue; + numImplyed++; + } + } + } + //System.out.println("First output is : "); + //printArray(output); + int[][] realoutput = new int[numImplyed][4]; + for(int i = 0; i < numImplyed; i++) + { + realoutput[i] = output[i]; + } + //System.out.println("Real output is : "); + //printArray(realoutput); + return realoutput; + } + public void printPuzzle() + { + for(int y = 0; y < puzzle.length; y++) + { + for(int x = 0; x < puzzle[y].length; x++) + { + System.out.print(puzzle[x][y] + " "); + } + System.out.print("\n"); + } + } + public void printArray(int[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[" + arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("," + arr[i]); + } + System.out.print("]\n"); + } + public void printArray(int[][] arr) + { + if(arr.length == 0) + { + System.out.println("[[]]"); + return; + } + System.out.print("[\t"); + printArray(arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("\t"); + printArray(arr[i]); + } + System.out.print("]\n"); + + } + public void printArray(boolean[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[" + arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("," + arr[i]); + } + System.out.print("]\n"); + } + public void printArray(Position[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[(" + arr[0].x + "," + arr[0].y + ")"); + for(int i = 1; i < arr.length; i++) + { + System.out.print(",(" + arr[i].x + "," + arr[i].y + ")"); + } + System.out.print("]\n"); + } + public void printArray(Constraint[] arr) + { + if(arr.length == 0) + { + System.out.println("[[]]"); + return; + } + System.out.print("[\t"); + printArray(arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("\t"); + printArray(arr[i]); + } + System.out.print("]\n"); + } + public void printArray(Constraint c) + { + System.out.print("(" + c.op + "," + c.targNumber + ","); + printArray(c.positions); + } +}
\ No newline at end of file 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 diff --git a/projects/project3_kenken/stab2/working3x3_1/3x3_1.txt b/projects/project3_kenken/stab2/working3x3_1/3x3_1.txt new file mode 100644 index 0000000..b23e027 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/3x3_1.txt @@ -0,0 +1,17 @@ +3 +5 +3, ,1 +0,0 +6,*,2 +0,1 +1,1 +2,/,2 +0,2 +1,2 +2,/,2 +1,0 +2,0 +2,-,2 +2,1 +2,2 + diff --git a/projects/project3_kenken/stab2/working3x3_1/3x3_2.txt b/projects/project3_kenken/stab2/working3x3_1/3x3_2.txt new file mode 100644 index 0000000..2556aa6 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/3x3_2.txt @@ -0,0 +1,17 @@ +3 +5 +2, ,1 +0,0 +9,*,3 +0,1 +0,2 +1,2 +2,-,2 +1,0 +2,0 +2,/,2 +1,1 +2,1 +2, ,1 +2,2 + diff --git a/projects/project3_kenken/stab2/working3x3_1/3x3_3.txt b/projects/project3_kenken/stab2/working3x3_1/3x3_3.txt new file mode 100644 index 0000000..a844c5b --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/3x3_3.txt @@ -0,0 +1,17 @@ +3 +5 +1,-,2 +0,1 +0,2 +2,-,2 +0,0 +1,0 +2, ,1 +1,1 +3,+,2 +2,0 +2,1 +3,/,2 +1,2 +2,2 + diff --git a/projects/project3_kenken/stab2/working3x3_1/Constraint.java b/projects/project3_kenken/stab2/working3x3_1/Constraint.java new file mode 100644 index 0000000..4d97055 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/Constraint.java @@ -0,0 +1,12 @@ +public class Constraint +{ + public String op; + public Position[] positions; + public int targNumber; + public Constraint(int targNumber,String op,Position[] pos) + { + this.op = op; + positions = pos; + this.targNumber = targNumber; + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/stab2/working3x3_1/KNode.java b/projects/project3_kenken/stab2/working3x3_1/KNode.java new file mode 100644 index 0000000..e82e0e2 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/KNode.java @@ -0,0 +1,18 @@ +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 diff --git a/projects/project3_kenken/stab2/working3x3_1/KStack.java b/projects/project3_kenken/stab2/working3x3_1/KStack.java new file mode 100644 index 0000000..613f9f2 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/KStack.java @@ -0,0 +1,54 @@ +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][4]; + int i = length-1; + for(KNode tmp = head; tmp != null; tmp = tmp.getNext()) + { + output[i] = tmp.getData(); + i--; + } + return output; + } + +} diff --git a/projects/project3_kenken/stab2/working3x3_1/Position.java b/projects/project3_kenken/stab2/working3x3_1/Position.java new file mode 100644 index 0000000..b036299 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/Position.java @@ -0,0 +1,11 @@ +public class Position +{ + public int x; + public int y; + public Position(int x, int y) + { + this.x = x; + this.y = y; + } + +}
\ No newline at end of file diff --git a/projects/project3_kenken/stab2/working3x3_1/Solver.java b/projects/project3_kenken/stab2/working3x3_1/Solver.java new file mode 100644 index 0000000..8c6a5a3 --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/Solver.java @@ -0,0 +1,853 @@ +import java.util.Scanner; +import java.io.*; + +public class Solver +{ + public int[][] puzzle; + public Constraint[] constraints; + public int size; + public Solver(String filename) + { + parsePuzzle(filename); + /*puzzle = new int[3][3]; + constraints = new Constraint[5]; + + Position[] p1 = new Position[1]; + p1[0] = new Position(0,0); + constraints[0] = new Constraint(3," ",p1); + + Position[] p2 = new Position[2]; + p2[0] = new Position(1,0); + p2[1] = new Position(1,1); + constraints[1] = new Constraint(6,"*",p2); + + Position[] p3 = new Position[2]; + p3[0] = new Position(2,0); + p3[1] = new Position(2,1); + constraints[2] = new Constraint(2,"/",p3); + + Position[] p4 = new Position[2]; + p4[0] = new Position(0,1); + p4[1] = new Position(0,2); + constraints[3] = new Constraint(2,"/",p4); + + Position[] p5 = new Position[2]; + p5[0] = new Position(1,2); + p5[1] = new Position(2,2); + constraints[4] = new Constraint(2,"-",p5); + + size = puzzle.length; + */ + //System.out.println("Everything parsed, data is:"); + //System.out.println("Puzzle:"); + //printArray(puzzle); + //System.out.println("Constraints:"); + //printArray(constraints); + //System.out.println("size: " + size); + } + private void parsePuzzle(String filename) + { + Scanner s = null; + try + { + s = new Scanner(new FileInputStream(filename)); + } + catch (Exception e) + { + System.out.println("Something went terribly wrong!\n" + e); + } + size = Integer.parseInt(s.nextLine().replaceAll("\n","")); + + puzzle = new int[size][size]; + + constraints = new Constraint[Integer.parseInt(s.nextLine().replaceAll("\n",""))]; + + //System.out.println("Puzzle size: " + size + " Cages: " + p.length); + for(int i = 0; s.hasNextLine();i++) + { + String t1 = s.nextLine(); + //System.out.println("Praseing: " + t1); + String[] t2 = t1.split(","); + //System.out.println("Parts length: " + t2.length); + if(t2.length > 1) + { + Position[] allcells = new Position[Integer.parseInt(t2[2])]; + for(int j = 0; j < Integer.parseInt(t2[2]);j++) + { + String[] coords = s.nextLine().split(","); + allcells[j] = new Position(Integer.parseInt(coords[1]),Integer.parseInt(coords[0])); + } + constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells); + //System.out.println("Created new constraint(" + Integer.parseInt(t2[0]) + "," + t2[1] + ","); + //printArray(allcells); + /* + for(Position c : allcells) + { + constraints[i] = new Constraint(Integer.parseInt(t2[0]),t2[1],allcells); + } + */ + //p[i] = new KCage(Integer.parseInt(t2[0]),getOp(t2[1]),allcells); + //System.out.println("Created " + p[i]); + } + } + } + public void put(int x, int y, int num) + { + puzzle[x][y] = num; + } + public int remove(int x, int y) + { + int num = puzzle[x][y]; + puzzle[x][y] = 0; + return num; + } + public boolean[] getPossibilities(int x, int y) + { + boolean[] row = getPossibilitiesByRow(y); + boolean[] col = getPossibilitiesByCol(x); + boolean[] cage = getPossibilitiesByCage(x,y); + boolean[] output = new boolean[size]; + for(int i = 0; i < size; i++) + { + if(row[i] && col[i] && cage[i]) + { + output[i] = true; + } + } + //System.out.println("Possibilities for (" + x + "," + y + ") are "); + //printArray(output); + return output; + } + public boolean[] getPossibilitiesByRow(int row) + { + boolean[] possibs = new boolean[size]; + for(int j = 0; j < size; j++) + {//Set all places is possibs to true + possibs[j] = true; + } + //Find all the possibilities + for(int j = 0; j < size; j++) + { //For every other place + if(puzzle[j][row] != 0) + { + //System.out.println("Setting (" + j + "," + row + "): " + puzzle[j][row] + " to false"); + possibs[puzzle[j][row]-1] = false; + } + } + return possibs; + } + public boolean[] getPossibilitiesByCol(int col) + { + boolean[] possibs = new boolean[size]; + for(int j = 0; j < size; j++) + {//Set all places is possibs to true + possibs[j] = true; + } + //Find all the possibilities + for(int j = 0; j < size; j++) + { //For every other place + if(puzzle[col][j] != 0) + { + //System.out.println("Setting (" + col + "," + j + "): " + puzzle[col][j] + " to false"); + possibs[puzzle[col][j]-1] = false; + } + } + return possibs; + } + public boolean[] getPossibilitiesByCage(int x, int y) + { + //System.out.println("Finding cage possibilities on (" + x + "," + y + ")"); + for(Constraint c : constraints) + { + //System.out.println("Testing a constraint: " + c.op); + for(Position p : c.positions) + { + //System.out.println("Found a position in this constraint: (" + p.x + "," + p.y + ")"); + if(p.x == x && p.y == y) + { + System.out.println("Found cell being talked about."); + //We found the cage that's being talked about + if(c.op.equals("+")) + { + //System.out.println("Found op: +"); + return getPossibilitiesByCageAdd(c); + } + else if(c.op.equals("-")) + { + //System.out.println("Found op: -"); + return getPossibilitiesByCageSub(c); + } + else if(c.op.equals("*")) + { + //System.out.println("Found op: *"); + return getPossibilitiesByCageMul(c); + } + else if(c.op.equals("/")) + { + //System.out.println("Found op: /"); + return getPossibilitiesByCageDiv(c); + } + else if(c.op.equals(" ")) + { + //System.out.println("Found op: (NONE)"); + boolean[] output = new boolean[size]; + output[c.targNumber-1] = true; + //System.out.println("Returning:"); + //printArray(output); + return output; + } + else + { + //System.out.println("Bad operator: (" + c.op + ")"); + return null; + } + } + } + } + System.out.println("Something has gone wrong in getPossibilitiesByCage"); + return null; + } + private boolean[] getPossibilitiesByCageAdd(Constraint c) + { + //System.out.println("Getting possibilities for add cage"); + //Try the numbers 1 to size for every square + boolean[] output = new boolean[size]; + int targ = c.targNumber; + //If any of the numbers are already in, subtract them from targ + for(Position p : c.positions) + { + targ -= puzzle[p.x][p.y]; + } + //possibilities are targnumber - 1*# of positions to fill + int numcells = c.positions.length; + int max = targ - numcells; + int min = 1; + for(int i = min; i < max; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageMul(Constraint c) + { + //Numbers can be from 1 to size for this one + //If the target number is odd, only an odd* an odd will work + int targ = c.targNumber; + //If any of the numbers are already in, divide the target by that. + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + //System.out.println("Found a number, useing division shortcut"); + targ /= puzzle[p.x][p.y]; + } + } + boolean[] output = new boolean[size]; + if(c.targNumber % 2 == 1) + { + //System.out.println("Found an odd number, useing odd numbers shortcut"); + for(int i = 1; i < size; i+= 2) + { + output[i-1] = true; + } + return output; + } + for(int i = 1; i < size+1; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageSub(Constraint c) + { + //If one of the items is already in it, find what the other value must be + boolean[] output = new boolean[size]; + int x1 = c.positions[0].x; + int y1 = c.positions[0].y; + int x2 = c.positions[1].x; + int y2 = c.positions[1].y; + if(puzzle[x1][y1] != 0) + { + int onlypossib = 0; + if(c.targNumber > puzzle[x1][y1]) + { + onlypossib = c.targNumber-puzzle[x1][y1]; + } + else if(c.targNumber < puzzle[x1][y1]) + { + onlypossib = puzzle[x1][y1] - c.targNumber; + } + output[onlypossib-1] = true; + return output; + } + if(puzzle[x2][y2] != 0) + { + int onlypossib = 0; + if(c.targNumber>puzzle[x2][y2]) + { + onlypossib = c.targNumber-puzzle[x2][y2]; + } + else if(c.targNumber < puzzle[x2][y2]) + { + onlypossib = puzzle[x2][y2] - c.targNumber; + } + output[onlypossib-1] = true; + return output; + } + //Otherwise, values can be from 1 to targnumber - 2 + for(int i = 1; i < c.targNumber-2; i++) + { + output[i-1] = true; + } + return output; + } + private boolean[] getPossibilitiesByCageDiv(Constraint c) + { + //If one of the items is already in it, find what the other value must be + boolean[] output = new boolean[size]; + int x1 = c.positions[0].x; + int y1 = c.positions[0].y; + int x2 = c.positions[1].x; + int y2 = c.positions[1].y; + if(puzzle[x1][y1] != 0) + { + int onlypossib = c.targNumber/puzzle[x1][y1]; + output[onlypossib-1] = true; + return output; + } + if(puzzle[x2][y2] != 0) + { + int onlypossib = c.targNumber/puzzle[x2][y2]; + output[onlypossib-1] = true; + return output; + } + //Otherwise, values can be from 1 to targnumber + for(int i = 1; i < c.targNumber+1; i++) + { + output[i-1] = true; + } + return output; + } + public boolean isSolved() + { + boolean tr = testRows(); + boolean tc = testCols(); + boolean ta = testCages(); + //System.out.println("Checking for solution(Rows: " + tr + ")(Cols: " + tc + ")(Cages: " + ta+"):"); + //printArray(puzzle); + if(!testRows() || !testCols() || !testCages()) + { + return false; + } + return true; + } + private boolean testCages() + { + for(Constraint c : constraints) + { + if(!testConstraint(c)) + { + return false; + } + } + return true; + } + private boolean testConstraint(Constraint c) + { + if(c.op.equals("+")) + { + int sum = 0; + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + sum += puzzle[p.x][p.y]; + } + else + { + return false; + } + } + if(sum == c.targNumber) + { + return true; + } + else + { + //System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + //printArray(c.positions); + return false; + } + } + else if(c.op.equals("-")) + { + Position p1 = c.positions[0]; + Position p2 = c.positions[1]; + if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0) + { + int num1 = puzzle[p1.x][p1.y]; + int num2 = puzzle[p2.x][p2.y]; + if(num1 - num2 == c.targNumber) + { + return true; + } + if(num2 - num1 == c.targNumber) + { + return true; + } + } + else + { + //System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + //printArray(c.positions); + return false; + } + return false; + } + else if(c.op.equals("*")) + { + int product = 1; + for(Position p : c.positions) + { + if(puzzle[p.x][p.y] != 0) + { + product *= puzzle[p.x][p.y]; + } + else + { + return false; + } + } + if(product == c.targNumber) + { + return true; + } + else + { + //System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + //printArray(c.positions); + //System.out.println("Product is " + product); + return false; + } + } + else if(c.op.equals("/")) + { + Position p1 = c.positions[0]; + Position p2 = c.positions[1]; + if(puzzle[p1.x][p1.y] != 0 && puzzle[p2.x][p2.y] != 0) + { + double num1 = puzzle[p1.x][p1.y]; + double num2 = puzzle[p2.x][p2.y]; + if(num1 / num2 == c.targNumber) + { + return true; + } + if(num2 / num1 == c.targNumber) + { + return true; + } + } + else + { + //System.out.println("Failed on constraint:("+c.targNumber+","+c.op+","); + //printArray(c.positions); + return false; + } + return false; + } + else if(c.op.equals(" ")) + { + int x = c.positions[0].x; + int y = c.positions[0].y; + if(puzzle[x][y] == c.targNumber) + { + return true; + } + else + { + return false; + } + } + //System.out.println("Something went wrong in testConstraint"); + return false; + } + private boolean testCols() + { + for(int i = 0; i < size; i++) + { + boolean[] uniqueCols = new boolean[size]; + for(int j = 0; j < size; j++) + { + if(puzzle[i][j] == 0) + { + return false; + } + uniqueCols[puzzle[i][j]-1] = true; + } + for(int j = 0; j < uniqueCols.length; j++) + { + if(!uniqueCols[j]) + { + return false; + } + } + } + //System.out.println("Something went wrong in testCols!"); + return true; + } + private boolean testRows() + { + for(int i = 0; i < size; i++) + { + boolean[] uniqueRows = new boolean[size]; + for(int j = 0; j < size; j++) + { + if(puzzle[j][i] == 0) + { + return false; + } + uniqueRows[puzzle[j][i]-1] = true; + } + for(int j = 0; j < uniqueRows.length; j++) + { + if(!uniqueRows[j]) + { + return false; + } + } + } + //System.out.println("Something went wrong in testRows"); + return true; + } + public int[][] implyByRows() + { + //System.out.println("Implying by rows..."); + int[][][] output = new int[size][4][size]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { + //System.out.println("Calling imply row helper on row " + i); + output[i] = implyByRowsHelper(i); + if(output[i].length > 0) + { + numImplyed++; + } + } + int[][] realoutput = new int[numImplyed][4]; + int j = 0; + for(int i = 0; i < numImplyed;i++) + { + if(output[i].length > 0) + { + realoutput[j] = output[i][0]; + j++; + } + } + return realoutput; + } + public int[][] implyByCols() + { + //System.out.println("Implying by cols..."); + int[][][] output = new int[size][4][size]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { + //System.out.println("Calling imply col helper on col " + i); + output[i] = implyByColsHelper(i); + if(output[i].length > 0) + { + numImplyed++; + } + } + int[][] realoutput = new int[numImplyed][4]; + int j = 0; + for(int i = 0; i < numImplyed;i++) + { + if(output[i].length > 0) + { + realoutput[j] = output[i][0]; + j++; + } + } + return realoutput; + } + public int[][] implyByCages() + { + //System.out.println("Implying by cages"); + int[][][][] output = new int[size][size][4][size]; + int numImplyed = 0; + //We should only be implying ONE number max! + for(int x = 0; x < size; x++) + { + for(int y = 0; y < size; y++) + { + //Scan for a num that has only 1 possibility + output[x][y] = implyByCagesHelper(x,y); + //System.out.println("Attempted to imply by cages on (" + x + "," + y + "):"); + //printArray(output[x][y]); + if(output[x][y].length == 1) + { + //numImplyed++; + //System.out.println("Implything by cage. returning:"); + //printArray(output[x][y]); + return output[x][y]; + } + else + { + //System.out.println("Unable to imply"); + } + } + } + //System.out.println("Unable to imply ANYTHING"); + int[][] realoutput = new int[0][0]; + return realoutput; + /* + int[][] realoutput = new int[1][4]; + int track = 0; + if(output.length == 1) + { + realoutput[0] = output[x][y][0]; + return realoutput; + } + */ + } + public int[][] implyByCagesHelper(int x, int y) + { + int[][] realoutput = new int[size][4]; + //System.out.println("Implying on cage(" + x + "," + y + ")"); + int[][] output = new int[size][4]; + if(puzzle[x][y] != 0) + { + //This square already has a number in it. + } + else + { + boolean[] possibs = getPossibilitiesByCage(x,y); + //System.out.println("Got possibilities:"); + //printArray(possibs); + int j = 0; + int numtrue = 0; + for(boolean b : possibs) + { + if(b) + { + numtrue++; + } + } + if(numtrue == 1) + { + for(int i = 0; i < possibs.length;i++) + { + if(possibs[i]) + { + realoutput = new int[1][4]; + puzzle[x][y] = i+1; + realoutput[j][0] = 0; + realoutput[j][1] = x; + realoutput[j][2] = y; + realoutput[j][3] = i; + return realoutput; + } + } + } + } + return realoutput; + } + private int[][] implyByRowsHelper(int row) + { + //System.out.println("Implying on row " + row); + //boolean[] places = new boolean[size]; + //Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num) + //this method may output more than 1 implyed number. + int[][] output = new int[size][4]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { //For each square + //This place already has something + if(puzzle[i][row] != 0) + { + //System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]); + } + else + { + boolean[] possibs = getPossibilitiesByRow(row); + //System.out.println("Possibilities for (" + i + "," + row + ") are:"); + //printArray(possibs); + //Find out how many possibilites for this place is true + int numtrue = 0; + int lasttrue = 0; + for(int j = 0; j < size;j++) + { + if(possibs[j]) + { + numtrue++; + lasttrue = j+1; + } + } + if(numtrue == 1) + { + puzzle[i][row] = lasttrue; + output[numImplyed][0] = 0; + output[numImplyed][1] = i; + output[numImplyed][2] = row; + output[numImplyed][3] = lasttrue; + numImplyed++; + } + } + } + //System.out.println("First output is : "); + //printArray(output); + int[][] realoutput = new int[numImplyed][4]; + for(int i = 0; i < numImplyed; i++) + { + realoutput[i] = output[i]; + } + //System.out.println("Real output is : "); + //printArray(realoutput); + return realoutput; + } + private int[][] implyByColsHelper(int col) + { + // System.out.println("Implying on row " + row); + //boolean[] places = new boolean[size]; + //Outputs all numbers that should go on the stack, each number is in the form (0,x,y,num) + //this method may output more than 1 implyed number. + int[][] output = new int[size][4]; + int numImplyed = 0; + for(int i = 0; i < size; i++) + { //For each square + //This place already has something + if(puzzle[col][i] != 0) + { + //System.out.println("(" + i + "," + row + ") already has " + puzzle[i][row]); + } + else + { + boolean[] possibs = getPossibilitiesByCol(col); + //System.out.println("Possibilities for (" + col + "," + i + ") are:"); + //printArray(possibs); + //Find out how many possibilites for this place is true + int numtrue = 0; + int lasttrue = 0; + for(int j = 0; j < size;j++) + { + if(possibs[j]) + { + numtrue++; + lasttrue = j+1; + } + } + if(numtrue == 1) + { + puzzle[col][i] = lasttrue; + output[numImplyed][0] = 0; + output[numImplyed][1] = col; + output[numImplyed][2] = i; + output[numImplyed][3] = lasttrue; + numImplyed++; + } + } + } + //System.out.println("First output is : "); + //printArray(output); + int[][] realoutput = new int[numImplyed][4]; + for(int i = 0; i < numImplyed; i++) + { + realoutput[i] = output[i]; + } + //System.out.println("Real output is : "); + //printArray(realoutput); + return realoutput; + } + public void printPuzzle() + { + for(int y = 0; y < puzzle.length; y++) + { + for(int x = 0; x < puzzle[y].length; x++) + { + System.out.print(puzzle[x][y] + " "); + } + System.out.print("\n"); + } + } + public void printArray(int[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[" + arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("," + arr[i]); + } + System.out.print("]\n"); + } + public void printArray(int[][] arr) + { + if(arr.length == 0) + { + System.out.println("[[]]"); + return; + } + System.out.print("[\t"); + printArray(arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("\t"); + printArray(arr[i]); + } + System.out.print("]\n"); + + } + public void printArray(boolean[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[" + arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("," + arr[i]); + } + System.out.print("]\n"); + } + public void printArray(Position[] arr) + { + if(arr.length == 0) + { + System.out.println("[]"); + return; + } + System.out.print("[(" + arr[0].x + "," + arr[0].y + ")"); + for(int i = 1; i < arr.length; i++) + { + System.out.print(",(" + arr[i].x + "," + arr[i].y + ")"); + } + System.out.print("]\n"); + } + public void printArray(Constraint[] arr) + { + if(arr.length == 0) + { + System.out.println("[[]]"); + return; + } + System.out.print("[\t"); + printArray(arr[0]); + for(int i = 1; i < arr.length; i++) + { + System.out.print("\t"); + printArray(arr[i]); + } + System.out.print("]\n"); + } + public void printArray(Constraint c) + { + System.out.print("(" + c.op + "," + c.targNumber + ","); + printArray(c.positions); + } +}
\ No newline at end of file diff --git a/projects/project3_kenken/stab2/working3x3_1/kenkensolver.java b/projects/project3_kenken/stab2/working3x3_1/kenkensolver.java new file mode 100644 index 0000000..d141d3f --- /dev/null +++ b/projects/project3_kenken/stab2/working3x3_1/kenkensolver.java @@ -0,0 +1,159 @@ + +import java.util.Scanner; +import java.io.*; +import java.awt.*; +import javax.swing.*; +public class kenkensolver +{ + public static boolean done = false; + public static void main(String args[]) throws IOException + { + String puzzlefile = ""; + System.out.println("Enter file:"); + Scanner scanner = new Scanner(new InputStreamReader(System.in)); + while(puzzlefile.equals("")) + { + String input = scanner.nextLine(); + File f = new File(input); + if(f.exists() && !f.isDirectory()) + { + puzzlefile = input; + } + else + { + System.out.println("Could not find file, please try again:"); + } + } + 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(); + JFrame frame = new JFrame(); + KenKenComponent kc = new KenKenComponent(puzzlefile, frame); + kc.setNumber(s.puzzle); + } + 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; + } + } + } + if(lastx != -1 && lasty != -1) + { + int[] guess = new int[4]; + boolean[] possibilities = s.getPossibilities(lastx,lasty); + 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 |
