| Copyright | Copyright (C) 2023 Yoo Chung |
|---|---|
| License | GPL-3.0-or-later |
| Maintainer | dev@chungyc.org |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Problems.P91
Description
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
>>>printKnightsTour $ knightsTour 6 (3,5)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
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
>>>printKnightsTour $ closedKnightsTour 61 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