Doubt : Direction Vector

This is the Solution for KNICOV problem.

This the another Problem on same lines from geeksforgeeks.

There are two arrays used named ‘dx’ and ‘dy’ which are common in both problems and named as ‘Direction Vector’ in gfgs solution.

I know they are used to somewhat check and validate next move in X and Y directions respectively.

But, I want to know how do you fill the values in these arrays?

And also can anyone share links to problems of these type?

1 Like

A knight move is defined as follows: It moves to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. (from Wikipedia)

So if you are at the square (x, y), you can either move to (x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1), (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2). Therefore you can extract the arrays dx = [2, 2, -2, -2, 1, 1, -1, -1] and dy = [1, -1, 1, -1, 2, -2, 2, -2] and iterate over them with

for (int move = 0; move < 8; move++) {
    new_x = old_x + dx[move];
    new_x = old_y + dy[move];
}

The order of possible moves can obviously vary. So you would end up at different

Here are two game theory problems about knights: A Chessboard Game, Chessboard Game, Again!

1 Like

direction array is used to go from a index to other indexes in certain directions as told in the question. The most common directions are going in 4 directions Up, Down, Left, Right, 8 directions Up, Down, Left, Right and 4 diagonal directions and knight directions(If you’ve played chess, you’d know how knight moves)

Now, we use 2 dimensional arrays to make a grid. suppose X,Y is the co-ordinate of the position in the grid. So how will you move upward direction. X+= (-1) and Y = 0. Add this in the direction array.

dx = {-1}
dy = {0}

Now, how will you move downward direction? X+= 1 and Y = 0. Add this also.

dx = {-1,1}
dy = {0,0}

Similarly after adding left and right directions, you will get,

dx = {-1,1,0,0}
dy = {0,0,-1,1}

So, now if you iterate through them and add them to X and Y one by one, you can move to all the 4 directions.

Here are the direction array of 8 direction movement and knight movement:

//8 direction movement
int dx[] = { -1, -1,  0, 1, 1, 1,  0, -1 };
int dy[] = {  0, -1, -1, -1,  0, 1, 1, 1 };


//knight movement
int dxK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int dyK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
1 Like

got it, Thanks mate! @afaxnraner

@sudip_95 Thanks mate!

1 Like