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;
}