0
Я пытаюсь написать Knights Walk Algorithm (перебор) с использованием Java. Я смог создать программу для перемещения через сетку 5x5, но программа всегда оставляет вне 06 клеток. И мой Рыцарь не может двигаться никуда от этих квадратов.Алгоритм Walk Knight Walk (Brute Force)
Для примера у меня есть следующие сетки:
----------------
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("----------------");
}
}
Update 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("----------------");
}
}
Это не «грубая сила». Вы только ищите дальнейшие действия, но никогда не «удаляете» их, если попадете в неразрешимое состояние. Google для «алгоритмов обратного отслеживания» – SJuan76
Алгоритмы грубой силы напоминают мне человека, снимающего стену с кувалдой, потому что он не любит цвет краски и не без оснований. Алгоритмы грубой силы буквально пытаются КАЖДОЙ возможности, пока один из них не работает, сравнимый с бросая колоду карт в воздух, поднимая ее, и если она не совсем в порядке, бросьте ее снова. (Основа богосорта по сути.) –