knight.cpp

软件课程设计（1） 是一些非常经典的程序

#include <iostream>
using namespace std;

class Knight  // 骑士类                    
{
	friend void tour (int,int,int);
private:
	bool ok (int,int);
	void Backtrack (int);
	void Display(int);             //打印出每次游历所走的步骤
	const static int dirc[9][3];     // 每步可以走的八个方向
	int Chess;                           // 棋盘规模n*n
	int	l;                          // 当前行坐标
	int	c;                           // 当前列坐标
	int **p;                        // 可行位置数组
	int **q;                        //按序存放（第几步，该步行数，列数）
	long sum;                       // 当前找到的可行解个数
};

// 第0行和第0列都不用
const int Knight::dirc[9][3] =             
{
	{0,0,0}, {0,1,2}, {0,2,1}, {0, -1,2}, {0, -2,1}, 
	{0, -2, -1}, {0, -1, -2}, {0,1, -2}, {0,2, -1} 
};

bool Knight::ok (int i, int j)
{
	if (i >= 1 && i <= Chess && j >= 1 && j <= Chess && !p[i][j])
		return true;
	return false;
}

void Knight::Backtrack (int t)
{
	if (t > Chess*Chess)  //共游遍棋盘上的所有点
	{
		sum++;
	    Display(Chess);	
	}
	else
	{
		for (int d = 1; d <= 8; d++)
		{
			l += dirc[d][1]; c += dirc[d][2];
			if (ok (l, c))
			{
				p[l][c] = t;
				q[t][1] = l;  q[t][2] =c;
				Backtrack (t + 1);
				p[l][c] = 0;
			}
			l -= dirc[d][1]; c -= dirc[d][2];
			q[t][1] = 0; q[t][2] = 0;          //否则撤消
		}
	}
}


void Knight::Display(int n)
{
    cout<<"第"<<sum<<"种走法:\n";
	for(int w=1;w<=n*n;w++)
	   {
		cout.width(3);
		cout<<"("<<q[w][1]<<","<<q[w][2]<<")-->";
	}
		cout<<endl;
}	

		
void tour (int u, int v, int n)
{
	Knight K;
	K.Chess = n;
	K.l = u;
	K.c = v;

	//初始化棋盘
	int **s = new int*[n + 1];
	for (int i = 0; i <= n; i++)
	{
		s[i] = new int[n + 1];
		for (int j = 0; j <= n; j++)
			s[i][j] = 0;
	} 
	
	
	int **y = new int*[n*n+1];
    for(int h = 0;h<=n*n;h++)
	{
          y[h] = new int[3];
		  for(int g=0;g<=2;g++)
			  y[h][g]=0;
	}

    s[u][v] = 1;          // 骑士出发处填1
    y[1][1]=u; y[1][2]=v;
	K.p = s;
	K.q = y;
	K.sum = 0;
	K.Backtrack(2);      // 从2开始填棋盘
	if (K.sum == 0) cout << "No solution!\n";
	else cout << "Total solutions: " << K.sum << endl;
	for (int k = 1; k <= n; k++)
		 delete[] s[k];
	delete[] s;
    for ( k = 1; k <= 2; k++)
		delete[] y[k];
	delete[] y;
}

int main()
{
	int Ln, Col, N;
	// 输入棋盘规模N*N
	cout << "请输入棋盘的规模(N*N): N = ";
	cin >> N;
	// 输入入口坐标值(Ln, Col)
	cout << "请输入骑士出发位置(Ln  Col): ";
	cin >> Ln >> Col;
	tour (Ln, Col, N);
	return 0;
}