骑士遍历算法

Question

我正在编写一个骑士周游算法，其中有两个数组：ACCESS和board。ACCESS是我用来确定下一步移动的数组，board是用户将看到的最终结果数组。我的算法会检查哪个方格可用的移动次数最少，并前往那里。如果有两个可能的移动，可用移动次数相同，则我会找到距离中心最远（最接近边界）的那个移动并前往该位置。这个算法应该能够始终得到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);
    }
}

- Sygnerical

---

为什么“那个算法应该找到完美的64步骑士之旅”？您确定不需要任何回溯吗？ - meriton

Answer 1

一条“骑士巡游”解法不可能只有60个步骤。棋盘上共有64个方格，因此一个“骑士巡游”必须恰好有64个步骤（如果它不是一个封闭循环解法，则可能仅有63个步骤）。如果你得到一个只有60个步骤的解法，则你的算法出了问题。

如果我对你的描述字面理解，并按照 Warnsdorff 的规则进行操作，你可能已经误解了这个“规则”。该“规则”旨在解决穷举“骑士巡游”算法由于可能性太多而效率低下的问题。它建议，在使用穷举、深度优先、回溯搜索算法时，总是首先探索选项本身具有最少选项的选择。即使使用这个规则，仍需要回溯，因为有时候会遇到需要回溯的死胡同。

我意识到这可能没有解决你的问题，但你发布了很多代码，这使得理解可能出现的问题变得复杂。我相信通过更好的封装可以大大简化它。如果有帮助的话，我很乐意提供一些建议 - 只需留下评论。

- sprinter