Consider an n × n chessboard and let A and B be two given squares. (a) Consider the problem of finding the maximal number of knight paths that start at A, end at B, and do not overlap, in the sense that they do not share a square other than A and B. Formulate the problem as a max-flow problem. (b) Solve the problem of part (a) using the max-flow algorithm of Section 3.3.2 for the case where n = 8, and the squares A and B are two opposite corners of the board.
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here