猫史档案馆

请注意，是教学类，不过这里只发c++代码在国际象棋棋盘上放置八个皇后（8x8），要求每两个皇后之间不能直接吃掉对方。 按给定顺序和格式输出所有八皇后问题的解（见样例）。 No.1 10000000 00000010 00001000 00000001 01000000 00010000 00000100 00100000 No.2 10000000 00000010 00010000 00000100 00000001 01000000 00001000 00100000 ...以下省略题解（带注释）： #include<bits/stdc++.h>//万能头文件 usingnamespacestd; inta[10000],b[10000];//a用于记录皇后的位置（下标为列数，值为行数），b用于标记 intans[65],cnt=1,num,x11[10000],y11[10000];//ans用于储存棋盘，1表示皇后，0表示空白，cnt用于存储解法数量 boolattack(intx[10000],inty[10000])//attack函数用于判断是否会被吃掉，true表示不会，false表示会 { for(inti=1;i<=7;i++) { for(intj=i+1;j<=8;j++) { if(x[i]==x[j]||y[i]==y[j]||abs(x[i]-x[j])==abs(y[i]-y[j]))returnfalse;//abs是绝对值函数，用于判断斜线 } } returntrue;//所有被吃判断未通过，不会被吃，所以此方案成立 } voiddfs(intstep)//全排列回溯解决 { if(step==9)//如果下标（step）撞到了“南墙”（出界） { for(inti=0;i<=7;i++)//i表示行数 { stringn="00000000";//一行空白棋盘 n[a[i+1]-1]='1';//将对应列变为“皇后”、 for(intj=0;j<=7;j++)ans[i*8+j+1]=n[j]-'0';//j表示列数（因为ans是1维列表，所以i要乘8，加1是因为从0开始），-'0'是用于变成数字类型 } for(inti=1;i<=8;i++)y11[i]=a[i],x11[i]=i; if(attack(x11,y11))//判断是否被吃 { cout<<"No."<<cnt<<endl;//输出前缀 //用与23~27同理的方法输出棋盘 for(inti=0;i<=7;i++) { for(intj=0;j<=7;j++)cout<<ans[j*8+i+1]<<''; cout<<endl; } cnt++;//累加 } return;//跳出函数（已是一种方法，后面的例子出现会重复，例：87654321，1如果改成其他数字就会重复，导致行数与其他皇后重叠，会出现多余的执行次数） } for(inti=1;i<=8;i++)//遍历每一行 { if(b[i]==0)//如果没有被标记 { a[step]=i;//皇后行数 b[i]=1;//标记（已有） dfs(step+1);//回溯 b[i]=0;//取消标记（准备下一种） } } } intmain() { dfs(1);//调用 return0;//好习惯 }