eightqueen.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 86 行
HTM
86 行
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>八个皇后</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 八个皇后</a></h1>
<h2> 说明</h2>
西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上，1970年与1971年， E.W.Dijkstra与N.Wirth曾经用这个问题来讲解程式设计之技巧。<br>
<h2>解法</h2>
关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中，不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。 <br>
<div style="text-align: center;"><img style="width: 169px; height: 167px;" alt="八个皇后" title="八个皇后" src="images/eightQueen-1.jpg"><br>
<br>
<br>
所以检查时，先判断是否在已放置皇后的可行进方向上，如果没有再行放置下一个皇后，如此就可大大减少递回的次数，例如以下为修剪过后的递回检查行进路径：<br>
<img style="width: 517px; height: 229px;" alt="八个皇后" title="八个皇后" src="images/eightQueen-2.jpg"><br>
<div style="text-align: left;"><br>
八个皇后的话，会有92个解答，如果考虑棋盘的旋转，则旋转后扣去对称的，会有12组基本解。 </div>
</div>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#define N 8 <br><br>int column[N+1]; // 同栏是否有皇后，1表示有 <br>int rup[2*N+1]; // 右上至左下是否有皇后 <br>int lup[2*N+1]; // 左上至右下是否有皇后 <br>int queen[N+1] = {0}; <br>int num; // 解答编号 <br><br>void backtrack(int); // 递回求解 <br><br>int main(void) { <br> int i; <br> num = 0; <br><br> for(i = 1; i <= N; i++) <br> column[i] = 1; <br><br> for(i = 1; i <= 2*N; i++) <br> rup[i] = lup[i] = 1; <br><br> backtrack(1); <br><br> return 0; <br>} <br><br>void showAnswer() {<br> int x, y;<br> printf("\n解答 %d\n", ++num);<br> for(y = 1; y <= N; y++) {<br> for(x = 1; x <= N; x++) {<br> if(queen[y] == x) {<br> printf(" Q");<br> }<br> else {<br> printf(" .");<br> }<br> }<br> printf("\n");<br> }<br>}<br><br>void backtrack(int i) { <br> int j;<br><br> if(i > N) { <br> showAnswer();<br> } <br> else { <br> for(j = 1; j <= N; j++) { <br> if(column[j] == 1 && <br> rup[i+j] == 1 && lup[i-j+N] == 1) { <br> queen[i] = j; <br> // 设定为占用<br> column[j] = rup[i+j] = lup[i-j+N] = 0; <br> backtrack(i+1); <br> column[j] = rup[i+j] = lup[i-j+N] = 1; <br> } <br> } <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class Queen {<br> // 同栏是否有皇后，1表示有 <br> private int[] column;<br> // 右上至左下是否有皇后<br> private int[] rup; <br> // 左上至右下是否有皇后<br> private int[] lup;<br> // 解答<br> private int[] queen;<br> <br> // 解答编号<br> private int num;<br> <br> public Queen() {<br> column = new int[8+1];<br> rup = new int[2*8+1];<br> lup = new int[2*8+1];<br> <br> for(int i = 1; i <= 8; i++) <br> column[i] = 1; <br><br> for(int i = 1; i <= 2*8; i++) <br> rup[i] = lup[i] = 1; <br> <br> queen = new int[8+1];<br> }<br> <br> public void backtrack(int i) {<br> if(i > 8) { <br> showAnswer();<br> } <br> else { <br> for(int j = 1; j <= 8; j++) { <br> if(column[j] == 1 && <br> rup[i+j] == 1 && <br> lup[i-j+8] == 1) { <br> queen[i] = j; <br> // 设定为占用<br> column[j] = rup[i+j] = lup[i-j+8] = 0; <br> backtrack(i+1); <br> column[j] = rup[i+j] = lup[i-j+8] = 1; <br> } <br> } <br> } <br> }<br> <br> protected void showAnswer() {<br> num++;<br> System.out.println("\n解答 " + num);<br> for(int y = 1; y <= 8; y++) {<br> for(int x = 1; x <= 8; x++) {<br> if(queen[y] == x) {<br> System.out.print(" Q");<br> }<br> else {<br> System.out.print(" .");<br> }<br> }<br> System.out.println();<br> }<br> }<br> <br> public static void main(String[] args) {<br> Queen queen = new Queen();<br> queen.backtrack(1);<br> }<br>} </pre>
<br>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?