Knight Project

You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.

Knight Project

Postby SrPuma » Tue Oct 08, 2013 1:30 am

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
SrPuma
 
Posts: 2
Joined: Tue Oct 08, 2013 1:10 am

Re: Knight Project

Postby nuntius » Tue Oct 08, 2013 7:18 pm

What data structure are you using to store the game board? (Or what type of structure do you want to use?)
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Knight Project

Postby saulgoode » Thu Oct 10, 2013 4:22 am

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.)
Last edited by saulgoode on Sun Oct 13, 2013 7:53 pm, edited 1 time in total.
saulgoode
 
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Knight Project

Postby SrPuma » Sat Oct 12, 2013 4:00 am

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


saulgoode wrote: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?
SrPuma
 
Posts: 2
Joined: Tue Oct 08, 2013 1:10 am

Re: Knight Project

Postby nuntius » Sat Oct 12, 2013 10:24 pm

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)
User avatar
nuntius
 
Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: Knight Project

Postby saulgoode » Sun Oct 13, 2013 9:40 am

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.
saulgoode
 
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: Knight Project

Postby Sophie » Thu Nov 21, 2013 11:20 am

Hi,
have anyone already solved this puzzle? I really need it, it would be a great help...
Sophie
 
Posts: 1
Joined: Thu Nov 21, 2013 11:18 am


Return to Homework

Who is online

Users browsing this forum: No registered users and 3 guests

cron