From 79e831829544b347269ffd72a2d0ab4ec0e180ef Mon Sep 17 00:00:00 2001 From: stephey Date: Sat, 10 Apr 2010 05:59:51 +0000 Subject: [PATCH] Modified my core code to be able to compile under "make single" Notes: -Compiler does not do as many int/Integer impicit-casts as the Java compiler; result is much time spent following compiler errors to fix casting ambiguities -ArrayList.java is ported from the Java library with Exceptions removed and only retains roughly half the built-in functions. Future Plans: -Impelment parsing and writing files to gain farmiliarity with using I/O. --- Robust/src/Tests/mlp/stephen/ArrayList.java | 16 +- Robust/src/Tests/mlp/stephen/Board.java | 349 ++++++++++++++++++ Robust/src/Tests/mlp/stephen/BoxLocation.java | 40 ++ .../Tests/mlp/stephen/PossibleNumbers.java | 106 ++++++ Robust/src/Tests/mlp/stephen/Solver.java | 61 +++ Robust/src/Tests/mlp/stephen/Test.java | 105 ++++++ 6 files changed, 676 insertions(+), 1 deletion(-) create mode 100644 Robust/src/Tests/mlp/stephen/Board.java create mode 100644 Robust/src/Tests/mlp/stephen/BoxLocation.java create mode 100644 Robust/src/Tests/mlp/stephen/PossibleNumbers.java create mode 100644 Robust/src/Tests/mlp/stephen/Solver.java create mode 100755 Robust/src/Tests/mlp/stephen/Test.java diff --git a/Robust/src/Tests/mlp/stephen/ArrayList.java b/Robust/src/Tests/mlp/stephen/ArrayList.java index 5234d907..e1e6df78 100644 --- a/Robust/src/Tests/mlp/stephen/ArrayList.java +++ b/Robust/src/Tests/mlp/stephen/ArrayList.java @@ -135,7 +135,6 @@ public class ArrayList int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { - Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; @@ -194,6 +193,21 @@ public class ArrayList } } + /** + * Returns a shallow copy of this ArrayList instance. (The + * elements themselves are not copied.) + * + * @return a clone of this ArrayList instance + */ + public ArrayList clone() + { + ArrayList clone = new ArrayList(this.size + 1); + systemArrayCopy(this.elementData, 0, clone.elementData, 0, this.size); + + clone.size = this.size; + + return clone; + } /** * Removes the element at the specified position in this list. diff --git a/Robust/src/Tests/mlp/stephen/Board.java b/Robust/src/Tests/mlp/stephen/Board.java new file mode 100644 index 00000000..80b15e11 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/Board.java @@ -0,0 +1,349 @@ + +public class Board +{ + private PossibleNumbers[][] board; + private boolean changesWereMade; + private boolean Error; //added to replace throwing Exceptions + + //attempts to solve the thing + // if is incomplete at the end of solving routine, will return false + public boolean solve() + { + do + { + //resets the flag to begin with + reset(); + + singlePass(); + if(Error) return false; + } + while(!isDone()); + + //if it's done, it's done... + return isComplete(); + + } + + /** + * This function eliminates used possibilities already and was originally + * intended for the "solve()" function. However, when used only once by itself, + * it can be used to check for duplicates without additional code. + */ + public void singlePass() + { + //Didn't use to be this messy, but this is how I fixed errors being thrown + checkRows(); + if(Error) return; + + checkColumns(); + if(Error) return; + + checkBoxes(); + if(Error) return; + } + + //used for cloning + private Board(PossibleNumbers[][] array) + { + changesWereMade = false; + board = array; + Error = false; + } + + public Board(int[][] input) + { + board = new PossibleNumbers[9][9]; + + for(int row = 0; row < 9; row++) + { + for(int column = 0; column < 9; column++) + { + if(input[row][column] != 0) + { + board[row][column] = new PossibleNumbers(input[row][column]); + } + else + { + board[row][column] = new PossibleNumbers(); + } + } + } + + Error = false; + changesWereMade = false; + + } + + public void checkRows() + { + for(int row = 0; row < 9; row ++) + { + //stores the numbers that we know are true already... + ArrayList numbersDone = new ArrayList(); + ArrayList pointData = new ArrayList(); + + //this for grabs the elements done + for(int element = 0; element < 9; element++) + { + if(board[row][element].considerable()) + { + numbersDone.add(board[row][element].getNum()); + pointData.add(new BoxLocation(row, element)); + changesWereMade = true; + } + } + + checkDuplicates(numbersDone, pointData); + if(hasError()) return; + + //these for loops eliminates them... + for(int index = 0; index < numbersDone.size(); index++) + { + Integer i = (Integer) numbersDone.get(index); + for(int element = 0; element < 9; element++) + { + if(!board[row][element].remove(i)) + { + this.setError(); + return; + } + } + } + + } + } + + public void checkColumns() + { + for(int column = 0; column < 9; column ++) + { + //stores the numbers that we know are true already... + ArrayList numbersDone = new ArrayList(); + ArrayList pointData = new ArrayList(); + + //this for grabs the elements done + for(int element = 0; element < 9; element++) + { + if(board[element][column].considerable()) + { + numbersDone.add(board[element][column].getNum()); + pointData.add(new BoxLocation(element, column)); + changesWereMade = true; + } + } + + checkDuplicates(numbersDone, pointData); + if(hasError()) return; + + //these for loops eliminates them... + for(int index = 0; index < numbersDone.size(); index++) + { + Integer i = (Integer) numbersDone.get(index); + for(int element = 0; element < 9; element++) + { + if(!board[element][column].remove(i)) + { + setError(); + return; + } + } + } + + } + } + + public void checkBoxes() + { + for(int boxRow = 0; boxRow <= 6; boxRow += 3) + { + for(int boxColumn = 0; boxColumn <= 6; boxColumn += 3) + { + checkBoxesHelper(boxRow, boxColumn); + if(hasError()) return; + } + } + } + + public void checkBoxesHelper(int startingRow, int startingColumn) + { + //stores elements to be removed... + ArrayList numbersDone = new ArrayList(); + ArrayList pointData = new ArrayList(); + + //checks for elements to be checked for + for(int row = startingRow; row < (3 + startingRow); row++) + { + for(int column = startingColumn; column < (3 + startingColumn); column++) + { + if(board[row][column].considerable()) + { + numbersDone.add(board[row][column].getNum()); + pointData.add(new BoxLocation(row, column)); + changesWereMade = true; + } + } + } + + + //checks for duplicates + checkDuplicates(numbersDone, pointData); + if(hasError()) return; + + //removes those elements + for(int index = 0; index < numbersDone.size(); index++) + { + Integer i = (Integer) numbersDone.get(index); + for(int row = startingRow; row < (3 + startingRow); row++) + { + for(int column = startingColumn; column < (3 + startingColumn); column++) + { + if(!board[row][column].remove(i)) + { + setError(); + return; + } + } + } + } + } + + public void reset() + { + changesWereMade = false; + } + + public boolean isDone() + { + return !changesWereMade; + } + + public boolean isComplete() + { + //searches through all elements to make sure they're done + for(int row = 0; row < 9; row++) + { + for(int column = 0; column < 9; column++) + { + if(!(board[row][column].isDone())) + { + return false; + } + } + } + + return true; + } + + public int[][] getArray() + { + int[][] result = new int[9][9]; + + for(int row = 0; row < 9; row++) + for(int column = 0; column < 9; column++) + result[row][column] = board[row][column].getNumNoTouch(); + + return result; + } + + public String toString() + { + String finalString = ""; + int[][] array = getArray(); + + + for(int row = 0; row < 9; row++) + { + for(int column = 0; column < 9; column++) + { + char outputChar = (char)(array[row][column] + 48) ; + + //replaces 0 with ? + if(outputChar == 48) + outputChar = '?'; + + finalString += " " + outputChar; + + //inserts pipes to separate them. + if(column == 2 || column == 5) + { + finalString += " |"; + } + } + + //inserts a row of awesomeness + if(row == 2 || row == 5) + { + finalString += "\n ---------------------"; + } + + //new line + finalString += "\n"; + } + + return finalString; + } + + public Board clone() + { + PossibleNumbers[][] newBoard = new PossibleNumbers[9][9]; + + //clones all the elements in the old board... + for(int row = 0; row < 9; row++) + { + for(int column = 0; column < 9; column++) + { + newBoard[row][column] = board[row][column].clone(); + } + } + + return new Board(newBoard); + } + + public void checkDuplicates(ArrayList array, ArrayList point) + { + //there's no need to check if there's only 1 element in here... + if(array.size() > 1) + { + //the last object doesn't need to checked against anything else + for(int element = 0; element < (array.size() - 1); element++) + { + //+ 1 because the element should not check against itself + for(int x = element + 1; x < array.size(); x++) + { + //Here's a bug that took an hour to find because of not auto-casting. + if(((Integer)array.get(element)).intValue() == ((Integer) array.get(x)).intValue()) + { + //System.out.println("FATAL ERROR WOULD HAVE BEEN THROWN: Duplicate item at " + point.get(element)); + this.setError(); + return; + } + } + } + } + } + + public ArrayList getEmptyBoxes() + { + //stores remaining empty boxes + ArrayList list = new ArrayList(); + + for(int row = 0; row < 9; row++) + for(int column = 0; column < 9; column++) + if(!board[row][column].isDone()) + list.add(board[row][column]); + + + return list; + } + + private void setError() + { + Error = true; + } + + public boolean hasError() + { + return Error; + } +} + diff --git a/Robust/src/Tests/mlp/stephen/BoxLocation.java b/Robust/src/Tests/mlp/stephen/BoxLocation.java new file mode 100644 index 00000000..497087c3 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/BoxLocation.java @@ -0,0 +1,40 @@ + +public class BoxLocation +{ + int row; + int column; + ArrayList array; + + public BoxLocation(int row, int column) + { + this.row = row; + this.column = column; + } + + private BoxLocation(int row, int column, ArrayList array) + { + this.row = row; + this.column = column; + this.array = array; + } + public String toString() + { + return "row " + (row + 1) + " column " + (column + 1); + } + + public int getRow() + { + return row; + } + + public int getColumn() + { + return column; + } + + public BoxLocation clone() + { + return new BoxLocation(row, column, (ArrayList) array.clone()); + } + +} diff --git a/Robust/src/Tests/mlp/stephen/PossibleNumbers.java b/Robust/src/Tests/mlp/stephen/PossibleNumbers.java new file mode 100644 index 00000000..7852f3d0 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/PossibleNumbers.java @@ -0,0 +1,106 @@ + +public class PossibleNumbers +{ + //would usually be set to 3 and that is done in the constructor + private int maxLookups; + + private ArrayList nums; + //this makes it so we don't have to reconsider numbers we've already searched... + private int timesTouched; + + public PossibleNumbers() + { + maxLookups = 3; + + nums = new ArrayList(); + for(int x = 1; x <= 9; x++) + nums.add(new Integer(x)); + + timesTouched = 0; + } + + public PossibleNumbers(int num) + { + maxLookups = 3; + + nums = new ArrayList(); + nums.add(new Integer(num)); + + timesTouched = 0; + } + + //private cloner + private PossibleNumbers(ArrayList array, int touched) + { + maxLookups = 3; + + nums = (ArrayList) array.clone(); + //reset counter to have everything in again... + //potentially triples the solving time but it will fix all + //known errors + timesTouched = 0; + } + + public boolean isDone() + { + return (nums.size() == 1); + } + + //this will be called before every search... + public boolean considerable() + { + return (isDone() && timesTouched <= maxLookups); + } + + + public Integer getNum() + { + timesTouched++; + return (Integer) nums.get(0); + } + + public int getNumNoTouch() + { + if(isDone()) + { + return ((Integer) nums.get(0)).intValue(); + } + + return 0; + } + + //Changed from void to boolean to account for board failures + public boolean remove(Integer num) + { + if(!isDone()) + { + nums.remove(num); + } + + if(nums.size() < 1) + { + //System.out.println("AN ERROR WOULD NORMALLY BE THROWN HERE; invalid remove preformed in PossibleNumbers.remove"); + return false; + } + return true; + } + + //this is used to clone the object + public PossibleNumbers clone() + { + return new PossibleNumbers(nums, timesTouched); + } + + public ArrayList getArray() + { + return nums; + } + + public void setPossibility(Integer i) + { + nums = new ArrayList(); + nums.add(i); + //that way it can be reconsidered... + timesTouched = 0; + } +} diff --git a/Robust/src/Tests/mlp/stephen/Solver.java b/Robust/src/Tests/mlp/stephen/Solver.java new file mode 100644 index 00000000..a9cab4f3 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/Solver.java @@ -0,0 +1,61 @@ + +public class Solver +{ + public static Board go(Board boardIn) +// throws FatalError //thrown when the first board fails + { + //makes sure we dont mess with the recursive boardness... + Board board = boardIn.clone(); + + //Try to solve and if there are are errors than abort the current try + if(!board.solve() && !board.hasError()) + { + //clones the board + Board clone = board.clone(); + //gets the possible numbers from cloned board + ArrayList possible = clone.getEmptyBoxes(); + + //for every element in possible numbers. + for(int j = 0; j < possible.size(); j++) + { + PossibleNumbers pn = (PossibleNumbers) possible.get(j); + + //saves the current edition of possibleNumbers for after testing it out. + PossibleNumbers revert = pn.clone(); + //get their cloned ArrayList of Numbers + ArrayList tryNumbers = pn.getArray(); + + //for all the elements in the ArrayList of numbers + for(int k = 0; k < tryNumbers.size(); k ++) + { + Integer i = (Integer) tryNumbers.get(k); + pn.setPossibility(i); + +// try + { + Board boardStacked = go(clone); + + //if they're not equal, that means it worked! + if(boardStacked.isComplete() && !boardStacked.hasError()) + return boardStacked; + } +// catch (Exception e) +// +// { +// //I don't care if a step in fails... +// //this just means we tried an invalid number +// } + } + + //reverts it back to the previous PossibleNumber before the changes... + pn = revert; + + } + //return empty if it fails... + return board; + } + else + return board; + } + +} diff --git a/Robust/src/Tests/mlp/stephen/Test.java b/Robust/src/Tests/mlp/stephen/Test.java new file mode 100755 index 00000000..d76e7d91 --- /dev/null +++ b/Robust/src/Tests/mlp/stephen/Test.java @@ -0,0 +1,105 @@ +public class Test +{ + public Test(){} + + public static void main(String args[]) { + + System.out.println("# it starts"); + Test t = new Test(); + t.doSomeWork(); + + } + + public void doSomeWork() + { + + //hard-coded in board solution: http://www.websudoku.com/?level=4&set_id=1031120945 + int[][] puzzle = new int[9][9]; + puzzle[0][0] = 3; + puzzle[0][1] = 0; + puzzle[0][2] = 6; + puzzle[0][3] = 0; + puzzle[0][4] = 0; + puzzle[0][5] = 8; + puzzle[0][6] = 0; + puzzle[0][7] = 0; + puzzle[0][8] = 4; + puzzle[1][0] = 0; + puzzle[1][1] = 0; + puzzle[1][2] = 0; + puzzle[1][3] = 4; + puzzle[1][4] = 0; + puzzle[1][5] = 0; + puzzle[1][6] = 0; + puzzle[1][7] = 0; + puzzle[1][8] = 0; + puzzle[2][0] = 0; + puzzle[2][1] = 0; + puzzle[2][2] = 9; + puzzle[2][3] = 0; + puzzle[2][4] = 0; + puzzle[2][5] = 0; + puzzle[2][6] = 6; + puzzle[2][7] = 2; + puzzle[2][8] = 0; + puzzle[3][0] = 0; + puzzle[3][1] = 0; + puzzle[3][2] = 0; + puzzle[3][3] = 0; + puzzle[3][4] = 3; + puzzle[3][5] = 0; + puzzle[3][6] = 0; + puzzle[3][7] = 6; + puzzle[3][8] = 5; + puzzle[4][0] = 8; + puzzle[4][1] = 0; + puzzle[4][2] = 0; + puzzle[4][3] = 1; + puzzle[4][4] = 0; + puzzle[4][5] = 2; + puzzle[4][6] = 0; + puzzle[4][7] = 0; + puzzle[4][8] = 7; + puzzle[5][0] = 5; + puzzle[5][1] = 3; + puzzle[5][2] = 0; + puzzle[5][3] = 0; + puzzle[5][4] = 6; + puzzle[5][5] = 0; + puzzle[5][6] = 0; + puzzle[5][7] = 0; + puzzle[5][8] = 0; + puzzle[6][0] = 0; + puzzle[6][1] = 7; + puzzle[6][2] = 2; + puzzle[6][3] = 0; + puzzle[6][4] = 0; + puzzle[6][5] = 0; + puzzle[6][6] = 1; + puzzle[6][7] = 0; + puzzle[6][8] = 0; + puzzle[7][0] = 0; + puzzle[7][1] = 0; + puzzle[7][2] = 0; + puzzle[7][3] = 0; + puzzle[7][4] = 0; + puzzle[7][5] = 1; + puzzle[7][6] = 0; + puzzle[7][7] = 0; + puzzle[7][8] = 0; + puzzle[8][0] = 9; + puzzle[8][1] = 0; + puzzle[8][2] = 0; + puzzle[8][3] = 2; + puzzle[8][4] = 0; + puzzle[8][5] = 0; + puzzle[8][6] = 7; + puzzle[8][7] = 0; + puzzle[8][8] = 6; + Board b = new Board(puzzle); + Board solved = Solver.go(b); + + System.out.println(solved); + } + +} -- 2.34.1