Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
422 PurelyFunctional.tv Newsletter

Knight move

Write a function that takes a chess position as a tuple (such as [:A 4]). If there were a knight there, where would it be able to move? Have the function return a collection of all possible moves for that knight. Assume there are no other pieces on the board. Be sure the knight doesn't leave the board.

Knight Move diagram

Examples

(knight-move [:D 3]) ;=> [[:B 2] [:C 1] [:B 4] [:C 5] [:E 5] [:F 4] [:E 1] [:F 2]]
(knight-move [:A 1]) ;=> [[:B 3] [:C 2]]

Thanks to this site for the problem idea, where it is rated Hard in JavaScript. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

@sztamas
Copy link

sztamas commented Apr 20, 2021

(def ord (comp int first name))

(defn file-idx [file]
  (- (ord file) (ord :A)))

(defn index->file [idx]
  (-> (+ (ord :A) idx) char str keyword))

(def valid-file? #(<= 0 (file-idx %) 7))

(def valid-rank? #(<= 1 % 8))

(defn valid-square? [[file rank]]
  (and (valid-file? file) (valid-rank? rank)))

(def knight-move-diffs
  (->> (for [two-squares [-2 2]
             one-square  [-1 1]]
         [[two-squares one-square]
          [one-square  two-squares]])
       (reduce concat)))

(defn move [[file rank] [file-diff rank-diff]]
  [(index->file (+ (file-idx file) file-diff))
   (+ rank rank-diff)])

(defn knight-move [coord]
  (->> (map move (repeat coord) knight-move-diffs)
       (filter valid-square?)))

@KingCode
Copy link

KingCode commented Apr 22, 2021

Thank you @stefan-westcott for the extra challenge of computing all shortest-paths, and @sztamas for the nice web app! I used it to test my solution (my edited submission above).

If anyone wants to try it, another interesting (but much harder) related challenge is the Knight's Tour for various side lengths, yielding all paths starting from a corner of the board and visiting each square exactly once, e.g. a solution for side length 5 could start with:

(knight-tour 5)
;;=> (([:A 1] [:C 2] [:E 3] [:D 5] [:B 4] [:A 2] [:C 3] [:D 1] [:B 2] [:A 4] [:C 5] [:E 4] [:D 2] [:B 1] [:A 3] [:B 5] [:D 4] [:E 2] [:C 1] [:B 3] [:A 5][:C 4] [:E 5] [:D 3] [:E 1]) ...)

I haven't been able to compute even a single path in reasonable time for solutions for larger than boards of side length 5 using brute force depth-first search.. There is a neat article here referencing faster methods.

@steffan-westcott
Copy link

steffan-westcott commented Apr 23, 2021

Here's my answer to the extra challenge of finding all shortest paths:

(defn extend-path [path]
  (map #(conj path %) (knight-move (peek path))))

(defn shortest-paths [src dest]
  (loop [reached #{src} paths [[src]]]
    (if (reached dest)
      (filter #(= dest (peek %)) paths)
      (let [paths' (remove (comp reached peek) (mapcat extend-path paths))]
        (recur (into reached (map peek paths')) paths')))))

@vmpj
Copy link

vmpj commented Apr 23, 2021

(def file2int {:A 1 :B 2 :C 3 :D 4 :E 5 :F 6 :G 7 :H 8})
(def int2file (clojure.set/map-invert file2int))

(defn valid-move? [move]
  (every? #(and (> % 0) (< % 9)) move))

(defn friendly-format [[f r]] [(int2file f) r])

(defn knight-move [[file rank]]
  (let [f (file2int file) r rank]
    (as-> '(2 2 -2 -2 1 -1 1 -1) l
          (map #(vector (+ f %1) (+ r %2)) l (reverse l))
          (filter valid-move? l)
          (map friendly-format l))))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment