作者jim97260 (區欠足易)
看板C_and_CPP
標題Re: [問題] 請問一下我的八皇后程式
時間Sun Dec 13 13:11:05 2009
我翻出了我以前修資料結構時寫的八皇后作業檔~"~
是用struct還有遞迴寫的
不過已經忘掉許多(畢竟是兩三年前了...)
要我講解的話 可能要讓我想一下XD
作業環境是VC6 不過應該都可以用
以下是CODE 先睹為快:
#include <stdio.h>
#include <stdlib.h>
#define N 8
typedef struct{ int row, col;}Position;
int place(Position q[], int n, int row[], int diagP[], int diagN[]);
void Number(int i);
int main()
{
Position queen[N];
int i, cnt = 0, row[N], diagP[(2 * N) - 1], diagN[(2 * N) - 1];
for (i = 0; i < N;row[i] = 0, queen[i].col = i++);
for (i = 0; i < (2 * N) - 1; diagP[i] = diagN[i] = 0, i++);
if (place(queen, 0, row, diagP, diagN))
printf("No solution\n");
else {
printf("There are ");
Number(1);
printf(" solution(s).\n");
}
system("pause");return 0;
}
int place(Position q[], int n, int row[], int diagP[], int diagN[])
{
if (n == N)
return 1;
for(int k = 0; k < N; k++) {
q[n].row = k;
if (row[k] != 1 && diagP[(n - k) + (N - 1)] != 1 && diagN[n + k] != 1) {
row[k] = 1;
diagP[(n - k) + (N - 1)] = 1;
diagN[n + k] = 1;
if (place(q, n+1, row, diagP, diagN))
{
printf("(");
Number(0);
printf("):\n");
for (int i = 0; i < N;printf(" %i", i + 1), i++);
for (printf("\n"), i = 0; i < N; i++) {
printf("%i", i + 1);
for (int j = 0; j < N; j++) {
if (j == q[i].row && q[i].col == i)
printf("■");
else
printf("□");
}
printf("\tqueen %i is at row %i and col %i.\n",i+1,q[i].row+1,q[i].col+1);
}
}
row[k] = 0;
diagP[(n - k) + (N - 1)] = 0;
diagN[n + k] = 0;
}
}
return 0;
}
void Number(int i){
static int cnt = 0;
if (i == 0)
printf("%i", ++cnt);
else
printf("%i", cnt);
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.228.33
1F：→ ilway25:話說我用過 Binary decision diagram 解 n Queen，很慢.. 12/13 13:53