108设有一个每行每列都有8个正方格的棋盘,使用8个棋子布到格子上,要求满足 以下条件: (1)任意两个棋子不在同一行和同一列上 (2)任意两个棋子不在同一斜线上。 问有多少种摆法。 解:把棋盘看作平面直角坐标系,横坐标设为i,纵坐标设为j,i、j的范围都为0~7,当 某个棋子占了(i)时,这个位置的垂直、水平和斜线方向都不能再放其它棋子。 合理布局的8个棋子对应的i肯定不同,关键问题是确定每个棋子的j坐标。 两个棋子水平和斜线方向共线的条件:j坐标相等、计是常量、i是常量。水平线共 8条(0~7),45(-7~7)和135(0~14)度角线各15条。用3个数组A、B、C记录棋 子的占用情况。初始全部为0,表示棋盘为空,当某个棋子占了(ij)时,将3个数组对应元 素置为1:A]=1B[+j]=1C[ij=1。以后的棋子只要检查对应的3个数组元素是否同 时为0即可。注意考虑数组下标的处理,C语言不支持负数下标。参考程序如下: #include <stdio. h> intA[8],B[15],C[15]; int x int count void output o i int k for(k=0;k<=7;k++) printf(%d ,x[k]) printf("Ⅶn"); void select(int i) for(j=0;j<=7;j+) if(!A[j]&&!B[i+j]&&!C[7+i一j) x[il=j A[j]=1;B[i+j=1;C[7+i-j=1 select(i+1) output o A[j]=0;B[i+j=0;C[7+i-j]=0} 10.8 设有一个每行每列都有 8 个正方格的棋盘，使用 8 个棋子布到格子上，要求满足 以下条件： （1）任意两个棋子不在同一行和同一列上； （2）任意两个棋子不在同一斜线上。 问有多少种摆法。 解：把棋盘看作平面直角坐标系，横坐标设为 i, 纵坐标设为 j，i、j 的范围都为 0～7，当 某个棋子占了(i,j)时，这个位置的垂直、水平和斜线方向都不能再放其它棋子。 合理布局的 8 个棋子对应的 i 肯定不同，关键问题是确定每个棋子的 j 坐标。 两个棋子水平和斜线方向共线的条件：j 坐标相等、i+j 是常量、i-j 是常量。水平线共 8 条（0～7），45（-7～7）和 135（0～14）度角线各 15 条。用 3 个数组 A、B、C 记录棋 子的占用情况。初始全部为 0，表示棋盘为空，当某个棋子占了(i,j)时，将 3 个数组对应元 素置为 1：A[j]=1 B[i+j]=1 C[i-j]=1。以后的棋子只要检查对应的 3 个数组元素是否同 时为 0 即可。注意考虑数组下标的处理，C 语言不支持负数下标。参考程序如下： #include <stdio.h> int A[8],B[15],C[15]; int x[8]; int count; void output() { int k; for (k=0;k<=7;k++) printf("%d ",x[k]); printf("\n"); count++; } void select(int i) { int j; for (j=0;j<=7;j++) if (!A[j] && !B[i+j] && !C[7+i-j]) { x[i]=j; A[j]=1; B[i+j]=1; C[7+i-j]=1; if (i<7) select(i+1); else output(); A[j]=0; B[i+j]=0; C[7+i-j]=0; } }