//________________链表版八皇后
  

  //修改 N  可以达到   N皇后   ！！！
  

  #include <iostream>
  

  #include <vector>
  

  #include <fstream>
  

  #include <time.h>
  

  using namespace std;
  

  #define  N 8
  

  bool haha(int **a,int i,int j)
  

  {
  

  

  int i_1 = i;
  

  int j_1 = j;
  

  for(int x =0;x<N;x++)
  

  {
  

  if(j_1+x <N)
  

  a[i_1][j_1+x]=0;
  

  if(j_1-x>=0)
  

  a[i_1][j_1-x]=0;
  

  if(i_1+x <N)
  

  a[i_1+x][j_1]=0;
  

  if(i_1-x>=0)
  

  a[i_1-x][j_1]=0;
  

  

  

  }
  

  

  

  for(int x =0;x<N;x++)
  

  {
  

  if(i_1+x<N&&j_1+x<N)
  

  a[i_1+x][j_1+x]=0;
  

  if(i_1+x<N&&j_1-x>=0)
  

  a[i_1+x][j_1-x]=0;
  

  }
  

  for(int x =0;x<N;x++)
  

  {
  

  if(i_1-x>=0&&j_1-x>=0)
  

  a[i_1-x][j_1-x]=0;
  

  if(i_1-x>=0&&j_1+x<N)
  

  a[i_1-x][j_1+x]=0;
  

  }
  

  a[i][j] = 1;
  

  return true;
  

  

  }
  

  typedef struct hh_tree_{
  

  int hh[N][N];
  

  int x;
  

  int y;
  

  hh_tree_ *next;
  

  }hh_tree,*phh_tree;
  

  void deletenew(hh_tree_* tree)
  

  {
  

  hh_tree_ *temp = tree;
  

  while(temp !=NULL)
  

  {
  

  tree = tree->next;
  

  delete (hh_tree_*)temp;
  

  temp = tree;
  

  

  }
  

  }
  

  phh_tree bahuanghou(phh_tree ,phh_tree ,int);
  

  int _tmain(int argc, _TCHAR* argv[])
  

  {
  

  clock_t tbegin,tend;
  

  tbegin = ::clock();
  

  

  int jishu =1;
  

  for(int i_i = 0;i_i < N;i_i++)
  

  {
  

  phh_tree begin;
  

  phh_tree end;
  

  int hangshu = 0;
  

  begin = new hh_tree;
  

  for(int i = 0;i<N;i++)
  

  for(int j = 0;j<N;j++)
  

  (begin->hh)[i][j] = 3;
  

  

  int *x[N];
  

  

  for(int i = 0;i<N;i++)
  

  x[i] = (begin->hh)[i];
  

  

  haha(x,0,i_i);
  

  begin->next = NULL;
  

  begin->x =0;
  

  begin->y =0;
  

  end = begin;
  

  for(int i = 0;i<N-1;i++)
  

  {
  

  begin = bahuanghou(begin,end,i);
  

  phh_tree temp =begin;
  

  while(temp != NULL)
  

  {
  

  temp = temp->next;
  

  }
  

  end = temp;
  

  }
  

  

  phh_tree temp =begin;
  

  while(temp != NULL)
  

  {
  

  cout<<"_______________"<<jishu<<endl;
  

  for(int i = 0;i<N;i++)
  

  {
  

  cout<<"\n";
  

  for(int j = 0;j<N;j++)
  

  {
  

  cout<<(temp->hh)[i][j]<<" ";
  

  }
  

  }
  

  cout<<"_______________"<<endl;
  

  temp = temp->next;
  

  jishu++;
  

  }
  

  deletenew(begin);
  

  begin = NULL;
  

  end =NULL;
  

  }
  

  tend = ::clock();
  

  cout<<(double)(tend-tbegin)/1000<<endl;
  

  getchar();
  

  return 0;
  

  }
  

  phh_tree bahuanghou(phh_tree begin,phh_tree end,int hangshu)
  

  {
  

  phh_tree be = begin;
  

  hh_tree_ *tou = NULL;
  

  hh_tree_ *wei = NULL;
  

  hh_tree_ *sb = begin;
  

  for(;be != NULL;)
  

  {
  

  for(int j = 0;j<N;j++)
  

  {
  

  if((be->hh)[hangshu+1][j] == 3)
  

  {
  

  hh_tree_ *node = new hh_tree_;
  

  int *x[N];
  

  for(int i_x = 0 ;i_x<N;i_x++)
  

  for(int j_x = 0;j_x<N;j_x++)
  

  {
  

  node->hh[i_x][j_x]=be->hh[i_x][j_x];
  

  }
  

  node->next = NULL;
  

  node->x = hangshu+1;
  

  node->y = j;
  

  for(int i = 0;i<N;i++)
  

  x[i] = (node->hh)[i];
  

  haha(x,hangshu+1,j);
  

  if(tou == NULL)
  

  {
  

  tou = node;
  

  wei = node;
  

  }
  

  else
  

  {
  

  wei->next = node;
  

  wei = node;
  

  }
  

  }
  

  

  }
  

  

  if(tou ==NULL)
  

  {
  

  if(sb == begin &&be == begin)
  

  {
  

  begin = begin->next;
  

  delete (hh_tree_*)be;
  

  sb =begin;
  

  be =begin;
  

  tou = NULL;
  

  wei = NULL;
  

  continue;
  

  }
  

  else
  

  {
  

  sb->next = be->next;
  

  delete  (hh_tree_*)be;
  

  be = sb;
  

  tou = NULL;
  

  wei = NULL;
  

  }
  

  }
  

  else
  

  {
  

  if(be == begin)
  

  {
  

  wei->next = be->next;
  

  delete  (hh_tree_*)be;
  

  begin = tou;
  

  //temp_ = tou;
  

  be = wei;
  

  sb=wei;
  

  tou = NULL;
  

  wei = NULL;
  

  }
  

  else
  

  {
  

  wei->next = be->next;
  

  sb->next = tou;
  

  sb = wei;
  

  delete  (hh_tree_*)be;
  

  be = wei;
  

  tou = NULL;
  

  wei = NULL;
  

  }
  

  }
  

  be = be->next;
  

  }
  

  return begin;
  

  

  }