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 17int 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 8int 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;} ?