Move The Knight From Position 1 To Position 2 With Less Than 10 Moves

I have a question. here is my chess board , ok? enter image description here I wanna move knight from postion 1 to postion 2 with all possible ways. but with less than 10 moves. ca

Solution 1:

Refactored your code, and shaped the solution into a depth first search (DFS) with a taxicab distance heuristic to favor the moves of the knight that are closer to the goal square. Additionally, introduced a recursive generator function in the event that one wants to control how often and how long the solutions are sought.

The solution count ramps up quickly, of course, when seeking more moves. Some quick testing reveals that there are...

• 108 solutions of 6 moves or less
• 1896 solutions of 8 moves or less
• 40432 solutions of 10 moves or less
• 736396 solutions of 12 moves or less

Inline comments assist in understanding the recursive generator function...

Running the code snippet will display all 108 solutions of 6 moves or less.

function printBoard( board ){
  let bm = '';
  for (let rank = 7; 0 <= rank; rank-- ) {
    for ( let file = 0; file < 8; file++ ) {
      if ( board[ rank ][ file ] === -1 ) {
        bm += " X ";
      } else if ( board[ rank ][ file ] === 0 ) {
        bm += " - ";
      } else {
        bm += ( " " + board[ rank ][ file ] ).slice( -2 ) + " ";
      }
    }
    bm += '\n'
  }
  return bm + '\n';
}

function genAndSortKnightMoves( knightRank, knightFile, goalRank, goalFile ) {
  const knightMoves = [ [-2,-1], [-2,1], [-1,-2], [-1,2], [1,-2], [1,2], [2,-1], [2,1] ];
  
  function isKnightOnTheBoard( r, f ){
    return ( 0 <= r && 0 <= f && r < 8 && f < 8 );
  }

  // Generate list of possible moves where the Knight is on the board and the
  // square has not already been visited.
  let moves = [];
  knightMoves.forEach( rf => {
    let rank = knightRank + rf[ 0 ];
    let file = knightFile + rf[ 1 ];
    if ( isKnightOnTheBoard( rank, file ) ) {
      moves.push( [ rank, file ] );
    }
  } );
  
  // Now, sort the moves based on which is closer to the goal using the
  // taxicab distance.
  moves.sort( ( a, b ) =>
      ( Math.abs( a[ 0 ] - goalRank ) + Math.abs( a[ 1 ] - goalFile ) )
    - ( Math.abs( b[ 0 ] - goalRank ) + Math.abs( b[ 1 ] - goalFile ) )
  );
  return moves;
}

// Set up zero filled 8 x 8 array.
let workingBoard = new Array( 8 ).fill( 0 ).map( () => new Array( 8 ).fill( 0 ) );

function* solve( startRank, startFile, goalRank, goalFile, maxDepth = 12, depth = 0 ) {

  // Set the square that the knight landed on.
  workingBoard[ startRank ][ startFile ] = ( depth === 0 ? -1 : depth );

  // If we reached the goal square, let's yield the result.
  if ( startRank === goalRank && startFile === goalFile ) {
  
    yield workingBoard;
    
  } else if ( depth < maxDepth ) {
  
    // Otherwise, if we haven't reached maxDepth, let's go deeper.  First, get
    // the list of candidate knight moves, sorted by the squares closest to the
    // goal using the simple taxicab distance.
    let candidateMoves = genAndSortKnightMoves( startRank, startFile, goalRank, goalFile );
    
    // Now, loop through the options, and if the square is empty, let's jump
    // to that square.
    for ( let move of candidateMoves ) {
      let rank = move[ 0 ];
      let file = move[ 1 ];
      if ( workingBoard[ rank ][ file ] === 0 ) {
        yield* solve( rank, file, goalRank, goalFile, maxDepth, depth + 1 );
      }
    }
  }
  
  // At this point, the recursion has unwound, so lets clear the knight off
  // the square by resetting it to zero.
  workingBoard[ startRank ][ startFile ] = 0;
  
}  


// Set up the solution, by creating the iterator with the beginning square and 
// goal square, and setting the max depth to the number of max moves sought.

let solutionsCount = 0;
let moveCountSought = 6;
const findSolution = solve( 0, 0, 7, 7, moveCountSought );

// Now, simply iterate over the yielded solutions.
do {

  let soln = findSolution.next();
  
  if ( soln.done ) {
    break;
  }
  
  if ( workingBoard[ 7 ][ 7 ] <= moveCountSought ) {
    solutionsCount++;
    console.log( printBoard( workingBoard ) );
  }
  
} while ( true );

console.log( `Number of solutions less than or equal to ${moveCountSought} moves is ${solutionsCount}.` );