0.02秒找到最优解的华容道程序

 

 

1. #include <stdio.h>
2. #include <stdint.h>
3. #include <string.h>
4. #include <time.h>
5. #include <immintrin.h>
6. #include <xmmintrin.h>
7. #include <set>
8. #include "cwisstable.h"
10. const char* NM[][4] = { {"曹","贼","真","爽"}, {"西","施"}, {"昭","君"}, {"貂","蝉"}, {"甄","姬"}, {"玉","环"}, {"美"}, {"美"}, {"美"}, {"美"} };
11. int W[] = { 2, 2, 2, 2, 2, 2, 1, 1, 1, 1 }; // 默认5个水平条，随后修改
12. int H[] = { 2, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
13. int T[10]; // Type
14. const int D[][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; // 后面有两处用下标判断移动方向
16. enum { MAX = 3600 * 10000 };
17. struct State {
18.   uint8_t aa[10][2];
19. #define CCY aa[0][0] // 曹操的y
20.   int p; // 局面路径的previous
21. #define cpy20(dst, src) _mm_storeu_si128((__m128i*)dst, _mm_loadu_si128((__m128i*)src)); *(int*)((uint8_t*)dst+16) = *(int*)((const uint8_t*)src+16)
22.   void operator= (const State& s) { cpy20(aa, s.aa); p = s.p; }
23.   void operator=(const char* s);
24.   void print(const char* s = "");
25. } q[MAX + 10 * 4]; // 最多40个move. MAX很大; 没判断qt < MAX
26. int qh, qt = 1; // queue head, tail
28. void State::operator= (const char* s) {
29.   int p = 6;
30.   for (int x = 3; x >= 0; x--)
31.     for (int y = 4; y >= 0; y--) {
32.     #define CASE(c, i) case c: aa[i][1] = x; aa[i][0] = y; break;
33.     switch (s[x * 5 + y]) {
34.     // 曹关张黄子龙(l)马
35.     CASE('c', 0) CASE('g', 1) CASE('z', 2) CASE('h', 3) CASE('l', 4) CASE('m', 5)
36.     case 'p':
37.       aa[p][1] = x; aa[p++][0] = y; break; // pawn
38.     }
39.   }
40.   static const char*  S[] = { "gg", "zz", "hh", "ll", "mm" };
41.   for (int i = 0; i < 5; i++) if (strstr(s, S[i])) W[i+1] = 1, H[i+1] = 2;
42.   for (int i = 0; i < 10; i++) T[i] = W[i] * 2 + H[i] - 2;
43. }
45. #define set2DArrayByCoordInA(a, b, what) for (int i = 0; i < 10; i++) { \
46.   const int x = a[i][1], y = a[i][0]; \
47.   for (int yy = y; yy < y + H[i]; yy++) \
48.     for (int xx = x; xx < x + W[i]; xx++) b[yy][xx] = what; \
49. }
51. void State::print (const char* s) {
52.   int idx[10] = {};
53.   const char* b[5][4] = {};
54.   set2DArrayByCoordInA(aa, b, NM[i][idx[i]++])
55.   for (int y = 0; y < 5; y++) {
56.     for (int x = 0; x < 4; x++) printf("%s", b[y][x] ? : "　");
57.     puts("");
58.   }
59.   printf("%s\n", s);
60. }
62. void print_path () { // 数组存的单链表就地翻转
63.   int prev = -1, next = -1, n = 0;
64.   for (int cur = qh; cur != -1; ++n) {
65.     next = q[cur].p; q[cur].p = prev;
66.     prev = cur; cur = next;
67.   }
68.   for (int p = 0; p != -1; p = q[p].p) q[p].print();
69.   printf("%d\n", n);
70. }
72. #pragma pack(1)
73. struct {
74.   uint8_t b[5][4];
75.   uint64_t n; // unique number
76.   uint8_t _[4];
77. } u __attribute__((aligned(32)));
78. #pragma pack()
80. #define Ah { \
81.   _mm256_store_si256((__m256i*)&u, _mm256_setzero_si256()); \
82.   set2DArrayByCoordInA(a, u.b, T[i]) \
83.   for (int y = 0; y < 5; y++) \
84.     for (int x = 0; x < 4; x++) u.n = u.n * 5 + u.b[y][x]; \
85. }
87. #ifdef st
88. CWISS_DECLARE_FLAT_HASHSET(Set, uint64_t); Set set = Set_new(MAX);
89. #define if_ok_add_state if (ok) { cpy20(q[qt].aa, a); \
90.   Ah if (!Set_contains(&set, &u.n)) { Set_insert(&set, &u.n); q[qt++].p = qh; } \
91. }
92. #else
93. std::set<uint64_t> set;
94. #define if_ok_add_state if (ok) { cpy20(q[qt].aa, a); \
95.   Ah if (set.find(u.n) == set.end()) { set.insert(u.n); q[qt++].p = qh; } \
96. }
97. #endif
99. int main (int argc, char* argv[]) {
100.   //q[0] = "pp zz""ccghh""ccgll""pp mm";
101.   q[0] = (argc == 2) ? argv[1] : "pzzpg""cc  g""ccllm""phhpm";
102.   q[0].p = -1;
104.   uint8_t a[10][2] __attribute__((aligned(32)));
105.   cpy20(a, q[0].aa);
106. #ifdef st
107.   Ah Set_insert(&set, &u.n);
108. #else
109.   Ah set.insert(u.n);
110. #endif
112.   double tm = clock();
113.   for (; qh < qt; qh++) {
114.     if (q[qh].CCY == 3) { print_path(); break; }
116.     cpy20(a, q[qh].aa);
117.     uint8_t b[5][4] __attribute__((aligned(32))), overflow[12];
118.     _mm256_store_si256((__m256i*)b, _mm256_set1_epi8(1));
119.     set2DArrayByCoordInA(a, b, 0)
121.     int qt1 = qt;
122.     for (int j = 0; j < 4; j++) {
123.       int ok;
124.       for (int i = 0; i < 6; i++) {
125.         const int ox = a[i][1], oy = a[i][0];
126.         int x = (a[i][1] += D[j][0]), y = (a[i][0] += D[j][1]);
127.         if (x < 0 || x + W[i] > 4 || y < 0 || y + H[i] > 5) ok = 0;
128.         else { // D[]的顺序不能换!
129.           if (j == 0) { y = oy + H[i]; ok = b[y][x] && (W[i] == 1 || b[y][x + 1]); }
130.           else if (j == 1) ok = b[y][x] & (!(W[i] - 1) | b[y][x + 1]); // W[i]1或2; 不更快
131.           else if (j == 2) ok = b[y][x] & (!(H[i] - 1) | b[y + 1][x]);
132.           else { x = ox + W[i]; ok = b[y][x] && (H[i] == 1 || b[y + 1][x]); }
133.         }
134.         if_ok_add_state
135.         a[i][1] -= D[j][0]; a[i][0] -= D[j][1];
136.       }
137.       for (int i = 6; i < 10; i++) {
138.         const int ox = a[i][1], oy = a[i][0];
139.         int x = (a[i][1] += D[j][0]), y = (a[i][0] += D[j][1]);
140.         if (x < 0 || x + W[i] > 4 || y < 0 || y + H[i] > 5) ok = 0;
141.         else {
142.           if (j == 0) y = oy + H[i];
143.           else if (j == 3) x = ox + W[i];
144.           ok = b[y][x];
145.         }
146.         if_ok_add_state
147.         a[i][1] -= D[j][0]; a[i][0] -= D[j][1];
148.       }
149.     }
150. #if 1
151.     int qt2 = qt - 1;
152.     if (qt2 > qt1 && q[qt2].CCY < q[qt1].CCY) { State t = q[qt1]; q[qt1] = q[qt2]; q[qt2] = t; }
153. #endif
154.   }
156.   printf("%.6f %d\n", (clock() - tm) / CLOCKS_PER_SEC, qt);
157.   return 0;
158. }

复制代码

有个负优化而不是bug. q[qt2].CCY < q[qt1].CCY的目的是优先搜索曹操靠下的局面。下方的y大，< 应为 >
既然优先把所有的块往下挪，为啥会出现q[qt2].CCY < q[qt1].CCY的情形呢？
当前局面是最左边时，程序确实优先往下挪，可挪不动。有2个合法移动：
美　　美  美曹贼美  美　美
美曹贼貂  美真爽貂  美曹贼貂
昭真爽蝉  昭　　蝉  昭真爽蝉
君甄玉环  君甄玉环  君甄玉环
美姬西施  美姬西施  美姬西施
我们是方向优先，且优先往下（前提是能挪动），块则是曹操第一，往下挪不动往上挪了。
qt1=11788 qt2=11789 qt=11790 (尚未使用）
把，和#if 0后发现，这个启发信息没用，速度一样（起码差别微乎其微）。
这个程序速度很快。以上结果是在Intel N100上跑的。注释掉找到局面则退出的代码，0.081639秒内搜索了81,340个局面，判断出无解。
On a SUN Sparcstation 2, the timings increase (at a rate of 0.005 second/pixel) from about 20 seconds for a 64**2 pixel image to about 320 seconds for 256**2 pixels. 〔详情〕
它功能强，支持各种块形状。我觉得华容道太难了，并不手动玩，也许可以改成3个长条6个小方块之类。
我alias gcc='g++ -mavx2'。Ah(q[0].aa)美吗？还是改成Emm?
“有2个合法移动”——不对啊，待查，结果：qh=10933 反正我0.02秒，不SEGV，不管啦！:-)
〔优化历史〕
AI写的五进制转换程序：

1. #include <stdio.h>
2. #include <stdint.h>
3. #include <immintrin.h>
5. // SSE优化版本
6. uint64_t convert_to_quinary_sse(uint8_t b[5][4])
7. {
8.   uint64_t n = 0;
10.   // 处理前16个元素（4行）使用SSE
11.   for (int y = 0; y < 4; y++) {
12.     // 加载4个uint8_t值到128位寄存器
13.     __m128i row = _mm_loadu_si128((__m128i *) b[y]);
15.     // 将uint8_t转换为uint64_t并进行五进制转换
16.     for (int x = 0; x < 4; x++) {
17.       uint8_t value = b[y][x];
18.       n = n * 5 + value;
19.     }
20.   }
22.   // 处理最后一行（第5行）
23.   for (int x = 0; x < 4; x++) {
24.     n = n * 5 + b[4][x];
25.   }
27.   return n;
28. }
30. // AVX2优化版本（处理所有20个元素）
31. uint64_t convert_to_quinary_avx2(uint8_t b[5][4])
32. {
33.   uint64_t n = 0;
35.   // 使用AVX2处理前16个元素
36.   for (int y = 0; y < 4; y++) {
37.     // 加载4个uint8_t值
38.     __m128i row = _mm_loadu_si128((__m128i *) b[y]);
40.     // 解包到32位整数
41.     __m128i zero = _mm_setzero_si128();
42.     __m128i row32 = _mm_cvtepu8_epi32(row);
44.     // 对每个元素进行五进制转换
45.     uint32_t values[4];
46.     _mm_storeu_si128((__m128i *) values, row32);
48.     for (int i = 0; i < 4; i++) {
49.       n = n * 5 + values[i];
50.     }
51.   }
53.   // 处理最后4个元素
54.   for (int x = 0; x < 4; x++) {
55.     n = n * 5 + b[4][x];
56.   }
58.   return n;
59. }
61. // 高度优化的AVX版本，使用并行计算
62. uint64_t convert_to_quinary_avx_parallel(uint8_t b[5][4])
63. {
64.   // 使用多个累加器并行计算
65.   uint64_t n1 = 0, n2 = 0, n3 = 0, n4 = 0;
67.   // 并行处理4行
68.   for (int y = 0; y < 4; y++) {
69.     // 加载当前行
70.     __m128i row = _mm_loadu_si128((__m128i *) b[y]);
72.     // 转换为32位整数
73.     __m128i row32 = _mm_cvtepu8_epi32(row);
75.     uint32_t values[4];
76.     _mm_storeu_si128((__m128i *) values, row32);
78.     // 并行累加（模拟并行处理）
79.     n1 = n1 * 625 + values[0] * 125 + values[1] * 25 + values[2] * 5 + values[3];
80.   }
82.   // 合并结果并添加最后一行
83.   uint64_t final_n = n1;
84.   for (int x = 0; x < 4; x++) {
85.     final_n = final_n * 5 + b[4][x];
86.   }
88.   return final_n;
89. }
91. // 基准版本（原始代码）
92. uint64_t convert_to_quinary_baseline(uint8_t b[5][4])
93. {
94.   uint64_t n = 0;
95.   for (int y = 0; y < 5; y++) {
96.     for (int x = 0; x < 4; x++) {
97.       n = n * 5 + b[y][x];
98.     }
99.   }
100.   return n;
101. }
103. int main()
104. {
105.   uint8_t b[5][4] = {
106.     { 1, 2, 3, 4 },
107.     { 0, 4, 2, 1 },
108.     { 3, 1, 4, 2 },
109.     { 2, 0, 1, 3 },
110.     { 4, 3, 0, 2 }
111.   };
113.   uint64_t result_baseline = convert_to_quinary_baseline(b);
114.   uint64_t result_sse = convert_to_quinary_sse(b);
115.   uint64_t result_avx2 = convert_to_quinary_avx2(b);
116.   uint64_t result_avx_parallel = convert_to_quinary_avx_parallel(b);
118.   printf("基准版本结果: %lu\n", result_baseline);
119.   printf("SSE优化结果:  %lu\n", result_sse);
120.   printf("AVX2优化结果: %lu\n", result_avx2);
121.   printf("AVX并行结果: %lu\n", result_avx_parallel);
123.   if (result_baseline == result_sse &&
124.       result_sse == result_avx2 && result_avx2 == result_avx_parallel) {
125.     printf("✓ 所有版本结果一致\n");
126.   } else
127.     printf("✗ 结果不一致\n");
128.   return 0;
129. }

复制代码

View Code　　

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！