A. 八皇後C++演算法流程圖
國際象棋還是撲克？
B. 八皇後問題的演算法思想實現起來可不可以簡單些
#include <stdio.h>
#include <math.h>
#define N 8
void Check(int p[]){
int i,j;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
if(abs(p[j]-p[i])==j-i)
return;
for(i=0;i<N;i++)
printf("%d ",p[i]);
printf("\n");
}
void Permute(int n,int p[]){
int i,j;
if(n==1)
Check(p);
for(i=0,j=n-1;i<N;i++)
if(!p[i]){
p[i]=j; Permute(j,p); p[i]=0;
}
}
int main(){
static int p[N];
int n=N;
Permute(n+1,p);
return 0;
}
C. 八皇後問題遞歸演算法不理解，求解
layout[row] = i; //嘗試在此位置上放上八皇後
放上去之後才開始檢查是不是合符八皇後的規則，
if(isSafe(row, i)) // 結果為true 意思是在此位置上放八皇後是符合規則的
lay(row+1) //那麼OK，我們可以繼續放下一層
八皇後是典型的循環裡面加遞歸， 和全排列很類似。在之後你可以看看DFS，深搜就是用這個原理
D. 八皇後問題求解的實現演算法
#include <stdio.h>
#include <math.h>
#define N 8
void Check(int p[]){
int i,j;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
if(abs(p[j]-p[i])==j-i)
return;
for(i=0;i<N;i++)
printf("%d ",p[i]);
printf("\n");
}
void Permute(int n,int p[]){
int i,j;
if(n==1)
Check(p);
for(i=0,j=n-1;i<N;i++)
if(!p[i]){
p[i]=j; Permute(j,p); p[i]=0;
}
}
int main(){
static int p[N];
int n=N;
Permute(n+1,p);
return 0;
}
E. 用遞歸函數設計八皇後問題的回溯演算法C++代碼
解析：遞歸實現n皇後問題。
演算法分析：
數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列。如果某列上已經有皇後，則為1，否則為0。
數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]。如果某條主對角線上已經有皇後，則為1，否則為0。
數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]。如果某條從對角線上已經有皇後，則為1，否則為0。
代碼如下：
#include <stdio.h>
static char Queen[8][8];
static int a[8];
static int b[15];
static int c[15];
static int iQueenNum=0; //記錄總的棋盤狀態數
void qu(int i); //參數i代錶行
int main()
{
int iLine,iColumn;
//棋盤初始化，空格為*，放置皇後的地方為@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0; //列標記初始化，表示無列沖突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、從對角線標記初始化，表示沒有沖突
for(iLine=0;iLine<15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return 0;
}
void qu(int i)
{
int iColumn;
for(iColumn=0;iColumn<8;iColumn++)
{
if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)
//如果無沖突
{
Queen[i][iColumn]='@'; //放皇後
a[iColumn]=1; //標記，下一次該列上不能放皇後
b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇後
c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇後
if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行
else //否則輸出
{
//輸出棋盤狀態
int iLine,iColumn;
printf("第%d種狀態為：\n",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c ",Queen[iLine][iColumn]);
printf("\n");
}
printf("\n\n");
}
//如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置
Queen[i][iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}
F. JAVA中八皇後問題演算法和流程圖。要求用回溯法，求大神解答，在線等如果有代碼就完美了
[cpp] view plainprint?
//--------------------------------------
//利用函數遞歸，解決八皇後問題
//
// zssure 2014-03-12
//--------------------------------------
#include <stdio.h>
#include <cmath>
int count=0;//全局計數變數
/*--------------------四個皇後----------------------*/
//#define QUEEN_NUM 4
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0,
// 0,0,0,0 };
/*--------------------五個皇後----------------------*/
//#define QUEEN_NUM 5
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0,
// 0,0,0,0,0 };
/*--------------------六個皇後----------------------*/
//#define QUEEN_NUM 6
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0,
// 0,0,0,0,0,0
// };
/*--------------------七個皇後----------------------*/
//#define QUEEN_NUM 7
//int label[QUEEN_NUM][QUEEN_NUM]={ 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0,
// 0,0,0,0,0,0,0
// };
/*--------------------八個皇後----------------------*/
#define QUEEN_NUM 8
int label[QUEEN_NUM][QUEEN_NUM]={0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0,
0,0,0,0};
void FillChessbox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n))//對角區域填充
{
if(label[i][j]==0)
label[i][j]=num;
}
int i=0,j=0;
while(i<QUEEN_NUM)//行填充
{
if(label[i][n]==0)
label[i][n]=num;
++i;
}
while(j<QUEEN_NUM)//列填充
{
if(label[m][j]==0)
label[m][j]=num;
++j;
}
}
void ClearChessBox(int m,int n,int num)
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
if(abs(i-m)==abs(j-n) && label[i][j]==num)
label[i][j]=0;
int i=0,j=0;
while(i<QUEEN_NUM)
{
if(label[i][n]==num)
label[i][n]=0;
++i;
}
while(j<QUEEN_NUM)
{
if(label[m][j]==num)
label[m][j]=0;
++j;
}
}
void AllClear()
{
for(int i=0;i<QUEEN_NUM;++i)
for(int j=0;j<QUEEN_NUM;++j)
label[i][j]=0;
}
void PrintResult()
{
for(int i=0;i<QUEEN_NUM;++i)
{
for(int j=0;j<QUEEN_NUM;++j)
printf("%d ",label[i][j]);
printf("\n");
}
}
bool EightQueen(int n/*皇後個數*/,int c/*已經放置的皇後個數*/)
{
//static int count=0;
//小於3x3的棋盤是無解的
if(n<4)
return false;
for(int i=0;i<n;++i)
{
if(label[c-1][i]==0)//存在可以放置第c個皇後的位置
{
label[c-1][i]=c+1;
if(c==n)/*已經放置完畢所有的皇後*/
{
++count;
PrintResult();
printf("**************************\n");
ClearChessBox(c-1,i,c+1);
//AllClear();
return true;
}
FillChessbox(c-1,i,c+1);
EightQueen(n,c+1);
ClearChessBox(c-1,i,c+1);
/*-------------------------------------------------------------------------------------------------------------------------
// 現場恢復，無論下一個皇後是否順利放置，都應該恢復現場。原因是
//
// 如果下一個皇後放置失敗，那麼自然應該將本次放置的皇後去除，重新放置，所以需要進行現場恢復（即回溯）；
// 如果下一個皇後放置成功，意味著本次放置已經滿足條件，是一個解，此時需要恢復現場，進行下一次的重新放置，尋找下一個解。
//
//------------------------------------------------------------------------------------------------------------------------*/
//if(!EightQueen(n,c+1))
// ClearChessBox(c-1,i,c+1);
}
}
return false;
}
int main()
{
EightQueen(QUEEN_NUM,1);
printf("%d\n",count);
return 0;
}
G. 尋求八皇後的迭代演算法解釋。
也不知是不是你想要的解釋，採用回溯法：（以前寫的，直接粘貼……）
用一個函數來判斷某個位置是否安全，安全的位置說明它所在的行、列和對角線上都沒有放置皇後，因此不會出現皇後互相攻擊的情況；否則該位置不安全。其具體實現的過程是找出所有放置過的皇後，將它們的位置與該位置進行比較判斷。又注意到同一行最多隻能放置一個皇後，因此，只需要對前面的各行逐行掃描皇後，就可以找出所有皇後的位置。
為便於顯示，假設棋盤的狀態為「-」時表示未放皇後狀態，為「Q」時表示放置了皇後的狀態。
//
判斷位置(
row,
col
)是否是安全位置
bool
safeJudge(
int
row,
int
col
)
const
{
int
qRow,
qCol;
//
檢查前面各行，看與前面放置的皇後是否發生攻擊
for(
qRow
=
0;
qRow
<
row;
qRow++
)
{
string
rowState
=
chessState[
qRow
];
//
尋找第qRow行放置皇後的列數
qCol
=
rowState.find(
"Q"
);
//
判斷是否安全
if(
qRow
==
row
||
qCol
==
col
||
(
qCol
-
qRow
)
==
(
col
-
row
)
||
(
qCol
+
qRow
)
==
(
col
+
row
)
)
return
false;
}
return
true;
}
試著先把第一個皇後放在棋盤上，然後再放第二個皇後，使兩個皇後不會互相攻擊，再放第三個皇後，使得它與前兩個皇後都不會互相攻擊，以此類推，直至所有的皇後都放上去。如果第七個皇後放上後，第八個皇後已經沒有安全位置可以放置，則試著調整第七個皇後的位置，再嘗試第八個皇後有沒有安全位置；如果第七個皇後的所有安全位置都已嘗試過了，第八個皇後還是沒有安全位置，則試著調整第六個皇後的位置。如此類推，最糟糕的情況是一直到將第一個皇後的位置進行調整。由此可見，採用回溯法，過程的實現形式非常簡單自然，然而這一過程的工作量非常大。
void
QueenChess::placeQueen(
int
row
)
{
//
窮盡第row行的所有列
for(
int
col
=
0;
col
<
8;
col++
)
{
if(
safeJudge(
row,
col
)
)
{
chessState[
row
][
col
]
=
"Q";
//
若還沒有放到第八行，則嘗試下一行
if(
row
<
7
)
placeQueen(
row
+
1
);
//
已經放置了八個皇後，列印出成功的棋盤，並將解數加1
else
{
solves++;
drawChess();
}
}
//
將該處的皇後取走，嘗試下一列位置
chessState[
row
]
=
"--------";
}
}
這個演算法能發現所有可能的解，不過它認為棋盤是具有行列編號的。事實上，棋盤並沒有行列編號，如位置（0,0）和（7,7）其實是對稱位置，因此這種演算法給出的某些解也是對稱的。為了便於理解，假設棋盤是具有行列編號的。
建立一個QueenChess類，見相應程序。
QueenChess::QueenChess()
{
solves
=
0;
for(
int
i
=
0;
i
<
8;
i++
)
chessState[
i
]
=
"--------";
}
void
QueenChess::drawChess()
{
int
i,
j;
cout
<<
"\n八皇後問題的第"
<<
solves
<<
"個解為："
<<
endl;
cout
<<
"
0
1
2
3
4
5
6
7"
<<
endl;
for(
i
=
0;
i
<
8;
i++
)
{
cout
<<
i
<<
"
";
for(
j
=
0;
j
<
8;
j++
)
cout
<<
chessState[
i
][
j
]
<<
"
";
cout
<<
endl;
}
system(
"pause"
);
}
void
QueenChess::solve()
{
//
從第0行開始放置皇後
placeQueen(
0
);
cout
<<
"\n八皇後問題總共的解的個數為："
<<
solves
<<
endl;
}
H. 八皇後演算法 free pascal
〖問題描述〗
在一個8×8的棋盤里放置8個皇後，要求每個皇後兩兩之間不相"沖"（在每一橫列豎列斜列只有一個皇後）。
〖問題分析〗(聿懷中學呂思博)
這道題可以用遞歸循環來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個問題：
1、沖突。包括行、列、兩條對角線：
（1）列：規定每一列放一個皇後，不會造成列上的沖突；
（2）行：當第I行被某個皇後佔領後，則同一行上的所有空格都不能再放皇後，要把以I為下標的標記置為被佔領狀態；
（3）對角線：對角線有兩個方向。在同一對角線上的所有點（設下標為(i,j)），要麼(i+j)是常數，要麼(i-j)是常數。因此，當第I個皇後佔領了第J列後，要同時把以(i+j)、(i-j)為下標的標記置為被佔領狀態。
2、數據結構。
（1）解數組A。A[I]表示第I個皇後放置的列；范圍：1..8
（2）行沖突標記數組B。B[I]=0表示第I行空閑；B[I]=1表示第I行被佔領；范圍：1..8
（3）對角線沖突標記數組C、D。
C[I-J]=0表示第（I-J）條對角線空閑；C[I-J]=1表示第（I-J）條對角線被佔領；范圍：-7..7
D[I+J]=0表示第（I+J）條對角線空閑；D[I+J]=1表示第（I+J）條對角線被佔領；范圍：2..16
〖演算法流程〗
1、數據初始化。
2、從n列開始擺放第n個皇後（因為這樣便可以符合每一豎列一個皇後的要求），先測試當前位置(n,m)是否等於0（未被佔領）:
如果是，擺放第n個皇後，並宣布佔領(記得要橫列豎列斜列一起來哦)，接著進行遞歸；
如果不是，測試下一個位置(n,m+1)，但是如果當n<=8,m=8時，卻發現此時已經無法擺放時，便要進行回溯。
3、當n>;8時，便一一列印出結果。
〖優點〗逐一測試標准答案，不會有漏網之魚。
〖參考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procereprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceretry(i:integer);
varj:integer;
begin
forj:=1to8do
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then
begin
a:=j;
b[j]:=1;
c[i+j]:=1;
d[i-j]:=1;
ifi<8thentry(i+1)
elseprint;
b[j]:=0;
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);
end.
==========================================
這是N皇後問題，看看吧：
在N*N的棋盤上，放置N個皇後，要求每一橫行每一列，每一對角線上均只能放置一個皇後，問可能的方案及方案數。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; //放皇後數組
b:array[2..2*max] of boolean; // 『/』對角線標志數組}
c:array[-(max-1)..max-1] of boolean;// 『\』對角線標志數組}
col:array[1..max] of boolean; //列標志數組}
total:integer; //統計總數}
procere output; //這里是輸出過程
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; //判斷第dep行第i列可放否？
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) and
(col[i]=true) then ok:=true
end;
procere try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do //每一行均有max種放法，對吧？xixi~~~~
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; // 『/』對角線已放標志
c[dep-i]:=false; // 『\』對角線已放標志
col[i]:=false; // 列已放標志
if dep=max then output
else try(dep+1); // 遞歸下一層
a[dep]:=0; //取走皇後,回溯
b[i+dep]:=true; //恢復標志數組
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
I. 八皇後究竟有多少種解法怎麼解
這樣算是最佳解 class Queen8{ static final int QueenMax = 8; static int oktimes = 0; static int chess[] = new int[QueenMax]; public static void main(String args[]){ for (int i=0;i<QueenMax;i++)chess[i]=-1; placequeen(0); System.out.println("\n\n\n八皇後共有"+oktimes+"個解法 made by yifi 2003"); } public static void placequeen(int num) { int i=0; boolean qsave[] = new boolean[QueenMax]; for(;i<QueenMax;i++) qsave[i]=true; i=0; while (i<num){ qsave[chess[i]]=false; int k=num-i; if ( (chess[i]+k >= 0) && (chess[i]+k < QueenMax) ) qsave[chess[i]+k]=false; if ( (chess[i]-k >= 0) && (chess[i]-k < QueenMax) ) qsave[chess[i]-k]=false; i++; } for(i=0;i<QueenMax;i++){ if (qsave[i]==false)continue; if (num<QueenMax-1){ chess[num]=i; placequeen(num+1); } else{ //num is last one chess[num]=i; oktimes++; System.out.println("這是第"+oktimes+"個解法 如下:"); System.out.println("第n行: 1 2 3 4 5 6 7 8"); for (i=0;i<QueenMax;i++){ String row="第"+(i+1)+"行: "; if (chess[i]==0); else for(int j=0;j<chess[i];j++) row+="--"; row+="++"; int j = chess[i]; while(j<QueenMax-1){row+="--";j++;} System.out.println(row); } } } } } 多少種解法就不好說了..
J. 求~~~pascal八皇後 非遞歸詳細演算法和程序
〖問題描述〗
在一個8×8的棋盤里放置8個皇後，要求每個皇後兩兩之間不相"沖"（在每一橫列豎列斜列只有一個皇後）。
〖問題分析〗(聿懷中學呂思博)
這道題可以用遞歸循環來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個問題：
1、沖突。包括行、列、兩條對角線：
（1）列：規定每一列放一個皇後，不會造成列上的沖突；
（2）行：當第I行被某個皇後佔領後，則同一行上的所有空格都不能再放皇後，要把以I為下標的標記置為被佔領狀態；
（3）對角線：對角線有兩個方向。在同一對角線上的所有點（設下標為(i,j)），要麼(i+j)是常數，要麼(i-j)是常數。因此，當第I個皇後佔領了第J列後，要同時把以(i+j)、(i-j)為下標的標記置為被佔領狀態。
2、數據結構。
（1）解數組A。A[I]表示第I個皇後放置的列；范圍：1..8
（2）行沖突標記數組B。B[I]=0表示第I行空閑；B[I]=1表示第I行被佔領；范圍：1..8
（3）對角線沖突標記數組C、D。
C[I-J]=0表示第（I-J）條對角線空閑；C[I-J]=1表示第（I-J）條對角線被佔領；范圍：-7..7
D[I+J]=0表示第（I+J）條對角線空閑；D[I+J]=1表示第（I+J）條對角線被佔領；范圍：2..16
〖演算法流程〗
1、數據初始化。
2、從n列開始擺放第n個皇後（因為這樣便可以符合每一豎列一個皇後的要求），先測試當前位置(n,m)是否等於0（未被佔領）:
如果是，擺放第n個皇後，並宣布佔領(記得要橫列豎列斜列一起來哦)，接著進行遞歸；
如果不是，測試下一個位置(n,m+1)，但是如果當n<=8,m=8時，卻發現此時已經無法擺放時，便要進行回溯。
3、當n>;8時，便一一列印出結果。
〖優點〗逐一測試標准答案，不會有漏網之魚。
〖參考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procereprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceretry(i:integer);
varj:integer;
begin
forj:=1to8do{每個皇後都有8種可能位置}
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then{判斷位置是否沖突}
begin
a:=j;{擺放皇後}
b[j]:=1;{宣布佔領第J行}
c[i+j]:=1;{佔領兩個對角線}
d[i-j]:=1;
ifi<8thentry(i+1){8個皇後沒有擺完，遞歸擺放下一皇後}
elseprint;{完成任務，列印結果}
b[j]:=0;{回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do{數據初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{從第1個皇後開始放置}
end.
==========================================
這是N皇後問題，看看吧：
在N*N的棋盤上，放置N個皇後，要求每一橫行每一列，每一對角線上均只能放置一個皇後，問可能的方案及方案數。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; //放皇後數組
b:array[2..2*max] of boolean; // 『/』對角線標志數組}
c:array[-(max-1)..max-1] of boolean;// 『\』對角線標志數組}
col:array[1..max] of boolean; //列標志數組}
total:integer; //統計總數}
procere output; //這里是輸出過程
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; //判斷第dep行第i列可放否？
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
(col[i]=true) then ok:=true
end;
procere try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do //每一行均有max種放法，對吧？xixi~~~~
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; // 『/』對角線已放標志
c[dep-i]:=false; // 『\』對角線已放標志
col[i]:=false; // 列已放標志
if dep=max then output
else try(dep+1); // 遞歸下一層
a[dep]:=0; //取走皇後,回溯
b[i+dep]:=true; //恢復標志數組
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.