8皇后有关问题的两种算法(c语言描述)
8皇后问题的两种算法(c语言描述)
/******************************************************************************************/ * description:由吴文虎老师对8皇后问题的描述,我参照其大意,写了这篇文章。具体对程序思路解释:判断 * 列是否安全,使用c[j];对于对角线使用l[k] k = i - j +5;j列放皇后,则i行记录q[i] = j; * l[i - j + 5 ] = false; r[i+j] = false;(表示一条直线,从左上到右下的直线。) * * /******************************************************************************************/ #include<math.h> #include<stdio.h> #include<stdlib.h> #define MIDDLE 8 #define MAX 17 int q[MAX]; bool c[MAX]; bool r[MAX]; bool l[MAX]; void show_result() { int i = 0; for(i = 1; i<= MIDDLE; i++) { printf("%d ",q[i]); } printf("\n"); } void put_chess(int n) { int i; int j; i = n; for(j = 1;j <=MIDDLE; j++) { if( ( c[j] == true )&&( l[i-j+9] == true )&&( r[i+j] == true) ) { q[i] = j; c[j] = false; l[i-j+9] = false; r[i+j] = false; if(i < MIDDLE) put_chess(i+1); if( i == MIDDLE ) show_result(); c[j] = true; r[i+j] = true; l[i-j+9] = true; } } } int main() { int i; for(i = 0; i< MAX ;i++) { c[i] = true; q[i] = 0; } for(i = 0; i< MAX; i++) { l[i] = true; r[i] = true; } put_chess(1); system("PAUSE"); return 0; } /******************************************************************************************/ * description:这是8皇后问题的另一种解法,其实,其精髓是就是以射线解决判断对角线是否已经被占用的问* 题 * /******************************************************************************************/ #include "stdafx.h" #include<math.h> #include<stdio.h> #include<stdlib.h> #define MAX 8 int board[MAX]; void show_result() { int i; for(i = 0; i < MAX; i++ ) printf("(%d,%d)",i,board[i]); printf("\n"); } int check_cross(int n) { int i; for( i = 0;i < n;i++) { if( board[i] == board[n] || (n-i) == abs(board[i] - board[n] )) return 1; } return 0; } void put_chess(int n) { int i; for(i = 0; i<MAX;i++) { board[n] = i; if( !check_cross(n) ) { if( n == MAX - 1) show_result(); else put_chess(n+1); } } } int main() { printf("The possible placements are:\n"); put_chess(0); system("PAUSE"); return 0; }