/*
重温八数码，优化算法
数据结构：一维数组。
num[i]表示第i+1行第num[i]列有元素，通过对num[i]初始化进行排列即可模拟所有格局。如：num[0]=3,表示第一行第3列有元素。
核心算法：判断是否在对角即可（横向、纵向已经在数据结构设计中避开，免去判断）
求下一排列
推广：在很多带回溯、递归的索搜，可试着用数组进行全排列并判断即可。
要点：熟悉掌握全排列算法。废话不多说，编译代码运行后逐步分析吧。
*/
#include<iostream>
using namespace std;
bool is_end(int *num,int len)
{
for(int i = 0;i<len;i++)
{
if(num[i]!=len-i-1)
return false;
}
return true;
}
bool check(int *num,int len)
{
for(int i =0;i<len-1;++i)
{
for(int j = i+1;j<len;++j)
{
if(i-j==num[i]-num[j]||j-i==num[i]-num[j])
return false;
}
}
return true;
}
void print(int *num,int len)
{
for(int i = 0;i<len;i++)
{
for(int j = 0;j<len;j++)
{
if(num[i] == j)
cout<<"☆ ";
else
cout<<"■ ";
}
cout<<endl;
}
}
void print_arrary(int *num,int len)
{
for(int i = 0;i<len;i++)
cout<<num[i];
cout<<endl;
}
int* Permutation(int *a, int n)//求n位排列a的下一个排列
{
int left = 0;
int right = 0;
int i = 1;
bool is_far = false;
left = n - 1;
while (left >= 0 && a[left-1] > a[left]) //找到 left = i = max{ i|pi-1<pi }
{
left--;
if(left == 0)
{
is_far = true;
break;
}
}
if(is_end(a,n)) //没有下一序列了．
return a;
right = n - 1;
while (a[right] < a[left-1]) //找到right = l = max{k|P(left)<Pk}
right--;
swap(a[right],a[left-1]);
right = n -1;
while (left < right)//逆置左右边界之间的元素，使其按增序排列
{
swap(a[right],a[left]);
left++;
right--;
}
return a;
}
int main()
{
const int len = 8; //数码的基数
int *num = new int[len];
int s = 1;
for(int i = 0;i<len;i++)
num[i] =i;
while(!is_end(num,len))
{
if(check(num,len))
{
printf("第%d个解为:\n",s);
print_arrary(num,len);
print(num,len);
cout<<endl;
s++;
}
num = Permutation(num,len);
}
delete num;
return 0;
}
