c# - ナイトツアー検索パスアルゴリズム

Question

[0,0]から始めて、すべての広場に行き、[0,0]に戻って座る必要があります

私のボードからの画像

これは私が試したコードです：

public class chess_F
{
    // save my current position
    struct position
    {
        public int row;
        public int col;
    };

    const int NOT_VISITED = 0;

    // my board
    private int[,] cols = new int[8, 8];


    // main function 
    public void Do()
    {
        position start;
        start.row = 0;
        start.col = 0;

        initializeBoard(ref cols);

        move(start, cols);
    }

    private void initializeBoard(ref int[,] board)
    {
        for (int i = 0; i < 8; i++)
            for (int j = 0; j < 8; j++)
                board[i, j] = NOT_VISITED;
    }

    private bool visited(int[,] board, position square)
    {
        return board[square.row, square.col] != NOT_VISITED;
    }


    /*  |---|---|-0-|---|-1-|---|---|---|
     *  |---|-7-|---|---|---|-2-|---|---|
     *  |---|---|---|-X-|---|---|---|---|
     *  |---|-6-|---|---|---|-3-|---|---|
     *  |---|---|-5-|---|-4-|---|---|---|
     *  |---|---|---|---|---|---|---|---|
     *  |---|---|---|---|---|---|---|---|
     *  |---|---|---|---|---|---|---|---|
     */

    // find all cols for my knight - can sit on
    private position[] findPath(position present, int[,] cols)
    {
        position[] temp = new position[8];
        position mytemp;

        for (int i = 0; i < 8; i++)
        {
            try
            {
                //path 0
                switch (i)
                {
                    case 0:
                        {
                            if (cols[present.row - 1, present.col - 2] == 0)
                            {
                                mytemp.row = present.row - 1;
                                mytemp.col = present.col - 2;
                                temp[i] = mytemp;
                            }
                            break;
                        }

                    //path 1
                    case 1:
                        {
                            if (cols[present.row + 1, present.col - 2] == 0)
                            {
                                mytemp.row = present.row + 1;
                                mytemp.col = present.col - 2;
                                temp[i] = mytemp;
                            } break;
                        }

                    //path 2
                    case 2:
                        {
                            if (cols[present.row + 2, present.col - 1] == 0)
                            {
                                mytemp.row = present.row + 2;
                                mytemp.col = present.col - 1;
                                temp[i] = mytemp;
                            } break;
                        }
                    //path 3
                    case 3:
                        {
                            if (cols[present.row + 2, present.col + 1] == 0)
                            {
                                mytemp.row = present.row + 2;
                                mytemp.col = present.col + 1;
                                temp[i] = mytemp;
                            } break;
                        }

                    //path 4
                    case 4:
                        {
                            if (cols[present.row + 1, present.col + 2] == 0)
                            {
                                mytemp.row = present.row + 1;
                                mytemp.col = present.col + 2;
                                temp[i] = mytemp;
                            } break;
                        }

                    //path 5
                    case 5:
                        {
                            if (cols[present.row - 1, present.col + 2] == 0)
                            {
                                mytemp.row = present.row - 1;
                                mytemp.col = present.col + 2;
                                temp[i] = mytemp;
                            } break;
                        }

                    //path 6
                    case 6:
                        {
                            if (cols[present.row - 2, present.col - 1] == 0)
                            {
                                mytemp.row = present.row - 2;
                                mytemp.col = present.col - 1;
                                temp[i] = mytemp;
                            } break;
                        }

                    //path 7
                    case 7:
                        {
                            if (cols[present.row - 2, present.col - 1] == 0)
                            {
                                mytemp.row = present.row - 2;
                                mytemp.col = present.col - 1;
                                temp[i] = mytemp;
                            } break;
                        }
                }
            }
            catch
            {
                mytemp.row = -1;
                mytemp.col = -1;
                temp[i] = mytemp;
            }
        }
        return temp;
    }

    // check all cols and row to check ...
    private bool allVisited(int[,] cols)
    {
        for (int i = 0; i < 8; i++)
            for (int j = 0; j < 8; j++)
                if (cols[i, j] != 1)
                    return false;
        return true;

    }


    // save true path
    int[,] truepath;
    private void move(position present, int[,] cols)
    {
        int[,] tempCols = cols;
        tempCols[present.row, present.col] = 1;
        position[] avaliable = findPath(present, tempCols);

        if (avaliable.Count() < 1)
            return;

        for (int i = 0; i < avaliable.Count(); i++)
        {
            if (allVisited(tempCols))
            {
                truepath = tempCols;
            }
            else
            {
                if (avaliable[i].row != -1 && avaliable[i].row != 0)
                    move(avaliable[i], tempCols);
            }
        }
    }
}

私の問題はtruepath変数が常にnullであり、トリップされた正方形を与えることができないことです

score 0 · Accepted Answer

行列の次元が等しい場合は、次のように使用できます
。行列を4つの象限に分割します。次に、
2つあります| 1
3 | 4、象限。
2番目の象限のパスは単純です。最初の行と最初の列です。
他のものもかなり単純です。円の点であるすべての要素（center = nxnの場合は行列の中心（n / 2、n / 2）、r = n / 2）。
難しい点は、点が円の一部であるかどうかを判断する方法です。

 public static PointF PointOnCircle(float radius, float angleInDegrees, PointF origin)
{
    // Convert from degrees to radians via multiplication by PI/180        
    float x = (float)(radius * Math.Cos(angleInDegrees * Math.PI / 180F)) + origin.X;
    float y = (float)(radius * Math.Sin(angleInDegrees * Math.PI / 180F)) + origin.Y;

    return new PointF(x, y);
}

参照https://stackoverflow.com/a/839904/349007

score 0 · Accepted Answer

move関数でいくつかの間違いを犯した可能性があります。以下の声明：</p>

if (avaliable[i].row != -1 && avaliable[i].row != 0)
                    move(avaliable[i], tempCols);

あなたは意味しません：

if (avaliable[i].row != -1 && avaliable[i].col!= -1)
                    move(avaliable[i], tempCols);

score 0 · Accepted Answer

Knights ツアーを確認したら、次のことを考えてみてください。

import java.awt.*;
import javax.swing.*;

@SuppressWarnings("serial")
public class KnightTour extends JComponent
{
    private int maxRows;    // number of rows (and cols!) on board
    private int move=0;     // how many successful moves we've made
    private int board[][];  // contains move number
    private static final int CELLSIZE = 30;  // graphical size of each cell of board

    public KnightTour(int maxRows)
    {
        JFrame frame = new JFrame("Knight Tour");
        this.maxRows = maxRows;
        board = new int[maxRows][maxRows];

        // clear the board
        for  (int i=0; i<maxRows; ++i)
         for (int j=0; j<maxRows; ++j)
           board[i][j] = 0;

        setPreferredSize(new Dimension(maxRows*CELLSIZE, maxRows*CELLSIZE));
        frame.getContentPane().add(this);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.pack();
        frame.setVisible(true);
    }

    private void showBoard()
    {
        repaint();
        try {
            Thread.sleep(0);
        } catch (InterruptedException e)
        { /* ignore, shouldn't happen */ }
    }

    @Override
    public void paintComponent(Graphics g)
    {
        for (int i=0; i<=maxRows; ++i) { // draw grid
             g.drawLine(0,i*CELLSIZE, CELLSIZE*maxRows,i*CELLSIZE);
             for (int j=0; j<=maxRows; ++j)
                g.drawLine(j*CELLSIZE, 0, j*CELLSIZE, CELLSIZE*maxRows);
        }
        for (int i=0; i<maxRows; ++i) // draw moves
            for (int j=0; j<maxRows; ++j)
                if (board[i][j] != 0)
                    g.drawString(""+board[i][j], CELLSIZE/4+i*CELLSIZE, CELLSIZE*3/4+j*CELLSIZE);
    }

    public boolean solve(int row, int column)
    {
        if (row < 0 || column < 0 || row >= maxRows || column >= maxRows || board[row][column]!=0)
            return false; // out of range or already been to this cell
        board[row][column] = ++move;
        showBoard();

        if (move == maxRows*maxRows)
            return true; // filled the board!

        // try all possible moves from here
        if (   solve(row-2, column-1)
            || solve(row-2, column+1)
            || solve(row+2, column-1)
            || solve(row+2, column+1)
            || solve(row-1, column-2)
            || solve(row+1, column-2)
            || solve(row-1, column+2)
            || solve(row+1, column+2)) {
           repaint(); // in case not showing each move separately
           return true; // success!
        }

        board[row][column] = 0; // failed - remove current move
        --move;
        showBoard();
        return false;
    }

    public static void main(String args[])
    {
        KnightTour board = new KnightTour(6);
        if (board.solve(0,0))  // try solution starting at upper left
            System.out.println("Solution found.");
        else
            System.out.println("No solution found.");
    }
}

最も重要な部分はこの方法です。それを見て、あなたの動きを試してみてください

public boolean solve(int row, int column)
    {
        if (row < 0 || column < 0 || row >= maxRows || column >= maxRows || board[row][column]!=0)
            return false; // out of range or already been to this cell
        board[row][column] = ++move;
        showBoard();

        if (move == maxRows*maxRows)
            return true; // filled the board!

        // try all possible moves from here
        if (   solve(row-2, column-1)
            || solve(row-2, column+1)
            || solve(row+2, column-1)
            || solve(row+2, column+1)
            || solve(row-1, column-2)
            || solve(row+1, column-2)
            || solve(row-1, column+2)
            || solve(row+1, column+2)) {
           repaint(); // in case not showing each move separately
           return true; // success!
        }

        board[row][column] = 0; // failed - remove current move
        --move;
        showBoard();
        return false;
    }

c# - ナイトツアー検索パスアルゴリズム

3 に答える 3

Related

Reference