java recurison - 需要帮助解决回溯骑士之旅 [英] java recurison - Need help for solving backtracking Knight's Tour
问题描述
我正在解决骑士巡回赛问题.在我的程序中，用户可以选择一个等于 3 或更大的数字 n.该数字将通过二维数组中的 n*n 确定表的大小.然后骑士会根据用户给出的起点，只要大于或等于0就开始它的旅程.
I am working on the Knight's Tour problem. In my program the user can select a number n equal to 3 or higher. The number will determine the table's size by n*n in a two-dimensional array. Then the knight will start it's tour based on the starting points given by the user as long as they are higher or equal to 0.
当骑士走到死胡同时(从输出可视化表中的第 12 回合开始)，我的问题就出现了.我想以某种方式跟踪它的运动，以便我可以挡住死胡同，后退一步并从那里开始尝试.我发现我可能需要一个三维数组，以便我可以保存每个方块中的所有转弯数.但话又说回来，我需要一个 ArrayList 女巫不是静态的.任何建议将不胜感激.这是我的代码:
My problem comes when the knight has come to a dead end (as of turn number 12 in the visualization table in the output). I want to somehow track it's movements so that I can block the dead end, go back a step and try from there. I've figured out that I might need a three-dimensional array so that I can save all the turn numbers in each square. But then again I need an ArrayList witch isn't static. Any suggestions will be appreciated. Here's my code:
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 表格输出如下所示:
My output for a 4*4 table looks like this:
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 上尝试不同的可能性时，您需要在每个递归步骤中检查它们.在您一步提供的代码中，您只尝试一种可能性，然后返回.这样做你无法探索所有的可能性.
When trying different possibilities on BackTracking you need to check them all in every recursion step. In the code you provide in a single step you only try one possibility and then return. Doing this you are not able to explore all the possibilities.
我的建议是更改函数参数以接受当前位置 (x,y) 和先前访问过的位置的布尔数组.如果你需要构造最终有效解的路径，我也建议加上步数(你完成的步数)和一个int数组来存储哪个位置在哪个步骤中被访问过.
My suggestion is to change the function arguments to accept the current position (x,y) and a boolean array for the positions that have been previously visited. If you need to construct the path of the final valid solution, I also suggest to add the step count (the number of steps you have done) and a int array to store which position has been visited in which step.
接下来我提供一个不是最有效的解决方案.事实上，您可以尝试修剪回溯的可能性以避免递归爆炸(CPU 效率)，并且您可以尝试避免矩阵的某些副本(内存效率).
Next I provide a solution which is not the most efficient. In fact, you can try to prune the backtracking possibilities to avoid the recurssion explosion (cpu efficiency) and you can try to avoid some copies of the matrixes (memory efficiency).
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) 的代码.
Try this code with size 5 and start position (0,0).
请注意:
- 您可以通过注释调试调用来启用/禁用调试迭代
- 我用 2 个阵列压缩了您执行移动的方式以避免重复，但为了清楚起见，您可以再次展开它.
- 在每个递归步骤中，在深入之前，我们检查是否可以执行移动，我们标记下一个位置并继续.在返回的路上，我们取消标记位置，检查移动是否到达成功的一步，并在需要时重建好的解决方案.
这篇关于java recurison - 需要帮助解决回溯骑士之旅的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
