Skip to content

Instantly share code, notes, and snippets.

@taroyabuki

taroyabuki/magicsquare2.cpp

Created March 18, 2014 04:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save taroyabuki/9613656 to your computer and use it in GitHub Desktop.
Save taroyabuki/9613656 to your computer and use it in GitHub Desktop.
Download ZIP
（結果の検証付き）スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++）http://blog.unfindable.net/archives/7179
Raw
magicsquare2.cpp
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <ctime>
#include <omp.h>
#include <unordered_set>
using namespace std;
const char* outputfile = "result";
int main()
{
clock_t start = clock();
const int B = 5;
const int N = 25;
const int S = 65;
const int mask = (1 << B) - 1;
int threads = omp_get_max_threads();
cout << "num of threads: " << threads << endl;
int* counts = new int[threads];
ofstream** files = new ofstream*[threads];
for (int t = 0; t < threads; ++t){
counts[t] = 0;
stringstream ss;
ss << outputfile << t;
files[t] = new ofstream(ss.str().c_str(), ios_base::binary);
}
unordered_set<string> all = unordered_set<string>();
#pragma omp parallel
#pragma omp for schedule(dynamic, 1024)
for (int i = 0; i < (1 << 25); ++i) {
if ((i % (1 << 20)) == 0) cout << (i / (1 << 20)) << "/32" << endl;
const int x7 = ((i >> (B * 0)) & mask) + 1;
if (x7 > N - 3) continue;
const int x9 = x7 + ((i >> (B * 1)) & mask) + 1;
if (x9 > N) continue;
const int x17 = x9 + ((i >> (B * 2)) & mask) + 1;
if (x17 > N) continue;
int used = (1 << x7) + (1 << x9) + (1 << x17);
const int x19 = x7 + ((i >> (B * 3)) & mask) + 1;
if (x19 > N || (used & (1 << x19))) continue;
used ^= (1 << x19);
const int x13 = ((i >> (B * 4)) & mask) + 1;
if (x13 > N || (used & (1 << x13))) continue;
used ^= (1 << x13);
for (int x1 = max(1, S - x7 - x13 - x19 - N); x1 <= min(N, S - x7 - x13 - x19 - 1); ++x1) {
if (!(used & (1 << x1))) {
used ^= (1 << x1);
const int x25 = S - x1 - x7 - x13 - x19;
if (!(used & (1 << x25))) {
used ^= (1 << x25);
for (int x5 = max(1, S - x9 - x13 - x17 - N); x5 <= min(N, S - x9 - x13 - x17 - 1); ++x5) {
if (!(used & (1 << x5))) {
used ^= (1 << x5);
const int x21 = S - x5 - x9 - x13 - x17;
if (!(used & (1 << x21))) {
used ^= (1 << x21);
for (int x2 = max(1, max(S - x1 - x5, S - x7 - x17) - 49); x2 <= min(N, min(S - x1 - x5, S - x7 - x17) - 3); ++x2) {
if (!(used & (1 << x2))) {
used ^= (1 << x2);
for (int x3 = max(1, S - x1 - x2 - x5 - N); x3 <= min(N, S - x1 - x2 - x5 - 1); ++x3) {
if (!(used & (1 << x3))) {
used ^= (1 << x3);
const int x4 = S - x1 - x2 - x3 - x5;
if (!(used & (1 << x4))) {
used ^= (1 << x4);
for (int x12 = max(1, S - x2 - x7 - x17 - N); x12 <= min(N, S - x2 - x7 - x17 - 1); ++x12) {
if (!(used & (1 << x12))) {
used ^= (1 << x12);
const int x22 = S - x2 - x7 - x12 - x17;
if (!(used & (1 << x22))) {
used ^= (1 << x22);
for (int x24 = max(1, max(S - x4 - x9 - x19, S - x21 - x22 - x25) - N); x24 <= min(N, min(S - x4 - x9 - x19, S - x21 - x22 - x25) - 1); ++x24) {
if (!(used & (1 << x24))) {
used ^= (1 << x24);
const int x14 = S - x4 - x9 - x19 - x24;
if (1 <= x14 && x14 <= N && !(used & (1 << x14))) {
used ^= (1 << x14);
const int x23 = S - x21 - x22 - x24 - x25;
if (1 <= x23 && x23 <= N && !(used & (1 << x23))) {
used ^= (1 << x23);
for (int x8 = max(1, S - x3 - x13 - x23 - N); x8 <= min(N, S - x3 - x13 - x23 - 1); ++x8) {
if (!(used & (1 << x8))) {
used ^= (1 << x8);
const int x18 = S - x3 - x8 - x13 - x23;
if (!(used & (1 << x18))) {
used ^= (1 << x18);
for (int x6 = max(1, S - x7 - x8 - x9 - N); x6 <= min(N, S - x7 - x8 - x9 - 1); ++x6) {
if (!(used & (1 << x6))) {
used ^= (1 << x6);
const int x10 = S - x6 - x7 - x8 - x9;
if (!(used & (1 << x10))) {
used ^= (1 << x10);
for (int x11 = max(1, max(S - x1 - x6 - x21, S - x12 - x13 - x14) - N); x11 <= min(N, min(S - x1 - x6 - x21, S - x12 - x13 - x14) - 1); ++x11) {
if (!(used & (1 << x11))) {
used ^= (1 << x11);
const int x15 = S - x11 - x12 - x13 - x14;
if (1 <= x15 && x15 <= N && !(used & (1 << x15))) {
used ^= (1 << x15);
const int x16 = S - x1 - x6 - x11 - x21;
if (1 <= x16 && x16 <= N && !(used & (1 << x16))) {
used ^= (1 << x16);
const int x20 = S - x5 - x10 - x15 - x25;
if (S == x16 + x17 + x18 + x19 + x20 && 1 <= x20 && x20 <= N && !(used & (1 << x20))) {
int check = (1 << x1) + (1 << x2) + (1 << x3) + (1 << x4) + (1 << x5) + (1 << x6) + (1 << x7) + (1 << x8) + (1 << x9) + (1 << x10) + (1 << x11) + (1 << x12) + (1 << x13) + (1 << x14) + (1 << x15) + (1 << x16) + (1 << x17) + (1 << x18) + (1 << x19) + (1 << x20) + (1 << x21) + (1 << x22) + (1 << x23) + (1 << x24) + (1 << x25);
if (check == 67108862 && 1 <= x1 && x1 <= 25 && 1 <= x2 && x2 <= 25 && 1 <= x3 && x3 <= 25 && 1 <= x4 && x4 <= 25 && 1 <= x5 && x5 <= 25 && 1 <= x6 && x6 <= 25 && 1 <= x7 && x7 <= 25 && 1 <= x8 && x8 <= 25 && 1 <= x9 && x9 <= 25 && 1 <= x10 && x10 <= 25 && 1 <= x11 && x11 <= 25 && 1 <= x12 && x12 <= 25 && 1 <= x13 && x13 <= 25 && 1 <= x14 && x14 <= 25 && 1 <= x15 && x15 <= 25 && 1 <= x16 && x16 <= 25 && 1 <= x17 && x17 <= 25 && 1 <= x18 && x18 <= 25 && 1 <= x19 && x19 <= 25 && 1 <= x20 && x20 <= 25 && 1 <= x21 && x21 <= 25 && 1 <= x22 && x22 <= 25 && 1 <= x23 && x23 <= 25 && 1 <= x24 && x24 <= 25 && 1 <= x25 && x25 <= 25 && 65 == x1 + x2 + x3 + x4 + x5 && 65 == x6 + x7 + x8 + x9 + x10 && 65 == x11 + x12 + x13 + x14 + x15 && 65 == x16 + x17 + x18 + x19 + x20 && 65 == x21 + x22 + x23 + x24 + x25 && 65 == x1 + x6 + x11 + x16 + x21 && 65 == x2 + x7 + x12 + x17 + x22 && 65 == x3 + x8 + x13 + x18 + x23 && 65 == x4 + x9 + x14 + x19 + x24 && 65 == x5 + x10 + x15 + x20 + x25 && 65 == x1 + x7 + x13 + x19 + x25 && 65 == x5 + x9 + x13 + x17 + x21) {
int t = omp_get_thread_num();
++counts[t];
stringstream ss;
ss << (char)x1 << (char)x2 << (char)x3 << (char)x4 << (char)x5 << (char)x6 << (char)x7 << (char)x8 << (char)x9 << (char)x10 << (char)x11 << (char)x12 << (char)x13 << (char)x14 << (char)x15 << (char)x16 << (char)x17 << (char)x18 << (char)x19 << (char)x20 << (char)x21 << (char)x22 << (char)x23 << (char)x24 << (char)x25;
*files[t] << ss.rdbuf();
#pragma omp critical
all.insert(ss.str());
}
}
used ^= (1 << x16);
}
used ^= (1 << x15);
}
used ^= (1 << x11);
}
}
used ^= (1 << x10);
}
used ^= (1 << x6);
}
}
used ^= (1 << x18);
}
used ^= (1 << x8);
}
}
used ^= (1 << x23);
}
used ^= (1 << x14);
}
used ^= (1 << x24);
}
}
used ^= (1 << x22);
}
used ^= (1 << x12);
}
}
used ^= (1 << x4);
}
used ^= (1 << x3);
}
}
used ^= (1 << x2);
}
}
used ^= (1 << x21);
}
used ^= (1 << x5);
}
}
used ^= (1 << x25);
}
used ^= (1 << x1);
}
}
}
int sum = 0;
for (int t = 0; t < threads; ++t) {
sum += counts[t];
files[t]->close();
}
cout << "num of solution: " << sum << endl;
cout << "num of solution (check): " << all.size() << endl;
clock_t now = clock();
double duration = double(now - start) / CLOCKS_PER_SEC;
cout << "time for count: " << duration << " sec." << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment