DFS Javaを使用したKnightのツアー

Question

Knight's tourを実装しようとしています。

私は、今のところ2〜3時間ほど良い計画をしています。まだ進んでいない。私は出発点を見つけることができないようです。

以下は、ナイトのツアーバージョンに変更する必要がある基本的なdfsメソッドです。

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 

私は単純化のためにボードサイズを5x5にしました。私はそれをgoogledしていくつかのソリューションを見て、彼らのほとんどは私に意味をなさないでした。 DFSメソッドを使用するにはどうすればよいですか？私は、DFSを使わずに再帰を使うのであれば、幾分実装することができると思う。しかし、私はどこにいても、DFSから始めるべきではない。

どこから始めたらいいですか？ 私は解決策を求めていません。開始する場所が必要です。

ありがとうございます。

Answer 1

Depth first searchこのように、グラフのノードを列挙するための一般的な戦略です。再帰的に、または反復的にユーザー定義のスタックによってサポートされて実装できます。検索するグラフは、明示的にエンコードすることができます。これは、通常、アプローチが説明されたときに行われます。

あなたのケースでは、グラフ（ゲームの何らかの種類の決定木です）を明示的にエンコードする必要はありません。実行可能な移動を選択し、グローバル状態（ボードを表す）上で新しい状態を表すことによって再帰的ノードを生成することができ、再帰的評価の後で次の実現可能な移動を続行する移動を取り消すことができる。このアプローチを使用すると、バックトラックは再帰を使用して実装できます。