n皇后问题的代码补充，给了一个框架，有点看不懂。
#include <iostream>
#include <windows.h>
using namespace std;
int abs(int a, int b) // 返回两个参数差值的绝对值
{
int c;
c=a-b;
if(c>=0) // 填写代码
c=c;
else
c=-c;
return c;
}
void print( ) // 对皇后位置进行输出，补充参数定义
{
// 填写代码
}
int Queen( ) // 基于回溯法解决n皇后问题，补充参数定义
{
int q[100],i,scheme[1000][100];
int scheme_index=0;
for(i=0; i<num; i++) //把第i行全部置1
{
q[i]=1;
}
i=0;
int c=0;
while(i<num)
{
if (q[i]<=num)
{
int j=0;
while((j<i)&&(q[j]!=q[i])&&(abs(q[j],q[i])!=abs(j,i)))
j++;
if(j<i)
{
q[i]=q[i]+1;
system("cls"); // 清屏
cout<<"移动步数为："<<c++<<endl;
print();
Sleep(speed);
}
else
{
i++;
system("cls");
print();
Sleep(speed);
}
if(i==num)
{
scheme_index++;
c--;
system("cls");
cout<<"移动步数为："<<c<<endl;
print();
}
}
else
{
q[i]=1;
i--;
c++;
if (i<0)
break;
q[i]=q[i]+1;
}
}
cout<<"共有"<<scheme_index<<"种方案！"<<endl;
}
int main()
{
int num;
cout<<"请输入皇后个数！\n";
cin>>num;
Queen(num);
return 0;
}
#include <iostream>
#include <memory.h>
#include <stdlib.h>
using namespace std;
//下面代表对于规模的大小的棋盘的路径，其中保存来回路径方便遍历
//保存的数字代表下一步的方向，8种方向用8个数字代表
int ans6_6[6][6][2] = {
{{3,4},{4,5},{3,6},{6,3},{4,6},{5,6}},
{{2,3},{5,2},{2,7},{2,4},{5,7},{7,6}},
{{1,4},{8,3},{7,8},{2,3},{4,1},{5,8}},
{{4,1},{5,4},{6,3},{7,1},{8,4},{7,5}},
{{3,2},{8,3},{3,6},{3,6},{7,1},{6,8}},
{{2,1},{2,8},{8,7},{7,2},{1,7},{8,7}}};
int ans6_8[6][8][2] = {
{{3,4},{3,5},{6,3},{6,3},{3,5},{5,3},{6,4},{6,5}},
{{3,2},{5,2},{5,7},{3,7},{7,2},{7,2},{4,7},{7,6}},
{{1,4},{8,3},{4,7},{1,4},{4,1},{2,7},{1,4},{8,5}},
{{4,1},{5,1},{6,5},{7,5},{5,6},{5,4},{6,4},{5,8}},
{{3,2},{8,3},{2,6},{3,8},{8,2},{3,8},{1,6},{8,6}},
{{2,1},{1,8},{1,7},{7,1},{2,1},{2,7},{8,1},{8,7}}};
int ans8_8[8][8][2] = {
{{3,4},{4,5},{6,4},{3,6},{4,6},{6,3},{4,6},{5,6}},
{{4,2},{2,5},{2,7},{5,2},{2,5},{2,7},{4,5},{7,6}},
{{1,4},{8,5},{6,8},{8,4},{4,3},{2,8},{4,1},{5,8}},
{{1,2},{4,8},{4,1},{1,3},{6,5},{1,3},{7,4},{5,8}},
{{1,4},{8,5},{6,2},{3,4},{8,5},{7,8},{4,1},{7,8}},
{{4,2},{4,5},{3,8},{1,8},{3,4},{4,7},{4,1},{8,5}},
{{1,3},{8,3},{6,3},{1,6},{8,7},{6,3},{6,7},{6,8}},
{{1,2},{2,8},{7,8},{7,2},{7,2},{8,2},{1,8},{7,8}}};
int ans8_10[8][10][2] = {
{{3,4},{3,5},{6,3},{3,6},{3,6},{5,6},{6,3},{3,6},{4,6},{5,6}},
{{3,2},{2,5},{2,7},{2,7},{7,2},{2,7},{2,7},{2,3},{7,4},{5,7}},
{{1,3},{8,5},{5,7},{5,6},{3,1},{3,5},{4,6},{5,4},{4,1},{7,8}},
{{1,4},{2,4},{7,4},{5,3},{2,4},{4,6},{3,7},{6,7},{4,1},{8,6}},
{{1,4},{5,1},{6,1},{2,4},{1,3},{7,2},{6,1},{2,8},{8,7},{5,8}},
{{4,2},{8,5},{8,1},{8,5},{4,2},{8,6},{7,8},{3,4},{6,4},{5,8}},
{{3,1},{8,3},{6,3},{2,6},{8,3},{6,3},{6,2},{3,6},{6,1},{6,7}},
{{1,2},{2,8},{1,7},{7,2},{7,2},{2,8},{7,2},{7,2},{8,1},{8,7}}};
int ans10_10[10][10][2] = {
{{3,4},{3,5},{4,6},{5,3},{3,6},{5,6},{4,6},{6,3},{4,6},{5,6}},
{{2,3},{5,3},{2,7},{2,7},{2,4},{7,2},{2,7},{2,3},{4,5},{7,5}},
{{1,3},{8,5},{7,1},{7,8},{3,1},{6,5},{4,5},{5,8},{4,1},{7,8}},
{{3,1},{4,5},{7,5},{4,2},{4,3},{8,3},{3,7},{1,5},{1,4},{5,8}},
{{1,4},{3,4},{6,7},{4,3},{1,5},{1,4},{7,1},{7,8},{5,7},{5,8}},
{{1,2},{1,5},{6,8},{4,7},{6,8},{7,8},{1,5},{5,6},{5,1},{8,6}},
{{4,2},{8,5},{8,2},{1,6},{4,8},{2,6},{8,6},{2,1},{4,1},{5,6}},
{{1,4},{2,5},{5,4},{2,6},{2,8},{1,6},{5,1},{2,1},{4,5},{5,6}},
{{1,3},{2,8},{6,3},{2,3},{6,3},{6,8},{6,3},{2,3},{6,1},{6,8}},
{{1,2},{8,1},{7,2},{8,2},{7,2},{7,1},{7,2},{1,2},{7,1},{7,8}}};
int ans10_12[10][12][2] = {
{{3,4},{3,5},{5,6},{3,6},{4,5},{3,6},{4,6},{3,6},{3,5},{3,6},{4,5},{5,6}},
{{2,4},{2,5},{6,7},{2,7},{2,5},{2,7},{5,6},{2,7},{4,5},{2,7},{4,7},{5,7}},
{{1,2},{8,1},{6,5},{1,5},{2,3},{6,8},{5,4},{1,8},{6,4},{1,3},{4,1},{5,8}},
{{1,2},{8,5},{4,3},{1,2},{6,3},{6,1},{7,2},{1,6},{6,4},{5,8},{4,1},{7,8}},
{{3,4},{1,5},{1,2},{4,2},{7,3},{2,1},{7,2},{8,6},{3,5},{8,6},{4,1},{5,8}},
{{1,3},{3,4},{6,7},{5,8},{3,5},{2,5},{7,6},{2,5},{4,1},{8,5},{6,7},{5,8}},
{{1,2},{8,5},{7,6},{4,7},{2,8},{3,5},{6,7},{1,3},{6,2},{3,4},{4,1},{5,8}},
{{2,4},{4,5},{8,1},{1,6},{1,2},{5,4},{1,2},{4,7},{1,6},{7,8},{4,1},{5,7}},
{{1,3},{2,3},{6,3},{6,3},{1,8},{6,3},{2,3},{6,3},{6,3},{6,3},{8,1},{6,8}},
{{1,2},{8,2},{7,8},{7,2},{7,1},{7,2},{8,2},{7,2},{7,8},{7,2},{7,1},{7,8}}};
//ceshi数组储存棋盘的往下走的方向变量，sign作为标记数组作为调转的中间变量
//answer数组存储由ceshi数组转换为的顺序数组
int ceshi[1005][1005], sign[1005][1005];
int answer[1005][1005];
//cheng_area输入x,y的范围，用来调转矩阵的方向
void change_area(int x_low, int x_high, int y_low, int y_high)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high;tmpb++)
{
if(ceshi[tmpa][tmpb] == 1)
sign[tmpa - 2][tmpb + 1] = 5;
if(ceshi[tmpa][tmpb] == 2)
sign[tmpa - 1][tmpb + 2] = 6;
if(ceshi[tmpa][tmpb] == 3)
sign[tmpa + 1][tmpb + 2] = 7;
if(ceshi[tmpa][tmpb] == 4)
sign[tmpa + 2][tmpb + 1] = 8;
if(ceshi[tmpa][tmpb] == 5)
sign[tmpa + 2][tmpb - 1] = 1;
if(ceshi[tmpa][tmpb] == 6)
sign[tmpa + 1][tmpb - 2] = 2;
if(ceshi[tmpa][tmpb] == 7)
sign[tmpa - 1][tmpb - 2] = 3;
if(ceshi[tmpa][tmpb] == 8)
sign[tmpa - 2][tmpb - 1] = 4;
}
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high;tmpb++)
ceshi[tmpa][tmpb] = sign[tmpa][tmpb];
}
//找到与其对应的数组将方向填入ceshi数组中
void marry(int x_low, int x_high, int y_low, int y_high)
{
int x_dif = x_high - x_low + 1;
int y_dif = y_high - y_low + 1;
if(x_dif == 6)
if(y_dif == 6)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans6_6[tmpa - x_low][tmpb - y_low][0];
}
else if(y_dif == 8)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans6_8[tmpa - x_low][tmpb - y_low][0];
}
if(x_dif == 8)
if(y_dif == 6)
{
for(int tmpa = 0; tmpa <= x_high - x_low; tmpa++)
for(int tmpb = 0; tmpb <= y_high - y_low; tmpb++)
{
ceshi[x_low + tmpa][y_high - tmpb] = ans6_8[tmpb][tmpa][0] + 2;
if(ceshi[x_low + tmpa][y_high - tmpb] > 8)
ceshi[x_low + tmpa][y_high - tmpb] -= 8;
}
}
else if(y_dif == 8)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans8_8[tmpa - x_low][tmpb - y_low][0];
}
else if(y_dif == 10)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans8_10[tmpa - x_low][tmpb - y_low][0];
}
if(x_dif == 10)
if(y_dif == 8)
{
for(int tmpa = 0; tmpa < x_dif; tmpa++)
for(int tmpb = 0; tmpb < y_dif; tmpb++)
{
ceshi[x_low + tmpa][y_high - tmpb] = ans8_10[tmpb][tmpa][0] + 2;
if(ceshi[x_low + tmpa][y_high - tmpb] > 8)
ceshi[x_low + tmpa][y_high - tmpb] -= 8;
}
}
else if(y_dif == 10)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans10_10[tmpa - x_low][tmpb - y_low][0];
}
else if(y_dif == 12)
{
for(int tmpa = x_low; tmpa <= x_high; tmpa++)
for(int tmpb = y_low; tmpb <= y_high; tmpb++)
ceshi[tmpa][tmpb] = ans10_12[tmpa - x_low][tmpb - y_low][0];
}
if(x_dif == 12)
if(y_dif == 10)
{
for(int tmpa = 0; tmpa < x_dif; tmpa++) //12
for(int tmpb = 0; tmpb < y_dif; tmpb++) //10
{
ceshi[x_low + tmpa][y_high - tmpb] = ans10_12[tmpb][tmpa][0] + 2;
if(ceshi[x_low + tmpa][y_high - tmpb] > 8)
ceshi[x_low + tmpa][y_high - tmpb] -= 8;
}
}
}
//分治，将棋盘规模大的划分成小的
void dp(int x_low, int x_high, int y_low, int y_high)
{
int x_dif = x_high - x_low + 1;
int y_dif = y_high - y_low + 1;
//若长和宽之和大于22，则需要分治成四份小的棋盘进行计算
if(y_dif + x_dif <= 22)
{
marry(x_low,x_high,y_low,y_high);
return;
}
int x_mid, y_mid;
if(x_dif % 4 == 0)
x_mid = x_low + x_dif/2;
else
x_mid = x_low + x_dif/2 + 1;
if(y_dif % 4 == 0)
y_mid = y_low + y_dif/2;
else
y_mid = y_low + y_dif/2 + 1;
dp(x_low, x_mid - 1, y_low, y_mid - 1);
dp(x_low, x_mid - 1, y_mid, y_high);
dp(x_mid, x_high, y_low, y_mid - 1);
dp(x_mid, x_high, y_mid, y_high);
//将四块棋盘调整方向，让他们可以和上面的图一样可以结合到一起
if(ceshi[x_mid - 2][y_mid - 1] != 6)
change_area(x_low, x_mid - 1, y_low, y_mid - 1);
if(ceshi[x_mid - 1][y_mid] != 1)
change_area(x_low, x_mid - 1, y_mid, y_high);
if(ceshi[x_mid + 1][y_mid] != 2)
change_area(x_mid, x_high, y_mid, y_high);
if(ceshi[x_mid][y_mid - 1] != 5)
change_area(x_mid, x_high, y_low, y_mid - 1);
//四块棋盘互相连接
ceshi[x_mid - 2][y_mid - 1] = 2;
ceshi[x_mid - 1][y_mid] = 3;
ceshi[x_mid + 1][y_mid] = 6;
ceshi[x_mid][y_mid - 1] = 7;
}
//由存储方向的棋盘数组，逐步转换为遍历顺序的answer数组
void zhuanhuan(int a, int b,int step)
{
while(answer[a][b] == 0)
{
step++;
answer[a][b] = step;
if(ceshi[a][b] == 1)
{
a -= 2;
b += 1;
}
else if(ceshi[a][b] == 2)
{
a -= 1;
b += 2;
}
else if(ceshi[a][b] == 3)
{
a += 1;
b += 2;
}
else if(ceshi[a][b] == 4)
{
a += 2;
b += 1;
}
else if(ceshi[a][b] == 5)
{
a += 2;
b -= 1;
}
else if(ceshi[a][b] == 6)
{
a += 1;
b -= 2;
}
else if(ceshi[a][b] == 7)
{
a -= 1;
b -= 2;
}
else if(ceshi[a][b] == 8)
{
a -= 2;
b -= 1;
}
}
}
int main()
{
//取消关联加速输出
std::ios::sync_with_stdio(false);
//初始化数组
for(int tmp = 0; tmp < 1000; tmp++)
{
memset(answer[tmp],0,sizeof(answer[tmp]));
memset(ceshi[tmp],0,sizeof(ceshi[tmp]));
}
int length, x_len, y_len;
cin >> length >> x_len >> y_len;
length--;
dp(0,length, 0,length);
zhuanhuan(x_len - 1, y_len - 1,0);
for(int tmpa = 0; tmpa <= length; tmpa++)
{
for(int tmpb = 0; tmpb <= length; tmpb++)
cout << answer[tmpa][tmpb] << " ";
cout <<endl;
}
}
小声讲一句， 我自己都看不懂自己的代码