神奇立方体

// Copyright © 2022, 飞麦 <[email protected]>, All rights reserved.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#define LEN 64 // 立方体边长(格数, 每格一字符, 填满需要262144字符)
#define BLOCK_NUM (LEN * LEN) // 独立线(1*64)、面(8*8)、体(4*4*4)的个数，线互不重叠、面互不重叠、体互不重叠
#define PUZZLE_NUM (LEN * LEN * LEN) // 立方体所有格子的数量
#define TYPE_NUM 7 // 块的类型数: 与x/y/z轴平行线(3种)、与x/y/z轴垂直面(3种)、体(1种)
const char* CHAR_A = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; // 填格之Base64字符
int puzzle_no; // 立方体的一维下标(z*64*64 + y*64 + x)
int x, y, z; // x轴坐标(0~63), y轴坐标(0~63), z轴坐标(0~63)
char puzzle_a[PUZZLE_NUM]; // 立方体所有字符(转为一维表示)
int select_a[PUZZLE_NUM]; // 每个格子的待选择字符在 CHAR_A 中的序号(0~63)
int64_t occupy_a_a[BLOCK_NUM][TYPE_NUM]; // 每个(3种线、3种面、1种体)块的64字符占用情况(每bit代表一个字符)

// 根据立方体中的当前字符位置，生成各轴坐标
void gen_puzzle_coordinate() {
  z = (puzzle_no >> 12) & 0x3f; // (puzzle_no / BLOCK_NUM) % LEN
  y = (puzzle_no >> 6) & 0x3f; // (puzzle_no / LEN) % LEN
  x = puzzle_no & 0x3f; // puzzle_no % LEN
}

// 设置各初始值
void init() {
  for (puzzle_no = 0; puzzle_no < PUZZLE_NUM; puzzle_no++) {
    select_a[puzzle_no] = 0; // 立方体中每格在 CHAR_A 中的候选字符下标
  }
  for (int block_no = 0; block_no < BLOCK_NUM; block_no++) {
    int64_t* occupy_a = occupy_a_a[block_no];
    for (int type_no = 0; type_no < TYPE_NUM; type_no++) {
      occupy_a[type_no] = 0; // 初始化线、面、体的64字符占用情况
    }
  }
  puzzle_no = 0; // 立方体中字符索引
  gen_puzzle_coordinate(); // 根据 puzzle_no 生成 x轴坐标, y轴坐标, z轴坐标
}

// 根据坐标计算当前格所属线、面、体的块位置
int calc_block_no(int type_no) {
  switch (type_no) {
    case 0: // 当前坐标所属的与x轴平行的(1格*64格)线的位置: (z * 64) + y
      return (z << 6) | y;
    case 1: // 当前坐标所属的与y轴平行的(1格*64格)线的位置: (x * 64) + z
      return (x << 6) | z;
    case 2: // 当前坐标所属的与z轴平行的(1格*64格)线的位置: (y * 64) + x
      return (y << 6) | x;
    case 3: // 当前坐标所属的与x轴垂直的(8格*8格)面的位置: (x * 64) + ((z / 8) * 8) + (y / 8)
      return (x << 6) | (z & 0x38) | (y >> 3);
    case 4: // 当前坐标所属的与y轴垂直的(8格*8格)面的位置: (y * 64) + ((x / 8) * 8) + (z / 8)
      return (y << 6) | (x & 0x38) | (z >> 3);
    case 5: // 当前坐标所属的与z轴垂直的(8格*8格)面的位置: (z * 64) + ((y / 8) * 8) + (x / 8)
      return (z << 6) | (y & 0x38) | (x >> 3);
    default: // 当前坐标所属的(4格*4格*4格)体的位置: ((z / 4) * 256) + ((y / 4) * 16) + (x / 4)
      return ((z >> 2) << 8) | ((y >> 2) << 4) | (x >> 2);
  }
}

// 根据类型获取当前格所属线、面、体的块
int64_t* got_block(int type_no) {
  return occupy_a_a[calc_block_no(type_no)];
}

// 计算字符在 CHAR_A 中的索引
int calc_occupy_bit_loc(char ch) {
  if (ch >= 'A' && ch <= 'Z') {
    return ch - 'A';
  }
  if (ch >= 'a' && ch <= 'z') {
    return 26 + ch - 'a';
  }
  if (ch >= '0' && ch <= '9') {
    return 52 + ch - '0';
  }
  if (ch == '+') {
    return 62;
  }
  return 63; // ch == '/'
}

// 计算字符在 CHAR_A 中的索引对应的二进制位
int64_t calc_occupy_bits(char ch) {
  return 1LL << calc_occupy_bit_loc(ch); // LL表示64位整数字面量
}

// 标记指定字符在所属线、面、体已被占用
void tag_occupy_one(int64_t bits, int64_t* occupy_a, int type_no) {
  occupy_a[type_no] |= bits;
}

// 标记指定字符在所属线、面、体中未被占用
void untag_occupy_one(int64_t bits, int64_t* occupy_a, int type_no) {
  occupy_a[type_no] &= ~bits;
}

// 判断指定位置的占位情况中的指定字符是否未被占用
bool one_occupy_free(int64_t bits, int64_t* occupy_a, int type_no) {
  return (occupy_a[type_no] & bits) == 0;
}

// 标记立方体中当前字符的所属线、面、体中指定字符已被占用
void tag_occupy_all(char ch) {
  int64_t bits = calc_occupy_bits(ch);
  for (int type_no = 0; type_no < TYPE_NUM; type_no++) {
    tag_occupy_one(bits, got_block(type_no), type_no);
  }
}

// 清除原字符的所属线、面、体的占位情况中该字符已被占用信息
void untag_occupy_all() {
  int64_t bits = calc_occupy_bits(puzzle_a[puzzle_no]);
  for (int type_no = 0; type_no < TYPE_NUM; type_no++) {
    untag_occupy_one(bits, got_block(type_no), type_no);
  }
}

// 判断立方体中当前字符的所属线、面、体的占位情况中该字符是否均未被占用
bool all_occupy_free(char ch) {
  int64_t bits = calc_occupy_bits(ch);
  for (int type_no = 0; type_no < TYPE_NUM; type_no++) {
    if (!one_occupy_free(bits, got_block(type_no), type_no)) {
      return false;
    }
  }
  return true;
}

// 寻找当前位置未被各所属线、面、体占用的字符并填入，同时更新占用情况
bool pick_free_and_tag_all() {
  int select = select_a[puzzle_no];
  char ch;
  while (select < LEN) {
    ch = CHAR_A[select];
    if (all_occupy_free(ch)) {
      break;
    }
    select++;
  }
  if (select >= LEN) {
    select_a[puzzle_no] = 0;
    return false; // 若所有字符均已被各所属线、面、体占用，则返回当前位置失败，以便后续回退位置
  }
  puzzle_a[puzzle_no] = ch;
  tag_occupy_all(ch);
  select_a[puzzle_no] = select + 1;
  return true;
}

// 改变立方体中的当前字符位置, 并重新计算各轴坐标
void add_puzzle_no(int change) {
  puzzle_no += change;
  if (puzzle_no >= 0 && puzzle_no < PUZZLE_NUM) {
    gen_puzzle_coordinate();
  }
}

// 挑选候选字符，若无可用字符则回退字符
void deal() {
  if (pick_free_and_tag_all()) {
    add_puzzle_no(1);
  } else { // 本程序中不会出现回退
    add_puzzle_no(-1);
    if (puzzle_no > 0) {
      untag_occupy_all();
    }
  }
}

// 求解每1*64线、每8*8面、每4*4*4体各Base64字符均不同的64*64*64立方体
bool solve() {
  while (puzzle_no >= 0 && puzzle_no < PUZZLE_NUM) {
    deal();
  }
  return puzzle_no >= 0; // 是否求解成功
}

// 输出立方体, 每行后换行, 每面后加一空行[每个面恰巧是中心对称的]
void output() {
  for (z = 0; z < LEN; z++) { // 每面
    for (y = 0; y < LEN; y++) { // 每行
      for (x = 0; x < LEN; x++) { // 每列
        printf("%c", puzzle_a[z << 12 | y << 6 | x]);
      }
      printf("\n");
    }
    printf("\n");
  }
}

void main() {
  init(); // 初始化
  if (solve()) { // 生成立方体所有字符
    output(); // 输出立方体所有字符
  }
}