关于8皇后解决方法的浅析
众所周知,解决8皇后最普遍的方法是回溯法
那具体是怎么样的呢?
大概思路:
- 定义一个int型数组queen,角标(1.2…7)代表皇后所在的行,值代表皇后所在的列
- 定义一个函数来进行以下步骤
- 弄一个循环,从第0列到第7列,给queen[i]赋值,也就是给第i行的皇后确定其所在的列,而且要每一列都要试一遍
- 制作一个函数,可以检查queen[i]得到的列是否符合“八皇后”的要求(即每一个皇后的同一行、同一列、对角线上不能再有另一个皇后) (怎么做这个函数后面详细说)
- 检查完之后,如果符合,那就开始调用自身这个函数,开始给下一行的皇后赋值;如果不符合,那就进入i++,给这一行的皇后换一列(重点!!!)(回溯法)
- 当i等于8的时候,也就是所有行的皇后都有自己的列的时候,就另外做一个函数,打印出来即可
- 检查函数:传入的参数是需要检查的皇后所在的行i,传入行之后,需要从第0行检查到第i-1行,如果列数相同(即同一列)或者列数之差等于行数之差(即在对角线上),就返回0,不然就返回1
- 展示函数:要打印8行8列,自然可以两个for循环嵌套,再来一个if判断,如果打印第i行打印到第j列,queen[i]=j(即这一行的皇后的列数刚好是在打印的列数)打印Q,不然就打印-(这个可以随意选择)
void eight_queen(int row){
if(row<N){
for(int i=0;i<N;i++){
queens[row]=i;
if(check(row))
eight_queen((row+1));
}
}
else {
sum++;
show();
}
}
int check(int row){
for(int i=0;i<row;i++){
if(queens[row]==queens[i]||abs(queens[row]-queens[i])==(row-i))
return 0;
}
return 1;
}
void show(void){
printf("\n\nthis is solution no.%d\n\n",sum);
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++){
if(queens[i]==j)
printf("Q");
else printvoid show(void){
printf("\n\nthis is solution no.%d\n\n",sum);
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++){
if(queens[i]==j)
printf("Q");
else printf("-");
}
printf("\n");
}
}
int main(){
int row=0;
eight_queen(row);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)