八（ 8 ）皇后问题-->回溯法-->源码
/*
* 皇后是国际象棋中威力最大的棋子。八皇后问题即在一个8*8的棋盘中
* 摆放 8 个皇后，使其不能互相攻击，即即任意两个皇后都不能处于同
* 一行、同一列或同一斜线上，问有多少种摆法。
* --------------------------------------------------------------
* 提示：现在可以采用一种叫做回溯法( backtracking ) 的技巧，就很
* 容易编写出这个程序。编写一个函数，把一个皇后放在某行的第 1 列
* 然后检查它是否与棋盘上的其它皇后互相攻击。如果存在互相攻击，函
* 数把皇后移到该行的第 2 列再进行检查。如果每列都存在互相攻击的
* 局面，函数就应该返回。但是，如果皇后可以放在这个位置，函数接着
* 应该递归调用自身，把一个皇后放在下一行。当递归调用返回时，函数
* 再把原先那个皇后移到下一列。当一个皇后成功地放置于最后一行时，
* 函数应该打印出棋盘，显示 8 个皇后的位置。
* --------------------------------------------------------------
* 2010-12-04
*/
|
/*
* There are 92 valid sulotions. The key to making the problem simple
* is to separate the functionality into separate functions. The search
* for confilcts is limited to only those rows with queens in them, as
* described in the comments. Doing this eliminates roughly 3/8 of th work.
*/
/*
* Solve the Eight Queens Problem
*/
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
/*
* The chessboard. If an element is TRUE, there is a queen on the square;
* If FALSE, no queen.
*/
int board[8][8];
/*
* Print board
* print out a valid solution.
*/
void print_board(void)
{
int row;
int column;
static int n_solutions;
n_solutions += 1;
printf( "Solutions #%d:\n", n_solutions );
/* Go through every elements of the instructos board[8][8] */
for( row=0; row<8; row+=1 )
{
for( column=0; column<8; column+=1 )
{
if( board[ row ][ column ] )
printf( "Q" );
else
printf(" + ");
}
putchar( '\n' ); //一行完
}
putchar( '\n' );
}
/*
* Conflicts
* Check the board for conflicts with the queen that was just placed.
* Node: because the queens are placed in the rows in order, there is
* need to look at rows below the current one as there are no queens there.
*/
int conflicts( int row, int column )
{
int i;
for( i=1; i<8; i+=1 ) // 注意理解
{
/*
* Check up, left, and right. ( Do not have to check down; no queens in
* those rows yet !)
*/
if( row-i >= 0 && board[ row-i ][ column ] )
return TRUE;
if( column-i >= 0 && board[ row ][ column-i ] )
return TRUE;
if( column+i < 8 && board[ row ][ column+i ] )
return TRUE;
/*
* Check the diagnoals: up and left, up and right. ( Do not have to check down;
* no queens in those rows yet !)
*/
if( row-i >=0 && column-i >=0 && board[ row-i ][column-i] )
return TRUE;
if( row-i >= 0 && column+i < 8 && board[ row-i ][ column+i ] )
return TRUE;
}
/* If we get this far, there were no conflicts */
return FALSE;
}
/*
* place_queen
* Try to place a queen in each column of the given row.
*/
void place_queen( int row )
{
int column;
/*
* Try each column, one by one.
*/
for( column = 0; column < 8; column ++ )
{
board[ row ][ column ] = TRUE;
/*
* See if this queen can attack any of the queens.
* Do not need to check this for the first queen.
*/
if( row==0 || !conflicts( row, column ) )
{
/*
* No conflicts -- if we are not yet done, place the next
* queen recursively. If done, print the solution !
*/
if( row < 7 )
place_queen( row + 1 );
else
print_board();
}
/*
* Remove the queen from this position
*/
board[ row ][ column ] = FALSE;
}
}
/*--------------------------------------------------------------
* 函数： 主函数
* 入口参数：无
* 出口参数：int
* 描述： 无 *
*-------------------------------------------------------------*/
int main( void )
{
place_queen( 0 );
return EXIT_SUCCESS;
}
/*--------------------End - of - file---------------------------*/
|
以下为程序运行后的部分截图->
阅读(1619) | 评论(1) | 转发(0) |
