Click here to Skip to main content
15,943,582 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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.
Java
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
Java
public class At {

    private final static int TahtaBoyutu = 8;
    public int base = TahtaBoyutu + 4;
    //ArrayList<Integer> hareketler = new ArrayList<>();
    //public final static int[][] aktar = new int[8][8];
    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();
        }
    }
Posted

1 solution

hmmm

why don't you run two for loops across your grid and use the grid value as the index into a linear array (as long as the grid values are unique)

Java
// pseudo code 

for rows = 0..7
  for cols = 0..7
     linear string array[grid[row, col]] = ascii(65+row) concat ascii(48+col) 
  end-for
end-for

for linear-index 1..64
  print linear string array[linear-index]
end-for 
 
Share this answer
 
Comments
FoxRoot 10-Nov-14 7:42am    
I tried this. But it doesn' t work at all. I think I need ArrayList or Generic type. However, couldn't resolve.
Garth J Lancaster 10-Nov-14 7:59am    
you fail to understand what 'pseudo code' is - its an idea, expressed in very rough code terms - its never meant to run directly
FoxRoot 10-Nov-14 8:03am    
Clearly, I know what puseudo code is. However;


public final static int[][] demo= new int[8][8];

for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
demo[grid[row, col]] = 0; // What to type here? I filled by zeros stil not working.
}
}
FoxRoot 10-Nov-14 7:43am    
Could you re-write it in Java please? Because I am newbie
and have some problems.
Garth J Lancaster 10-Nov-14 8:02am    
no, I suck mightely at java - you know for loops, arrays - you just have to declare a string array of 65 elements, and look up how to turn an integer into an ascii character or string - iirc, you can go something like char c = (ascii)int .... you also need to know that in ASCII, 65 is 'A', 66 is 'B'... and 48 is '0', 49 is '1'

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900