骑士的游览回溯

Question

我正在骑士的游览问题，并使用回溯算法。我的代码最终没有产生正确的输出，它只是一遍又一遍地重复最后两个条目，直到没有达到n^2 -1。

这是我的代码。我正在关注这个伪代码http://www.wou.edu/~broegb/Cs345/KnightTour.pdf

visited = [[False for x in range(5)] for y in range(5)] 

def move(x,y,m): 

    result=False 
    if x<0 or x>=5 or y<0 or y>=5: 
     return False 
    if visited[x][y]==True: 
     return False 
    if m==24: 
     print "a solution has been found" 
     print x,",",y 


     visited[x][y]=True 
     return True 

    else: 
     result=result or move(x+2,y+1,m+1) 
     result=result or move(x+2,y-1,m+1) 
     result=result or move(x-2,y+1,m+1) 
     result=result or move(x-2,y-1,m+1) 
     result=result or move(x+1,y+1,m+1) 
     result=result or move(x+1,y-1,m+1) 
     result=result or move(x-1,y+1,m+1) 
     result=result or move(x-1,y-1,m+1) 
    if result==True: 
     print x,",",y 

     return True 
    else: 
     visited[x][y]=False 
     return False 

Answer 1

在算法结束时，您将设置visited[x][y]=True设置为true。它必须在你确定你已经在那里后才能设置。我还为您的代码做了一些增强：

N = 5 # This way you can test it with 5 or 6 and even 100 if you want to. 
visited = [[False for x in range(N)] for y in range(N)] 

def move(x,y,m): 

    result=False 
    if x<0 or x>=N or y<0 or y>=N or visited[x][y]==True: # You may merge these two ifs. 
     return False 
    visited[x][y]=True 
    if m==(N * N - 1): 
     print "a solution has been found" 
     visited[x][y]=True # Set visited here tot true. 
     return True 
    else: 
     print x,",",y 
     if (move(x+2,y+1,m+1) or move(x+2,y-1,m+1) 
      or move(x-2,y+1,m+1) or move(x-2,y-1,m+1) 
      or move(x+1,y+1,m+1) or move(x+1,y-1,m+1) 
      or move(x-1,y+1,m+1) or move(x-1,y-1,m+1)): # Place them in one if. 
      print x,",",y 

      return True 
    return False # If the algorithm comes here it may return false 

print move(2,1,0) 

Answer 2

您似乎在下半年的举动中犯了错误。您所添加/从y中减去1 /，而这应该是2，全套动作因此看起来是这样的：

result=result or move(x+2,y+1,m+1) 
    result=result or move(x+2,y-1,m+1) 
    result=result or move(x-2,y+1,m+1) 
    result=result or move(x-2,y-1,m+1) 
    result=result or move(x+1,y+2,m+1) 
    result=result or move(x+1,y-2,m+1) 
    result=result or move(x-1,y+2,m+1) 
    result=result or move(x-1,y-2,m+1) 

Answer 3

你正在实施中的伪算法有错误。在递归的情况下，你永远不会将visited的值设置为True。

在执行任何递归调用之前，请尝试将块中的行visited[x][y]=True块移至以下else块。 （您也可以复制它，但它并不真正做它在哪里有用。）

Answer 4

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

}