나이트 투어 되돌아 가기

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

당신은 움직임의 후반 부분에서 실수를 한 것으로 보인다. 당신이 구현하고

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

의사 코드 알고리즘에 오류가 :이 이동의 완전한 세트 따라서 다음과 같습니다 2.이어야한다 반면 당신은 Y로/1을 뺀/추가된다. 재귀 적 경우 에 visited 값을 설정하지 마십시오.

재귀 호출을 수행하기 전에 if 블록의 visited[x][y]=True 블록을 else 블록으로 옮겨보십시오. (복사 할 수도 있지만 실제로는 아무 것도 유용하지 않습니다.)

Answer 4

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

}