Knight Project

[SrPuma]

Good morning, i would like to say hi to this community as im new here and im in need of a big help as im new to the Languange LISP as well, my issue is that i have to make a small app, chess game like where i have 2 pairs of knights in a chess board, black and white pieces, being the purpose to have them swap their positions with each other with the least movements possible, could someone point me to the right direction maybe?

Code: Select all

(defun getPos (row col)
  (list
    (list (+ row 2) (+ col 1))
    (list (+ row 2) (- col 1))
    (list (+ row 1) (+ col 2))
    (list (+ row 1) (- col 2))
    (list (- row 2) (+ col 1))
    (list (- row 2) (- col 1))
    (list (- row 1) (+ col 2))
    (list (- row 1) (- col 2))) )

Being as it is im trying to follow the Knight Tour example, how can i build the function to verify if the position to be moved into is not "filled" with another knight?

Best Regards

[nuntius]

What data structure are you using to store the game board? (Or what type of structure do you want to use?)

[saulgoode]

The stated problem can be simplified to the task of finding the shortest path from the white knight's starting square to the black knight's starting square. The actual place where the knights meet each other would lie midway along this path.

Unlike the Knight's Tour problem, there are an infinite number of routes that your knights could conceivably take (since there's no restriction against revisiting a square). The situation is not hopeless, however, because if given an upper bound to the number of moves that can be made, only a finite number of routes are possible. The absolute worst case for an upper bound would be 63 moves, the number of moves in a knight's tour solution.

The problem then becomes attempting each possible path until the upper bound is exceeded. If a solution is found before exceeding your upper bound, the number of moves of that solution becomes the new upper bound, and you continue your search. When you reach the point where no more routes can be found with fewer moves than your upper bound, you have your solution (if the number of moves equals the upper bound then you have an additional solution).

This approach leads to an untenable number of iterations when the upper bound is too large, but it would seem manageable if the solution can be found in a dozen or so moves. Since the number of iterations grows exponentially, it would be advisable to start with an upper bound of one and if no solution is found increase it by one, repeating until a solution is found. Hopefully a solution will arise before the upper bound reaches the point where it requires days to iterate through all the possible moves. (It would seem to me that even the worst case positioning of the starting and ending squares shouldn't demand more than a dozen moves, though I haven't done any analysis on this. EDIT: after some investigation, I've determined that a knight can reach any square on the board in six or fewer moves.)

[SrPuma]

What data structure are you using to store the game board? (Or what type of structure do you want to use?)

The stated problem can be simplified to the task of finding the shortest path from the white knight's starting square to the black knight's starting square. The actual place where the knights meet each other would lie midway along this path.

Unlike the Knight's Tour problem, there are an infinite number of routes that your knights could conceivably take (since there's no restriction against revisiting a square). The situation is not hopeless, however, because if given an upper bound to the number of moves that can be made, only a finite number of routes are possible. The absolute worst case for an upper bound would be 63 moves, the number of moves in a knight's tour solution.

The problem then becomes attempting each possible path until the upper bound is exceeded. If a solution is found before exceeding your upper bound, the number of moves of that solution becomes the new upper bound, and you continue your search. When you reach the point where no more routes can be found with fewer moves than your upper bound, you have your solution (if the number of moves equals the upper bound then you have an additional solution).

This approach leads to an untenable number of iterations when the upper bound is too large, but it would seem manageable if the solution can be found in a dozen or so moves. Since the number of iterations grows exponentially, it would be advisable to start with an upper bound of one and if no solution is found increase it by one, repeating until a solution is found. Hopefully a solution will arise before the upper bound reaches the point where it requires days to iterate through all the possible moves. (It would seem to me that even the worst case positioning of the starting and ending squares shouldn't demand more than a dozen moves, though I haven't done any analysis on this.)

The board will be nxn as we are asked to create a matrix (list with n lists of n atoms), my problem is that we still havent reached that part in the classes and having other projects of other areas piling up i need to start researching, thus asking for aid here

how can i create a chess based on that to work with the row and cols of the knights movements?

[nuntius]

It sounds like you have a lot of reading and practice to do.

This might help you get started, though its a proper matrix, not a list of lists.

Code: Select all

(let ((board (make-array '(8 8))))
  (dotimes (i 8)
    (dotimes (j 8)
      (setf (aref board i j) (+ (* 8 i) j))))
  board)

[saulgoode]

The problem you've stated does not actually require that you create a chessboard. When your program attempts to move a piece, it cares whether 1) you have exceeded the 'upper limit' for number of moves allowed, 2) the move is valid for a knight, 3) the destination square lands on the chessboard, and 4) the same move has already been made from the same square.

Since you want to create a "path" as you move from square to square, you will only need to keep track of the the xy position of the squares along the path, as well as what knight moves you haven't yet attempted on those squares.

[Sophie]

Hi,
have anyone already solved this puzzle? I really need it, it would be a great help...