登录
当前位置： 首页 > 知识库问答 >
问题：

骑士巡演算法

裴永年
2023-03-14

我正在尝试编写一个骑士之旅算法，它有两个数组，访问和板。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);
    }
}

共有1个答案

巫欣荣
2023-03-14

没有60步的骑士之旅解决方案。棋盘上有64个方格，因此骑士之旅必须有64个移动（如果不是闭环解决方案，则可能有63个）。如果你得到一个60步的解，那么你的算法就失败了。

如果我逐字解释你的描述，你可能误解了沃恩斯多夫的规则。“规则”旨在解决穷举骑士之旅算法由于可能性的数量而效率低下的问题。它表明，当使用穷举、深度优先、回溯搜索算法时，总是首先探索选项本身最少的选项。这仍然需要回溯，因为即使使用规则有时也会导致需要回溯的死胡同。

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

 类似资料：
  • 骑士巡演的问题

    我制作了这段代码来完成骑士之旅，你必须和一个没有重复的骑士一起到达棋盘上的每一个方块，但我有一些问题。它只会打印一个没有移动的空棋盘，我不知道如何修复它。 测试人员： 如果您有任何建议，我将不胜感激，我正在为一门课做这件事，所以我需要尽快完成。

  • 在国际象棋骑士巡回赛中遇到困难

    我试着用回溯法为骑士之旅问题编写代码。我的代码适用于4x4矩阵，但对于8x8矩阵，它不会在输出屏幕上显示任何内容。 我不知道我做错了什么。 我的代码就是这样工作的： 如果所有的广场都参观过 其他的 > 向solution vector添加下一步动作之一，并递归检查该动作是否会导致解决方案。（一个骑士最多可以走八步。我们在这一步的八步中选择一步）。 如果在上述步骤中选择的移动没有导致解决方案，则从解

  • 骑士之旅

    我正在尝试编写骑士之旅递归算法： 谁能告诉我哪里出错了？我已经一步一步地检查了什么池算法正在添加到列表中。什么是大惊奇算法在添加4,3池和6,4池后，应该用6,4作为实际位置来称呼它自己，但我不知道为什么它用4,3作为实际位置来称呼自己。

  • 7.11.骑士之旅

    另一个经典问题，我们可以用来说明第二个通用图算法称为 “骑士之旅”。骑士之旅图是在一个棋盘上用一个棋子当骑士玩。图的目的是找到一系列的动作，让骑士访问板上的每格一次。一个这样的序列被称为“旅游”。骑士的旅游难题已经吸引了象棋玩家，数学家和计算机科学家多年。一个 $$8 \times 8$$ 棋盘的可能的游览次数的上限为 $$1.305 \times 10^{35}$$ ;然而，还有更多可能的死胡同

  • 骑士游爪哇

    当我运行程序而不是找到骑士之旅时，我收到了一个StackOverflow错误。任何想法是什么导致了这一点，以及我如何改变我的代码，实际上找到骑士之旅，并摆脱这个错误。项目是为我的CS280课程，并在周五到期，请帮助。谢谢！！

  • FG 骑士进度条

    《FG 骑士进度条》是《异星工厂网页版》作者基于《骑士进度条 2》复刻的另一款放置游戏，相对来说，界面看起来像是一款游戏了。玩法上变化不大，增加了成就功能。 可以导入《骑士进度条2》的存档，接档直接玩。

相关问答

巡演练习#7：二叉树等价国际象棋（骑士）运动，避免下棋Java中的骑士之旅（递归），使用图和DFS递归骑士之旅中变量的正确声明（Java家庭作业）Lambda演算Haskell的Beta转换

相关文章

mysql巡检脚本(必看篇)巡回练习：等效二叉树单身人士去JavaScript排序算法动画演示效果的实现方法oracle自动巡检脚本生成html报告的方法

相关阅读

富士康java后端美团骑行后端面经（oc）成都天巡微小 java实习面经美团骑行运营社招面经卫士通测试面经

相关工具

FG 骑士进度条巡云轻论坛系统文件安全卫士Spread_for_ASP.NET 在线演示子虚博客演示版

相关文档

LeetCode 题解动画演示算法珠玑常规算法教程数据挖掘算法Way to Algorithm 算法之路
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.