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.