騎士之旅算法幫助

Question

好吧，大家好，我知道騎士的巡迴問題對於所有學生都很受歡迎，而且我很難找到我的工作。我使用這種遞歸算法來完成整個移動過程，但是，一旦我到達第50步，我必須回溯，因爲沒有可用的移動，並且我最終從未完成巡視。我通過一個ChessNode（持有像訪問了節點，移動它被訪問等等的事情），下一行，下一列和前一節點的移動計數。

private int moveRecur(ChessNode current, int row, int column, int moveV){ 
    current.moveVisited = moveV+1; 
    if(current.moveVisited > 63){ 
     return 0; 
    } 
     if(current.position==13 && aboard[row-1][column+2].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row-1][column+2], row-1, column+2, current.moveVisited); 
     } 
     else if(current.position==22 && aboard[row-2][column+1].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row-2][column+1], row-2, column+1, current.moveVisited); 
     } 
     else if(current.position == 50 && aboard[row+1][column-2].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row+1][column-2], row+1, column-2, current.moveVisited); 
     } 
     else if(current.position == 41 && aboard[row+2][column-1].visited != 1){ 
      current.visited =1; 
      moveRecur(aboard[row+2][column-1], row+2, column-1, current.moveVisited); 
     } 
     else if(current.position == 46 && aboard[row+2][column+1].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row+2][column+1], row+2, column+1, current.moveVisited); 
     } 
     else if(current.position == 53 && aboard[row+1][column+2].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row+1][column+2], row+1, column+2, current.moveVisited); 
     } 
     else if(current.position == 10 && aboard[row-1][column-2].visited != 1){ 
      current.visited = 1; 
      moveRecur(aboard[row-1][column-2], row-1, column-2, current.moveVisited); 
     } 
     else if (current.position == 17 && aboard[row-2][column-1].visited != 1){ 
      current.visited =1; 
      moveRecur(aboard[row-2][column-1], row-2, column-2, current.moveVisited); 
     } 
     if(row+1>=0 && row+1<8 && column+2>=0 && column+2<8){ 
      if(aboard[row+1][column+2].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row+1][column+2], row+1, column+2, current.moveVisited); 
      } 
     } 
     if(row+2>=0 && row+2<8 && column+1>=0 && column+1<8){ 
      if(aboard[row+2][column+1].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row+2][column+1], row+2, column+1, current.moveVisited); 
      } 
     } 
     if(row-1>=0 && row-1<8 && column-2>=0 && column-2<8){ 
      if(aboard[row-1][column-2].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row-1][column-2], row-1, column-2, current.moveVisited); 
      } 
     } 
     if(row-2>=0 && row-2<8 && column-1>=0 && column-1<8){ 
      if(aboard[row-2][column-1].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row-2][column-1], row-2, column-1, current.moveVisited); 
      } 
     } 
     if(row+1>=0 && row+1<8 && column-2>=0 && column-2<8){ 
      if(aboard[row+1][column-2].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row+1][column-2], row+1, column-2, current.moveVisited); 
      } 
     } 
     if(row+2>=0 && row+2<8 && column-1>=0 && column-1<8){ 
      if(aboard[row+2][column-1].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row+2][column-1], row+2, column-1, current.moveVisited); 
      } 
     } 
     if(row-1>=0 && row-1<8 && column+2>=0 && column+2<8){ 
      if(aboard[row-1][column+2].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row-1][column+2], row-1, column+2, current.moveVisited); 
      } 
     } 
     if(row-2>=0 && row-2<8 && column+1>=0 && column+1<8){ 
      if(aboard[row-2][column+1].visited != 1){ 
       current.visited = 1; 
       moveRecur(aboard[row-2][column+1], row-2, column+1, current.moveVisited); 
      } 
     } 
    //System.out.println(current.position + " "+current.moveVisited); 
    current.visited = 0;  
    return 0; 
} 

所以，最初我檢查可以移動到角落板位置的點，然後根據可用的移動進行遞歸調用。所以我想我的主要問題是我做錯了什麼？或者是否有另一個條件可以讓巡演變得更加直觀？

提前致謝！

Answer 1

我在C＃中實現了這個程序。你可以在這裏找到它：

http://github.com/danieltian/KnightBoard

它只會雖然找到的第一個解決方案。我不是說要複製它，但你可以看看它，看看它是否有幫助。

Answer 2

這是Knight在java中的遊覽代碼，並且擁有輝煌的佈局。我使用遞歸進行回溯。這是我的班級任務。如果您在理解或運行此代碼時遇到任何問題，請與我聯繫。

package knights.tour; 
import java.awt.*; 
import java.awt.event.*; 
import java.util.logging.*; 
import javax.swing.*; 


public class KnightsTour extends JFrame implements ActionListener{ 

//All the static variables used between action listeners and functions. 
public static String path; 
public static int btnPressed = 0; 
public static int rowSelected; 
public static String[] pathArray; 
public static int[][] coordinatesArray; 
public static int columnSelected; 
public static int flag =0; 
public static int increment = 0; 
public static JPanel panel1 = new JPanel(); 
public static JPanel panel3 ; 
public static JButton btnStart = new JButton("Start Animation"); 
public static JButton btnClear = new JButton("Clear"); 
public static JTextArea lblPath = new JTextArea(); 
public static JLabel lblStartRow = new JLabel(); 
public static JLabel lblStartColumn = new JLabel(); 
public static JButton[][] button; 
public static int variableForIncrement=0; 
static int row ; 
static int column ; 
static int[][] array = new int[row][column]; 
public static int count = 1; 


KnightsTour(){ 

    //Setting layout of the frame in the constructor and adding buttons to the panel and the frame. 
    getContentPane().setLayout(new GridLayout(2,1)); 
    lblPath.setLineWrap(true); 
    lblPath.setColumns(10); 
    lblPath.setSize(700, 100); 
    lblPath.setEditable(false); 
    panel1.add(btnStart); 
    panel1.add(btnClear); 
    panel1.add(lblStartRow); 
    panel1.add(lblStartColumn); 
    panel1.add(lblPath); 
    panel3 = new JPanel(new GridLayout(row,column)); 

    // Initializing Array of buttons for the user to click on the chess board. 
    button= new JButton[row][column]; 
    array = new int[row][column]; 
    coordinatesArray = new int[row*column][2]; // This array stores the coordinates as the Knight        
    for(int i=0;i<row;i++){ 
     for(int j=0;j<column;j++){ 
      button[i][j] = new JButton(); 
     } 
    } 

    //Setting background of the buttons to black and white for chessboard layout. 
    for(int i=0;i<row;i++){ 
     for(int j=0;j<column;j++){ 
      if(i%2 ==j%2){ 
       button[i][j].setBackground(Color.BLACK); 
       button[i][j].setForeground(Color.WHITE); 
     } 
      else{ 
       button[i][j].setBackground(Color.WHITE); 
      } 
      panel3.add(button[i][j]); 
      button[i][j].addActionListener(this); 
     } 
    } 

    btnClear.addActionListener(this); 
    btnStart.addActionListener(this); 
    add(panel3); 
    add(panel1); 
    setDefaultCloseOperation(EXIT_ON_CLOSE); 

} 

public static void main(String[] args) { 
    // TODO code application logic here 
    String input =JOptionPane.showInputDialog("Enter the rows and columns in the format    (row,column)"); 
    String[] ar = input.split(","); 
    row = Integer.parseInt(ar[0]); // Finding out row and column from the user input. 
    column = Integer.parseInt(ar[1]); 
    pathArray = new String[row*column]; // This array is kept to store the path of the knight. 
    JFrame frame = new KnightsTour();  
    frame.setVisible(true); 
    frame.setSize(700,700); 

} 


//All the computation takes place in this function. It checks the neighbour and recursively calls itself. 
public static void neighbourRecursion(int a,int b){ 

    pathArray[increment] = Integer.toString(a) + "," + Integer.toString(b); // Storing the path of the Knight 
    increment++; 
    array[a][b] = count;              //Stroing value of count. 
    button[a][b].setText(String.valueOf(count)); 
    coordinatesArray[variableForIncrement][0] = button[a][b].getX();   //Finding coordinates of buttons to show animation 
    coordinatesArray[variableForIncrement][1] = button[a][b].getY(); 
    count++; 
    variableForIncrement++; 

    //Checking for valid neighbours and calling itself recursively. 
    if(a <= row-3 && b<=column-2){ 
     if(alreadyVisited(a+2,b+1)){ 
     neighbourRecursion(a+2,b+1); 
     } 
    } 
    if(a<=row-3 && b>=1){ 
     if(alreadyVisited(a+2,b-1)){ 
     neighbourRecursion(a+2,b-1); 
    } 
    } 
    if(a>=2 && b<=column-2){ 
     if(alreadyVisited(a-2,b+1)){ 
     neighbourRecursion(a-2,b+1); 
    } 
    } 

    if(a>=2 && b>=1){ 
     if(alreadyVisited(a-2,b-1)){ 

     neighbourRecursion(a-2,b-1); 
    } 

    } 
    if(a<=row-2 && b>=2){ 
     if(alreadyVisited(a+1,b-2)){ 

     neighbourRecursion(a+1,b-2); 
    } 
    } 

    if(a<=row-2 && b<=column-3){ 
     if(alreadyVisited(a+1,b+2)){ 

     neighbourRecursion(a+1,b+2); 
    } 
    } 
    if(a>=1 && b>=2){ 
     if(alreadyVisited(a-1,b-2)){ 
     neighbourRecursion(a-1,b-2); 
    } 
    } 
    if(a>=1 && b <=column-3){ 
     if(alreadyVisited(a-1,b+2)){ 
     neighbourRecursion(a-1,b+2); 
    } 
    } 


    //Breaking condition of the function. 
    if(count == (row*column)+1){ 
    } 


    // Backtracking condition if there is no neighbour. 
    else{ 
     button[a][b].setText(""); 
     array[a][b]=0; 
     count--; 
     variableForIncrement--; 
     if(increment >0){ 
     increment--; 
     } 
     return ; 

    } 


} 
//This function checks if the neighbour is already visited. 
public static boolean alreadyVisited(int a,int b){ 

if(array[a][b] != 0){ 
    return false; 
} 
else{ 
    return true; 
} 
} 

@Override 
public void actionPerformed(ActionEvent e) { 
    //when clear is pressed all arrays and global variables are set to initial conditon. 
if(e.getSource() == btnClear){ 
     for(int i =0;i<row;i++){ 
      for(int j=0;j<column;j++){ 
       array[i][j] = 0; 
       button[i][j].setText(""); 
       count = 1; 
       lblPath.setText(""); 
       lblStartRow.setText(""); 
       lblStartColumn.setText(""); 
       flag =0; 
       variableForIncrement=0; 
       increment =0; 
       path =" "; 

    } 
     } 

     } 

//If start animation button is pressed animation is started. 
     else if(e.getSource() == btnStart){ 
      animate(); 
     } 

     // When the button is pressed. 

     else{ 
     for(int i=0;i<row;i++){ 
     for(int j=0;j<column;j++){ 
     if(e.getSource() == button[i][j]){ 
      if(flag == 1){ 
       lblPath.setText(" Please press clear before clicking again"); // Button pressed  twice without reset. 
      } 
      else{ 
     rowSelected = i; 
     columnSelected =j; 
     // If odd * odd board and selected postion is odd then No path is possible. 
     if(row%2 ==1 && column%2 == 1 && rowSelected%2 ==0 && columnSelected%2 == 1 || row%2 ==1 &&  column%2 == 1 && rowSelected%2 ==1 && columnSelected%2 == 0){ 
      lblPath.setText(" Path not possible from this point"); 
     } 
     else{ 
      int count; 
     lblStartRow.setText("Starting Row : "+String.valueOf(rowSelected + 1)); 
     lblStartColumn.setText("Starting Column : "+String.valueOf(columnSelected + 1)); 
     count = 1; 
     flag = 1; 
     startTour(); //Start tour function called. 
     for(int q=0;q<row;q++){ 
      for(int w=0;w<column;w++){ 
       if(array[i][j] == 0){ 
        count++; 
       } 
      } 

     } 
     if(count > 2){ 
      lblPath.setText(" No Path found"); 
     } 

     //Printing path of the knight here. 
     else{ 
     for(int k=0;k<pathArray.length;k++){ 
      path = path+"->"+ pathArray[k]; 
     } 
     lblPath.setText(" Path : \n"+ path.substring(5)); 
     } 
     btnPressed = 1; 
     break; 
    } 

      } 
     } 

    } 



} 
} } 


//Function for the animation. 
void animate(){ 
    if(btnPressed == 1){ 
    btnPressed =0; 
    Graphics g = getGraphics(); 
    for(int i=0;i<(row*column)-1;i++){ 
    try { 
     Thread.sleep(600); // this function slows down drawing of lines. 

    } catch (InterruptedException ex) { 

    } 
      g.setColor(Color.RED); // setting colour or line to red. 
      g.drawLine((coordinatesArray[i][0]+65),(coordinatesArray[i][1]+50),(coordinatesArray[i+1] [0]+65),(coordinatesArray[i+1][1]+50)); 
    } 
    } 
    else{ 
     lblPath.setText(" Please clear, select a button to see the animation again"); //Animate button pressed twice without clear. 
    } 

} 

//This function calls the neighbour function with the selected row and column by the user. 
    static void startTour(){ 
     neighbourRecursion(rowSelected,columnSelected); 
    for(int i=0;i<row;i++){ 
     for(int j=0;j<column;j++){ 
      System.out.print(array[i][j]+" "); 
     } 
     System.out.println(); 
    } 
    } 

}