算法每日一个（九）——___回溯法

LNH_Sniper

问题：应用回溯法求解四皇后问题。

asd82937121

不应该是八皇后吗？  L哥的意思是不是 棋盘也变成4*4的了

LNH_Sniper

asd82937121 发表于 2011-7-12 09:53

                               
登录/注册后可看大图

不应该是八皇后吗？  L哥的意思是不是 棋盘也变成4*4的了

yes，说的对，本身皇后问题就是在N X N 的棋盘上进行的，对于此类问题的解决办法也不唯一，回溯法只是其中一种。可以考虑下

asd82937121

直到现在回溯法都不是太明白  自己看了好长时间写出来的还木有反应  真不知道该怎么搞这种算法， L哥能给指点指点么

chao_prince

最近有点事，都没过来，今天继续、、

/*
**        Slove the 4 queen problem
**        By chao_prince
**        7/12/11
*/

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

int board[4][4];

void print_board()
{
        int row;
        int column;
        static int n_soluctions;

        n_soluctions += 1;

        printf( "Soluctions #%d:\n", n_soluctions );

        for( row = 0; row < 4; row += 1 )
        {
                for( column = 0; column < 4; column += 1 )
                {
                        if( board[row][column] )
                                printf( " Q" );
                        else
                                printf( " +" );
                }
                putchar( '\n' );
        }
        putchar( '\n' );
}

int conflicts( int row, int column )
{
        int i;

        for( i = 1; i < 4; i++ )
        {
                if( row - i >= 0 && board[row-i][column] )
                        return TRUE;
                if( column - i >= 0 && board[row][column-i] )
                        return TRUE;
                if( column + i < 4 && board[row][column+i] )
                        return TRUE;

                if( row - i >= 0 && column - i >= 0 
                        && board[row-i][column-i] )
                        return TRUE;
                if( row - i >= 0 && column + i < 4 
                        && board[row-i][column+i] )
                        return TRUE;
        }
        return FALSE;
}

void place_queen(int row)
{
        int column;
        
        for( column = 0; column < 4; column += 1 )
        {
                board[row][column] = TRUE;
                if( row == 0 || !conflicts(row, column) )
                {
                        if( row < 3 )
                                place_queen(row+1);
                        else
                                print_board();
                }
                board[row][column] = FALSE;
        }
}

int main()
{
        place_queen(0);

        return 0;
}

Be_envious

等 这几天忙完了  回来好好看一遍

紫色枫叶

chao_prince 发表于 2011-7-12 13:28

                               
登录/注册后可看大图

最近有点事，都没过来，今天继续、、

恩，这个算法是经典算法，记得以前学java的时候看过。差不多都还给老师了。经你这么一写，醍醐灌顶。我在你的代码基础上稍微做了些修改。

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

int **board;

void print_board(int n)
{        
    int row;
    int column;
    static int n_soluctions;
    n_soluctions += 1;
    printf( "Soluctions #%d:\n", n_soluctions );
    for( row = 0; row < n; row += 1 )
    { 
         for( column = 0; column < n; column += 1 )
        {
            if( board[row][column] )
               printf( " Q" );
            else
                printf( " +" );
        }
                putchar( '\n' );
    }
    putchar( '\n' );
}

int conflicts(int row, int column, int n)
{

    int i;
    for( i = 1; i < n; i++ )
    {
        if(row - i >= 0 && board[row-i][column])           
            return TRUE;
        if(column - i >= 0 && board[row][column-i])
            return TRUE;
        if(column + i < n && board[row][column+i])
            return TRUE;
        if(row - i >= 0 && column - i >= 0 
            && board[row-i][column-i])
                        return TRUE;
        if(row - i >= 0 && column + i < n 
            && board[row-i][column+i])
            return TRUE;
    }
    return FALSE;
}

void place_queen(int row, int n)
{
    int column;
    for(column = 0; column < n; column += 1)
    {        
        board[row][column] = TRUE;
        if(row == 0 || !conflicts(row, column, n))
        {                                                    
            if(row < n - 1)
                place_queen(row+1, n);
            else
               print_board(n);
        }
        board[row][column] = FALSE;
    }
}

int main(int argc, char **argv)
{
        printf("请输入皇后数(偶数):");
        int n = 0;
        scanf("%d", &n);
        board = new int*[n];
        for(int i = 0; i < n; i++)
        {
                board[i] = new int[n];
        }
        
        for(int i = 0; i < n; i++)
        {
                for(int j = 0; j < n; j++)
                        board[i][j] = FALSE;
        }
        place_queen(0, n);
        for(int i = 0; i < n; i++)
        {
               delete [] board[i];
               board[i] = NULL;
        }
        delete []board;
        board = NULL;
        system("pause");
        return 0;
}

χīǎοゅ东

学习学习一下

junpeng003

一起加油，为了鱼C美好的明天！

sako_sc

学习学习一下

猪猪BBUn咕咕

好文章转过来方便自己看

jhlsp

学习学习一下