Knight's shortest path

Recently I did a written test, I was asked to make a small game.

When the game starts, a knight and an destination will randomly appear on the board, where the knight wins when he moves to the destination.

Correspondingly, I need to provide two help buttons, one can prompt the next step, and the other directly helps to move to the destination.

Here is my answer, I will give some code and my reference below:

Frontend Repo (React.js): Github Varsion | chess-game-front

Backend Repo (Rails): Github Varsion | chess-game-server

For the shortest path problem, obviously, we can use BFS to solve, for this uncommon algorithm, it is a bit difficult to do independently, so I found a reference Knight’s Shortest Path on Chessboard

Here is my Ruby solution:

• A chessboard posiniton entity: it will store the initial position move to current position steps

  class Node
    attr_accessor :position, :parent, :steps
  
    def initialize(position:, steps: 0, parent: nil)
      @position = position
      @parent = parent
      @steps = steps
    end
  end
  

• A chess service: convenient controller call the logic

  class ChessService < ApplicationService
    attr_reader :steps_count, :next_step, :steps
  
    COL = %w(a b c d e f g h)
    ROW = %w(1 2 3 4 5 6 7 8)
  
    # movable situations
    DX = [2, 2, -2, -2, 1, 1, -1, -1]
    DY = [-1, 1, -1, 1, -2, 2, -2, 2]
  
    # BFS to get Knight shortest path
    def initialize(position, destination)
      @steps_count = 0
      @steps = []
      @next_step = ""
      if position == destination
        @steps_count = 0
        @steps = [] << destination
        @next_step = destination
      else
        build(position, destination)
      end
    end
  
    # BFS logic
    def build(position, destination)
      visited = []
      queue = [] << position
      node_steps = {}
  
      while !queue.empty?
        node = queue.pop
  
        dist = node_steps[node]&.steps || 0
  
        if node == destination
          @steps_count = dist
          break
        end
  
        unless visited.include?(node)
          visited << node
  
          (0..7).each do |i|
            new_x = COL.index(node[0]) + DX[i]
            new_y = ROW.index(node[1]) + DY[i]
  
            if (new_x >= 0 && new_x < 8) && (new_y >= 0 && new_y < 8)
              new_position = COL[new_x] + ROW[new_y]
              queue.unshift(new_position)
              node_steps[new_position] = Node.new(position: new_position, steps: dist + 1, parent: node_steps[node])
            end
          end
        end
      end
  
      # backward from destination
      next_step = node_steps[destination]
      @steps << destination
      until next_step.parent.nil?
        next_step = next_step.parent
        @steps.unshift(next_step.position)
      end
  
      @next_step = next_step.position
    end
  end
  

• Called by controller

  # params[:position] and params[:destination] are like "e6", represents the position on the chessboard
  chess_service = ChessService.new(params[:position], params[:destination])
  
  # then we will get this info to return
  {
    steps: chess_service.steps,
    next_step: chess_service.next_step,
    steps_count: chess_service.steps_count,
   }
  

  ---

  Write at the end, I deployed these services and you can use them through these links.

  Page: Vercel | Chess Game

  Server: Render | Chess Game Server

  It should be noted that I used a free service when deploying the backend, so the first request will start the service, which may take about 2 minutes to start successfully.