[演算法(Algorithm)] 騎士走棋盤(Knight's Tour)

• 騎士走棋盤問題(騎士巡邏):
  • 在西洋棋上，騎士要如何走過棋盤上每個點，且每個點只能走一次
  • 如果最後能走回原點，則稱為封閉式巡邏(tour is closed)，否則稱為開放式巡邏(tour is open)
  • 騎士巡邏為離散數學圖論中的漢米爾頓路徑(Hamiltonian path)問題的特例 騎士巡邏可以用線性時間求出
• 西洋棋相關知識:
  • 西洋棋盤由 8×8的格子所組成，所以共有64個格子，但探討這個問題時，可能會用其它大小的棋盤(ex: 5×5 或 16×16)
  • 西洋棋中，騎士的走法為：「直走或橫走2格，轉90度再走一格」。 所以一個點通常有8種走法
• 作法:
  • 選定一座標 起點
  • 依序嘗試下一步可能的8種走法，是否可行
    • 是否走過?
    • 是否出界?
  • 每找到一種可行的走法，則重複上步驟，直到某一步，8種走法都走不通，或走完64步
  • 當某步，8種走法都走不通，則還原回上一步，繼續8種走法中，未試過的走法
  • 重複上步驟，直到走完64步，或嘗試完全部走法
• Demo:
• 演算法
  • JS

  var steps = [{ x:-2, y:1}, {x:-1, y:2}, {x:1, y:2}, {x:2, y:1}, 
               {x:2, y:-1}, {x:1, y:-2}, {x:-1, y:-2}, {x:-2, y:-1}];
  
  var chessboard  = getNewChessboard();    
  var curstep = 1;    
  
  var knightTour = function(coord){
      var next = { x: 0, y: 0};        
      chessboard[coord.x][coord.y] = curstep++;
      if(curstep > 64) {        
          printBoard();                         // 找到解答, 顯示棋盤
          return true;
      }else{
          for(var i = 0; i < 8; i++){	      // 每個點可能有8種走法
              next.x = coord.x + steps[i].x;
              next.y = coord.y + steps[i].y;
              // 檢查下一步的位置會不會超出棋盤，或是否已走過
              if(next.x >= 0 && next.x <=7 && next.y >= 0 && next.y <= 7 
                 && chessboard[next.x][next.y] == 0)
              {
                  if(knightTour(next))
                      return true;
              }
          }
          chessboard[coord.x][coord.y] = 0; 
          curstep--;
          return false;
      }
  };