递归 Java 编程，Knight's Tour 快把我逼疯了
Recursive Java programming, Knight's Tour driving me nuts
我一直在做一个学校项目，但无法找出问题所在。遇到死胡同时，骑士跳回上一步原地的问题
我已经添加了一个 4x4 测试的输出，你可以清楚地看到骑士在看到 12 号有死路时跳回 11 号转弯。然后它从 11 号转弯继续， "solves the tour".
此外，我不确定如果某个模式不能解决问题，该如何继续。因为那时我需要以某种方式记录该模式，这样我就不会再次进入相同的模式。抱歉我的英语不好，在此先感谢您。
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");
if (takeTour(x-2, y+1))
{
return true;
}
}
// 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");
if (takeTour(x-2, y-1))
{
return true;
}
}
// 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");
if (takeTour(x-1, y-2))
{
return true;
}
}
// 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");
if (takeTour(x+1, y-2))
{
return true;
}
}
// 2 Right, 1 Up
if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
{
System.out.println("x:" + x + ", y:" + y + " (2r,1u)moving to x:" + (x+2) + ", y:" + (y-1));
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up");
if (takeTour(x+2, y-1))
{
return true;
}
}
// 2 Right, 1 Down
if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
{
System.out.println("x:" + x + ", y:" + y + " (2r,1d)moving to x:" + (x+2) + ", y:" + (y+1));
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down");
if (takeTour(x+2, y+1))
{
return true;
}
}
// 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");
if (takeTour(x+1, y+2))
{
return true;
}
}
// 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");
if (takeTour(x-1, y+2))
{
return true;
}
}
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 < 1 )
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();
}
}
}
这是 4x4 的输出：
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 (2r,1d)moving to x:2, y:1
x:1, y:0 (2r,1d)moving to x:3, y:1
x:0, y:1 (2r,1d)moving to x:2, y:2
x:1, y:1 (2r,1u)moving to x:3, y:0
x:1, y:1 (2r,1d)moving to x:3, y:2
x:1, y:2 (2r,1d)moving to x:3, y:3
X: 0, Y: 0. Moving 2 Right, 1 Down
X: 2, Y: 1. Moving 2 Left, 1 Down
X: 0, Y: 2. Moving 2 Up, 1 Right
X: 1, Y: 0. Moving 2 Right, 1 Down
X: 3, Y: 1. Moving 2 Left, 1 Down
X: 1, Y: 2. Moving 2 Up, 1 Right
X: 2, Y: 0. Moving 2 Left, 1 Down
X: 0, Y: 1. Moving 2 Right, 1 Down
X: 2, Y: 2. Moving 2 Left, 1 Down
X: 0, Y: 3. Moving 2 Up, 1 Right
X: 1, Y: 1. Moving 2 Right, 1 Up
X: 1, Y: 1. Moving 2 Right, 1 Down
X: 3, Y: 2. Moving 2 Left, 1 Down
X: 1, Y: 1. Moving 2 Down, 1 Right
X: 1, Y: 2. Moving 2 Right, 1 Down
Did not find any way to complete Knights Tour!
1 4 7 12
8 11 2 5
3 6 9 13
10 14 15 16
最好的办法是向递归调用的方法添加 List<Point> visited。我还将您的 int x 和 int y 参数更改为 Point。这样你就可以直接调用 visited.contains(point) 来确定你是否已经在那个 Point 上完成了测试。在这种情况下，您不会使用那个特定的 Point 进行递归调用，而是继续进行下一个调用。
我找到问题了！我必须在 takeTour(int x, int y) 中的每 8 个 if(takeTour(x+-a, y+-b)) 语句中放置 else 块，然后 return false。现在我只是想知道如何才能跟踪模式，以便我可以返回一步并尝试新的一步
我一直在做一个学校项目，但无法找出问题所在。遇到死胡同时，骑士跳回上一步原地的问题
我已经添加了一个 4x4 测试的输出，你可以清楚地看到骑士在看到 12 号有死路时跳回 11 号转弯。然后它从 11 号转弯继续， "solves the tour".
此外，我不确定如果某个模式不能解决问题，该如何继续。因为那时我需要以某种方式记录该模式，这样我就不会再次进入相同的模式。抱歉我的英语不好，在此先感谢您。
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");
if (takeTour(x-2, y+1))
{
return true;
}
}
// 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");
if (takeTour(x-2, y-1))
{
return true;
}
}
// 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");
if (takeTour(x-1, y-2))
{
return true;
}
}
// 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");
if (takeTour(x+1, y-2))
{
return true;
}
}
// 2 Right, 1 Up
if (x < squares -2 && y > 0 && table[x+2][y-1] == 0)
{
System.out.println("x:" + x + ", y:" + y + " (2r,1u)moving to x:" + (x+2) + ", y:" + (y-1));
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Up");
if (takeTour(x+2, y-1))
{
return true;
}
}
// 2 Right, 1 Down
if (x < squares -2 && y < squares -1 && table[x+2][y+1] == 0)
{
System.out.println("x:" + x + ", y:" + y + " (2r,1d)moving to x:" + (x+2) + ", y:" + (y+1));
moves.add("X: " + x + ", Y: " + y + ". Moving 2 Right, 1 Down");
if (takeTour(x+2, y+1))
{
return true;
}
}
// 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");
if (takeTour(x+1, y+2))
{
return true;
}
}
// 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");
if (takeTour(x-1, y+2))
{
return true;
}
}
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 < 1 )
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();
}
}
}
这是 4x4 的输出：
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 (2r,1d)moving to x:2, y:1
x:1, y:0 (2r,1d)moving to x:3, y:1
x:0, y:1 (2r,1d)moving to x:2, y:2
x:1, y:1 (2r,1u)moving to x:3, y:0
x:1, y:1 (2r,1d)moving to x:3, y:2
x:1, y:2 (2r,1d)moving to x:3, y:3
X: 0, Y: 0. Moving 2 Right, 1 Down
X: 2, Y: 1. Moving 2 Left, 1 Down
X: 0, Y: 2. Moving 2 Up, 1 Right
X: 1, Y: 0. Moving 2 Right, 1 Down
X: 3, Y: 1. Moving 2 Left, 1 Down
X: 1, Y: 2. Moving 2 Up, 1 Right
X: 2, Y: 0. Moving 2 Left, 1 Down
X: 0, Y: 1. Moving 2 Right, 1 Down
X: 2, Y: 2. Moving 2 Left, 1 Down
X: 0, Y: 3. Moving 2 Up, 1 Right
X: 1, Y: 1. Moving 2 Right, 1 Up
X: 1, Y: 1. Moving 2 Right, 1 Down
X: 3, Y: 2. Moving 2 Left, 1 Down
X: 1, Y: 1. Moving 2 Down, 1 Right
X: 1, Y: 2. Moving 2 Right, 1 Down
Did not find any way to complete Knights Tour!
1 4 7 12
8 11 2 5
3 6 9 13
10 14 15 16
最好的办法是向递归调用的方法添加 List<Point> visited。我还将您的 int x 和 int y 参数更改为 Point。这样你就可以直接调用 visited.contains(point) 来确定你是否已经在那个 Point 上完成了测试。在这种情况下，您不会使用那个特定的 Point 进行递归调用，而是继续进行下一个调用。
我找到问题了！我必须在 takeTour(int x, int y) 中的每 8 个 if(takeTour(x+-a, y+-b)) 语句中放置 else 块，然后 return false。现在我只是想知道如何才能跟踪模式，以便我可以返回一步并尝试新的一步