随笔-20  评论-12  文章-0  trackbacks-0
5皇后问题:在8*8的国际象棋棋盘上,放5个皇后,使它们控制整个棋盘,即在任何一格放一个棋子,都会马上被吃掉。
下面介绍回溯解法
定义一个表示点的数据结构:
1 struct Pt {Int x,y;};
算法:
 1 Void show_five_queen(Pt arr[],Int x = 0,Int y = 0,Int k = 0)
 2 {
 3     if(k==5)
 4     {
 5         check(arr);
 6         return;
 7     }
 8     for(Int i=x; i<8; i++)
 9     {
10         for(Int j=y; j<8; j++)
11         {
12             arr[k].x = i;
13             arr[k].y = j;
14             show_five_queen(arr,i+((j+1)/8),(j+1)%8,k+1);    // 避免重复回溯,要求只按索引顺序显示所有点
15         }
16     }
17 }
终止条件:
 1 Void check(Pt arr[])
 2 {
 3     for(Int i=0; i<8; i++)
 4     {
 5         for(Int j=0; j<8; j++)
 6         {
 7             Bool found = False;
 8             for(Int k=0; k<5; k++)
 9             {
10                 if(arr[k].x==|| arr[k].y==|| abs(arr[k].x-i)==abs(arr[k].y-j))
11                 {
12                     found = True;
13                     break;
14                 }
15             }
16             if(!found)
17                 return;
18         }
19     }
20 
21     showboard(arr);
22 }
效果图:




posted on 2009-02-10 11:25 宋振华 阅读(2039) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理