将骑士从位置 1 移动到位置 2，移动少于 10 次 [英] 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

我想用所有可能的方式将骑士从位置 1 移动到位置 2.但少于10个动作.任何人都可以帮我做这件事吗?

I wanna move knight from postion 1 to postion 2 with all possible ways. but with less than 10 moves. can any one help me have to do this?

function isSafe(x,y,board){
if(x >= 0 && y >= 0 && x < 8 && y < 8 && board[y][x] == 0){return true}
else{return false}
}


function printBoard(board){
for(let i = 0; i < 8; i++){
    for(let x = 0; x < 8; x++){
        console.log(board[i][x] + "  ");
    }
}
}


function solve(){
let board = [];
for(let i = 0; i < 8; i++){
    board[i] = [];
    for(let x = 0; x < 8; x++){
        board[i][x] = 0;
    }
}
var move_x = [2, 1, -1, -2, -2, -1, 1, 2];
var move_y = [1, 2, 2, 1, -1, -2, -2, -1];

board[0][0] = 1;

var pos = 1;

 if(solveKTUtil(board,0,0,move_x,move_y,pos)){
    printBoard(board);
  }
   else{console.log('no answer')}
    console.log(board)
 }


function solveKTUtil(board,curr_x,curr_y,move_x,move_y,pos){
if(curr_x == 7 && curr_y == 7){return true}
for(let i = 0; i < 8; i++){
    var new_y = curr_y + move_y[i] ;
    var new_x = curr_x + move_x[i] ;
    
    if(isSafe(new_x,new_y,board)){
        console.log(new_x,new_y)
        board[new_y][new_x] = pos;
        if(board[7][7] === 1){return true}
        else{
           solveKTUtil(board,curr_x,curr_y,move_x,move_y,pos);
            
        }
    }
   }
   return false

}
solve();

现在它不能正常工作了.请帮帮我

now it's nowt working fine . please help me

推荐答案

重构您的代码，并将解决方案塑造为深度优先搜索 (DFS)，并采用出租车距离启发式算法，以支持更接近目标的骑士移动目标广场.此外，还引入了递归生成器函数，以防有人想要控制寻求解决方案的频率和时间.

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...

• 6 步或更少的 108 个解决方案
• 8 步或更少步的 1896 个解
• 10 步以内的 40432 个解
• 12 步或更少的 736396 个解

内联注释有助于理解递归生成器函数...

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

运行代码片段将显示 6 步或更少的所有 108 个解决方案.

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}.` );

这篇关于将骑士从位置 1 移动到位置 2，移动少于 10 次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！