📄 subject_19916.htm
字号:
<p>
序号：19916 发表者：moonbird 发表日期：2002-11-01 11:36:12
<br>主题：求教8皇后问题？
<br>内容：1。1，2，3，4，5，6的全排列怎样写？<BR>2。在8*8的棋盘上放8个皇后，问怎样放8个互相吃不到？<BR><BR><BR>能解释的详细一下吗？我初学者，谢谢！
<br><a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p>
<hr size=1>
<blockquote><p>
回复者：scudetto 回复日期：2002-11-01 11:40:52
<br>内容：去看看数据结构的书，一般有提到
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：moonbird 回复日期：2002-11-01 11:46:12
<br>内容：谢谢。<BR>比如说。。。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
<font color=red>答案被接受</font><br>回复者：雷神 回复日期：2002-11-01 13:41:27
<br>内容：把简单的演示代码贴过来大家看看：<BR><BR>/*<BR>* ８皇后问题：<BR>*<BR>* 问题描述：<BR>* 在一个８×８的棋盘里放置８个皇后，要求每个皇后两两之间不相冲突<BR>*（在每一横列，竖列，斜列只有一个皇后）。<BR>* <BR>* 数据表示：<BR>* 用一个 8 位的 8 进制数表示棋盘上皇后的位置：<BR>* 比如：45615353 表示：<BR>* 第0列皇后在第4个位置<BR>* 第1列皇后在第5个位置<BR>* 第2列皇后在第6个位置<BR>* 。。。<BR>* 第7列皇后在第3个位置<BR>*<BR>* 循环变量从 00000000 加到 77777777 （8进制数）的过程，就遍历了皇后所有的情况<BR>* 程序中用八进制数用一个一维数组 data[] 表示<BR>*<BR>* 检测冲突：<BR>* 横列冲突：data[i] == data[j]<BR>* 斜列冲突：(data[i]+i) == (data[j]+j) 或者 (data[i]-i) == (data[j]-j)<BR>*<BR>* 好处：<BR>* 采用循环，而不是递规，系统资源占有少<BR>* 可计算 n 皇后问题<BR>* 把问题线性化处理，可以把问题分块，在分布式环境下用多台计算机一起算。<BR>*<BR>* ToDo：<BR>* 枚举部分还可以进行优化，多加些判断条件速度可以更快。<BR>* 输出部分可以修改成棋盘形式的输出<BR>* <BR>* @author cinc 2002-09-11<BR>*<BR>*/<BR><BR>public class Queen {<BR> int size;<BR> int resultCount;<BR> <BR> public void compute ( int size ) {<BR> this.size = size;<BR> resultCount = 0;<BR> int data[] = new int[size];<BR> int count; // 所有可能的情况个数<BR> int i,j;<BR> <BR> // 计算所有可能的情况的个数<BR> count = 1;<BR> for ( i=0 ; i<size ; i++ ) {<BR> count = count * size;<BR> }<BR> // 对每一个可能的情况<BR> for ( i=0 ; i<count ; i++ ) {<BR> // 计算这种情况下的棋盘上皇后的摆放位置，用 8 进制数表示<BR> // 此处可优化<BR> int temp = i;<BR> for ( j=0 ; j<size ; j++ ) {<BR> data [j] = temp % size;<BR> temp = temp / size;<BR> }<BR> // 测试这种情况是否可行，如果可以，输出<BR> if ( test(data) )<BR> output( data );<BR> }<BR> }<BR><BR> /*<BR> * 测试这种情况皇后的排列是否可行<BR> * <BR> */<BR> public boolean test( int[] data ) {<BR> int i,j;<BR> for ( i=0 ; i<size ; i++ ) {<BR> for ( j=i+1 ; j<size ; j++ ) {<BR> // 测试是否在同一排<BR> if ( data[i] == data[j] )<BR> return false;<BR> // 测试是否在一斜线<BR> if ( (data[i]+i) == (data[j]+j) )<BR> return false;<BR> // 测试是否在一反斜线<BR> if ( (data[i]-i) == (data[j]-j) )<BR> return false;<BR> }<BR> }<BR> return true;<BR> }<BR><BR> /*<BR> * 输出某种情况下皇后的坐标<BR> *<BR> */<BR> public void output ( int[] data ) {<BR> int i;<BR> System.out.print ( ++resultCount + ": " );<BR> for ( i=0 ; i<size ; i++ ) {<BR> System.out.print ( "(" + i + "," + data[i] + ") " );<BR> }<BR> System.out.println ();<BR> }<BR> public static void main(String args[]) {<BR> (new Queen()).compute( 8 );<BR> }<BR>}
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：scudetto 回复日期：2002-11-01 22:22:08
<br>内容：提供一个求解八皇后的算法(我也是copy的)<BR>{<BR>输入棋盘大小值n;<BR>m = 0;<BR>good = 1;<BR>do<BR>{<BR> if(good)<BR> {<BR> if(m==n)<BR> {<BR> 输出解；<BR> 改变之，形成下一个候选解;<BR> }<BR> else<BR> 扩展当前候选解至下一列;<BR> }<BR> else<BR> 改变之, 形成下一个候选解;<BR> good=检查当前候选解的合理性; <BR>}while(m != 0)<BR>}<BR><BR><BR>嚯，终于巧完了，但愿对你有帮助！！！
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：moonbird 回复日期：2002-11-02 17:12:46
<br>内容：谢谢大家。
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：jeppeter 回复日期：2002-11-18 19:09:31
<br>内容：我问一下，这是要求出一个解就可以了，还是要求出所有的解，这两个问题的方法，略有不同，但我所知的，这上面的方法没有对求解的问题进行一定程度的化简，本来可以不用这样的方法来求，可以对任意多的方格求出它的N皇后问题是否有解，且这些所有的解，这个当然不能用我种搜索的方法，而是与皇后的本身的位置关系，以后我会公布这个答案
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：赵耀 回复日期：2002-12-05 16:34:51
<br>内容：都是高手啊~~~~小弟要加油了~~
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
<hr size=1>
<blockquote><p>
回复者：kwest 回复日期：2002-12-07 14:58:25
<br>内容：回溯搜索法
<br>
<a href="javascript:history.go(-1)">返回上页</a><br><a href=http://www.copathway.com/cndevforum/>访问论坛</a></p></blockquote>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -