CODEWITHSUNDEEP
javaalgorithmsearchgraph-algorithmgame-theory
swapnil
swapnil

Reputation: 75

Minimum number steps to reach goal in chess - knight traversal with BFS

Code given below works for chess of size less than 13 efficiently, but after that it takes too much time and runs forever. I want to reduce time to reach till end node. Also this code finds minimum path from starti,startj to endi,endj where starti and startj takes value from 1 to n-1.

Here is the problem that I am trying to solve:
https://www.hackerrank.com/challenges/knightl-on-chessboard/problem

Program: 

import java.util.LinkedList;<br>
import java.util.Scanner;

class Node {

    int x,y,dist;

    Node(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }

    public String toString() {
        return "x: "+ x +" y: "+y +" dist: "+dist;
    }
}

class Solution {

    public static boolean checkBound(int x, int y, int n) {

        if(x >0 && y>0 && x<=n && y<=n)
            return true;
        return false;
    }

    public static void printAnswer(int answer[][], int n) {
        for(int i=0; i<n-1; i++) {
            for(int j=0; j<n-1; j++) {
                System.out.print(answer[i][j]+" ");
            }
            System.out.println();
        }

    }

    public static int findMinimumStep(int n, int[] start, int[] end, int a, int b) {

        LinkedList<Node> queue = new LinkedList();
        boolean visited[][] = new boolean[n+1][n+1];
        queue.add(new Node(start[0],start[1],0));       
        int x,y;

        int[] dx = new int[] {a, -a, a, -a, b, -b, b, -b};
        int[] dy = new int[] {b, b, -b, -b, a, a, -a, -a};


        while(!queue.isEmpty()) {
            Node z = queue.removeFirst();
            visited[z.x][z.y] = true;

            if(z.x == end[0] && z.y == end[1])
                return z.dist;

            for(int i=0; i<8; i++)
            {
                x = z.x + dx[i];
                y = z.y + dy[i];            
                if(checkBound(x,y,n) && !visited[x][y])
                    queue.add(new Node(x,y,z.dist+1));
            }
        }
        return -1;
    }

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int start[] = new int[] {1,1};
        int goal[] = new int[] {n,n};
        int answer[][] = new int[n-1][n-1];

        for(int i=1; i<n; i++) {
            for(int j=i; j<n; j++) {
                int result = findMinimumStep(n, start, goal, i, j);
                answer[i-1][j-1] = result;
                answer[j-1][i-1] = result;
            }
        }
        printAnswer(answer,n);

    }
}

Upvotes: 2

Views: 1848

Answers (3)

Dimitris
Dimitris

Reputation: 589

The most effective solution in your problem is Dijkstra's algorithm. Treat the squares as nodes and draw edges towards the other squares/nodes that the knight can visit. Then run the algorithm for this graph. It performs in logarithmic time so it scales pretty good for big problems.

A* search suggest by MrSmith, is a heuristic so I would not suggest it for this kind of problem.

Dijkstra is an important algorithm and implementing it will help you solve many similar problems in the future, for example you can also solve this problem problem with the same logic.

Upvotes: 0

DAle
DAle

Reputation: 9117

You set visited too late and the same cells are added multiple times to the queue, then you pop them from the queue without checking their visited state that makes things even worse. This leads to the fast growth of the queue.

You need to set visited right after you add the Node to the queue:

if(checkBound(x,y,n) && !visited[x][y]) {
    queue.add(new Node(x,y,z.dist+1)); 
    visited[x][y] = true;   
}

Upvotes: 2

MrSmith42
MrSmith42

Reputation: 10151

Even if you optimize your code, you will not reduce the complexity of the algorithm.

I think you need to think about how to reduce the search space. Or search it in a clever order.

I would go for a A*-search

Upvotes: 0

Related Questions