Knight Tour mit DFS Java

Question

Ich versuche Knight's tour zu implementieren.

Ich habe gearbeitet (mehr wie Planung) es für fast 2 ~ 3 Stunden jetzt. und ich habe immer noch keine Fortschritte gemacht. Ich finde, dass ich den Ausgangspunkt nicht finden kann.

Unten ist die grundlegende dfs-Methode, die ich zu Ritter Tour Version ändern muss.

class StackK 
{ 
private final int MAX_VERTS = 25; 
private int[] st; 
private int top; 
// ------------------------------------------------------------ 
public boolean isFull() 
{return (top == MAX_VERTS-1);} 
// ------------------------------------------------------------ 
public StackK()   // constructor 
    { 
    st = new int[MAX_VERTS]; // make array 
    top = -1; 
    } 
// ------------------------------------------------------------ 
public void push(int j) // put item on stack 
    { st[++top] = j; } 
// ------------------------------------------------------------ 
public int pop()   // take item off stack 
    { return st[top--]; } 
// ------------------------------------------------------------ 
public int peek()   // peek at top of stack 
    { return st[top]; } 
// ------------------------------------------------------------ 
public boolean isEmpty() // true if nothing on stack 
    { return (top == -1); } 
// ------------------------------------------------------------ 
} // end class StackK 

class VertexK 
{ 
public char label;  // label (e.g. 'A') 
public boolean wasVisited; 
// ------------------------------------------------------------ 
public VertexK(char lab) // constructor 
    { 
    label = lab; 
    wasVisited = false; 
    } 
// ------------------------------------------------------------ 
} // end class VertexK 

class GraphK 
{ 
private final int MAX_VERTS = 5; 
private VertexK VertexKList[]; // list of vertices 
private int adjMat[][];  // adjacency matrix 
private int nVerts;   // current number of vertices 
private StackK theStack; 
// ------------------------------------------------------------ 
public GraphK()    // constructor 
    { 
    VertexKList = new VertexK[MAX_VERTS]; 
             // adjacency matrix 
    adjMat = new int[MAX_VERTS][MAX_VERTS]; 
    nVerts = 0; 
    for(int y=0; y<MAX_VERTS; y++)  // set adjacency 
    for(int x=0; x<MAX_VERTS; x++) // matrix to 0 
     adjMat[x][y] = 0; 
    theStack = new StackK(); 
    for(int i=0;i<MAX_VERTS;i++) 
     addVertex((char)('A'+i)); 

    } 


// ------------------------------------------------------------ 
public void move(int row, int col) 
{ 

} 
// ------------------------------------------------------------ 
public void addVertex(char lab) 
    { 
    VertexKList[nVerts++] = new VertexK(lab); 
    } 
// ------------------------------------------------------------ 
public void addEdge(int start, int end) 
    { 
    adjMat[start][end] = 1; 
    } 

// ------------------------------------------------------------ 
public void displayVertexK(int v) 
    { 
    System.out.print(VertexKList[v].label); 
    } 


// ------------------------------------------------------------ 

public void dfs() // depth-first search 
    {         
    VertexKList[0].wasVisited = true; 
    displayVertexK(0);     
    theStack.push(0); 

    displayAdj(); 


    while(!theStack.isEmpty())  
    { 

    int v = getAdjUnvisitedVertexK(theStack.peek()); 
    if(v == -1)      
     theStack.pop(); 
    else       
     { 
     VertexKList[v].wasVisited = true; 
     displayVertexK(v);     
     theStack.push(v);     
     } 
    } // end while 

    // stack is empty, so we're done 
    for(int j=0; j<nVerts; j++)   // reset flags 
    VertexKList[j].wasVisited = false; 
    } // end dfs 

// ------------------------------------------------------------ 
// returns an unvisited VertexK adj to v 
public int getAdjUnvisitedVertexK(int v) 
    { 
    for(int j=0; j<nVerts; j++) 
    if(adjMat[v][j]==1 && VertexKList[j].wasVisited==false) 
     return j; 
    return -1; 
    } // end getAdjUnvisitedVertexK() 
// ------------------------------------------------------------ 
public void displayAdj() 
{ 
    for(int i=0;i<nVerts;i++){ 
     for(int k=0;k<nVerts;k++) 
      System.out.print(adjMat[i][k]); 
    System.out.println(""); 
    } 
} 
// ------------------------------------------------------------ 
} // end class GraphK 

public class KnightApp 
{ 
public static void main(String[] args) 
    { 
    GraphK k = new GraphK(); 

    k.displayAdj(); 


    } // end main() 
} // end class DFSApp 

Ich wählte die Board-Größe 5 x 5 zur Vereinfachung. Ich habe es gegoogelt und einige der Lösungen gesucht und die meisten von ihnen ergaben für mich keinen Sinn. Wie kann ich die DFS-Methode nutzen? Ich denke, ich könnte es etwas implementieren, wenn Rekursion ohne Verwendung von DFS verwendet werden würde. Ich habe jedoch keine Ahnung, nicht einmal, wo ich mit DFS anfangen soll.

Kann mir jemand eine Anleitung geben, wo ich anfangen soll? Ich frage nicht nach einer Lösung, brauche nur einen Platz zum Starten

Vielen Dank im Voraus.

Answer 1

Depth first search als solche ist eine allgemeine Strategie für die Aufzählung der Knoten eines Graphen; es kann rekursiv oder iterativ von einem benutzerdefinierten Stack unterstützt werden. Der zu durchsuchende Graph kann explizit kodiert werden, was normalerweise geschieht, wenn der Ansatz erklärt wird.

In Ihrem Fall muss der Graph (der eine Art Entscheidungsbaum eines Spiels ist) nicht explizit kodiert werden; Neue Nachfolgerknoten können erzeugt werden, indem eine machbare Bewegung ausgewählt wird, die den neuen Zustand in einem globalen Zustand repräsentiert (die Tafel darstellt), und nach der rekursiven Bewertung die Bewegung rückgängig machen, um mit der nächsten machbaren Bewegung fortzufahren. Mit diesem Ansatz kann Backtracking über Rekursion implementiert werden.