Horsin around part 2

Computer Science Level 3

In the board shown, there are positions that are reachable by the knight and some that aren't.

From the positions that are reachable, considering that the knight always takes the shortest path to any position, what is the farthest position from the knight and how many moves does it take to reach it?

If i i is the row index as seen in the image, j j is the column index also as seen in the image, and d d is the number of moves it takes to reach the position, what is i × j × d i\times j\times d of this position?


Clarification: The farthest distance is the one that takes the most moves to reach.

Try solving an easier version here .


The answer is 1859.

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.

2 solutions

João Areias
Dec 28, 2017

The board can be interpreted as a graph where positions are nodes and the movement from one position to the other is an edge. From that, we can use the Breadth-First search to find the distance to a position. We just need to choose then the position with the largest distance, which in this case is the position (13, 13) with a distance of 11 moves. As seen here:

Here is my implementation of the algorithm in c++ 

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
#include <bits/stdc++.h>
#define size 16
using namespace std;

short bfs(short start_x, short start_y, short end_x, short end_y, short board[size+4][size+4]){
    /* 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;
}

void copy(short b1[size+4][size+4], short b2[size+4][size+4]){
    for(short i=0; i<size+4; i++){
        for(short j=0; j<size+4; j++)
            b2[i][j] = b1[i][j];
    }
}

int main(){
    /* Board representation:
        - 0 Places where the knight can move to
        - 1 Places where knight can't move to
    */
    // +4 adds boundry to the knight
    short board[size+4][size+4] = {
        {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,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
        {1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
        {1,1,0,1,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1},
        {1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1},
        {1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1},
        {1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1},
        {1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1},
        {1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1},
        {1,1,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,1,1},
        {1,1,0,1,0,1,0,0,0,1,1,0,0,0,1,0,1,0,1,1},
        {1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,1,0,0,1,1},
        {1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1},
        {1,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,1,1},
        {1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1},
        {1,1,0,1,0,0,0,0,1,0,0,1,0,0,0,0,1,0,1,1},
        {1,1,0,1,1,0,0,0,0,1,1,0,0,0,0,1,1,0,1,1},
        {1,1,0,0,0,0,0,0,0,0,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,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
    };
    short board_copy[size+4][size+4];
    short max_i = -1, max_j = -1, max_d = -1, d;
    for(short i=2; i<18; i++){
        for(short j=2; j<18; j++){
            copy(board, board_copy);
            d = bfs(3, 2, i, j, board_copy);
            printf("i = %02hd  j = %02hd  d = %02hd\n", i-2, j-2, d);
            if(d > max_d){
                max_i = i-2;
                max_j = j-2;
                max_d = d;
            }
        }

    }
    printf("\nMax distance found at:\n");
    printf("i = %02hd  j = %02hd  d = %02hd\n", max_i, max_j, max_d);
    return 0;
}

4 Helpful 0 Interesting 0 Brilliant 0 Confused

Isn't it possible to reach a further spot, i.e., (14,15)? (Taking 14 as the vertical component and 15 as the horizontal) Is the following path incorrect?: (0,1), (1,3), (2,5), (4,6), (5,8), (6,10), (8,9), (9,11), (10,13), (12,14), (14,15)

kabir arora - 3 years, 5 months ago

Log in to reply

That's the thing, because of how the knight moves, it takes fewer steps to reach (14,15) and (15,14) than to reach (13, 13) both of them only takes 10 steps

João Areias - 3 years, 5 months ago
Pegajoso Piston
Jan 7, 2018

Start by giving all positions a knights-move away from the start a value of 1. Every position a knights-move away from any of those that was not already traversed is given a value of 2 and so on. When this is finished, the position (13, 13) is the farthest away at 11 moves. My code can be seen here .

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Nice code and it gives a great visualization of the algorithm.

João Areias - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...