|
#2
diycai2021-12-24 16:00
 程序代码：#include <stdio.h> #define __int64 long long unsigned __int64 list[64]; unsigned __int64 result[4860]; int counter = 0; void print(unsigned __int64 map) { int i, j; for (i=0; i<8; i++) { for (j=0; j<8; j++) { if (map & 1) { printf("Q "); } else { printf("* "); } map >>= 1; } printf("\n"); } printf("\n"); } void initList() { int i, j, k; unsigned char *p; for (i=0; i<8; i++) { for (j=0; j<8; j++) { p = (unsigned char *)&list[i*8+j]; p[i] = 0xff; for (k=0; k<8; k++) { p[k] |= 1<<j; p[k] |= 1<<(j-i+k); p[k] |= 1<<(j+i-k); } } } } unsigned __int64 flip(unsigned __int64 value) { int i; unsigned char *p1, *p2; unsigned __int64 ret = 0; p1 = (unsigned char *)&ret; p2 = (unsigned char *)&value; for (i=0; i<8; i++) { p1[i] = p2[7-i]; } return ret; } unsigned __int64 rotate(unsigned __int64 value) { int i, j; unsigned char *p1, *p2; unsigned __int64 ret = 0; p1 = (unsigned char *)&ret; p2 = (unsigned char *)&value; for (i=0; i<8; i++) { for (j=0; j<8; j++) { p1[i] <<= 1; p1[i] |= p2[7-j] & 1; p2[7-j] >>= 1; } } return ret; } unsigned __int64 image(unsigned __int64 value) { int i, j; unsigned char *p1, *p2; unsigned __int64 ret = 0; p1 = (unsigned char *)&ret; p2 = (unsigned char *)&value; for (i=0; i<8; i++) { for (j=0; j<8; j++) { p1[i] <<= 1; p1[i] |= p2[i] & 1; p2[i] >>= 1; } } return ret; } unsigned __int64 getMin(unsigned __int64 value) { unsigned __int64 ret, temp; int i; ret = ~0; for (i=0; i<4; i++) { value = rotate(value); if (ret > value) { ret = value; } temp = flip(value); if (ret > temp) { ret = temp; } temp = image(value); if (ret > temp) { ret = temp; } temp = flip(temp); if (ret > temp) { ret = temp; } } return ret; } void checkPosition(unsigned __int64 positionBitmap) { int i; unsigned __int64 attackBitmap, temp; attackBitmap = 0; i = 0; temp = positionBitmap; while (temp) { if (temp & 1) { attackBitmap |= list[i]; } temp >>= 1; i++; } if ((~attackBitmap) == 0) { temp = getMin(positionBitmap); for (i=0; i<counter; i++) { if (temp == result[i]) { return; } } result[counter++] = temp; print(temp); } } int main() { int i, j, n; unsigned __int64 bitmap = 0x1F; unsigned __int64 temp; initList(); checkPosition(bitmap); while (1) { i = 0; n = 0; temp = 1; for (i=0; i<63; i++,temp<<=1) { if (bitmap & temp) { n++; if ((bitmap & (temp<<1)) == 0) { bitmap ^= temp; bitmap |= (temp<<1); temp = 1; for (j=0; j<n-1; j++,temp<<=1) { bitmap |= temp; } for (; j<i; j++,temp<<=1) { bitmap &= ~temp; } break; } } } if (i >= 63) { break; } checkPosition(bitmap); } printf("%d\n", counter); return 0; } |
要求：在8x8棋盘上放置五个皇后，使得棋盘上无安全格点。找出所有独立解并以简化形式输出。用c++来解。
（独立解的含义是，给定任意两个解，若这两个解互相不能通过旋转变换(90°，180°，270°)或镜像变换(水平、垂直)或以上变换的组合变为对方,则称这两个解互相独立。如下图中，(c)和(d)中的解呈水平镜像关系，因此实质上是同一个解;(c)和(e)中的解不能通过以上变换变成对方，因此互相独立。）
该问题共有4860种可能的布置方案，其中包含638个独立解。
要求用c++来解，若答出，请在回复区回复源码。
简化形式样例（Q为皇后位置）：
* * * * * * * *
* * * * * Q * *
* * Q * * * * *
* * * * Q * * *
* * * * * * Q *
* * * Q * * * *
* * * * * * * *
* * * * * * * *
[此贴子已经被作者于2021-12-22 20:29编辑过]
