恩 快該NOIP了。。。不過我還啥都不會呢..前幾天和Ceeji神牛聊天時才想起來這個…事情
然後就拜託他來幫忙了。。。不過TBH 我實在技術很菜。。（呃 看到這篇的神牛們莫嘲笑俺..）
先練下簡單的搜索…不過 我基本沒做過搜索的題 恩 於是就從最基礎的八皇后做起…
做了好久 另外 向ceeji神牛表示深深的感謝 呃 問了很多小白問題.. 恩 先不說這個了 題最重要.
首先八皇后問題 介紹 先看看維基百科是怎麼說的：
八皇后問題是一個以西洋棋為背景的問題：如何能夠在 8×8 的西洋棋棋盤上放置八個皇后，使得任何一個皇后都無法直接吃掉其他的皇后？為了達到此目的，任兩個皇后都不能處於同一條橫行、縱行或斜線上。
這道題裡面 最重要的部分是 判斷是否能夠放在這裡
8 Queens - Check
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| int check(int a,int b)/* 判断能否放置在此 */
{
int i,j;
for(i=0;i<QUEENS;i++)/* 判断纵行 */
if(i!=a)
if(q[i][b]==1)
return -1;
for(i=b-1;i>=0;i--)/* 判断横行 */
if(q[a][i])
return -1;
for(i=a-1,j=b-1;i>=0&&j>=0;i--,j--)/* 判断自坐标到左上 */
if(q[i][j])
return -1;
for(i=a+1,j=b-1;i<8&&j>=0;i++,j--)/* 判断自坐标到左下 */
if(q[i][j])
return -1;
return 0;
}
|
依次檢查縱行橫行斜行有無皇后 若有便返回-1 表示不能放置於此 如果可以放置 則返回0.輸入的為皇后坐標 a代表縱坐標 b代表橫坐標
接下來是 遞歸函數問題 這部分之前基本沒有寫過 全是考ceeji神牛才寫出來的
8 Queens - Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| void slove(int ky)
{
int i;
if(ky==QUEENS)/* 检测是否完成 */
{
output();
return;
}
for(i=0;i<QUEENS;i++)
if(!check(i,ky)0&&!q[i][ky]) /* 判断是否满足放棋子的条件 */
{
q[i][ky]=1;
slove(ky+1); /* 遞歸函數 ky用來記錄遞歸次數 */
q[i][ky]=0;
}
return;
}
|
首先是檢查 遞歸是否應該結束 如果不結束 繼續執行
因為 對於八皇后問題 因為橫行和豎行都不能 放置其他的棋子 所以 每一橫行和縱行都只可能有 1個棋子
所以 同時用ky代表縱行 搜索在這一縱行里那一個格子能夠放下棋子 這樣能夠少寫一層循環 優化速度.
check函數檢查是否能夠放下棋子 如果可以則繼續遞歸 不可以就回溯到上一步進行繼續搜索..
最後是一些其他的函數
8 Queens
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| /*
ID:fanzeyi
PROB:8-queens
LANG:C
*/
#include <stdio.h>
#include <stdlib.h>
#define QUEENS 8 //皇后人数
short q[QUEENS][QUEENS];
int number=0;/* 记录 结果次数 */
void init()/* 初始化数组 */
{
int i,j;
for(i=0;i<QUEENS;i++)
for(j=0;j<QUEENS;j++)
{
q[i][j]=0;
lin[i][j]=0;
}
}
void output()/* 输出安排 */
{
int i,j;
for(i=0;i<QUEENS;i++)
{
for(j=0;j<QUEENS;j++)
printf("%d",q[i][j]);
printf("\n");
}
number++;
}
int main()
{
init();
slove(0);
printf("total:%d\n",number);
return 0;
}
|
恩 這是其他的非算法部分函數 將8預定義可以 將其推廣成解決N皇后問題的程序（不過這個程序應該跑到11皇后就差不多了。。。再多估計速度超慢..其實還可以優化的 看wiki上寫的 12皇后問題有 14,200 個解 …不知道一共有多少個可能性了..= =）
好了 這個就到這裡 繼續做題.～