09. C Pro 深度算法求解八皇后问题及其另一种表示形式

有时候真的感概，撸码并Debug一天，搞得自己头昏脑胀，结果第二天才发现，原来两行代码的执行顺序错了 -_-!

八皇后问题：

方法一、二维数组

#define N 8
int a[N][N] = { 0 };
int count = 0;

int abs(int x, int y) {
　　return x >= y ? (x - y) : (y - x);
}
void dps(int x){
　　if (x == N ) {
　　　　count++;
　　　　printf("\n方案%d：\n",count);
　　　　for (int i = 0; i < N; i++) {
　　　　　　for (int j = 0; j < N; j++) 
　　　　　　　　printf("%d\t", a[i][j]==1?a[i][j]:0);
　　　　　　printf("\n");
　　　　}
　　　　return;
　　}

　　for (int k = 0; k < N; k++) {
　　　　if (a[x][k] == 0) {
　　　　　　for (int i = 0; i < N; i++) {
　　　　　　　　for (int j = 0; j < N; j++) {
　　　　　　　　　　a[x][j] -= 1;
　　　　　　　　　　a[i][k] -= 1;
　　　　　　　　　　if (abs(x, i) == abs(j, k)) a[i][j] -= 1;
　　　　　　　　}
　　　　　　}
　　　　　　a[x][k] = 1;
　　　　　　dps(x + 1);
　　　　　　for (int i = 0; i < N; i++) {
　　　　　　　　for (int j = 0; j < N; j++) {
　　　　　　　　　　a[x][j] += 1;
　　　　　　　　　　a[i][k] += 1;
　　　　　　　　　　if (abs(x, i) == abs(j, k)) a[i][j] += 1;
　　　　　　　　}
　　　　　　}
　　　　　　a[x][k] = 0;
　　　　}
　　}

　　return;
}

int main() {
　　dps(0);
　　getchar(); return 0;
}

方法二、一维数组，place函数暂时没看懂

int solution[N], j, k, count, sols;
int place(int row, int col) {
　　for (j = 0; j < row; j++) {
　　　　if (row - j == solution[row] - solution[j] || row + solution[row] == j + solution[j] || solution[j] == solution[row])
　　　　return 0;
　　}
　　return 1;
}

void backtrack(int row) {
　　count++;
　　if (N == row) {
　　　　sols++;
　　　　for (k = 0; k < N; k++)
　　　　　　printf("%d\t", solution[k]);
　　　　printf("\n\n");
　　}
　　else {
　　　　for (int i = 0; i < N; i++) {
　　　　　　solution[row] = i;
　　　　　　if (place(row, i)) backtrack(row + 1);
　　　　}
　　}
}

void queens() {
　　backtrack(0);
}

int main() {
　　queens();
　　printf("The total solutions : %d\n", sols);
　　getchar(); return 0;
}

体彩29选7的组合：

#define MAXN 7
#define NUM 29
int num[NUM];
int lottery[MAXN] = { 0 };

void combine(int n, int m) {
　　int i, j;
　　for (i = n; i >= m; i--) {
　　　　lottery[m - 1] = num[i - 1];
　　　　if (m > 1)
　　　　　　combine(i - 1, m - 1);
　　　　else {
　　　　　　for (j = MAXN - 1; j >= 0; j--)
　　　　　　　　printf("%3d", lottery[j]);
　　　　　　printf("\n");
　　　　　　getchar();
　　　　}
　　}
}

int main(void) {
　　for (int i = 0; i < NUM; i++) num[i] = i + 1;
　　combine(NUM, MAXN);
　　getchar(); return 0;
}