LNH_Sniper 发表于 2011-7-12 09:52:53

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

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

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

本帖最后由 asd82937121 于 2011-7-12 09:54 编辑

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

LNH_Sniper 发表于 2011-7-12 12:00:47

asd82937121 发表于 2011-7-12 09:53 static/image/common/back.gif
不应该是八皇后吗？L哥的意思是不是 棋盘也变成4*4的了

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

asd82937121 发表于 2011-7-12 13:27:58

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

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

最近有点事，都没过来，今天继续、、/*
**        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;

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 )
                                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 )
                        return TRUE;
                if( column - i >= 0 && board )
                        return TRUE;
                if( column + i < 4 && board )
                        return TRUE;

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

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

int main()
{
        place_queen(0);

        return 0;
}

Be_envious 发表于 2011-7-13 23:27:14

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

紫色枫叶 发表于 2011-7-20 22:59:58

本帖最后由 紫色枫叶 于 2011-7-20 23:09 编辑

chao_prince 发表于 2011-7-12 13:28 static/image/common/back.gif
最近有点事，都没过来，今天继续、、
恩，这个算法是经典算法，记得以前学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 )
               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)         
            return TRUE;
      if(column - i >= 0 && board)
            return TRUE;
      if(column + i < n && board)
            return TRUE;
      if(row - i >= 0 && column - i >= 0
            && board)
                        return TRUE;
      if(row - i >= 0 && column + i < n
            && board)
            return TRUE;
    }
    return FALSE;
}

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

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


χīǎοゅ东 发表于 2012-11-1 18:39:13

学习学习一下

junpeng003 发表于 2013-9-9 12:17:11

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

sako_sc 发表于 2013-9-16 20:29:02

学习学习一下

猪猪BBUn咕咕 发表于 2013-11-17 08:53:44

好文章转过来方便自己看

jhlsp 发表于 2014-3-2 16:17:35

学习学习一下
页: [1]
查看完整版本: 算法每日一个（九）——___回溯法