8 Queen Problem

八皇后問題
在 8 * 8 的棋盤上擺入八個皇后，兩兩之間不能在同一行、同一列或對角線上， 求出共幾種解法並印出。

思路
可利用遞迴方式解決，每次放一個新的都與前面作比較，檢驗是否合格。

#include<iostream>
#include<conio.h>   // getch()
#include<cmath>
using namespace std;

#define max 8
int answer = 0;    // 放外面 因為會一直累加 

class QueenPuzzle
{
 int queens[max];
 
 public:
  void print();
  void place(int i);   // 放入 
  int isValid(int n);   // 放入第 n 個是否合格
};

void QueenPuzzle::print()
{
 for(int i = 0; i < max; i++)
 {
  for(int j = 0; j < max; j++)
  {
   if(j == queens[i])
    cout << "Q ";
   else
    cout << "1 ";
  }
  cout << endl;    // 排完一列 換行 
 }
 
 if(getch() == 'q')    // 按 q 鍵正常退出
  exit(0);      
}

void QueenPuzzle::place(int i)
{
 for(int j = 0; j < max; j++)
 {
  if(i == max)
  {
   answer++;
   cout << "第 " << answer << " 組解: " << endl;
   print();
   
   return;
  }
  
  queens[i] = j;
  
  if(isValid(i))    // 成功 下面一位 如果不行 就回到迴圈 j++ 往右一格 
   place(i+1);
 }
}

int QueenPuzzle::isValid(int n)   
{
 for(int i = 0; i < n; i++)   // 和前面幾個作比較
 {
  if(queens[i] == queens[n])  // 同一列
   return 0;
  if(abs(queens[n] - queens[i]) == n - i)   // 在對角線上 
   return 0; 
 }
 return 1;
}

int main(void)
{
 QueenPuzzle puzzle;
 puzzle.place(0);
 cout << "共 " << answer << " 組解 " << endl; 
}