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/

@steffan-westcott
Copy link

steffan-westcott commented Apr 12, 2021

(def files [:A :B :C :D :E :F :G :H])

(defn knight-move [[from-file from-rank]]
  (let [from-x (.indexOf files from-file)]
    (for [dx [-2 -1 1 2]
          :let [to-file (get files (+ from-x dx))]
          :when to-file
          dy (if (odd? dx) [-2 2] [-1 1])
          :let [to-rank (+ from-rank dy)]
          :when (<= 1 to-rank 8)]
      [to-file to-rank])))

@tvirolai
Copy link

tvirolai commented Apr 12, 2021

(def rank [:A :B :C :D :E :F :G :H])

(defn knight-move [[x y]]
  (let [x-number (.indexOf rank x)]
    (vec
     (for [X (range (- x-number 2) (+ x-number 3))
           Y (range (- y 2) (+ y 3))
           :let [distance (+ (Math/abs (- X x-number))
                             (Math/abs (- Y y)))]
           :when (and (= 3 distance)
                      (< -1 X 8)
                      (< 0 Y 9))]
       [(get rank X) Y]))))

@vpetruchok
Copy link

vpetruchok commented Apr 12, 2021

(defn knight-move [[cur-col-name cur-row]]
  (let [col-name->col  (fn [col-name]
                         (-> col-name
                             name
                             first
                             int
                             (- (int \A))
                             inc))
        col->col-name  (fn [col]
                         (-> col
                             dec 
                             (+ (int \A))
                             char
                             str
                             keyword))
        cur-col (col-name->col cur-col-name)]
    (->> (for [col-offset [-2 -1 1 2]
               row-offset [-2 -1 1 2]
               :when (= 3 (+ (Math/abs col-offset) (Math/abs row-offset)))]
           [(+ cur-col col-offset) (+ cur-row row-offset)])
         (filter (fn [[col row]]
                   (and (pos? col) (pos? row))))
         (map (fn [[col row]]
                [(col->col-name col) row])))))

@prairie-guy
Copy link

prairie-guy commented Apr 12, 2021

(def possible-moves                                                                                                                                            
  (->>(for [x [1 -1] y [2 -2]] [[x y] [y x]])                                                                                                         
      (flatten)                                                                                                                                      
      (partition 2)))

(defn legal-move? [[x2 y2]]                                                                                                                                
  (and (> x2 0) (> y2 0) (< x2 9) (< y2 9)))

(defn make-move [[x1 y1] [dx dy]]                                                                                                                          
  (let [x2 (+ x1 dx), y2 (+ y1 dy)]                                                                                                                   
    (if (legal-move? [x2 y2])                                                                                                                              
      [x2 y2]                                                                                                                                         
      [])))

(defn knight-move [[a n]]                                                                                                                             
  (let [a2n {:A 1, :B 2, :C 3, :D 4, :E 5, :F 6, :G 7, :H 8}                                                                                          
        n2a (map-invert a2n)]                                                                                                                         
    (->> (map #(make-move [(a2n a) n] %) possible-moves)                                                                                                            
         (filter (complement empty?))                                                                                                                 
         (map (fn [[x y]] [(n2a x) y]))                                                                                                               
         (sort))))

@diavoletto76
Copy link

diavoletto76 commented Apr 12, 2021

I assume the order of moves is not relevant even if the return value is a vector.

(defn swap [x]
  (let [base (dec (int \A))]
    (if (instance? Long x)
      (keyword (str (char (+ x base))))
      (- (int (first (name x))) base))))

(defn swap-coord [[x y]] [(swap x) y])

(defn knight-move [xy]
  (let [[x y] (swap-coord xy)]
    (->> (for [f1 [+ -] f2 [+ -] a [1 2] b [1 2]
               :let [x' (f1 x a)]
               :let [y' (f2 y b)]
               :when (and (not= a b) (> x' 0) (> y' 0))]
           [(f1 x a) (f2 y b)])
         (mapv swap-coord))))

@miner
Copy link

miner commented Apr 12, 2021

(def kfiles [:A :B :C :D :E :F :G :H])

(def ifile (reduce-kv (fn [m i kf] (assoc m kf i)) {} kfiles))

(defn knight-move [[f r]]
  (let [i (ifile f)]
    (into [] (keep (fn [[fdiff rdiff]]
                     (let [r2 (+ r rdiff)]
                       (when (<= 1 r2 8)
                         (when-let [f2 (nth kfiles (+ i fdiff) nil)]
                           [f2 r2])))))
          [[-2 -1] [-1 -2] [-2 1] [-1 2] [1 2] [2 1] [1 -2] [2 -1]])))

;; note: order of offsets corresponds to given examples

@jaihindhreddy
Copy link

jaihindhreddy commented Apr 13, 2021

(let [ranks [:A :B :C :D :E :F :G :H]
      rank->int (into {} (map-indexed #(vector %2 %)) ranks)]
  (defn move
    "Moves a position by given amount in x and y direction.
     returns nil if the move is out of bounds"
    [[rank file] [x y]]
    (let [rank' (nth ranks (+ y (rank->int rank)) nil)
          file' (+ file x)]
      (when (and (<= 1 file' 8) rank')
        [rank' file']))))

(defn knight-move [pos]
  (keep #(move pos %)
        [[-1 -2] [-2 -1]
         [ 1 -2] [ 2 -1]
         [ 2  1] [ 1  2]
         [-2  1] [-1  2]]))

@simbiotiqu
Copy link

simbiotiqu commented Apr 13, 2021

(def hrow (mapv (comp keyword str char) (range 65 73)))

(def vrow (vec (range 1 9)))

(def movement-diff
  [[-2 -1]
   [-1 -2]
   [-2 1]
   [-1 2]
   [1 2]
   [2 1]
   [1 -2]
   [2 -1]])

(defn pos->chesspos [[h v]] [(get hrow h)
                             (get vrow v)])

(defn chesspos->pos [[ch cv]]
  [(.indexOf hrow ch)
   (.indexOf vrow cv)])

(defn possible-pos [[h v]]
  (map (fn [[hdiff vdiff]]
         [(+ h hdiff)
          (+ v vdiff)])
       movement-diff))

(defn on-board? [p]
  (and
   (>= p 0)
   (<= p 7)))

(defn valid-pos? [[h v]]
  (and (on-board? h)
       (on-board? v)))

(defn knight-move [chess-pos]
  (->> chess-pos
       chesspos->pos
       possible-pos
       (filter valid-pos?)
       (mapv pos->chesspos)))

@mchampine
Copy link

mchampine commented Apr 14, 2021

(defn knight-move [[file rank]]
  (let [knnk (apply merge (map-indexed (fn [i r] {i r r i}) [:A :B :C :D :E :F :G]))
        deltas (for [r [1 -1 2 -2] f [1 -1 2 -2] :when (odd? (+ r f))] [r f])]
    (->> (map #(mapv + % [(knnk file) rank]) deltas) ;; all knight-shaped moves
         (filter (fn [[r f]] (and (<= 1 r 8) (<= 1 f 8)))) ;; on the board?
         (mapv (fn [[a b]] [(knnk a) b])))))  ;; convert file nums to keywords

@xqz-u
Copy link

xqz-u commented Apr 14, 2021

(def files-start (int \A))

(defn file->num
  [file]
  (-> file
      name
      first
      int
      (- files-start)))

(defn num->file
  [file-num]
  (-> file-num
      (+ files-start)
      char
      str
      keyword))

(defn to-chess-pos
  [[file-num rank]]
  [(num->file file-num) (inc rank)])

(defn chess-pos?
  [chess-pos]
  (every? #(<= 0 % 7) chess-pos))

(defn knight-move
  [[file rank]]
  (let [chess-pos-num [(file->num file) (dec rank)]]
    (when (chess-pos? chess-pos-num)
      (->> [[-2 -1] ;; knight motions, ordered first by file then by rank
            [-2 1]
            [-1 -2]
            [-1 2]
            [1 -2]
            [1 2]
            [2 -1]
            [2 1]]
           (map #(map + % chess-pos-num)) ;; move knight
           (filter chess-pos?)  ;; check illegal moves
           (mapv to-chess-pos)))))  ;; format output

@sztamas
Copy link

sztamas commented Apr 19, 2021

Interesting problem!

Brings back nice memories of this page I did years ago, when I was playing around with HTML 5 Canvas:

https://tamas-szabo.com/knightjumps/

@steffan-westcott
Copy link

steffan-westcott commented Apr 19, 2021

As a bit of fun, I was inspired by @sztamas to add a shortest knight move path challenge!

Building on your knight-move function, add a new function which takes source and destination squares and returns a collection of all shortest paths of knight moves between them.

Examples:

(shortest-paths [:H 6] [:F 2]) ; => ( [[:H 6] [:G 4] [:F 2]] )
(shortest-paths [:A 1] [:B 1]) ; => ( [[:A 1] [:B 3] [:D 2] [:B 1]]   [[:A 1] [:C 2] [:A 3] [:B 1]] )

Would anyone like to try it? I'll post my answer later.

@nwjsmith
Copy link

nwjsmith commented Apr 19, 2021

(def board-coordinates
  (for [x (range 1 9)
        y (range 1 9)]
    [x y]))

(def offsets
  [[-2 -1]
   [-1 -2]
   [-2 1]
   [-1 2]
   [1 2]
   [2 1]
   [1 -2]
   [2 -1]])

(defn coordinate
  [[column row]]
  [(inc (.indexOf [:A :B :C :D :E :F :G :H] column)) row])

(defn position
  [[x y]]
  [(get [:A :B :C :D :E :F :G :H] (dec x)) y])

(defn knight-move
  [pos]
  (let [[x y] (coordinate pos)]
    (->> (for [[x-offset y-offset] offsets] [(+ x x-offset) (+ y y-offset)])
         (map (fn [candidate] (some #{candidate} board-coordinates)))
         (remove nil?)
         (map position))))

@KingCode
Copy link

KingCode commented Apr 20, 2021

I have added a solution to @stefan-westcott's shortest-paths function:

(def move-fns (let [half (->> (for [f [inc dec] 
                                     g [#(+ % 2) #(- % 2)]]
                                 [f g]))]
                (->> half (map reverse) (into half)
                     (map (fn [[row-fn col-fn]]
                            (fn [[r c]]
                              [(row-fn r) (col-fn c)]))))))

(defn neighbours [rc]
  (->> move-fns (map #(% rc))))

(defn in-bounds [rc]
  (every? #(< 0 % 9) rc))

(defn moves [rc]
  (->> rc neighbours (filter in-bounds)))

;; de/formatting
(def kw<->dig (let [l->d (->> "ABCDEFGH" (map str) (map keyword) 
                              (zipmap (range 1 9)))]
                (into l->d (zipmap (vals l->d) (keys l->d)))))

(defn ->rc [[kw rank]]
  (->> kw kw<->dig (vector rank)))

(defn ->kw+rank [[row col]]
  (-> col kw<->dig (vector row)))


(defn knight-move [file+rank]
  (->> file+rank ->rc 
       moves
       (map ->kw+rank))) 

;; shortest-paths challenge 
(defn new-paths [[from {:keys [paths]}] step seen]
  (->> from moves (remove seen)
       (map #(vector % {:paths (->> paths 
                                    (mapv (fn [p] 
                                            (conj p %))))
                        :distance (inc step)}))))

(defn new-entries [pinfo step visited]
  (->> pinfo
       (group-by #(-> % val :distance))
       (#(% step))
       (mapcat #(new-paths % step visited))))

(defn merge-into [pinfo new-entries]
  (->> new-entries
       (reduce (fn [acc [loc {:keys [paths distance]}]]
                 (update acc loc (fn [{paths' :paths :or {paths' []}}]
                                   {:paths (concat paths paths')
                                    :distance distance})))
               pinfo)))

(defn expand [from to]
  (loop [step 0 
         pinfo {from {:distance step
                      :paths [[from]]}}
         seen #{from}]
    (if (some #{to} (keys pinfo))
      pinfo
      (let [added (new-entries pinfo step seen)]
        (recur (inc step)
               (merge-into pinfo 
                           added)
               (into seen (map first added)))))))


(defn shortest-paths [from to]
  (let [to (->rc to)
        paths  (-> (expand (->rc from) to)
                   (get to)
                   :paths)]
    (->> paths (map #(->> % (map ->kw+rank))))))

@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