8 replies to this topic

[ngage]

A chessboard was given to us. Where in there was a Knight and King was placed on certain positions. Our aim is to reach the king from the knight in minimum no of counts. As we know, knight can either move 2 steps vertical/horizontal and 1 step horizontal/vertical. same goes here as well. Proper image of the chess board was given in the question paper, and all the positions(max 8) were given that knight can take in the first step.

plz tell me the logic behind it

[WingedPanther]

What part of the logic are you asking about? I can think of two different approaches to solve the problem off the top of my head. Do you have any ideas? Will this be C or C++?

[ngage]

well m asking about how to proceed through the question meaning by there are several ways in which knight can reach the king's position(from the starting position of knight in chessboard say 1row 2 col)
so how we can recursively define movement of knight so that it reaches the kings position with minimum number of steps

[Mathematix]

Homework! Just decide which are the best moves form a list of legal moves that progressively move you towards your goal.

[WingedPanther]

Is recursion required? I would mark all the spaces the knight can reach in 1 move with one, then all the spaces it can reach with 2 moves with two, etc.

[ngage]

i know the best moves which knight can take
but the question is how to implement them in c/c++ becoz there is no uniform pattern that knight follows

@WingedPanther
can u give me some of the code that comes in ur mind to implement wht ur saying(i.e marking all spaces that knight can reach step by step and eventually it will reach kings position)i think even in ur idea there is recursion

[PythonPower]

I would formulate it as a dynamic programming problem.

Given you are at position X and need to reach position Y. We define quick(Position) to be the shortest path from Position to Y. At each step you can move in 8 different ways. For each of those different moves find the new Position and check whether quick(Position) is the smallest from your current position. One you've found the smallest path from a new position, return the path returned by quick(Position) with the intermediate position appended as well.

To speed it all up use memoization (probably not needed for an 8×8 board). And by the end you should have an optimal path.

Also consider:
Dijkstra's algorithm - Wikipedia, the free encyclopedia

[WingedPanther]

I'm just envisioning an 8x8 array that I would cycle through a few times. I don't have any particular code in mind. I start with a basic algorithm, such as what I described above, then I incrementally turn pieces of it into actual code. I tend to code a bit, test a bit, code a bit, test a bit. So really, I'm looking at a while loop with nested for loops. The while loop is (while a square isn't reached),and the for loops traverse the array.

[LukeyJ]

Well if a piece can move 1 in either direction and 2 another. You need to work out in relation the other piece is to the other. Say 3 and 2, suggesting 2 to the right and 2 down, or 2 up depending on what axis you want. Then figure out which muliples of the 2 and 1 there is. Well, I think that may be an option but I haven't checked it. Hope it gives some inspiration.