Hello everyone,
I am studying on alghroitms. So, I have found a tradiational problem; which is "Knight's Tour".
Basicly, I have created the solution. However, I cannot format it.
23 8 59 62 25 10 29 54
60 63 24 9 52 55 26 11
7 22 61 58 41 28 53 30
64 37 40 51 56 49 12 27
21 6 57 42 39 46 31 48
36 3 38 45 50 43 16 13
5 20 1 34 15 18 47 32
2 35 4 19 44 33 14 17
This is sample of output. I want to see the output like this
First: G3 (Number 1)
Second: H1 (Number 2)
Third: F2 (Number 3)
and so on.
What is the best way to do this. I sorted the array but, still have problems. I am loosing the old indexes. So I can' t rename them.
Here is my code:
Main.
public static void main(String[] args) {
At _at = new At();
_at.grid = new int[_at.base][_at.base];
_at.total = (_at.base - 4) * (_at.base - 4);
for (int r = 0; r < _at.base; r++) {
for (int c = 0; c < _at.base; c++) {
if (r < 2 || r > _at.base - 3 || c < 2 || c > _at.base - 3) {
_at.grid[r][c] = -1;
}
}
}
int row = 2 + (int) (Math.random() * (_at.base - 4));
int col = 2 + (int) (Math.random() * (_at.base - 4));
_at.grid [row][col] = 1;
if (_at.solve(row, col, 2)) {
_at.printResult();
} else {
System.out.println("no result");
}
}
Horse Class
public class At {
private final static int TahtaBoyutu = 8;
public int base = TahtaBoyutu + 4;
public final static int[][] moves = {{1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2},
{-2, 1}, {-2, -1}, {-1, -2}};
public static int[][] grid;
public int total;
public boolean solve(int r, int c, int count) {
if (count > total) {
return true;
}
List<int[]> nbrs = neighbors(r, c);
if (nbrs.isEmpty() && count != total) {
return false;
}
Collections.sort(nbrs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
});
for (int[] nb : nbrs) {
r = nb[0];
c = nb[1];
grid[r][c] = count;
if (!orphanDetected(count, r, c) && solve(r, c, count + 1)) {
return true;
}
grid[r][c] = 0;
}
return false;
}
private static List<int[]> neighbors(int r, int c) {
List<int[]> nbrs = new ArrayList<>();
for (int[] m : moves) {
int x = m[0];
int y = m[1];
if (grid[r + y][c + x] == 0) {
int num = countNeighbors(r + y, c + x);
nbrs.add(new int[]{r + y, c + x, num});
}
}
return nbrs;
}
private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : moves) {
if (grid[r + m[1]][c + m[0]] == 0) {
num++;
}
}
return num;
}
public boolean orphanDetected(int cnt, int r, int c) {
if (cnt < total - 1) {
List<int[]> nbrs = neighbors(r, c);
for (int[] nb : nbrs) {
if (countNeighbors(nb[0], nb[1]) == 0) {
return true;
}
}
}
return false;
}
public void printResult() {
for (int[] row : grid) {
for (int i : row) {
if (i == -1) {
continue;
}
System.out.printf("%2d ", i);
}
System.out.println();
}
}