queen.c

n皇后问题的C语言实现,有图形界面的,非常之经典的程序,用的是回溯法

#include "Conio.h"
#include "graphics.h"
#include <stdio.h>
#include <math.h>
#define closegr closegraph

int count=0;  /*问题解的个数*/

void initgr(void) /* BGI初始化 */
{
  int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
  registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
  initgraph(&gd, &gm, "");
}

int place(int k,int *x)
 {  int i=1;
     while(i<k)
   {
     if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))
          return 0;
     i++;
   }

    return 1;
 }


void newwindow(int n,int *x,int count)
{  int i,j,a,b;
   a=500;
   b=50+(count-1)*(n+1)*10;
   setcolor(WHITE);
   for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
       rectangle(a+10*(i-1),b+10*(i-1),a+10+10*(j-1),b+10+10*(j-1));
    for(i=1;i<=n;i++)
     circle(a+5+10*(x[i]-1),b+5+10*(i-1),4);
}

void nqueens(int n,int *x)
 { int k,i;
   x[1]=0 ;
   k=1;
   while(k>0)
   {  x[k]=x[k]+1;
      while ((x[k]<=n)&&(!place(k,x)))
        x[k]=x[k]+1;
      if(x[k]<=n)
       { setcolor(WHITE);
         getch();
         circle(125+50*(x[k]-1),75+50*(k-1),20);
         if(k==n)
            { count++;
              getch();
              newwindow(n,x,count);
              getch();
              printf("\n");
              k--;
             for(i=1;i<=n;i++)
                 printf("%d ",x[i]);
             for(i=k;i<=n;i++)
                { setcolor(BLACK);
                  circle(125+50*(x[i]-1),75+50*(i-1),20);
                }

             }
         else
         {
           k=k+1;
           x[k]=0;
         }
        }
      else
      {  k--;
         setcolor(BLACK);
         getch();
         circle(125+50*(x[k]-1),75+50*(k-1),20);

      }
   }

}

 main(void)
{ int *x,i,j,n;
  printf("please input n:");
  scanf("%d",&n);
  x=(int *)malloc((n+1)*sizeof(int));
  initgr();  /* BGI初始化 */
   for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
    rectangle(100+50*(i-1),50+50*(i-1),150+50*(j-1),100+50*(j-1));
  nqueens(n,x);
  setcolor(RED);
  outtextxy(300,450,"END");
  getch();  /* 暂停一下，看看前面绘图代码的运行结果 */
  closegr();  /* 恢复TEXT屏幕模式 */

}