I need an advice regarding this problem called "Knight Path". Given an n*n board whose cells are initialized to 0, I need to determine, given an arbitrary Knight's position, if the knight can pass through every cell on the board exactly once, where every cell the Knight had visited will be marked as counter, counting from: 1 - n^2. If a path is possible, I need to print the board. I need to print all the valid boards. The knight, for those who do not know the rules for chess, can move either up or down one square vertically and over two squares horizontally OR up or down two squares vertically and over one square horizontally.
For example given a 5*5 board, starting at (0,0) the method should print:
{{1,16,11,6,21},
{10,5,20,15,12},
{17,2,13,22,7},
{4,9,24,19,14},
{25,18,3,8,23}};
The above out put would be one of few, as there could be different other ways considering different initial positions. I've written the below code but it doesn't print anything. I need to spot the logic flaws here so I can make it work.
public class KnightDemo {
static int counter = 1;
public static void KnightPath(int[][] b, int i, int j) {
b[i][j] = counter;
if (counter == b.length * b[0].length) {
printMatrix(b);
return;
} else {
counter ;
if (isValid(b, i - 1, j 2) && b[i - 1][j 2] == 0) {
KnightPath(b, i - 1, j 2);
} else {
return;
}
if (isValid(b, i - 2, j 1) && b[i - 1][j 1] == 0) {
KnightPath(b, i - 2, j 1);
} else {
return;
}
if (isValid(b, i - 1, j - 2) && b[i - 1][j - 2] == 0) {
KnightPath(b, i - 1, j - 2);
} else {
return;
}
if (isValid(b, i - 2, j - 1) && b[i - 2][j - 1] == 0) {
KnightPath(b, i - 2, j - 1);
} else {
return;
}
if (isValid(b, i 2, j - 1) && b[i 2][j - 1] == 0) {
KnightPath(b, i 2, j - 1);
} else {
return;
}
if (isValid(b, i 1, j - 2) && b[i 1][j - 2] == 0) {
KnightPath(b, i 1, j - 2);
} else {
return;
}
if (isValid(b, i 1, j 2) && b[i 1][j 2] == 0) {
KnightPath(b, i 1, j 2);
} else {
return;
}
if (isValid(b, i 2, j 1) && b[i 2][j 1] == 0) {
KnightPath(b, i 2, j 1);
} else {
return;
}
}
}
public static boolean isValid(int[][] a, int i, int j) {
if (i > a.length - 1 || i < 0 || j > a[0].length - 1 || j < 0) {
return false;
}
return true;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
KnightPath(b, i, j);
}
}
}
public static void printMatrix(int[][] matrix) {
for (int[] rows: matrix) {
StringBuilder buff = new StringBuilder();
buff.append("[");
for (int i = 0; i < rows.length; i ) {
int value = rows[i];
buff.append(value);
if (i < rows.length - 1) {
buff.append(", ");
}
}
buff.append("]");
System.out.println(buff.toString());
}
}
}
The output is
[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[16, 17, 18, 19, 20]
[21, 22, 23, 24, 25]
CodePudding user response：
To solve for all paths, you need to reset the placed values of paths you've exhausted so that newer paths can access them. Additionally, your counter should reflect how deep you've gone, so that if you back out to try another path, your counter should roll back, too. I would recommend passing a counter as a parameter rather than using a static counter. Also, if you want to try all valid possibilities, then you need to avoid those return statements whenever one possibility is deemed invalid.
public static void KnightPath(int[][] b, int i, int j, int counter) {
...
if (isValid(b, i - 1, j 2) && b[i - 1][j 2] == 0) {
KnightPath(b, i - 1, j 2, counter 1);
}
...
b[i][j] = 0;
}
public static void main(String[] args) {
...
KnightPath(b, i, j, 1);
...
}
CodePudding user response：
Based on the OP's explanation in the comments section, the goal is to map out all possible paths a knight can take from a location on the board. Basically, given the knight's location b[i][j], calculate all legal paths.
If a knight is at {0, 0}, the knight has only two legal paths that end in {1, 2} and {2, 1}. The idea here is to capture that in a map. Then, move on to the next location on the board (i.e. {1, 0}) and repeat the process. Since each board location can be identified as an integer (counter), we can use it to map the paths...
0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
...
n=[{n^-2 - 3, n^-2 - 2}, {n^-2 - 2, n^-2 - 3}] // last location is always a corner
To make it simple, I decided to create a Java record of coordinates to store the {x, y} coordinates of the end location of a given path, making my map <Integer, Set<Coordinates>>
The logic here is quite simple. First, seed the map with empty lists for each one corresponding location in the matrix. Then, iterate through the matrix (2D array) and calculate all the legal paths a knight can take from this location. For each legal path, add the Coordinates of the end location of the path. I used a Set to eliminate duplicate coordinates.
My solution (perhaps not optimal) is as follows (used OP code as baseline) - Need Java 15 or later to run. For Java 14 or earlier, replace Coordinates with an Integer[] of length 2, and store the coordinates in it.
public class KnightDemo {
static int counter = 0;
static Map<Integer, Set<Coordinates>> map = new HashMap<>();
public static void KnightPath(int[][] b, int i, int j) {
Set<Coordinates> paths = map.get(counter);
if (isValid(b, i - 1, j 2)) {
paths.add(new Coordinates(i - 1, j 2));
map.put(counter, paths);
}
if (isValid(b, i - 2, j 1)) {
paths.add(new Coordinates(i - 2, j 1));
map.put(counter, paths);
}
if (isValid(b, i - 1, j - 2)) {
paths.add(new Coordinates(i - 1, j - 2));
map.put(counter, paths);
}
if (isValid(b, i - 2, j - 1)) {
paths.add(new Coordinates(i - 2, j - 1));
map.put(counter, paths);
}
if (isValid(b, i 2, j - 1)) {
paths.add(new Coordinates(i 2, j - 1));
map.put(counter, paths);
}
if (isValid(b, i 1, j - 2)) {
paths.add(new Coordinates(i 1, j - 2));
map.put(counter, paths);
}
if (isValid(b, i 1, j 2)) {
paths.add(new Coordinates(i 1, j 2));
map.put(counter, paths);
}
if (isValid(b, i 2, j 1)) {
paths.add(new Coordinates(i 2, j 1));
map.put(counter, paths);
}
counter ;
}
public static boolean isValid(int[][] a, int i, int j) {
return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
map.put(counter, new HashSet<>()); // add a new set before calculating paths
KnightPath(b, i, j);
}
}
map.entrySet().stream().forEach(System.out::println);
}
private static record Coordinates(int row, int col) {
@Override
public String toString() {
return "{" row ", " col "}";
}
}
}
The program outputs:
0=[{1, 2}, {2, 1}]
1=[{2, 2}, {1, 3}, {2, 0}]
2=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
3=[{2, 2}, {1, 1}, {2, 4}]
4=[{2, 3}, {1, 2}]
5=[{2, 2}, {0, 2}, {3, 1}]
6=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
7=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
8=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
9=[{3, 3}, {2, 2}, {0, 2}]
10=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
11=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
12=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
13=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
14=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
15=[{2, 2}, {1, 1}, {4, 2}]
16=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
17=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
18=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
19=[{2, 2}, {1, 3}, {4, 2}]
20=[{3, 2}, {2, 1}]
21=[{3, 3}, {2, 2}, {2, 0}]
22=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
23=[{2, 2}, {2, 4}, {3, 1}]
24=[{2, 3}, {3, 2}]
UPDATE: Can you use this in a real game of chess?
Yes, you can! Suppose you seed the matrix with black and white. You could enhance the logic so that, if the end location corresponds to your color, you don't add as a valid path since it is blocked by one of your pieces.
SECOND UPDATE: Same code but using Coordinate object as key
public class KnightDemo {
static int counter = 0;
static Map<Coordinates, Set<Coordinates>> map = new HashMap<>();
public static void KnightPath(int[][] b, Coordinates coordinates) {
Set<Coordinates> paths = map.get(coordinates);
if (isValid(b, coordinates.row() - 1, coordinates.col() 2)) {
paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 2, coordinates.col() 1)) {
paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 1, coordinates.col() - 2)) {
paths.add(new Coordinates(coordinates.row() - 1, coordinates.col() - 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() - 2, coordinates.col() - 1)) {
paths.add(new Coordinates(coordinates.row() - 2, coordinates.col() - 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 2, coordinates.col() - 1)) {
paths.add(new Coordinates(coordinates.row() 2, coordinates.col() - 1));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 1, coordinates.col() - 2)) {
paths.add(new Coordinates(coordinates.row() 1, coordinates.col() - 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 1, coordinates.col() 2)) {
paths.add(new Coordinates(coordinates.row() 1, coordinates.col() 2));
map.put(coordinates, paths);
}
if (isValid(b, coordinates.row() 2, coordinates.col() 1)) {
paths.add(new Coordinates(coordinates.row() 2, coordinates.col() 1));
map.put(coordinates, paths);
}
}
public static boolean isValid(int[][] a, int i, int j) {
return i >= 0 && i < a.length && j >= 0 && j < a[0].length;
}
public static void main(String[] args) {
int[][] b = new int[5][5];
for (int i = 0; i < b.length; i ) {
for (int j = 0; j < b[0].length; j ) {
Coordinates coordinates = new Coordinates(i, j);
map.put(coordinates, new HashSet<>());
KnightPath(b, coordinates);
counter ;
}
}
map.entrySet().stream().forEach(System.out::println);
}
private static record Coordinates(int row, int col) {
@Override
public String toString() {
return "{" row ", " col "}";
}
}
}
Outputs:
{0, 0}=[{1, 2}, {2, 1}]
{2, 2}=[{0, 1}, {3, 4}, {1, 4}, {0, 3}, {4, 1}, {3, 0}, {1, 0}, {4, 3}]
{4, 4}=[{2, 3}, {3, 2}]
{0, 1}=[{2, 2}, {1, 3}, {2, 0}]
{2, 3}=[{1, 1}, {4, 4}, {0, 2}, {0, 4}, {4, 2}, {3, 1}]
{0, 2}=[{2, 3}, {1, 4}, {2, 1}, {1, 0}]
{2, 4}=[{1, 2}, {0, 3}, {4, 3}, {3, 2}]
{0, 3}=[{2, 2}, {1, 1}, {2, 4}]
{0, 4}=[{2, 3}, {1, 2}]
{3, 0}=[{2, 2}, {1, 1}, {4, 2}]
{3, 1}=[{2, 3}, {1, 2}, {1, 0}, {4, 3}]
{1, 0}=[{2, 2}, {0, 2}, {3, 1}]
{3, 2}=[{1, 1}, {4, 4}, {2, 4}, {1, 3}, {4, 0}, {2, 0}]
{1, 1}=[{2, 3}, {0, 3}, {3, 0}, {3, 2}]
{3, 3}=[{1, 2}, {1, 4}, {4, 1}, {2, 1}]
{1, 2}=[{0, 0}, {3, 3}, {2, 4}, {0, 4}, {3, 1}, {2, 0}]
{3, 4}=[{2, 2}, {1, 3}, {4, 2}]
{1, 3}=[{0, 1}, {3, 4}, {3, 2}, {2, 1}]
{1, 4}=[{3, 3}, {2, 2}, {0, 2}]
{4, 0}=[{3, 2}, {2, 1}]
{4, 1}=[{3, 3}, {2, 2}, {2, 0}]
{2, 0}=[{1, 2}, {0, 1}, {4, 1}, {3, 2}]
{4, 2}=[{3, 4}, {2, 3}, {3, 0}, {2, 1}]
{2, 1}=[{0, 0}, {3, 3}, {1, 3}, {0, 2}, {4, 0}, {4, 2}]
{4, 3}=[{2, 2}, {2, 4}, {3, 1}]
They don't print in the same order, but you can tell that coordinates {2, 2} is the same set as counter==12 in the previous example. Cell {2, 2} is the 13th cell from the top-left.