bahuanghou.zip_YUV

#include <iostream> #include <stdlib.h> #include <time.h> #include <string.h> using namespace std; const int Size = 8; int queen[Size]; bool Conflict(int r, int p) { for (int i = 0; i < r; ++ i) { if (p == queen[i]) return true; if (r + p == i + queen[i]) return true; if (r - p == i - queen[i]) return true; } return false; } int Count(int r, int p) { int t = 0; for (int i = r + 1; i < 8; ++ i) for (int j = 0; j < 8; ++ j) if (!Conflict(i, j)) t ++; return t; } void PrintAns() { cout << "**************************************************************" << endl; cout << "* 八皇后问题例解 *" << endl; cout << "**************************************************************" << endl; cout << "* *" << endl; cout << "* +"; for (int j = 0; j < 8; ++ j) cout << "---+"; cout << " *" << endl; for (int i = 0; i < 8; ++ i) { cout << "* |"; for (int j = 0; j < 8; ++ j) if (queen[i] == j) cout << " Q |"; else cout << " |"; cout << " *" << endl; cout << "* +"; for (int j = 0; j < 8; ++ j) cout << "---+"; cout << " *" << endl; } cout << "* *" << endl; cout << "**************************************************************" << endl; } bool PutQueen(int row) { int temp = -1, count[Size]; if (row == 7) { PrintAns(); return true; } memset(count, -1, sizeof(count)); for (int i = 0; i < 8; ++ i) { if (!Conflict(row + 1, i)) count[i] = Count(row + 1, i); } for (int i = 0; i < 8; ++ i) if (temp < count[i]) temp = count[i]; if (temp == -1) return false; for (int i = 0; i < 8; ++ i) if (temp == count[i]) { queen[row + 1] = i; if (PutQueen(row + 1)) return true; } return false; } int main() { srand((unsigned)time(NULL)); while (true) { queen[0] = rand() % Size; if (PutQueen(0)) break; } }