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

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

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

1. /*
   
2. **        Slove the 4 queen problem
   
3. **        By chao_prince
   
4. **        7/12/11
   
5. */
   
6. 
   
7. #include <stdio.h>
   
8. #include <stdlib.h>
   
9. 
   
10. #define TRUE 1
    
11. #define FALSE 0
    
12. 
    
13. int board[4][4];
    
14. 
    
15. void print_board()
    
16. {
    
17.         int row;
    
18.         int column;
    
19.         static int n_soluctions;
    
20. 
    
21.         n_soluctions += 1;
    
22. 
    
23.         printf( "Soluctions #%d:\n", n_soluctions );
    
24. 
    
25.         for( row = 0; row < 4; row += 1 )
    
26.         {
    
27.                 for( column = 0; column < 4; column += 1 )
    
28.                 {
    
29.                         if( board[row][column] )
    
30.                                 printf( " Q" );
    
31.                         else
    
32.                                 printf( " +" );
    
33.                 }
    
34.                 putchar( '\n' );
    
35.         }
    
36.         putchar( '\n' );
    
37. }
    
38. 
    
39. int conflicts( int row, int column )
    
40. {
    
41.         int i;
    
42. 
    
43.         for( i = 1; i < 4; i++ )
    
44.         {
    
45.                 if( row - i >= 0 && board[row-i][column] )
    
46.                         return TRUE;
    
47.                 if( column - i >= 0 && board[row][column-i] )
    
48.                         return TRUE;
    
49.                 if( column + i < 4 && board[row][column+i] )
    
50.                         return TRUE;
    
51. 
    
52.                 if( row - i >= 0 && column - i >= 0
    
53.                         && board[row-i][column-i] )
    
54.                         return TRUE;
    
55.                 if( row - i >= 0 && column + i < 4
    
56.                         && board[row-i][column+i] )
    
57.                         return TRUE;
    
58.         }
    
59.         return FALSE;
    
60. }
    
61. 
    
62. void place_queen(int row)
    
63. {
    
64.         int column;
    
65.        
    
66.         for( column = 0; column < 4; column += 1 )
    
67.         {
    
68.                 board[row][column] = TRUE;
    
69.                 if( row == 0 || !conflicts(row, column) )
    
70.                 {
    
71.                         if( row < 3 )
    
72.                                 place_queen(row+1);
    
73.                         else
    
74.                                 print_board();
    
75.                 }
    
76.                 board[row][column] = FALSE;
    
77.         }
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.         place_queen(0);
    
83. 
    
84.         return 0;
    
85. }

复制代码

Be_envious

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

紫色枫叶

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

                               
登录/注册后可看大图

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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define TRUE 1
   
5. #define FALSE 0
   
6. 
   
7. int **board;
   
8. 
   
9. void print_board(int n)
   
10. {        
    
11.     int row;
    
12.     int column;
    
13.     static int n_soluctions;
    
14.     n_soluctions += 1;
    
15.     printf( "Soluctions #%d:\n", n_soluctions );
    
16.     for( row = 0; row < n; row += 1 )
    
17.     {
    
18.          for( column = 0; column < n; column += 1 )
    
19.         {
    
20.             if( board[row][column] )
    
21.                printf( " Q" );
    
22.             else
    
23.                 printf( " +" );
    
24.         }
    
25.                 putchar( '\n' );
    
26.     }
    
27.     putchar( '\n' );
    
28. }
    
29. 
    
30. int conflicts(int row, int column, int n)
    
31. {
    
32. 
    
33.     int i;
    
34.     for( i = 1; i < n; i++ )
    
35.     {
    
36.         if(row - i >= 0 && board[row-i][column])           
    
37.             return TRUE;
    
38.         if(column - i >= 0 && board[row][column-i])
    
39.             return TRUE;
    
40.         if(column + i < n && board[row][column+i])
    
41.             return TRUE;
    
42.         if(row - i >= 0 && column - i >= 0
    
43.             && board[row-i][column-i])
    
44.                         return TRUE;
    
45.         if(row - i >= 0 && column + i < n
    
46.             && board[row-i][column+i])
    
47.             return TRUE;
    
48.     }
    
49.     return FALSE;
    
50. }
    
51. 
    
52. void place_queen(int row, int n)
    
53. {
    
54.     int column;
    
55.     for(column = 0; column < n; column += 1)
    
56.     {        
    
57.         board[row][column] = TRUE;
    
58.         if(row == 0 || !conflicts(row, column, n))
    
59.         {                                                   
    
60.             if(row < n - 1)
    
61.                 place_queen(row+1, n);
    
62.             else
    
63.                print_board(n);
    
64.         }
    
65.         board[row][column] = FALSE;
    
66.     }
    
67. }
    
68. 
    
69. int main(int argc, char **argv)
    
70. {
    
71.         printf("请输入皇后数(偶数):");
    
72.         int n = 0;
    
73.         scanf("%d", &n);
    
74.         board = new int*[n];
    
75.         for(int i = 0; i < n; i++)
    
76.         {
    
77.                 board[i] = new int[n];
    
78.         }
    
79.         
    
80.         for(int i = 0; i < n; i++)
    
81.         {
    
82.                 for(int j = 0; j < n; j++)
    
83.                         board[i][j] = FALSE;
    
84.         }
    
85.         place_queen(0, n);
    
86.         for(int i = 0; i < n; i++)
    
87.         {
    
88.                delete [] board[i];
    
89.                board[i] = NULL;
    
90.         }
    
91.         delete []board;
    
92.         board = NULL;
    
93.         system("pause");
    
94.         return 0;
    
95. }

复制代码

χīǎοゅ东

学习学习一下

junpeng003

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

sako_sc

学习学习一下

猪猪BBUn咕咕

好文章转过来方便自己看

jhlsp

学习学习一下