Copyright | Copyright (C) 2023 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

Part of Ninety-Nine Haskell Problems. Some solutions are in Solutions.P91.

# Documentation

knightsTour :: Int -> (Int, Int) -> Maybe [(Int, Int)] Source #

Another famous problem is this one: How can a knight jump on an \(N \times N\) chessboard in such a way that it visits every square exactly once?

Write a function which returns a knight's tour ending at a particular square. Represent the squares by their coordinates with the tuple \((x,y)\), where \(1 \leq x \leq N\) and \(1 \leq y \leq N\). A tour will be a list of these tuples of length \(N \times N\).

### Examples

`>>>`

24 7 32 17 22 5 33 16 23 6 31 18 8 25 10 19 4 21 15 34 1 28 11 30 26 9 36 13 20 3 35 14 27 2 29 12`printKnightsTour $ knightsTour 6 (3,5)`

### Hint

A straightforward backtracking algorithm can be very slow even for moderately sized boards such as \(8 \times 8\). Consider using Warnsdorff's rule. Alternatively, consider using a divide-and conquer algorithm which finds knight's tours for smaller boards and patching them together.

closedKnightsTour :: Int -> Maybe [(Int, Int)] Source #

The same as `knightsTour`

, except return a circular tour.
I.e., the knight must be able to jump from the last position in the tour to the first position in the tour.
Start the tour from \((1,1)\).

### Examples

`>>>`

1 14 31 20 3 8 32 21 2 7 30 19 13 36 15 4 9 6 22 33 24 27 18 29 25 12 35 16 5 10 34 23 26 11 28 17`printKnightsTour $ closedKnightsTour 6`