Stop recursive calls for tree generation with BFS

Question

I was tasked to write a program that finds the shortest path between a knight and a target tile in a chess board. The task specified to store knight's possible moves in a tree and find paths to the target with recursion. I've been wrestling with getMoves recursion call here in spite of trying to store the previously visited tile to avoid bouncing back and forth between two positions and create an infinite loop.

I've seen some solutions in StackOverflow that involve graphs and even simpler approaches. This code uses trees and BFS mainly because that's the topic I'm studying (and the exercise specifies this approach) so that's basically the reason I stick to this way. So, we have three classes here: Board, Knightand TreeMoves where all possible moves are stored. BFS lives inside TreeMoves and the idea is basically to traverse the generated tree for each recursion call to check if any node in the current tree has the same position as target. In other words, I create all knight's possible moves, run BFS to see if any of them equals my target, if not call the function recursively to create a deeper level in the tree that branches out from each previous move (except the already visited)

I've thought through a way to create a shorter version for the community but I might confuse you guys by doing so.

The code works well if the target is reachable by any knight immediate moves, although moving it away slightly from the target outputs the infinite loop I mentioned.

Can anyone hint me what I'm doing wrong please?

Cheers!

class Board{
  static size = 8;

  targetPos = [];
  targetToken = 't';
  moveToken = 'a';

  static isOutOfBoundaries(x,y){
    if(x>Board.size-1||x<0)
      return true;
    else if(y>Board.size-1||y<0)
      return true;
    else
      return false;
  }

  constructor(){
    this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·')); 
  }

  visualize(){
    this.tiles.forEach(row=>console.log(row.join(' ')));
  }

  placeItem(position, token){
    if(Board.isOutOfBoundaries(position[0],position[1]))
      throw new Error(`Piece/Target is out board boundaries`);
    else
      this.tiles[position[1]][position[0]] = token;
  }
  
  markPieceMoves(piece){
    for(let i = 0; i<piece.moves.length; ++i)
      this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
  }

}

class MovesTree{
  constructor(position){
    
    this.pos = position;
    this.uur = null; 
    this.rru = null;
    this.rrd = null;
    this.ddr = null;
    this.ddl = null;
    this.lld = null;
    this.llu = null;
    this.uul = null;
  }

  BFS(func,target){
    let queue = [this];
    while(queue.length>0){
      queue.push(...func(queue[0]));
      if(target.toString()===queue[0].pos.toString())
        return queue[0];
      queue.shift();
    }
  }

  toArray(node){
    let array = [];
    if(node.uur!==null)
      array.push(node.uur);
    if(node.rru!==null)
      array.push(node.rru);
    if(node.rrd!==null)
      array.push(node.rrd);
    if(node.ddr!==null)
      array.push(node.ddr);
    if(node.ddl!==null)
      array.push(node.ddl);
    if(node.lld!==null)
      array.push(node.lld);
    if(node.llu!==null)
      array.push(node.llu);
    if(node.uul!==null)
      array.push(node.uul);
    return array;
  }

  DFS(node, target, path=[]){
    if(node.pos.toString()===target.toString()){
      return path;
    }else{
    path.push(node.pos);
      if(node.uur!==null)
        this.DFS(node.uur, target, path);
      if(node.rru!==null)
        this.DFS(node.rru, target, path);
      if(node.rrd!==null)
        this.DFS(node.rrd, target, path);
      if(node.ddr!==null)
        this.DFS(node.ddr, target, path);
      if(node.ddl!==null)
        this.DFS(node.ddl, target, path);
      if(node.lld!==null)
        this.DFS(node.lld, target, path);
      if(node.llu!==null)
        this.DFS(node.llu, target, path);
      if(node.uul!==null)
        this.DFS(node.uul, target, path);
    }
  }
}
class Knight{
  token = 'k';
  constructor(row,col){
    this.position = [row,col];
    this.moves = new MovesTree(this.position);
  }

  getMoves(node, target, visited){
    const twoSteps = 2;
    const oneStep = 1;

    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]-twoSteps))
      node.uur=new MovesTree([node.pos[0]+oneStep,node.pos[1]-twoSteps]);
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]-oneStep))
      node.rru=new MovesTree([node.pos[0]+twoSteps,node.pos[1]-oneStep]);
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]+oneStep))
      node.rrd=new MovesTree([node.pos[0]+twoSteps,node.pos[1]+oneStep]);
    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]+twoSteps))
      node.ddr=new MovesTree([node.pos[0]+oneStep,node.pos[1]+twoSteps]);
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]+twoSteps))
      node.ddl=new MovesTree([node.pos[0]-oneStep,node.pos[1]+twoSteps]);
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]+oneStep))
      node.lld=new MovesTree([node.pos[0]-twoSteps,node.pos[1]+oneStep]);
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]-oneStep))
      node.llu=new MovesTree([node.pos[0]-twoSteps,node.pos[1]-oneStep]);
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]-twoSteps))
      node.uul=new MovesTree([node.pos[0]-oneStep,node.pos[1]-twoSteps]);

    const found = this.moves.BFS(this.moves.toArray, target);
    if(found !== undefined){
      console.log(`Found: ${found}`)
      return;
    }
    else{
      console.log(node)
      if(node.uur!==null&&node.uur!==visited)
        this.getMoves(node.uur, target, node);
      if(node.rru!==null&&node.rru!==visited)
        this.getMoves(node.rru, target, node);
      if(node.rrd!==null&&node.rrd!==visited)
        this.getMoves(node.rrd, target, node);
      if(node.ddr!==null&&node.ddr!==visited)
        this.getMoves(node.ddr, target, node);
      if(node.ddl!==null&&node.ddl!==visited)
        this.getMoves(node.ddl, target, node);
      if(node.lld!==null&&node.lld!==visited)
        this.getMoves(node.lld, target, node);
      if(node.llu!==null&&node.llu!==visited)
        this.getMoves(node.llu, target, node);
      if(node.uul!==null&&node.uul!==visited)
        this.getMoves(node.uul, target, node);
    }
  }    

}
const board = new Board();
board.targetPos = [5,2];
const knight = new Knight(5,4); //Try new Knight(6,4) to get to target in one move
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)

knight.getMoves(knight.moves, board.targetPos, knight.moves);
knight.moves.DFS(knight.moves, board.targetPos);
board.visualize();

Answer 1

Thankfully I didn't give up trying to find the answer. My code had some structure problems that I fixed by moving the getMovesmethod to the MovesTree class plus some corrections here and there. The main point was to use the BFS to control the moves generation in a simple way. To my surprise this method not only avoided infinite loops but let me discover that the shortest path is actually a collection of moves that are really well explained in this question: Knight's Shortest Path on Chessboard if I'm not mistaken. Anyways here you go the final code.

  static size = 8;

  targetPos = [];
  targetToken = 't';
  moveToken = 'a';

  static isOutOfBoundaries(x,y){
    if(x>Board.size-1||x<0)
      return true;
    else if(y>Board.size-1||y<0)
      return true;
    else
      return false;
  }

  constructor(){
    this.tiles = Array.from(Array(Board.size), ()=>Array.from(Array(Board.size), tile=>'·')); 
  }

  visualize(){
    this.tiles.forEach(row=>console.log(row.join(' ')));
  }

  placeItem(position, token){
    if(Board.isOutOfBoundaries(position[0],position[1]))
      throw new Error(`Piece/Target is out board boundaries`);
    else
      this.tiles[position[1]][position[0]] = token;
  }
  
  markPieceMoves(piece){
    for(let i = 0; i<piece.moves.length; ++i)
      this.tiles[piece.moves[i][1]][piece.moves[i][0]] = this.moveToken;
  }

}

class MovesTree{
  constructor(position){
    
    this.pos = position;

    // -
    //|
    //|
    this.uur = null; 
    
    //  |
    //--
    this.rru = null;

    //--
    //  |
    this.rrd = null;

    //|
    //|
    // -
    this.ddr = null;

    // |
    // |
    //-
    this.ddl = null;

    // --
    //|
    this.lld = null;

    //|
    // --
    this.llu = null;

    //-
    // |
    // |
    this.uul = null;

  }

  static getMoves(node){
    const twoSteps = 2;
    const oneStep = 1;
    // -
    //|
    //|
    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]-twoSteps))
      node.uur=new MovesTree([node.pos[0]+oneStep,node.pos[1]-twoSteps]);

    //  |
    //--
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]-oneStep))
      node.rru=new MovesTree([node.pos[0]+twoSteps,node.pos[1]-oneStep]);
    //--
    //  |
    if(!Board.isOutOfBoundaries(node.pos[0]+twoSteps,node.pos[1]+oneStep))
      node.rrd=new MovesTree([node.pos[0]+twoSteps,node.pos[1]+oneStep]);
    //|
    //|
    // -
    if(!Board.isOutOfBoundaries(node.pos[0]+oneStep,node.pos[1]+twoSteps))
      node.ddr=new MovesTree([node.pos[0]+oneStep,node.pos[1]+twoSteps]);
    // |
    // |
    //-
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]+twoSteps))
      node.ddl=new MovesTree([node.pos[0]-oneStep,node.pos[1]+twoSteps]);
    // --
    //|
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]+oneStep))
      node.lld=new MovesTree([node.pos[0]-twoSteps,node.pos[1]+oneStep]);
    //|
    // --
    if(!Board.isOutOfBoundaries(node.pos[0]-twoSteps,node.pos[1]-oneStep))
      node.llu=new MovesTree([node.pos[0]-twoSteps,node.pos[1]-oneStep]);
    //-
    // |
    // |
    if(!Board.isOutOfBoundaries(node.pos[0]-oneStep,node.pos[1]-twoSteps))
      node.uul=new MovesTree([node.pos[0]-oneStep,node.pos[1]-twoSteps]);

  }    

  BFS(func,target){
    let queue = [this];
    while(queue.length>0){
      if(target.toString()!==queue[0].pos.toString()){
        MovesTree.getMoves(queue[0])
        queue.push(...func(queue[0]));
      }
      else
        return; 
      queue.shift();
    }
  }

  DFS(node, target, path){

    let visited; 
    path === undefined ? visited = [node.pos]: visited = this.mergePath(path, node.pos);
    if(node.pos.toString()===target.toString()){
      visited.reverse();
      console.log(visited);
      return;
    }
    else{
      if(node.uur!==null)
        this.DFS(node.uur, target, visited);
      if(node.rru!==null)
        this.DFS(node.rru, target, visited);
      if(node.rrd!==null)
        this.DFS(node.rrd, target, visited);
      if(node.ddr!==null)
        this.DFS(node.ddr, target, visited);
      if(node.ddl!==null)
        this.DFS(node.ddl, target, visited);
      if(node.lld!==null)
        this.DFS(node.lld, target, visited);
      if(node.llu!==null)
        this.DFS(node.llu, target, visited);
      if(node.uul!==null)
        this.DFS(node.uul, target, visited);
    }
  }

  toArray(node){

    let array = [];

    if(node.uur!==null)
      array.push(node.uur);
    if(node.rru!==null)
      array.push(node.rru);
    if(node.rrd!==null)
      array.push(node.rrd);
    if(node.ddr!==null)
      array.push(node.ddr);
    if(node.ddl!==null)
      array.push(node.ddl);
    if(node.lld!==null)
      array.push(node.lld);
    if(node.llu!==null)
      array.push(node.llu);
    if(node.uul!==null)
      array.push(node.uul);
    return array;
  }

  mergePath(path, current){
    let merged = [];
    merged.push(current);
    path.forEach(step=>{
      merged.push(step)
    });
    return merged;
  }
}
class Knight{
  token = 'k';
  constructor(row,col){
    this.position = [row,col];
    this.moves = new MovesTree(this.position,this);
  }
}
const board = new Board();
board.targetPos = [6,0];
const knight = new Knight(0,7);
board.placeItem(knight.position, knight.token);
board.placeItem(board.targetPos, board.targetToken)

knight.moves.BFS(knight.moves.toArray, board.targetPos);
knight.moves.DFS(knight.moves, board.targetPos)
board.visualize();