Knight’s Tour问题没有输出我的代码。

huangapple go评论64阅读模式
英文:

Not getting any output to my code for Knight's Tour Problem

问题

问题:

给定一个N*N的棋盘,骑士位于一个空棋盘的第一个方格上。根据国际象棋的规则移动,骑士必须访问每个方格恰好一次。打印它们被访问的每个方格的顺序。

我使用了回溯,但没有得到任何输出

#include <bits/stdc++.h>
using namespace std;

bool valid(int a, int b)
{
    // 检查有效性
    if (a < 0 || a > 7 || b < 0 || b > 7)
        return false;

    return true;
}

bool backtrack(vector<vector<int>> &chess, vector<pair<int, int>> &moves, int i, int j)
{
    // 找到答案
    if (chess[i][j] == 63)
        return true;
        
    else
    {
        bool flag = false;

        for (int k = 0; k < moves.size(); k++)
        {
            int a = i + moves[k].first, b = j + moves[k].second;
            // 如果有效,并且没有被访问过
            if (valid(a, b) && chess[a][b] == -1)
            {
                chess[a][b] = chess[i][j] + 1;

                // 递归下一步
                flag = backtrack(chess, moves, a, b);

                // 如果没有找到解答,回溯
                if (!flag)
                    chess[a][b] = -1;
                
                // 中断,返回答案
                else
                    break;
            }
        }
        return flag;
    }
}

int main()
{
    vector<vector<int>> chess(8, vector<int>(8, -1));

    vector<pair<int, int>> moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
    
    chess[0][0] = 0;

    backtrack(chess, moves, 0, 0);

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            cout << chess[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
英文:

Problem:

Given a N*N board with the Knight placed on the first block
of an empty board. Moving according to the rules of chess
knight must visit each square exactly once. Print the order
of each cell in which they are visited.

I used backtracking, but not getting any output

#include &lt;bits/stdc++.h&gt;
using namespace std;
bool valid(int a, int b)
{
//check validity
if (a &lt; 0 || a &gt; 7 || b &lt; 0 || b &gt; 7)
return false;
return true;
}
bool backtrack(vector&lt;vector&lt;int&gt;&gt; &amp;chess, vector&lt;pair&lt;int, int&gt;&gt; &amp;moves, int i, int j)
{
//ans found
if (chess[i][j] == 63)
return true;
else
{
bool flag = false;
for (int k = 0; k &lt; moves.size(); k++)
{
int a = i + moves[k].first, b = j + moves[k].second;
//if valid.. and not already visited
if (valid(a, b) &amp;&amp; chess[a][b] == -1)
{
chess[a][b] = chess[i][j] + 1;
//recurse for next moves
flag = backtrack(chess, moves, a, b);
//if solution not found..backtrack
if (!flag)
chess[a][b] = -1;
//break..return ans
else
break;
}
}
return flag;
}
}
int main()
{
vector&lt;vector&lt;int&gt;&gt; chess(8, vector&lt;int&gt;(8, -1));
vector&lt;pair&lt;int, int&gt;&gt; moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};
chess[0][0] = 0;
backtrack(chess, moves, 0, 0);
for (int i = 0; i &lt; 8; i++)
{
for (int j = 0; j &lt; 8; j++)
{
cout &lt;&lt; chess[i][j] &lt;&lt; &quot; &quot;;
}
cout &lt;&lt; endl;
}
return 0;
}

答案1

得分: 1

将你的移动顺序更改为(较少纠缠):

    vector<pair<int, int>> moves = { {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

然后它将正常工作。相当快速。

有多个可能的解决方案。还有其他选择搜索顺序的策略,可能会改善情况。

以下是一个允许您玩棋盘大小的替代版本:

#include <iostream>
#include <iomanip>
#include <utility>
using namespace std;

const int N = 8;
int A[N][N]{};
pair<int, int> jump[] = { {1,2}, {2,1} ,{2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

//==========================================================

void display()
{
   for (int i = 0; i < N; i++)
   {
      for (int j = 0; j < N; j++) cout << setw(3) << A[i][j];
      cout << '\n';
   }
}

//==========================================================

bool check(int mv, int i, int j)
{
   if (i < 0 || i >= N || j < 0 || j >= N || A[i][j]) return false;
   A[i][j] = mv;
   return true;
}

//==========================================================

bool solve(int mv, int i0, int j0)                       // 主要回溯例程
{
   if (mv == N * N)                                      // *** 完成
   {
      display();
      return true;
   }

   for (int jp = 0; jp < 8; jp++)
   {
      int i = i0 + jump[jp].first;
      int j = j0 + jump[jp].second;
      if (check(mv, i, j) && solve(mv + 1, i, j)) return true;      // *** 主要递归调用 ***
   }
   A[i0][j0] = 0;
   return false;
}

//==========================================================

int main()
{
   int i = 0, j = 0, mv = 0;
   A[i][j] = mv;
   solve(mv + 1, i, j);
}

请注意,我已将C++代码的HTML编码符号替换为正常的C++语法。

英文:

Change the ordering of your moves to (the less tangled)

    vector&lt;pair&lt;int, int&gt;&gt; moves = { {1,2}, {2,1}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };

and it will work. Quite quickly.

There are multiple possible solutions. There are also other strategies for choosing the search order which may improve things.

Here is an alternative version, allowing you to play with the size of the board:

#include &lt;iostream&gt;
#include &lt;iomanip&gt;
#include &lt;utility&gt;
using namespace std;
const int N = 8;
int A[N][N]{};
pair&lt;int,int&gt; jump[] = { {1,2}, {2,1} ,{2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2} };
//==========================================================
void display()
{
for ( int i = 0; i &lt; N; i++ )
{
for ( int j = 0; j &lt; N; j++ ) cout &lt;&lt; setw( 3 ) &lt;&lt; A[i][j];
cout &lt;&lt; &#39;\n&#39;;
}
}
//==========================================================
bool check( int mv, int i, int j )
{
if ( i &lt; 0 || i &gt;= N || j &lt; 0 || j &gt;= N || A[i][j] ) return false;
A[i][j] = mv;
return true;
}
//==========================================================
bool solve( int mv, int i0, int j0 )                       // main backtracking routine
{
if ( mv == N * N )                                      // *** COMPLETION
{
display();
return true;
}
for ( int jp = 0; jp &lt; 8; jp++ )
{
int i = i0 + jump[jp].first ;
int j = j0 + jump[jp].second;
if ( check( mv, i, j ) &amp;&amp; solve( mv + 1, i, j ) ) return true;      // *** MAIN RECURSIVE CALL ***
}
A[i0][j0] = 0;
return false;
}
//==========================================================
int main()
{
int i = 0, j = 0, mv = 0;
A[i][j] = mv;
solve( mv + 1, i, j );
}

答案2

得分: 0

我没有找到任何无限循环。但你的代码永远不会到达打印行,因为你正在使用一种蛮力搜索算法,而你使用的棋盘尺寸太大,以至于蛮力计算不可行,需要合理的时间。

维基百科说,8x8棋盘上有“26,534,728,821,064个封闭的骑士之旅”,基本上意味着你可以找到该特定棋盘的解决方案数量。然而:

对于除了最小的棋盘之外的所有棋盘,使用蛮力搜索骑士之旅是不切实际的。例如,在8×8的棋盘上,有大约4×1051个可能的移动序列,这远远超出了现代计算机(或计算机网络)执行如此大型集合上的操作的能力。然而,这个数字的大小并不反映问题的难度,问题可以“通过人类的洞察和聪明才智……轻松解决。” - 维基百科(骑士之旅 - 蛮力算法)

这意味着在如此庞大的空间中找到其中一个解决方案的概率是极低的。

你需要使用另一种具有更快运行时间的算法,如分而治之,或在那个页面上列出的其他算法。

英文:

I did not find any infinite loop. But your code never reaches the printing lines, because you are using a brute-force searching algorithm, and the board size you are using is so large that it can't feasibly be computed with brute force in a reasonable amount of time.

Wikipedia says that there are "26,534,728,821,064 closed tours" on an 8x8 board, and basically this means the number of solutions that you can find for that particular board. However:

> A brute-force search for a knight's tour is impractical on all but the smallest boards. For example, there are approximately 4×1051 possible move sequences on an 8 × 8 board, and it is well beyond the capacity of modern computers (or networks of computers) to perform operations on such a large set. However, the size of this number is not indicative of the difficulty of the problem, which can be solved "by using human insight and ingenuity ... without much difficulty." - Wikipedia (Knight's tour - Brute force algorithms)

It means that the probability of finding one of those solutions in that large of a space is extremely low.

You need to use another algorithm with faster runtime, such as divide and conquer, or others that are listed on that page.

答案3

得分: 0

你的代码中没有bug。只是算法需要稍微改进以提高速度。

一个技巧是首先选择那些未来邻居不多的单元格。在以下代码中:

  • 我设置了一个可能位置的列表。
  • 对于每个位置,我计算了未来可能的位置数。
  • 我根据这些数字对可能的首选位置进行排序。

通过这种修改,即使对于N=20,我也可以立即得到结果。

结果

 0 59 14 31 48 27 12 29
15 32 53 60 13 30 49 26
58  1 56 45 54 47 28 11
33 16 61 52 63 44 25 50
2 57 42 55 46 51 10 39
17 34 19 62 43 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6
英文:

There is not bug in your code. Simply, the algorithm must be slightly improved to be faster.

One trick in to first select cells that do not have much future neighbours.
In the following code,

  • I set a list of possible positions.
  • For each position, I calculate the number of future possible positions
  • I sort the possible first positions according to these numbers

With this modification, I got the result about instantaneously, even for N=20.

Result

 0 59 14 31 48 27 12 29
15 32 53 60 13 30 49 26
58  1 56 45 54 47 28 11
33 16 61 52 63 44 25 50
2 57 42 55 46 51 10 39
17 34 19 62 43 40  7 24
20  3 36 41 22  5 38  9
35 18 21  4 37  8 23  6
#include &lt;vector&gt;
#include &lt;utility&gt;
#include &lt;iostream&gt;
#include &lt;cstdlib&gt;
#include &lt;iomanip&gt;
#include &lt;numeric&gt;
#include &lt;algorithm&gt;

#define N 8					// 8
#define two_n_m1 (N*N-1)	// 63 = N*N - 1

using namespace std;

bool valid(int a, int b) {
    //check validity
    return (a &gt;= 0 &amp;&amp; a &lt; N &amp;&amp; b &gt;= 0 &amp;&amp; b &lt; N);
}

int count_neighbors (vector&lt;vector&lt;int&gt;&gt; &amp;chess, vector&lt;pair&lt;int, int&gt;&gt; &amp;moves, int i, int j) {
	int count = 0;
	for (auto&amp; mov: moves) {
		int a = i + mov.first, b = j + mov.second;
		if (valid(a, b) &amp;&amp; (chess[a][b] == -1)) {
			count ++;
		}
	}
	return count;
}

bool backtrack(vector&lt;vector&lt;int&gt;&gt; &amp;chess, vector&lt;pair&lt;int, int&gt;&gt; &amp;moves, int i, int j) {
    //ans found
    if (chess[i][j] == two_n_m1) return true;
	vector&lt;pair&lt;int, int&gt;&gt; neighbors;
	
	for (auto&amp; mov: moves) {
		int a = i + mov.first, b = j + mov.second;
		if (valid(a, b) &amp;&amp; (chess[a][b] == -1)) {
			neighbors.push_back ({a, b});
		}
	}
	int n = neighbors.size();
	if (n == 0) return false;
	if (n == 1) {
		int a = neighbors[0].first, b = neighbors[0].second;
		chess[a][b] = chess[i][j] + 1;
		return backtrack(chess, moves, a, b);
	}
	vector&lt;int&gt; future;
	for (auto&amp; candidate: neighbors)  {
		int count = count_neighbors (chess, moves, candidate.first, candidate.second);
		future.push_back (count);                                                                
	}
	vector&lt;int&gt; index(n);
	std::iota (index.begin(), index.end(), 0);
	auto comp = [&amp;] (int i, int j) {return future[i] &lt; future[j];};
	std::sort (index.begin(), index.end(), comp);

	for (int k = 0; k &lt; n; k++) {
		int kp = index[k];
		int a = neighbors[kp].first, b = neighbors[kp].second;
			chess[a][b] = chess[i][j] + 1;
			auto flag = backtrack(chess, moves, a, b);
			if (flag) return true;
			chess[a][b] = -1;
	}
	return false;
}

int main()
{
    vector&lt;vector&lt;int&gt;&gt; chess(N, vector&lt;int&gt;(N, -1));

    vector&lt;pair&lt;int, int&gt;&gt; moves = {{2, -1}, {2, 1}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {-1, -2}, {1, -2}};

    chess[0][0] = 0;

    auto check = backtrack(chess, moves, 0, 0);
	
	if (!check) {
		cout &lt;&lt; &quot;No solution found\n&quot;;
		std::exit (1);
	}

    for (int i = 0; i &lt; N; i++)
    {
        for (int j = 0; j &lt; N; j++)
        {
            cout &lt;&lt; right &lt;&lt; setw(2) &lt;&lt; chess[i][j] &lt;&lt; &quot; &quot;;
        }
        cout &lt;&lt; endl;
    }
    return 0;
}

huangapple
  • 本文由 发表于 2023年2月27日 15:25:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/75577712.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定