我正在研究骑士之旅问题。 在我的程序中，用户可以选择等于 3 或更大的数字 n。该数字将确定二维数组中 n*n 的表大小。然后，只要起点大于或等于0，小骑士就会根据用户给出的起点开始旅行。
当骑士走到死胡同时(截至输出中可视化表中的第 12 回合)，我的问题就出现了。 我想以某种方式跟踪它的运动，这样我就可以堵住死胡同，后退一步并从那里尝试。我发现我可能需要一个三维数组，以便我可以保存每个方 block 中的所有转弯数字。但话又说回来，我需要一个不是静态的 ArrayList。任何建议将不胜感激。这是我的代码:
package knightsTour;
import java.util.Scanner;
import java.util.ArrayList;
public class KnightsTour
{
private static int turns = 0;
private static ArrayList<String> moves = new ArrayList<String>();
private static int squares;
private static int table[][];
private static boolean takeTour(int x, int y) {
// Checks if all squares is used. If true, algorithm will stop
if (checkIfFinished())
return true;
table[x][y] = ++turns;
// 2 Left, 1 Down
if (x > 1 && y < squares -1 && table[x-2][y+1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Down. Turn: " + turns);
if (takeTour(x-2, y+1))
{
return true;
}
else
{
return false;
}
}
// 2 Left, 1 Up
if (x > 1 && y > 0 && table[x-2][y-1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Left, 1 Up. Turn: " + turns);
if (takeTour(x-2, y-1))
{
return true;
}
else
{
return false;
}
}
// 2 Up, 1 Left
if (y > 1 && x > 0 && table[x-1][y-2] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Left. Turn: " + turns);
if (takeTour(x-1, y-2))
{
return true;
}
else
{
return false;
}
}
// 2 Up, 1 Right
if (y > 1 && x < squares -1 && table[x+1][y-2] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Up, 1 Right. Turn: " + turns);
if (takeTour(x+1, y-2))
{
return true;
}
else
{
return false;
}
}
// 2 Right, 1 Up
if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up. Turn: " + turns);
if (takeTour(x+2, y-1))
{
return true;
}
else
{
return false;
}
}
// 2 Right, 1 Down
if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down. Turn: " + turns);
if (takeTour(x+2, y+1))
{
return true;
}
else
{
return false;
}
}
// 2 Down, 1 Right
if (y < squares -2 && x < squares-1 && table[x+1][y+2] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Right. Turn: " + turns);
if (takeTour(x+1, y+2))
{
return true;
}
else
{
return false;
}
}
// 2 Down, 1 Left
if (y < squares -2 && x > 0 && table[x-1][y+2] == 0)
{
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Down, 1 Left. Turn: " + turns);
if (takeTour(x-1, y+2))
{
return true;
}
else
{
return false;
}
}
/*
I need some code here before it gives up searching
*/
// If we'd tried every single paths
// and we still end up here, there's no solution
return false;
}
// Checks if all squares is used
private static boolean checkIfFinished()
{
for (int i = 0; i < squares; i++)
{
for (int j = 0; j < squares; j++)
{
if (table[i][j] == 0)
return false;
}
}
return true;
}
// Made this to save code from 3 duplicates
private static void invalidNumber()
{
System.out.println("Invalid number! Killing proccess");
System.exit(0);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Number of squares: ");
squares = Integer.parseInt(sc.nextLine());
if (squares < 3 )
invalidNumber();
System.out.println("Note: Start values is from 0 -> n-1"
+ "\n0,0 is at top left side");
System.out.print("X start value: ");
int x = Integer.parseInt(sc.nextLine());
if (x < 0 || x > squares -1)
invalidNumber();
System.out.print("Y start value: ");
int y = Integer.parseInt(sc.nextLine());
if (y < 0 || y > squares -1)
invalidNumber();
sc.close();
table = new int[squares][squares];
boolean tourComplete = takeTour(x, y);
for (String s : moves)
{
System.out.println(s);
}
if (!tourComplete)
System.out.println("Did not find any way to complete Knights Tour!");
// Print the table with the move-numbers
for (int i = 0; i < squares; i++)
{
for (int j = 0; j < squares; j++)
{
System.out.printf("%4d", table[j][i]);
}
System.out.println();
}
}
}
我的 4*4 表格输出如下所示:
Number of squares: 4
Note: Start values is from 0 -> n-1
0,0 is at top left side
X start value: 0
Y start value: 0
X: 0, Y: 0. Moving 2 Right, 1 Down. Turn: 1
X: 2, Y: 1. Moving 2 Left, 1 Down. Turn: 2
X: 0, Y: 2. Moving 2 Up, 1 Right. Turn: 3
X: 1, Y: 0. Moving 2 Right, 1 Down. Turn: 4
X: 3, Y: 1. Moving 2 Left, 1 Down. Turn: 5
X: 1, Y: 2. Moving 2 Up, 1 Right. Turn: 6
X: 2, Y: 0. Moving 2 Left, 1 Down. Turn: 7
X: 0, Y: 1. Moving 2 Right, 1 Down. Turn: 8
X: 2, Y: 2. Moving 2 Left, 1 Down. Turn: 9
X: 0, Y: 3. Moving 2 Up, 1 Right. Turn: 10
X: 1, Y: 1. Moving 2 Right, 1 Up. Turn: 11
Did not find any way to complete Knights Tour!
1 4 7 12
8 11 2 5
3 6 9 0
10 0 0 0
最佳答案
当在 BackTracking 上尝试不同的可能性时，您需要在每个递归步骤中检查所有可能性。在您一步提供的代码中，您仅尝试一种可能性，然后返回。这样做您无法探索所有可能性。
我的建议是更改函数参数以接受当前位置 (x,y) 和先前访问过的位置的 boolean 数组。如果你需要构建最终有效解决方案的路径，我还建议添加步数(你已经完成的步数)和一个 int 数组来存储哪一步访问了哪个位置。
接下来我提供一个不是最有效的解决方案。事实上，您可以尝试修剪回溯的可能性，以避免递归爆炸(CPU 效率)，并且可以尝试避免某些矩阵副本(内存效率)。
package knightsTour;
import java.util.Scanner;
public class KnightsTour {
private static final int[] MOVE_X = new int[] { -2, -2, -1, -1, +1, +1, +2, +2 };
private static final int[] MOVE_Y = new int[] { +1, -1, +2, -2, +2, -2, +1, -1 };
private final int SQUARES;
private final int INIT_X;
private final int INIT_Y;
private int[][] path;
public KnightsTour(int squares, int x, int y) {
this.SQUARES = squares;
this.INIT_X = x;
this.INIT_Y = y;
}
public int[][] getPath() {
return this.path;
}
public boolean takeTour() {
boolean[][] visited = new boolean[this.SQUARES][this.SQUARES];
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
visited[i][j] = false;
}
}
visited[this.INIT_X][this.INIT_Y] = true;
this.path = new int[this.SQUARES][this.SQUARES];
return takeTourBT(this.INIT_X, this.INIT_Y, 0, visited, this.path);
}
private boolean takeTourBT(int posX, int posY, int step, boolean[][] visited, int[][] path) {
debug(step, visited);
if (checkIfFinished(visited)) {
return true;
}
// Increase the step count
++step;
// Try recursively (cut when a branch success)
boolean success = false;
for (int i = 0; i < MOVE_X.length && !success; ++i) {
int nextX = posX + MOVE_X[i];
int nextY = posY + MOVE_Y[i];
if (nextX >= 0 && nextX < this.SQUARES && nextY >= 0 && nextY < this.SQUARES && !visited[nextX][nextY]) {
// Next position is valid and has not been visited
// Mark position
visited[nextX][nextY] = true;
// Call
boolean branchSuccess = takeTourBT(nextX, nextY, step, visited, path);
if (branchSuccess) {
// We are comming back from the good solution, mark the path
path[nextX][nextY] = step;
}
success = success | branchSuccess;
// Unmark the position for next try
visited[nextX][nextY] = false;
}
}
return success;
}
// Adds some verbose for debugging
private void debug(int step, boolean[][] visited) {
System.out.println("*********************** STEP " + String.valueOf(step) + " ***********************");
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
if (visited[i][j]) {
System.out.print("X ");
} else {
System.out.print(". ");
}
}
System.out.println("");
}
System.out.println("*******************************************************");
}
// Checks if all squares is used
private boolean checkIfFinished(boolean[][] visited) {
for (int i = 0; i < this.SQUARES; ++i) {
for (int j = 0; j < this.SQUARES; ++j) {
if (!visited[i][j]) {
return false;
}
}
}
return true;
}
public static void main(String[] args) {
// Process arguments
int squares = 0;
int x = 0;
int y = 0;
try (Scanner sc = new Scanner(System.in)) {
System.out.print("Number of squares: ");
squares = Integer.parseInt(sc.nextLine());
if (squares < 3) {
throw new Exception("[ERROR] Invalid number of squares");
}
System.out.println("Note: Start values is from 0 -> n-1" + "\n0,0 is at top left side");
System.out.print("X start value: ");
x = Integer.parseInt(sc.nextLine());
if (x < 0 || x > squares - 1) {
throw new Exception("[ERROR] Invalid start x position");
}
System.out.print("Y start value: ");
y = Integer.parseInt(sc.nextLine());
if (y < 0 || y > squares - 1) {
throw new Exception("[ERROR] Invalid start y position");
}
} catch (Exception e) {
// Error occurred, exit
System.err.println("Killing process");
System.exit(1);
}
// Initialize the KnightsTour
KnightsTour kt = new KnightsTour(squares, x, y);
// Make the tour
boolean success = kt.takeTour();
// Post process
if (success) {
System.out.println("The tour was sucessfull!");
} else {
System.out.println("Did not find any way to complete Knights Tour!");
}
int[][] path = kt.getPath();
for (int i = 0; i < path.length; ++i) {
for (int j = 0; j < path[i].length; ++j) {
String stepSTR = (path[i][j] < 10) ? "0" + String.valueOf(path[i][j]) : String.valueOf(path[i][j]);
System.out.print(stepSTR + " ");
}
System.out.println("");
}
}
}
尝试使用大小为 5 和起始位置 (0,0) 的代码。
请注意:
- 您可以通过注释调试调用来启用/禁用调试迭代
- 我用 2 个数组压缩了执行移动的方式，以避免重复，但为了清楚起见，您可以再次展开它。
- 在每个递归步骤中，在深入之前，我们检查是否可以执行移动，标记下一个位置并继续。在返回的路上，我们取消标记位置，检查移动是否到达成功的步骤，并在需要时重建好的解决方案。
关于java 递归 - 需要帮助解决回溯骑士之旅，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42723630/