1
我写一个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中做了什么？ –