我寫一個java程序來解決棘手的三角形(方格像一個三角形遊戲 - Here are the rules,和繼承人的圖片)的Java併發修改遞歸行爲
該項目工程通過所有可能的行動作用中,遞歸使得移動,然後迭代新的可能移動等等,直到找到基本情況。
基座情況如下:
- 的可能的移動數量= 0
我的代碼
修訂版(2017年2月26日)來解決併發修改錯誤 public int stackSolve(三角形inputTriangle,Stack stackIn,int depth)引發InvalidArgumentException {
System.out.println("in stackSolve(). current Triangle: ");
inputTriangle.printTriangle();
if (inputTriangle.possibleMoves.size() ==0){
System.out.println("num possible moves: 0");
if (inputTriangle.nonNonEmptySpots() == 1){
System.out.println("Winning solution found.");
return 1;
}
else{
System.out.println("non winning solution found. Going higher in recursion tree");
return 0;
}
}
else{
System.out.println("Number of moves: "+inputTriangle.possibleMoves.size());
for (Move mv : inputTriangle.possibleMoves){
System.out.println("Making move : "+mv.toString());
inputTriangle.makeMove(mv);
System.out.println("move made");
stackIn.push(mv);
System.out.println("entering deeper in recursion tree, calling stackSolve on triangle");
stackSolve(inputTriangle,stackIn,depth+1);
System.out.println("undoing move: "+mv);
stackIn.pop();
inputTriangle.undoMove(mv);
System.out.println("MOVE UNDONE");
}
System.out.println("EXITED FOR LOOP");
return 0;
}
我一直在通過可能的舉動反覆出現奇怪的行爲。遞歸層n正在進行第一次移動,遞歸到遞歸層n + 1中,但是當程序返回到層n時,而不是繼續遍歷剩餘的可能移動,程序進入層n-1。如果有人能讓我知道爲什麼會發生這種情況,我會很感激。
這裏是我的代碼的輸出:
in stackSolve(). current Triangle:
-
2 3
4 5 6
Number of moves: 2
Making move : MOVE object: from:4 | mid: 2 | to: 1
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
1
- 3
- 5 6
Number of moves: 1
Making move : MOVE object: from:6 | mid: 5 | to: 4
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
1
- 3
4 - -
Number of moves: 1
Making move : MOVE object: from:1 | mid: 3 | to: 6
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
-
- -
4 - 6
num possible moves: 0
non winning solution found. Going higher in recursion tree
undoing move: MOVE object: from:1 | mid: 3 | to: 6
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:6 | mid: 5 | to: 4
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:4 | mid: 2 | to: 1
MOVE UNDONE
Making move : MOVE object: from:6 | mid: 3 | to: 1
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
1
2 -
4 5 -
Number of moves: 1
Making move : MOVE object: from:4 | mid: 5 | to: 6
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
1
2 -
- - 6
Number of moves: 1
Making move : MOVE object: from:1 | mid: 2 | to: 4
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle:
-
- -
4 - 6
num possible moves: 0
non winning solution found. Going higher in recursion tree
undoing move: MOVE object: from:1 | mid: 2 | to: 4
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:4 | mid: 5 | to: 6
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:6 | mid: 3 | to: 1
MOVE UNDONE
EXITED FOR LOOP
Triangle of Size: 6 solved in: -1.0 seconds
這裏是三角類 - 很長
private double aColCoef = 1.0/8.0;
private double bColCoef = 1.0/2.0;
private double cColVal = 3.0/8.0;
private double aRowCoef = 1.0/2;
private double bRowCoef = 1.0/2;
private double cRowVal = 0.0;
private String emptySpotChar = "-";
private int numSpacesInPrint = 2;
public int numPieces;
private int initialEmptySpot;
private int numCols;
public int maxRows;
public ArrayList<Position> positions;
public ArrayList<Move> possibleMoves;
public Triangle(int numPieces, int initialEmptySpot) throws InvalidArgumentException {
if (this.isValidNumPieces(numPieces)){
this.numPieces = numPieces;
this.initialEmptySpot = initialEmptySpot;
this.numCols = solveQuadratic(this.aColCoef,this.bColCoef, (this.cColVal - numPieces));
this.maxRows = solveQuadratic(this.aRowCoef,this.bRowCoef, this.cRowVal- numPieces);
this.positions = getPositions(this.numPieces,initialEmptySpot);
this.possibleMoves = new ArrayList<Move>();
setPossibleMoves();
}
else{
throw new InvalidArgumentException("Number of Pieces Invalid");
}
}
public Triangle(int numPieces, ArrayList<Integer> emptySpots) throws InvalidArgumentException {
if (this.isValidNumPieces(numPieces)){
this.numPieces = numPieces;
this.initialEmptySpot = initialEmptySpot;
this.numCols = solveQuadratic(this.aColCoef,this.bColCoef, (this.cColVal - numPieces));
this.maxRows = solveQuadratic(this.aRowCoef,this.bRowCoef, this.cRowVal- numPieces);
this.positions = getPositions(this.numPieces,emptySpots);
this.possibleMoves = new ArrayList<Move>();
setPossibleMoves();
}
else{
throw new InvalidArgumentException("Number of Pieces Invalid");
}
}
private ArrayList<Position> getPositions(int numPieces, ArrayList<Integer> emptySpots) throws InvalidArgumentException {
ArrayList<Position> returnPositions = new ArrayList<Position>();
for (int i = 1; i <= numPieces; i++){
boolean emptySpot = false;
for (Integer j : emptySpots){
if (j.intValue() == i){
emptySpot = true;
}
}
if (emptySpot){
returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),true,i));
}
else {
returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),false,i));
}
}
return returnPositions;
}
private void setPossibleMoves() {
possibleMoves.clear();
for (int i = 0; i < this.positions.size(); i ++){
positions.get(i).setPossibleMoveSpots();
}
for (Position pos : positions){
this.possibleMoves.addAll(pos.getMoves());
}
}
private ArrayList<Position> getPositions(int numPieces,int initEmptySpot) throws InvalidArgumentException {
ArrayList<Position> returnPositions = new ArrayList<Position>();
for (int i = 1; i <= numPieces; i++){
if (i == initEmptySpot){
returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),true,i));
}
else {
returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),false,i));
}
}
return returnPositions;
}
public void makeMove(Move mv){
mv.makeMove();
setPossibleMoves();
}
public void makeMove(int mv){
possibleMoves.get(mv).makeMove();
setPossibleMoves();
}
static int getMidValue(int x1, int x2) {
return (int) (x1 + ((x2-x1)/2));
}
public Position getPositionObjectByN(int n) {
return this.positions.get(n);
}
// returns position object given row and column value of the target position
public Position getPositionAt(int col, int row) {
for (Position pos : this.positions){
if (pos.row == row && pos.col == col){
return pos;
}
}
System.out.println("Position at: col:"+col+", row: "+row+" Does not exist.");
return null;
}
private int getRow(int pieceNumber) throws InvalidArgumentException {
if (!this.isValidNumPieces(pieceNumber)){
while (!this.isValidNumPieces(pieceNumber)){
pieceNumber--;
}
return (this.solveQuadratic(this.aRowCoef, this.aRowCoef, this.cRowVal - pieceNumber) + 1);
}
return this.solveQuadratic(this.aRowCoef, this.aRowCoef, this.cRowVal - pieceNumber);
}
private int getCol(int pieceNumber) throws InvalidArgumentException {
if (pieceNumber == 1){
return 0;
}
else if (this.isValidNumPieces(pieceNumber)){
return this.getRow(pieceNumber) -1;
}
else{
int upperBound = pieceNumber;
while (!this.isValidNumPieces(upperBound)){
upperBound++;
}
int upperBoundRow = this.getRow(upperBound);
int numNumbersBack = upperBound - pieceNumber;
return upperBoundRow - 2*numNumbersBack -1;
}
}
private int solveQuadratic(double a, double b, double c) throws InvalidArgumentException {
double d = Math.pow(b, 2) - 4 *a *c;
if (d < 0){
throw new InvalidArgumentException("Invalid Quadratic Arguments");
}
else if (d == 0){
return (int) ((-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c ))/ (2*a));
}
else {
int x1 = (int) ((-b + Math.sqrt(Math.pow(b, 2) - 4 * a * c ))/ (2*a));
int x2 = (int) ((-b - Math.sqrt(Math.pow(b, 2) - 4 * a * c ))/ (2*a));
if (x1> 0){
return x1;
}
return x2;
}
}
private boolean isValidNumPieces(int numPieces) {
long calc_num = 8*numPieces+1;
long t = (long) Math.sqrt(calc_num);
if (t*t==calc_num) {
return true;
}
return false;
}
public void printTriangle(){
System.out.println();
int rowHeight = this.maxRows;
int indent = (int) (rowHeight * this.numSpacesInPrint);
String spacer = stringRepeater(" ",this.numSpacesInPrint);
int i = 1;
System.out.print(stringRepeater(" ",indent) + spacer);
while (i < (this.numPieces+1)){
if (this.isValidNumPieces(i)){
Position curPosition = getPositionObjectByN(i-1);
if (!curPosition.isEmpty){
if (i < 10){
System.out.print(spacer + i + " ");
}
else {
System.out.print(spacer + i);
}
}
else{
System.out.print(spacer + this.emptySpotChar);
}
i ++;
System.out.print(" \n"+ stringRepeater(" ",indent));
indent -= this.numSpacesInPrint;
}
else{
Position curPosition = this.getPositionObjectByN(i-1);
if (!curPosition.isEmpty){
if (i < 10){
System.out.print(spacer + i + " ");
}
else{
System.out.print(spacer + i);
}
}
else{
System.out.print(spacer + this.emptySpotChar);
}
i += 1;
}
}
System.out.println();
}
public void printMoves() {
if (possibleMoves.size() ==0)
System.out.println("NO Moves");
for (Move mv : possibleMoves){
System.out.println(mv);
}
}
public void printPositions() {
for (Position pos : this.positions){
System.out.println(pos);
}
}
public String stringRepeater(String input, int count){
String returnStr = "";
for (int i = 0 ; i < count; i++){
returnStr = returnStr + input;
}
return returnStr;
}
// this method might not work
public boolean isValidSpot(int col, int row) {
if (row >= (Math.abs(col)+1)){
if ((isOdd(col) && !isOdd(row)) || (!isOdd(col) && isOdd(row)) ){
if (row <= maxRows){
return true;
}
else{
}
}
else{
}
}
else{
}
return false;
}
private boolean isOdd(int i) {
if (i % 2 == 0){
return false;
}
return true;
}
public void reset() throws InvalidArgumentException{
this.positions.clear();
this.positions.addAll(this.getPositions(this.numPieces, this.initialEmptySpot));
this.possibleMoves.clear();
setPossibleMoves();
}
public void undoMove(Move mv){
mv.from.isEmpty = false;
mv.mid.isEmpty = false;
mv.to.isEmpty = true;
setPossibleMoves();
}
public Triangle returnCopy() throws InvalidArgumentException {
ArrayList<Integer> emptySpots = new ArrayList<Integer>();
for (Position p : positions){
if (p.isEmpty){
emptySpots.add(new Integer(p.n));
}
}
Triangle copy = new Triangle(numPieces, emptySpots);
return copy;
}
public int nonNonEmptySpots(){
int ret = 0;
for (Position p : positions){
if (!p.isEmpty){
ret++;
}
}
return ret;
}
你可以發佈inputTriangle代碼嗎? – Massimo
你在StackSolve.java:45中做了什麼? –