Chinaunix首页 | 论坛 | 博客
  • 博客访问: 388890
  • 博文数量: 55
  • 博客积分: 1907
  • 博客等级: 上尉
  • 技术积分: 869
  • 用 户 组: 普通用户
  • 注册时间: 2010-11-04 19:30
文章分类

全部博文(55)

文章存档

2011年(32)

2010年(23)

分类: C/C++

2010-12-04 11:51:53

八( 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---------------------------*/

以下为程序运行后的部分截图->


 

阅读(1650) | 评论(1) | 转发(0) |
0

上一篇:数组之8.5

下一篇:LINUX 一些命令的使用

给主人留下些什么吧!~~

chinaunix网友2010-12-07 09:52:43

很好的, 收藏了 推荐一个博客,提供很多免费软件编程电子书下载: http://free-ebooks.appspot.com