From 89cdf3efb49335e7c07a68a5a64657eeec2288a6 Mon Sep 17 00:00:00 2001 From: Alexander Pickering Date: Mon, 6 Feb 2017 11:41:36 -0500 Subject: Inital commit --- .../project3_kenken/stab2/working3x3_1/3x3_1.txt | 17 + .../project3_kenken/stab2/working3x3_1/3x3_2.txt | 17 + .../project3_kenken/stab2/working3x3_1/3x3_3.txt | 17 + .../stab2/working3x3_1/Constraint.java | 12 + .../project3_kenken/stab2/working3x3_1/KNode.java | 18 + .../project3_kenken/stab2/working3x3_1/KStack.java | 54 ++ .../stab2/working3x3_1/Position.java | 11 + .../project3_kenken/stab2/working3x3_1/Solver.java | 853 +++++++++++++++++++++ .../stab2/working3x3_1/kenkensolver.java | 159 ++++ 9 files changed, 1158 insertions(+) create mode 100644 projects/project3_kenken/stab2/working3x3_1/3x3_1.txt create mode 100644 projects/project3_kenken/stab2/working3x3_1/3x3_2.txt create mode 100644 projects/project3_kenken/stab2/working3x3_1/3x3_3.txt create mode 100644 projects/project3_kenken/stab2/working3x3_1/Constraint.java create mode 100644 projects/project3_kenken/stab2/working3x3_1/KNode.java create mode 100644 projects/project3_kenken/stab2/working3x3_1/KStack.java create mode 100644 projects/project3_kenken/stab2/working3x3_1/Position.java create mode 100644 projects/project3_kenken/stab2/working3x3_1/Solver.java create mode 100644 projects/project3_kenken/stab2/working3x3_1/kenkensolver.java (limited to 'projects/project3_kenken/stab2/working3x3_1') 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 -- cgit v1.2.3-70-g09d2