我正在尝试写一个 Knights Walk Algorithm (蛮力)使用 Java。我能够创建一个程序来移动 5x5 网格，但该程序总是将 06 个单元格遗漏在板上。我的骑士也无法从这些方 block 移动到任何地方。
例如我有以下网格:
----------------
a1,b1,c1,d1,e1
a2,b2,c2,d2,e2
a3,b3,c3,d3,e3
a4,b4,c4,d4,e4
a5,b5,c5,d5,e5
----------------
我的算法打印出以下路径和访问的单元格
a1 -> b3
b3 -> c5
c5 -> a4
a4 -> c3
c3 -> d5
d5 -> b4
b4 -> a2
a2 -> c1
c1 -> d3
d3 -> e5
e5 -> c4
c4 -> a3
a3 -> b5
b5 -> d4
d4 -> c2
c2 -> e3
e3 -> d1
d1 -> b2
Cells Visited : [a1, b3, c5, a4, c3, d5, b4, a2, c1, d3, e5, c4, a3, b5, d4, c2, e3, d1, b2, b2, b2, b2, b2, b2, b2]
如您所见，网格仍有以下六个单元格未被触及(x 标记已访问)。
----------------
x,b1,x,x,e1
x,x,x,d2,e2
x,x,x,x,x
x,x,x,x,e4
a5,x,x,x,x
这使得以下 6 个单元格:
b1,e1,d2,e2,e4,a5
保持原样，我似乎也无法从这些单元格移动到任何其他单元格。
谁能指出我可能做错了什么？。我在下面给出了我的代码:
import java.util.ArrayList;
import java.util.List;
public class KnightsWalk {
String[] colnames = {"a", "b", "c", "d", "e","f","g","h"};
String[] rownumbers = {"1", "2", "3", "4", "5","6","7","8"};
static final int gridSize = 5; //Specify the grid size here
static String grid[][] = new String[gridSize][gridSize];
static int[][] moves = {{2, 1},{1, 2},{-1,-2},{-2,-1},{2,-1},{-2,1},{-1,2},{1,-2}};//All Possible Moves
//Visited Cells
static List<String> visitedCells = new ArrayList<>();
private void initGrid() {
if (gridSize>=3 || gridSize<=8) {
for (int col = 0; col < grid.length; col++) {
for (int row = 0; row < grid.length; row++) {
grid[row][col] = colnames[col] + rownumbers[row];
}
}
} else {
System.out.println("Grid Size of "+gridSize+" is Not Supported ");
System.exit(0);
}
}
private boolean canMoveToCell(int[] cellvisiting) {
try{
//check if the cell visiting has been visited before
String cell = grid[cellvisiting[0]][cellvisiting[1]];
boolean canmove = !visitedCells.contains(cell);
return canmove;
}
catch(ArrayIndexOutOfBoundsException ex){
return false;
}
}
private void walk(int cell[]) {
String start = grid[cell[0]][cell[1]];
visitedCells.add(start); //Add the starting cell to already visited
if(visitedCells.size() == (gridSize*gridSize)){
return;
}
int[] nextCellToMoveto = null;
for(int[] move:moves){
int[] nc1 = { cell[0]+move[0], cell[1]+move[1] };
if (canMoveToCell(nc1)) {
printMove(cell, nc1);
nextCellToMoveto=nc1;
break;
}
else{
int[] nc2 = { cell[0]+move[1], cell[1]+move[0] };
if(canMoveToCell(nc2)){
printMove(cell, nc2);
nextCellToMoveto=nc2;
break;
}
else{
nextCellToMoveto=cell;
}
}
}
walk(nextCellToMoveto);
}
public static void main(String[] args) {
KnightsWalk gw = new KnightsWalk();
gw.initGrid();
gw.printGrid();
for (int row = 0; row < grid.length; row++) {
for (int col = 0; col < grid.length; col++) {
int startingcell [] = {row,col};
System.out.println("Cells Visited : "+visitedCells);
visitedCells.clear();//Clearing the Previous cells visited when hit a dead end
gw.walk(startingcell);
System.out.println("Trying with Starting Cell : "+grid[startingcell[0]][startingcell[1]]);
}
}
System.out.println("Cells Visited : "+visitedCells);
}
/**
* Auxiliary Support Methods for user output support
*/
private void printMove(int[] start, int[] end) {
System.out.println(grid[start[0]][start[1]] + " -> " + grid[end[0]][end[1]]);
}
private void printGrid() {
System.out.println("----------------");
for (String[] row : grid) {
for (int col = 0; col < grid.length; col++) {
String sep = (col < grid.length - 1) ? "," : "";
System.out.print(row[col] + sep);
}
System.out.println("\n");
}
System.out.println("----------------");
}
}
更新代码 3 现在它打印解决方案如下:
----------------
a1,a2,a3,a4,a5
b1,b2,b3,b4,b5
c1,c2,c3,c4,c5
d1,d2,d3,d4,d5
e1,e2,e3,e4,e5
----------------
25 of out 25 Cells Visited in the order [a1, c2, a3, b1, d2, e4, c3, b5, d4, e2, c1, a2, b4, d5, e3, d1, b2, a4, c5, b3, a5, c4, e5, d3, e1]
BUILD SUCCESSFUL (total time: 0 seconds)
更新后的代码如下:
import java.util.ArrayList;
import java.util.List;
public class KnightsWalk {
String[] rownames = {"a", "b", "c", "d", "e", "f", "g", "h"};
String[] colnames = {"1", "2", "3", "4", "5", "6", "7", "8"};
static final int gridSize = 5; //Specify the grid size here
static String grid[][];
static int[][] moves = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};//All Possible Moves
static List<String> visitedCells = new ArrayList<>(); //Visited Cells
int numberOfMoves = 0;
private void initGrid() {
if (gridSize >= 3 && gridSize <= 8) {
grid = new String[gridSize][gridSize];
int rownum = 0;
for (String[] gridrow : grid) {
for (int cell = 0; cell < gridrow.length; cell++) {
gridrow[cell] = rownames[rownum] + colnames[cell];
}
rownum += 1;
}
} else {
System.out.println("Grid Size of " + gridSize + " is Not Supported ");
System.exit(0);
}
}
private boolean canWalkToCell(int[] cellvisiting) {
//check if the cell visiting has been visited before
try {
//Method chained to return if the cell is in the list
String cell = grid[cellvisiting[0]][cellvisiting[1]];
if(visitedCells.contains(cell)){
return false;
}
else{
return true;
}
} catch (ArrayIndexOutOfBoundsException ex) {
//This is the lazy way to check if the coordinates are in the grid
return false;
}
}
private boolean walk(int cell[]) {
String nextCell = grid[cell[0]][cell[1]];
visitedCells.add(nextCell); //Add the starting cell to already visited
numberOfMoves += 1;
if (numberOfMoves == (gridSize * gridSize)) {
return true;
}
for (int[] move : moves) {
int[] nc = {cell[0] + move[0], cell[1] + move[1]};
if (canWalkToCell(nc)) {
if(walk(nc)){
return true;
}
}
}
//Backtracking
numberOfMoves -= 1;
visitedCells.remove(nextCell);
return false;
}
public static void main(String[] args) {
KnightsWalk gw = new KnightsWalk();
gw.initGrid();
gw.printGrid();
int startingcell[] = {0, 0};
gw.walk(startingcell);
System.out.println("" + visitedCells.size() + " of out " + (gridSize * gridSize) + " Cells Visited in the order " + visitedCells);
}
/**
* Auxiliary Support Methods for user output support
*/
private void printAtteptedMove(int[] start, int[] end) {
System.out.println(grid[start[0]][start[1]] + " -> " + grid[end[0]][end[1]]);
}
private void printGrid() {
System.out.println("----------------");
for (String[] gridrow : grid) {
for (int cell = 0; cell < gridrow.length; cell++) {
String sep = (cell < gridrow.length - 1) ? "," : "";
System.out.print(gridrow[cell] + sep);
}
System.out.println("\n");
}
System.out.println("----------------");
}
}
最佳答案
问题在于它不是真正的蛮力算法。你只是开始奔跑，直到什么都不可能。对于蛮力算法，您也必须尝试所有其他可能的移动，而不仅仅是那些以 a1->b3->c5 开头的移动 尝试暴力的递归函数
当您的移动列表(对于单个移动)完成时，我也不明白您为什么需要以下代码。
else{
int[] nc2 = { cell[0]+move[1], cell[1]+move[0] };
if(canMoveToCell(nc2)){
printMove(cell, nc2);
nextCellToMoveto=nc2;
break;
}
else{
nextCellToMoveto=cell;
}
更新: OP 的更新版本仍然存在错误。如果您尝试一条新路径，它应该忘记“visitedcells”中的旧路径。所以你要做的是:在函数“walk”中的 for 循环之后，从列表“visitedCells.txt”中删除元素。 您可以在此处的输出中看到您的错误:
[...]
h2 -> f1
b6 -> a8
f2 -> h1
这不是我想的样子
关于Java Knights Walk 算法(蛮力)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25224275/