RarnuC(IDE)

#define MAXN 16 /* 定义栈结点，表示一个皇后的位置 */ typedef struct node { int row; /* 行 */ int col; /* 列 */ int tag; /* 布局标记 */ } NODE; /* 进行皇后问题处理 * 参数 n 表示棋盘的大小 * 返回找到的答案个数 */ int queens(int n) { /* 定义解答树堆栈 */ NODE stack[MAXN * MAXN]; /* 栈顶索引，初始化为 -1（栈空） */ int top = -1; /* 攻击标志，表示同一列及对角线上是否有皇后 */ int col[MAXN] = {0}, md[2 * MAXN - 1] = {0}, sd[2 * MAXN - 1] = {0}; int str, stc, i; /* 解决方案个数 */ int scount = 0; /* 初始化栈 */ for(i = 0; i < n; i++) { stack[++top].row = 0; stack[top].col = n - 1 - i; stack[top].tag = 0; } /* 以行为单位开始回溯 */ while(top >= 0) { str = stack[top].row; stc = stack[top].col; if(stack[top].tag == 0) { /* 如果栈顶元素的位置并没有确立 */ if(col[stc] || md[str - stc + n - 1] || sd[str + stc]) { /* 如果同一列或同一对角线上已有皇后，则退回 */ top--; } else { /* 占据这个位置，设置列、对角线上的攻击标志 */ col[stc] = 1; md[str - stc + n - 1] = 1; sd[str + stc] = 1; /* 标记栈顶元素的 tag 值 */ stack[top].tag = 1; if(str == n - 1) { /* 如果此时已经到达最后一行 * 则表示此种布局方法是成功的 * 输出相关信息 */ printf("A solution is:\n"); for(i = 0; i <= top; i++) { if(stack[i].tag) printf("%4d,%3d;", stack[i].row, stack[i].col); } printf("\n"); /* 解决方案数增 1 */ scount++; } else { /* 如果此时没有到达最后一行 * 则继续进栈并初始化 */ for(i = 0; i < n; i++) { stack[++top].row = str + 1; stack[top].col = n - 1 - i; stack[top].tag = 0; } } } } else { /* 如果栈顶元素位置已确立 * 则栈顶元素出栈，初始化攻击标志 * 准备继续寻找其它的方法 */ col[stc] = 0; md[str - stc + n - 1] = 0; sd[str + stc] = 0; top--; } } return(scount); } void main() { int n; int scount = 0; printf("\nInput n (n <= 15) = "); scanf("%d", &n); if(n > MAXN - 1) { printf("### n > %d ###\n", MAXN - 1); exit(1); } scount = queens(n); printf("%d sulotions found.\n", scount); getch(); }