Aide de l'algorithme du Tour du Chevalier

Question

Bon, tout le monde, je sais que le problème de la visite du chevalier est populaire pour tous les étudiants de cs et j'ai du mal à faire fonctionner le mien. J'utilise cet algorithme récursif pour progresser dans les mouvements, cependant, une fois que j'arrive au mouvement 50, je dois revenir en arrière car aucun mouvement n'est disponible et je finis par ne jamais terminer le tour. Je passe un ChessNode (contenant des choses comme si le noeud a été visité, déplacé, visité, etc ...), la rangée suivante, la colonne suivante et le nombre de déplacements du noeud précédent.

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; 
} 

Alors, d'abord je vérifie les taches qui peuvent se déplacer aux positions du conseil d'administration de coin, puis-je faire des appels récursifs à base de mouvements disponibles. Donc je suppose que ma question principale est de faire quelque chose de mal? ou y at-il une autre condition que je peux utiliser pour rendre le tour un peu plus intuitif?

Merci d'avance!

Answer 1

J'ai une implémentation de ce programme en C#. Vous pouvez le trouver ici:

http://github.com/danieltian/KnightBoard

Il ne trouverez que la première solution bien. Je ne dis pas de le copier, mais vous pouvez le regarder et voir si ça aide.

Answer 2

Ceci est le code du tour de Knight en Java et a une mise en page brillante. Je l'ai fait en utilisant backtracking en utilisant la récursivité. C'était mon affectation de classe. Contactez-moi si vous avez des problèmes de compréhension ou d'exécution de ce code.

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(); 
    } 
    } 

}