騎士之旅發現路徑算法

Question

我必須從[0,0]出發訪問，那麼所有方從我的單板返回/坐在[0,0]

圖片

這是我試圖代碼：

public class chess_F 
{ 
    // save my current position 
    struct position 
    { 
     public int row; 
     public int col; 
    }; 

    const int NOT_VISITED = 0; 

    // my board 
    private int[,] cols = new int[8, 8]; 


    // main function 
    public void Do() 
    { 
     position start; 
     start.row = 0; 
     start.col = 0; 

     initializeBoard(ref cols); 

     move(start, cols); 
    } 

    private void initializeBoard(ref int[,] board) 
    { 
     for (int i = 0; i < 8; i++) 
      for (int j = 0; j < 8; j++) 
       board[i, j] = NOT_VISITED; 
    } 

    private bool visited(int[,] board, position square) 
    { 
     return board[square.row, square.col] != NOT_VISITED; 
    } 


    /* |---|---|-0-|---|-1-|---|---|---| 
    * |---|-7-|---|---|---|-2-|---|---| 
    * |---|---|---|-X-|---|---|---|---| 
    * |---|-6-|---|---|---|-3-|---|---| 
    * |---|---|-5-|---|-4-|---|---|---| 
    * |---|---|---|---|---|---|---|---| 
    * |---|---|---|---|---|---|---|---| 
    * |---|---|---|---|---|---|---|---| 
    */ 

    // find all cols for my knight - can sit on 
    private position[] findPath(position present, int[,] cols) 
    { 
     position[] temp = new position[8]; 
     position mytemp; 

     for (int i = 0; i < 8; i++) 
     { 
      try 
      { 
       //path 0 
       switch (i) 
       { 
        case 0: 
         { 
          if (cols[present.row - 1, present.col - 2] == 0) 
          { 
           mytemp.row = present.row - 1; 
           mytemp.col = present.col - 2; 
           temp[i] = mytemp; 
          } 
          break; 
         } 

        //path 1 
        case 1: 
         { 
          if (cols[present.row + 1, present.col - 2] == 0) 
          { 
           mytemp.row = present.row + 1; 
           mytemp.col = present.col - 2; 
           temp[i] = mytemp; 
          } break; 
         } 

        //path 2 
        case 2: 
         { 
          if (cols[present.row + 2, present.col - 1] == 0) 
          { 
           mytemp.row = present.row + 2; 
           mytemp.col = present.col - 1; 
           temp[i] = mytemp; 
          } break; 
         } 
        //path 3 
        case 3: 
         { 
          if (cols[present.row + 2, present.col + 1] == 0) 
          { 
           mytemp.row = present.row + 2; 
           mytemp.col = present.col + 1; 
           temp[i] = mytemp; 
          } break; 
         } 

        //path 4 
        case 4: 
         { 
          if (cols[present.row + 1, present.col + 2] == 0) 
          { 
           mytemp.row = present.row + 1; 
           mytemp.col = present.col + 2; 
           temp[i] = mytemp; 
          } break; 
         } 

        //path 5 
        case 5: 
         { 
          if (cols[present.row - 1, present.col + 2] == 0) 
          { 
           mytemp.row = present.row - 1; 
           mytemp.col = present.col + 2; 
           temp[i] = mytemp; 
          } break; 
         } 

        //path 6 
        case 6: 
         { 
          if (cols[present.row - 2, present.col - 1] == 0) 
          { 
           mytemp.row = present.row - 2; 
           mytemp.col = present.col - 1; 
           temp[i] = mytemp; 
          } break; 
         } 

        //path 7 
        case 7: 
         { 
          if (cols[present.row - 2, present.col - 1] == 0) 
          { 
           mytemp.row = present.row - 2; 
           mytemp.col = present.col - 1; 
           temp[i] = mytemp; 
          } break; 
         } 
       } 
      } 
      catch 
      { 
       mytemp.row = -1; 
       mytemp.col = -1; 
       temp[i] = mytemp; 
      } 
     } 
     return temp; 
    } 

    // check all cols and row to check ... 
    private bool allVisited(int[,] cols) 
    { 
     for (int i = 0; i < 8; i++) 
      for (int j = 0; j < 8; j++) 
       if (cols[i, j] != 1) 
        return false; 
     return true; 

    } 


    // save true path 
    int[,] truepath; 
    private void move(position present, int[,] cols) 
    { 
     int[,] tempCols = cols; 
     tempCols[present.row, present.col] = 1; 
     position[] avaliable = findPath(present, tempCols); 

     if (avaliable.Count() < 1) 
      return; 

     for (int i = 0; i < avaliable.Count(); i++) 
     { 
      if (allVisited(tempCols)) 
      { 
       truepath = tempCols; 
      } 
      else 
      { 
       if (avaliable[i].row != -1 && avaliable[i].row != 0) 
        move(avaliable[i], tempCols); 
      } 
     } 
    } 
} 

我的問題是truepath變量總是爲空，我不能給triped方

Answer 1

如果你的矩陣尺寸是相等的，那麼你可以使用這個：
將矩陣分成4個象限。那麼你有
2 | 1
3 | 4，象限。
第二象限上的路徑很簡單：第一行和第一列。
其他人也很公平。所有元素都是點陣的點（如果nxn（n/2，n/2）和r = n/2），則中心=矩陣的中心。
難點是如何確定一個點是否是圓的一部分。

public static PointF PointOnCircle(float radius, float angleInDegrees, PointF origin) 
{ 
    // Convert from degrees to radians via multiplication by PI/180   
    float x = (float)(radius * Math.Cos(angleInDegrees * Math.PI/180F)) + origin.X; 
    float y = (float)(radius * Math.Sin(angleInDegrees * Math.PI/180F)) + origin.Y; 

    return new PointF(x, y); 
} 

參考https://stackoverflow.com/a/839904/349007

Answer 2

當我回顧騎士之旅，也許這可以給你一個想法：

import java.awt.*; 
import javax.swing.*; 

@SuppressWarnings("serial") 
public class KnightTour extends JComponent 
{ 
    private int maxRows; // number of rows (and cols!) on board 
    private int move=0;  // how many successful moves we've made 
    private int board[][]; // contains move number 
    private static final int CELLSIZE = 30; // graphical size of each cell of board 

    public KnightTour(int maxRows) 
    { 
     JFrame frame = new JFrame("Knight Tour"); 
     this.maxRows = maxRows; 
     board = new int[maxRows][maxRows]; 

     // clear the board 
     for (int i=0; i<maxRows; ++i) 
     for (int j=0; j<maxRows; ++j) 
      board[i][j] = 0; 

     setPreferredSize(new Dimension(maxRows*CELLSIZE, maxRows*CELLSIZE)); 
     frame.getContentPane().add(this); 
     frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
     frame.pack(); 
     frame.setVisible(true); 
    } 

    private void showBoard() 
    { 
     repaint(); 
     try { 
      Thread.sleep(0); 
     } catch (InterruptedException e) 
     { /* ignore, shouldn't happen */ } 
    } 

    @Override 
    public void paintComponent(Graphics g) 
    { 
     for (int i=0; i<=maxRows; ++i) { // draw grid 
      g.drawLine(0,i*CELLSIZE, CELLSIZE*maxRows,i*CELLSIZE); 
      for (int j=0; j<=maxRows; ++j) 
       g.drawLine(j*CELLSIZE, 0, j*CELLSIZE, CELLSIZE*maxRows); 
     } 
     for (int i=0; i<maxRows; ++i) // draw moves 
      for (int j=0; j<maxRows; ++j) 
       if (board[i][j] != 0) 
        g.drawString(""+board[i][j], CELLSIZE/4+i*CELLSIZE, CELLSIZE*3/4+j*CELLSIZE); 
    } 

    public boolean solve(int row, int column) 
    { 
     if (row < 0 || column < 0 || row >= maxRows || column >= maxRows || board[row][column]!=0) 
      return false; // out of range or already been to this cell 
     board[row][column] = ++move; 
     showBoard(); 

     if (move == maxRows*maxRows) 
      return true; // filled the board! 

     // try all possible moves from here 
     if ( solve(row-2, column-1) 
      || solve(row-2, column+1) 
      || solve(row+2, column-1) 
      || solve(row+2, column+1) 
      || solve(row-1, column-2) 
      || solve(row+1, column-2) 
      || solve(row-1, column+2) 
      || solve(row+1, column+2)) { 
      repaint(); // in case not showing each move separately 
      return true; // success! 
     } 

     board[row][column] = 0; // failed - remove current move 
     --move; 
     showBoard(); 
     return false; 
    } 

    public static void main(String args[]) 
    { 
     KnightTour board = new KnightTour(6); 
     if (board.solve(0,0)) // try solution starting at upper left 
      System.out.println("Solution found."); 
     else 
      System.out.println("No solution found."); 
    } 
} 

最重要的部分就是這個方法，看看它和嘗試你的動作

public boolean solve(int row, int column) 
    { 
     if (row < 0 || column < 0 || row >= maxRows || column >= maxRows || board[row][column]!=0) 
      return false; // out of range or already been to this cell 
     board[row][column] = ++move; 
     showBoard(); 

     if (move == maxRows*maxRows) 
      return true; // filled the board! 

     // try all possible moves from here 
     if ( solve(row-2, column-1) 
      || solve(row-2, column+1) 
      || solve(row+2, column-1) 
      || solve(row+2, column+1) 
      || solve(row-1, column-2) 
      || solve(row+1, column-2) 
      || solve(row-1, column+2) 
      || solve(row+1, column+2)) { 
      repaint(); // in case not showing each move separately 
      return true; // success! 
     } 

     board[row][column] = 0; // failed - remove current move 
     --move; 
     showBoard(); 
     return false; 
    } 

Answer 3

也許你犯了一些錯誤移動功能。下面的語句：

if (avaliable[i].row != -1 && avaliable[i].row != 0) 
        move(avaliable[i], tempCols); 

你不是說：

if (avaliable[i].row != -1 && avaliable[i].col!= -1) 
        move(avaliable[i], tempCols);