关于跳马程序代码,请高手指点?

Question

如何完成国际象棋里的跳马程序啊?8*8的棋盘,64个格子,马要走过每个格子不能重复,国际象棋和中国象棋一样,马都是走日,只是中国象棋是走线上,国际象棋是走格子里,当我将n设为4时程序正常，当设为5或以上时会抛出一个StackOverflowError异常。如那位大虾能帮小弟我看看怎么解决，感激不尽。代码未写注释，看起来可能比较吃力，见谅。
Grid：每个方格public class Grid {private int x;private int y;public Grid() {}public Grid(int x, int y) {
this.x = x;
this.y = y;
}/**
* @return the x
*/
public int getX() {
return x;
}/**
* @param x the x to set
*/
public void setX(int x) {
this.x = x;
}/**
* @return the y
*/
public int getY() {
return y;
}/**
* @param y the y to set
*/
public void setY(int y) {
this.y = y;
}public String toString() {
return "( " + x + ", " + y + " )";
}
}Step：“马”走的每一步
import java.util.Vector;public class Step {private Vector<Grid> canGrid;private Grid step;/**
* @return the canStep
*/
public Vector<Grid> getCanGrid() {
return canGrid;
}/**
* @param canStep the canStep to set
*/
public void setCanGrid(Vector<Grid> canGrid) {
this.canGrid = canGrid;
}/**
* @return the step
*/
public Grid getStep() {
return step;
}/**
* @param step the step to set
*/
public void setStep(Grid step) {
this.step = step;
}public void removeStep(Grid step) {
canGrid.remove(step);
}
}GoStep：“马”走的整个过程
import java.util.Vector;public class GoStep {private Vector<Step> steps = new Vector<Step>();/**
* @return the steps
*/
public Vector<Step> getSteps() {
return steps;
}/**
* @param steps the steps to set
*/
public void setSteps(Vector<Step> steps) {
this.steps = steps;
}public Step getLastStep() {
if(steps == null || steps.size() == 0)
return null;return steps.elementAt(steps.size() - 1);
}public void addStep(Step step) {
steps.add(step);
}public void removeLastSteps() {
Step last = getLastStep();if(last == null) {
return;
}if(last.getCanGrid().size() == 1) {
steps.remove(last);
removeLastSteps();
}
}public Grid[] getGoedSteps() {
Grid[] goed = new Grid[steps.size()];for(int i = 0; i < steps.size(); i++) {
goed[i] = steps.elementAt(i).getStep();
}return goed;
}public String toString() {
/*String str = "Start:\n";Grid[] goed = getGoedSteps();
for(int i = 0; i < goed.length; i++) {
str += goed[i] + " -->\n";
}str += "End.\t StepNum: " + goed.length;*/String str = "Start: ";Grid[] goed = getGoedSteps();
for(int i = 0; i < goed.length; i++) {
str += goed[i] + " --> ";
}str += "End.\t StepNum: " + goed.length;return str;
}
}GoHorse：走“马”的逻辑主类
import java.util.Vector;public class GoHorse {private final static int WI = 5;private GoStep goStep;public static void main(String[] args) {
GoHorse horse = new GoHorse();for(int i = 1; i <= WI; i++) {
for(int j = 1; j <= WI; j++) {
Grid start = new Grid(i, j);
if(horse.gohorse(start)) {
System.out.println(horse.goStep);
return;
}
}
}
}public boolean gohorse(Grid start) {
goStep = new GoStep();Step step = new Step();
Vector<Grid> vec = new Vector<Grid>();
vec.add(start);
step.setCanGrid(vec);
step.setStep(start);goStep.addStep(step);
go();if(goStep.getSteps().size() == WI * WI) {
return true;
}return false;
}private void go() {
System.out.println(goStep);if(goStep.getSteps().size() == WI * WI) {
return;
}Step step = goStep.getLastStep();
Grid grid = step.getStep();Vector<Grid> canGrid = getCanGoGrids(grid);
if(canGrid.size() == 0) {
if(step.getCanGrid().size() == 1) {
goStep.removeLastSteps();if(goStep.getSteps().size() == 0) {
return;
}step = goStep.getLastStep();
grid = step.getStep();
step.removeStep(grid);
step.setStep(step.getCanGrid().elementAt(0));
go();
return;
} else {
step.removeStep(grid);
step.setStep(step.getCanGrid().elementAt(0));
go();
}
} else {
Step newStep = new Step();
newStep.setCanGrid(canGrid);
newStep.setStep(canGrid.elementAt(0));goStep.addStep(newStep);
go();
}
}private Vector<Grid> getCanGoGrids(Grid grid) {Vector<Grid> vec = new Vector<Grid>();int x = grid.getX();
int y = grid.getY();verifyAndAddGrid(vec, new Grid(x + 1, y + 2));
verifyAndAddGrid(vec, new Grid(x + 1, y - 2));
verifyAndAddGrid(vec, new Grid(x + 2, y + 1));
verifyAndAddGrid(vec, new Grid(x + 2, y - 1));
verifyAndAddGrid(vec, new Grid(x - 1, y + 2));
verifyAndAddGrid(vec, new Grid(x - 1, y - 2));
verifyAndAddGrid(vec, new Grid(x - 2, y + 1));
verifyAndAddGrid(vec, new Grid(x - 2, y - 1));Grid[] goed = goStep.getGoedSteps();
for(int i = vec.size() - 1; i >= 0; i--) {
Grid can = vec.elementAt(i);for(int j = 0; j < goed.length; j++) {
Grid has = goed[j];if((can.getX() == has.getX()) && (can.getY() == has.getY())) {
vec.remove(can);
}
}
}return vec;
}private void verifyAndAddGrid(Vector<Grid> vec, Grid grid) {
if(verifyGrid(grid))
vec.add(grid);
}private boolean verifyGrid(Grid grid) {int x = grid.getX();
int y = grid.getY();boolean can = (x >= 1 && x <= WI) && (y >= 1 && y <= WI);if(!can) {
return false;
}return true;
}
}运行错误：
Exception in thread "main" java.lang.StackOverflowError
at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source)
at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source)
at java.nio.charset.CharsetEncoder.encode(Unknown Source)
at sun.nio.cs.StreamEncoder$CharsetSE.implWrite(Unknown Source)
at sun.nio.cs.StreamEncoder.write(Unknown Source)
at java.io.OutputStreamWriter.write(Unknown Source)
at java.io.BufferedWriter.flushBuffer(Unknown Source)
at java.io.PrintStream.write(Unknown Source)
at java.io.PrintStream.print(Unknown Source)
at java.io.PrintStream.println(Unknown Source)
at horse.GoHorse.go(GoHorse.java:52)
at horse.GoHorse.go(GoHorse.java:79)
at horse.GoHorse.go(GoHorse.java:87)
at horse.GoHorse.go(GoHorse.java:87)

Answer 1

先帮你格式化一下：public class Grid { private int x;
private int y; public Grid() {} public Grid(int x, int y) {
this.x = x;
this.y = y;
} /**
 * @return the x
 */
public int getX() {
return x;
} /**
 * @param x the x to set
 */
public void setX(int x) {
this.x = x;
} /**
 * @return the y
 */
public int getY() {
return y;
} /**
 * @param y the y to set
 */
public void setY(int y) {
this.y = y;
} public String toString() {
return "( " + x + ", " + y + " )";
}}//////////////////////////////////////////////////////////////////////////////////////////////////Step：“马”走的每一步
import java.util.Vector;public class Step { private Vector<Grid> canGrid;
private Grid step; /**
 * @return the canStep
 */
public Vector<Grid> getCanGrid() {
return canGrid;
} /**
 * @param canStep the canStep to set
 */
public void setCanGrid(Vector<Grid> canGrid) {
this.canGrid = canGrid;
} /**
 * @return the step
 */
public Grid getStep() {
return step;
} /**
 * @param step the step to set
 */
public void setStep(Grid step) {
this.step = step;
} public void removeStep(Grid step) {
canGrid.remove(step);
}}////////////////////////////////////////////////////////////////////////////////////////GoStep：“马”走的整个过程
import java.util.Vector;public class GoStep { private Vector<Step> steps = new Vector<Step>(); /**
 * @return the steps
 */
public Vector<Step> getSteps() {
return steps;
} /**
 * @param steps the steps to set
 */
public void setSteps(Vector<Step> steps) {
this.steps = steps;
} public Step getLastStep() {
if (steps == null || steps.size() == 0) return null;
return steps.elementAt(steps.size() - 1);
} public void addStep(Step step) {
steps.add(step);
} public void removeLastSteps() {
Step last = getLastStep();
if (last == null) { return; }
if (last.getCanGrid().size() == 1) {
steps.remove(last);
removeLastSteps();
}
} public Grid[] getGoedSteps() {
Grid[] goed = new Grid[steps.size()];
for (int i = 0; i < steps.size(); i++) {
goed[i] = steps.elementAt(i).getStep();
}
return goed;
} public String toString() {
/*
 * String str = "Start:\n"; Grid[] goed = getGoedSteps(); for(int i = 0; i <
 * goed.length; i++) { str += goed[i] + " -->\n"; } str += "End.\t StepNum: " +
 * goed.length;
 */
String str = "Start: ";
Grid[] goed = getGoedSteps();
for (int i = 0; i < goed.length; i++) {
str += goed[i] + " --> ";
}
str += "End.\t StepNum: " + goed.length;
return str;
}}/////////////////////////////////////////////////////////////////////////////////////////////////GoHorse：走“马”的逻辑主类
import java.util.Vector;public class GoHorse { private final static int WI = 5;
private GoStep goStep; public static void main(String[] args) {
GoHorse horse = new GoHorse();
for (int i = 1; i <= WI; i++) {
for (int j = 1; j <= WI; j++) {
Grid start = new Grid(i, j);
if (horse.gohorse(start)) {
System.out.println(horse.goStep);
return;
}
}
}
} public boolean gohorse(Grid start) {
goStep = new GoStep();
Step step = new Step();
Vector<Grid> vec = new Vector<Grid>();
vec.add(start);
step.setCanGrid(vec);
step.setStep(start);
goStep.addStep(step);
go();
if (goStep.getSteps().size() == WI * WI) { return true; }
return false;
} private void go() {
System.out.println(goStep);
if (goStep.getSteps().size() == WI * WI) { return; }
Step step = goStep.getLastStep();
Grid grid = step.getStep();
Vector<Grid> canGrid = getCanGoGrids(grid);
if (canGrid.size() == 0) {
if (step.getCanGrid().size() == 1) {
goStep.removeLastSteps();
if (goStep.getSteps().size() == 0) { return; }
step = goStep.getLastStep();
grid = step.getStep();
step.removeStep(grid);
step.setStep(step.getCanGrid().elementAt(0));
go();
return;
} else {
step.removeStep(grid);
step.setStep(step.getCanGrid().elementAt(0));
go();
}
} else {
Step newStep = new Step();
newStep.setCanGrid(canGrid);
newStep.setStep(canGrid.elementAt(0));
goStep.addStep(newStep);
go();
}
} private Vector<Grid> getCanGoGrids(Grid grid) {
Vector<Grid> vec = new Vector<Grid>();
int x = grid.getX();
int y = grid.getY();
verifyAndAddGrid(vec, new Grid(x + 1, y + 2));
verifyAndAddGrid(vec, new Grid(x + 1, y - 2));
verifyAndAddGrid(vec, new Grid(x + 2, y + 1));
verifyAndAddGrid(vec, new Grid(x + 2, y - 1));
verifyAndAddGrid(vec, new Grid(x - 1, y + 2));
verifyAndAddGrid(vec, new Grid(x - 1, y - 2));
verifyAndAddGrid(vec, new Grid(x - 2, y + 1));
verifyAndAddGrid(vec, new Grid(x - 2, y - 1));
Grid[] goed = goStep.getGoedSteps();
for (int i = vec.size() - 1; i >= 0; i--) {
Grid can = vec.elementAt(i);
for (int j = 0; j < goed.length; j++) {
Grid has = goed[j];
if ((can.getX() == has.getX()) && (can.getY() == has.getY())) {
vec.remove(can);
}
}
}
return vec;
} private void verifyAndAddGrid(Vector<Grid> vec, Grid grid) {
if (verifyGrid(grid)) vec.add(grid);
} private boolean verifyGrid(Grid grid) {
int x = grid.getX();
int y = grid.getY();
boolean can = (x >= 1 && x <= WI) && (y >= 1 && y <= WI);
if (!can) { return false; }
return true;
}}