Horsin around

Computer Science Level 1

In this chessboard, considering that the knight cannot walk into the black squares, what is the minimum number of steps it needs to go from a1 to c7?


The answer is 4.

João Areias by João Areias , 24, Brazil

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

4 solutions

João Areias
Dec 27, 2017

We can think of the board as a graph where every node is a position on the board and every edge is a possible move from one position to another. Then one can apply the breadth-first search algorithm to find the shortest path. Here is my c++11 implementation on an implicit graph. 

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
#include <bits/stdc++.h>

using namespace std;

short bfs(short start_x, short start_y, short end_x, short end_y, short board[12][12]){
    /* Returns the distance from start to goal.
    Returns -1 if no path is found */
    queue< tuple<short, short, short> > bfs_queue;
    tuple<short, short, short> placeholder;
    short pos_x = start_x;
    short pos_y = start_y;
    short dist = 0;
    board[pos_x][pos_y] = 1;
    bfs_queue.push(make_tuple(pos_x, pos_y, 0));

    while(pos_x != end_x || pos_y != end_y){
        if(bfs_queue.empty())
            return -1;
        placeholder = bfs_queue.front();
        bfs_queue.pop();

        pos_x = get<0>(placeholder);
        pos_y = get<1>(placeholder);
        dist  = get<2>(placeholder);

        if(!board[pos_x+2][pos_y+1]){
            board[pos_x+2][pos_y+1] = 1;
            bfs_queue.push(make_tuple(pos_x+2, pos_y+1, dist+1));
        }
        if(!board[pos_x+2][pos_y-1]){
            board[pos_x+2][pos_y-1] = 1;
            bfs_queue.push(make_tuple(pos_x+2, pos_y-1, dist+1));
        }
        if(!board[pos_x-2][pos_y+1]){
            board[pos_x-2][pos_y+1] = 1;
            bfs_queue.push(make_tuple(pos_x-2, pos_y+1, dist+1));
        }
        if(!board[pos_x-2][pos_y-1]){
            board[pos_x-2][pos_y-1] = 1;
            bfs_queue.push(make_tuple(pos_x-2, pos_y-1, dist+1));
        }
        if(!board[pos_x+1][pos_y+2]){
            board[pos_x+1][pos_y+2] = 1;
            bfs_queue.push(make_tuple(pos_x+1, pos_y+2, dist+1));
        }
        if(!board[pos_x-1][pos_y+2]){
            board[pos_x-1][pos_y+2] = 1;
            bfs_queue.push(make_tuple(pos_x-1, pos_y+2, dist+1));
        }
        if(!board[pos_x+1][pos_y-2]){
            board[pos_x+1][pos_y-2] = 1;
            bfs_queue.push(make_tuple(pos_x+1, pos_y-2, dist+1));
        }
        if(!board[pos_x-1][pos_y-2]){
            board[pos_x-1][pos_y-2] = 1;
            bfs_queue.push(make_tuple(pos_x-1, pos_y-2, dist+1));
        }
    }
    return dist;
}

int main(){
    /* Board representation:
        - 0 Places where the knight can move to
        - 1 Places where knight can't move to
    */
    short board[12][12] = {
        {1,1,1,1,1,1,1,1,1,1,1,1},
        {1,1,1,1,1,1,1,1,1,1,1,1},
        {1,1,0,0,0,0,0,0,0,0,1,1},
        {1,1,0,0,0,0,0,0,1,0,1,1},
        {1,1,0,0,0,0,0,0,0,0,1,1},
        {1,1,0,0,0,1,1,0,0,0,1,1},
        {1,1,0,0,0,1,1,0,0,0,1,1},
        {1,1,0,1,0,0,0,0,0,0,1,1},
        {1,1,0,1,0,0,0,0,0,0,1,1},
        {1,1,0,0,0,0,0,0,0,0,1,1},
        {1,1,1,1,1,1,1,1,1,1,1,1},
        {1,1,1,1,1,1,1,1,1,1,1,1},
    };
    // bfs(9, 2, 4, 4, board)
    printf("%hd\n", bfs(9, 2, 3, 4, board));
    return 0;
}

and here is one path

As by request, I've added a python version, I also added more comments to hopefully help 

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
from queue import Queue

def bfs(src, dst, board):
    bfs_queue = Queue()

    x, y = src
    dist = 0
    board[x][y] = 1
    bfs_queue.put((x, y, dist))

    while (x, y) != dst:
        # Returns -1 if can't find path
        if bfs_queue.empty():
            return -1

        # Get knight position from queue
        x, y, dist = bfs_queue.get()

        """
        Add all available knights moves to queue
        """
        if board[x+2][y+1] == 0:
            board[x+2][y+1] = 1
            bfs_queue.put((x+2, y+1, dist+1))

        if board[x+2][y-1] == 0:
            board[x+2][y-1] = 1
            bfs_queue.put((x+2, y-1, dist+1))

        if board[x-2][y+1] == 0:
            board[x-2][y+1] = 1
            bfs_queue.put((x-2, y+1, dist+1))

        if board[x-2][y-1] == 0:
            board[x-2][y-1] = 1
            bfs_queue.put((x-2, y-1, dist+1))

        if board[x+1][y+2] == 0:
            board[x+1][y+2] = 1
            bfs_queue.put((x+1, y+2, dist+1))

        if board[x+1][y-2] == 0:
            board[x+1][y-2] = 1
            bfs_queue.put((x+1, y-2, dist+1))

        if board[x-1][y+2] == 0:
            board[x-1][y+2] = 1
            bfs_queue.put((x-1, y+2, dist+1))

        if board[x-1][y-2] == 0:
            board[x-1][y-2] = 1
            bfs_queue.put((x-1, y-2, dist+1))

    return dist



def main():
    """ Board representation:
        - 0 Places where the knight can move to
        - 1 Places where knight can't move to

        1 added as padding around the board so knight
        won't travel outside
    """
    board = [
        [1,1,1,1,1,1,1,1,1,1,1,1],
        [1,1,1,1,1,1,1,1,1,1,1,1],
        [1,1,0,0,0,0,0,0,0,0,1,1],
        [1,1,0,0,0,0,0,0,1,0,1,1],
        [1,1,0,0,0,0,0,0,0,0,1,1],
        [1,1,0,0,0,1,1,0,0,0,1,1],
        [1,1,0,0,0,1,1,0,0,0,1,1],
        [1,1,0,1,0,0,0,0,0,0,1,1],
        [1,1,0,1,0,0,0,0,0,0,1,1],
        [1,1,0,0,0,0,0,0,0,0,1,1],
        [1,1,1,1,1,1,1,1,1,1,1,1],
        [1,1,1,1,1,1,1,1,1,1,1,1],
    ]
    src = (9, 2) # Index of knights initial position
    dst = (3, 4) # Index of knights final position

    print(bfs(src, dst, board))


if __name__ == "__main__":
    main()

10 Helpful 2 Interesting 2 Brilliant 1 Confused

Você é brasileiro? No xadrez em inglês a peça do cavalo é chamado de cavaleiro (Knight). Só uma observação. Aliás, bom problema.

A Former Brilliant Member - 3 years, 5 months ago

Log in to reply

Vish, agora que eu vi que eu coloquei errado no problema também né, valeu por me mostrar. No título era só como um trocadilho mesmo por conta do desenho do (Knight) ser um cavalo mesmo não tendo esse nome no inglês mas valeu mesmo assim.

João Areias - 3 years, 5 months ago

Log in to reply

Acontece, o título ficou bom

A Former Brilliant Member - 3 years, 5 months ago

This should be a logic problem.

Munem Shahriar - 3 years, 5 months ago

Log in to reply

Works by logic too, that's a good thing about this problem. What you do by logic is the same as what you do on the breadth-first search algorithm and the example is small enough that you can work it by hand but at the same time it should give you some intuition on how the algorithm works. I really liked your answer, but now I challenge you, can you generalize the problem for, given an arbitrary start position, how you can reach an arbitrary end position?

João Areias - 3 years, 5 months ago

It can be approached by an algorithm, however, this is much more time consuming. I always prefer a more simple and shorter proof, and I feel that a solution such as mine (see below/above) is more elegant (which is done by logic).

Stephen Mellor - 3 years, 5 months ago

can someone do this in python?

J M - 3 months, 2 weeks ago

Log in to reply

There it is, I've added to my solution

João Areias - 3 months, 1 week ago
Munem Shahriar
Dec 27, 2017

Solution: 4 moves.

Reason: The first valid move for the white knight must be c2. After c2, the knight should move to b4 or e3 or e1. If the knight moves to e3 and e1, it must take more than 4 moves to reach c7. So the knight should move to b4. After b4, the knight should move either a6 or c6. We observe that if the knight moves to a6, it takes just 2 moves to reach c7 from b4. So the knight should move to a6.

Hence the minimum number of moves required for the knight to reach a7 is 4.

9 Helpful 0 Interesting 1 Brilliant 0 Confused

I just want to write another answer A1→C2→A3→B5→C7

3 Helpful 0 Interesting 2 Brilliant 0 Confused
Stephen Mellor
Dec 28, 2017

We can find a solution in 4 steps: A1 → C2 → B4 → A6 → C7. Now we just need to prove it is the shortest.

The knight starts on a black square, and has to get to a black square. Since, each move alternates the colour, it will take an even number of moves. 2 moves is clearly not possible just by looking at it (even ignoring the squares that it can't pass through) but if you want a more rigorous approach you can use Pythagoras. Therefore, 4 is the lower bound, and it is possible, so it is the answer.

2 Helpful 1 Interesting 1 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...