3

我正在尝试编写一个有两个数组，ACCESS 和 board 的 Knights Tour 算法。ACCESS 是我用来确定下一步是什么的数组，而 board 是用户将看到的最终结果的数组。我的算法检查以找到可用移动次数最少的方格并去那里。如果碰巧有 2 个可能的移动具有相同数量的可用移动，我会找到离中心最远的移动（最靠近边界）并移动到那个位置。这个算法应该一直给出一个完美的 64 步骑士巡回赛程序，但我通常只能得到大约 60 步，谁能告诉我为什么它没有给出 64？

import java.util.*;
import java.io.*;
import java.text.DecimalFormat;

class KnightsTour
{
    public static void main(String args[]) throws IOException
    {
        boolean hasnextmove = true;
        Knight knight = new Knight();
        knight.getStart();
        do
        {
            knight.move();
            knight.newposition();
            hasnextmove = knight.hasnextmove();
        }while(hasnextmove == true);
        knight.displayBoard();
    }
}

class Knight
{
    DecimalFormat twoDigits = new DecimalFormat("00");
    private int board[][];
    private int startRow, startCol, rowPos, colPos, smallest;
    private int k = 2;
    private boolean move = true;
    final private int ACCESS[][] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                                    {0, 0, 2, 3, 4, 4, 4, 4, 3, 2, 0, 0},
                                    {0, 0, 3, 4, 6, 6, 6, 6, 4, 3, 0, 0},
                                    {0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
                                    {0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
                                    {0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
                                    {0, 0, 4, 6, 8, 8, 8, 8, 6, 4, 0, 0},
                                    {0, 0, 3, 4, 6, 6, 6, 6, 4, 3, 0, 0},
                                    {0, 0, 2, 3, 4, 4, 4, 4, 3, 2, 0, 0},
                                    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
                                    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
//                                      constructor, initializes values and the board
    public Knight()
    {
        board = new int[8][8];
        for(int i = 0; i < 8; i++)
            for(int k = 0; k < 8; k++)
                board[i][k] = 0;
        startRow = 0;
        startCol = 0;
        rowPos = 0;
        colPos = 0;
    }
//                                      tests to see if there is another move available
    public boolean hasnextmove()
    {
        if(ACCESS[rowPos + 1][colPos + 2] != 0 || ACCESS[rowPos + 1][colPos - 2] != 0 || ACCESS[rowPos - 1][colPos + 2] != 0 || ACCESS[rowPos - 1][colPos - 2] != 0 || ACCESS[rowPos - 2][colPos + 1] != 0 || ACCESS[rowPos - 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos + 1] != 0)
            return true;
        else
            return false;
    }
//                                      gets user input for starting square of the knight
    public void getStart() throws IOException
    {
        Scanner input = new Scanner(System.in);
        System.out.println("Please input the starting row number of the knight: ");
        startRow = input.nextInt() + 1;
        System.out.println("Please input the starting column number of the knight: ");
        startCol = input.nextInt() + 1;
        rowPos = startRow;
        colPos = startCol;
        board[startRow - 2][startCol - 2] = 1;
        ACCESS[startRow][startCol] = 0;
    }
//                                      displays the board
    public void displayBoard()
    {
        System.out.println("This is the game board");
        for(int i = 0; i < 8; i++)
        {
            for(int k = 0; k < 8; k++)
            {
                System.out.print(twoDigits.format(board[i][k]) + " ");
            }
            System.out.println();
        }
    }
//                                      sees if there is a possible move and if so, what is the smallest number space that the knight can move
    public void move()
    {
        smallest = 50;

        if(ACCESS[rowPos + 1][colPos + 2] != 0 || ACCESS[rowPos + 1][colPos - 2] != 0 || ACCESS[rowPos - 1][colPos + 2] != 0 || ACCESS[rowPos - 1][colPos - 2] != 0 || ACCESS[rowPos - 2][colPos + 1] != 0 || ACCESS[rowPos - 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos - 1] != 0 || ACCESS[rowPos + 2][colPos + 1] != 0)
            move = true;
        else
            move = false;

        if(move == true)
        {
            if(ACCESS[rowPos + 1][colPos + 2] < smallest && ACCESS[rowPos + 1][colPos + 2] != 0)
                smallest = ACCESS[rowPos + 1][colPos + 2];

            if(ACCESS[rowPos + 1][colPos - 2] < smallest && ACCESS[rowPos + 1][colPos - 2] != 0)
                smallest = ACCESS[rowPos + 1][colPos - 2];

            if(ACCESS[rowPos - 1][colPos + 2] < smallest && ACCESS[rowPos - 1][colPos + 2] != 0)
                smallest = ACCESS[rowPos - 1][colPos + 2];

            if(ACCESS[rowPos - 1][colPos - 2] < smallest && ACCESS[rowPos - 1][colPos - 2] != 0)
                smallest = ACCESS[rowPos - 1][colPos - 2];

            if(ACCESS[rowPos + 2][colPos + 1] < smallest && ACCESS[rowPos + 2][colPos + 1] != 0)
                smallest = ACCESS[rowPos + 2][colPos + 1];

            if(ACCESS[rowPos + 2][colPos - 1] < smallest && ACCESS[rowPos + 2][colPos - 1] != 0)
                smallest = ACCESS[rowPos + 2][colPos - 1];

            if(ACCESS[rowPos - 2][colPos + 1] < smallest && ACCESS[rowPos - 2][colPos + 1] != 0)
                smallest = ACCESS[rowPos - 2][colPos + 1];

            if(ACCESS[rowPos - 2][colPos - 1] < smallest && ACCESS[rowPos - 2][colPos - 1] != 0)
                smallest = ACCESS[rowPos - 2][colPos - 1];
        }
    }
//                                          moves the knight to the smallest numbered square it can
    public void newposition()
    {
        int temprow = rowPos;
        int tempcol = colPos;
        int possiblemoves = 0;
        boolean moved = false;
        boolean specialcasemoved = false;
//                                          moves pieces to new spot
        if(ACCESS[rowPos - 2][colPos + 1] == smallest && moved == false)
        {
            temprow = rowPos - 2;
            tempcol = colPos + 1;
            possiblemoves++;
        }
        if(ACCESS[rowPos - 1][colPos + 2] == smallest && moved == false)
        {
            temprow = rowPos - 1;
            tempcol = colPos + 2;
            possiblemoves++;
        }
        if(ACCESS[rowPos + 1][colPos + 2] == smallest && moved == false)
        {
            temprow = rowPos + 1;
            tempcol = colPos + 2;
            possiblemoves++;
        }
        if(ACCESS[rowPos + 2][colPos + 1] == smallest && moved == false)
        {
            temprow = rowPos + 2;
            tempcol = colPos + 1;
            possiblemoves++;
        }
        if(ACCESS[rowPos + 2][colPos - 1] == smallest && moved == false)
        {
            temprow = rowPos + 2;
            tempcol = colPos - 1;
            possiblemoves++;
        }
        if(ACCESS[rowPos + 1][colPos - 2] == smallest && moved == false)
        {
            temprow = rowPos + 1;
            tempcol = colPos - 2;
            possiblemoves++;
        }
        if(ACCESS[rowPos - 1][colPos - 2] == smallest && moved == false)
        {
            temprow = rowPos - 1;
            tempcol = colPos - 2;
            possiblemoves++;
        }
        if(ACCESS[rowPos - 2][colPos - 1] == smallest && moved == false)
        {
            temprow = rowPos - 2;
            tempcol = colPos - 1;
            possiblemoves++;
        }
        if(possiblemoves > 1)
        {
            double distance = 0;
            double tempdistance;
            if(ACCESS[rowPos - 2][colPos + 1] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 2 - 1)), 2) + Math.pow((6.5 - (colPos + 1 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos - 2;
                    tempcol = colPos + 1;
                }
            }
            if(ACCESS[rowPos - 1][colPos + 2] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 1 - 1)), 2) + Math.pow((6.5 - (colPos + 2 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos - 1;
                    tempcol = colPos + 2;
                }
            }
            if(ACCESS[rowPos + 1][colPos + 2] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 1 - 1)), 2) + Math.pow((6.5 - (colPos + 2 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos + 1;
                    tempcol = colPos + 2;
                }
            }
            if(ACCESS[rowPos +2][colPos + 1] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 2 - 1)), 2) + Math.pow((6.5 - (colPos + 1 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos + 2;
                    tempcol = colPos + 1;
                }
            }
            if(ACCESS[rowPos + 2][colPos - 1] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 2 - 1)), 2) + Math.pow((6.5 - (colPos - 1 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos + 2;
                    tempcol = colPos - 1;
                }
            }
            if(ACCESS[rowPos + 1][colPos - 2] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos + 1 - 1)), 2) + Math.pow((6.5 - (colPos - 2 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos + 1;
                    tempcol = colPos - 2;
                }
            }
            if(ACCESS[rowPos - 1][colPos - 2] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 1 - 1)), 2) + Math.pow((6.5 - (colPos - 2 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos - 1;
                    tempcol = colPos - 2;
                }
            }
            if(ACCESS[rowPos - 2][colPos - 1] == smallest)
            {
                tempdistance = Math.sqrt(Math.pow((6.5 - (rowPos - 2 - 1)), 2) + Math.pow((6.5 - (colPos - 1 - 1)), 2));
                if(tempdistance > distance)
                {
                    distance = tempdistance;
                    temprow = rowPos - 2;
                    tempcol = colPos - 1;
                }
            }
/*          boolean m1, m2, m3, m4, m5, m6, m7, m8;
            m1 = m2 = m3 = m4 = m5 = m6 = m7 = m8 = false;
            int randomnumber;
            if(ACCESS[rowPos - 2][colPos + 1] == smallest)
            {
                m1 = true;
            }
            if(ACCESS[rowPos - 1][colPos + 2] == smallest)
            {
                m2 = true;
            }
            if(ACCESS[rowPos + 1][colPos + 2] == smallest)
            {
                m3 = true;
            }
            if(ACCESS[rowPos + 2][colPos + 1] == smallest)
            {
                m4 = true;
            }
            if(ACCESS[rowPos + 2][colPos - 1] == smallest)
            {
                m5 = true;
            }
            if(ACCESS[rowPos + 1][colPos - 2] == smallest)
            {
                m6 = true;
            }
            if(ACCESS[rowPos - 1][colPos - 2] == smallest)
            {
                m7 = true;
            }
            if(ACCESS[rowPos - 2][colPos - 1] == smallest)
            {
                m8 = true;
            }
            do
            {
                Random rand = new Random();
                int randomNum = (int) (rand.nextInt(6)+1) + 1;

                switch(randomNum) 
                {
                    case 1:
                        if(m1 == true)
                        {
                            temprow = rowPos - 2;
                            tempcol = colPos + 1;
                            specialcasemoved = true;
                        }
                    case 2:
                        if(m2 == true)
                        {
                            temprow = rowPos - 1;
                            tempcol = colPos + 2;
                            specialcasemoved = true;
                        }
                    case 3:
                        if(m3 == true)
                        {
                            temprow = rowPos + 1;
                            tempcol = colPos + 2;
                            specialcasemoved = true;
                        }
                    case 4:
                        if(m4 == true)
                        {
                            temprow = rowPos + 2;
                            tempcol = colPos + 1;
                            specialcasemoved = true;
                        }
                    case 5:
                        if(m5 == true)
                        {
                            temprow = rowPos + 2;
                            tempcol = colPos - 1;
                            specialcasemoved = true;
                        }
                    case 6:
                        if(m6 == true)
                        {
                            temprow = rowPos + 1;
                            tempcol = colPos - 2;
                            specialcasemoved = true;
                        }
                    case 7:
                        if(m7 == true)
                        {
                            temprow = rowPos - 1;
                            tempcol = colPos - 2;
                            specialcasemoved = true;
                        }
                    case 8:
                        if(m8 == true)
                        {
                            temprow = rowPos - 2;
                            tempcol = colPos - 1;
                            specialcasemoved = true;
                        }
                }
            }while(specialcasemoved == false);*/
        }
        rowPos = temprow;
        colPos = tempcol;
        System.out.println(possiblemoves);
        possiblemoves = 0;
        ACCESS[rowPos][colPos] = 0;
        board[rowPos - 2][colPos - 2] = k;
        k++;
//      System.out.println(rowPos + " " + colPos);
    }
}
4

1 回答 1

1

没有 60 步的骑士巡回赛解决方案。棋盘上有 64 个方格，因此 Knight's Tour 必须正好有 64 步（如果不是闭环解决方案，则可能有 63 步）。如果你得到一个包含 60 步的解决方案，那么你的算法就被打破了。

如果我按字面解释您的描述，您可能误解了 Warnsdorff 的规则。“规则”旨在解决详尽的 Knight's Tour 算法由于可能性的数量而效率低下的问题。它表明，当使用详尽的、深度优先的回溯搜索算法时，始终首先探索本身具有最少选项的选项。这仍然需要回溯，因为即使使用规则有时也会导致需要退出的死胡同。

我意识到这可能无法解决您的问题，但是您发布了很多代码，这使得准确理解可能出现的问题变得复杂。我相信通过更好的封装可以大大简化它。如果有帮助，我很乐意发表一些建议 - 请发表评论。

于 2015-02-13T05:35:19.270 回答