文章目录
序言
问题如上（每个阵型都可以进行旋转或翻转，最终填满日历拼图），其实这是之前诸葛亮列传的兵法题（可惜狗宝更新后把能这个能白嫖资源的列传给删了，emmm），那个网上有很多现成的答案，现在这个每天都不一样，用脑子想还是得花点时间。
代码如下可自取，感觉作为一道leetcode题不错，但是不用一些特殊的寄巧处理还是挺慢的，穷举情况实在是太多。目前常规7×7拼图求解时间1000秒左右，如果是5×5拼图的话，只需要0.1秒。
求解思路暂时搁置，其实本质是一个整数规划，所以关键在于怎么样能更快，一开始写了个纯穷举+DP，结果跑个5×5的都要将近半个小时，7×7的更是估算要100万个小时。后来根据问题的特殊性做了一些剪枝处理，复杂度大大降低。
贴一个明天（12月6日）的求解结果（这个结果要旋转180度，1表示拼图上原本就不能放的格子，2-9分别表示不同阵型的块）：
[[1. 1. 1. 1. 2. 2. 2.]
[5. 6. 6. 6. 2. 2. 2.]
[5. 6. 6. 7. 7. 7. 7.]
[5. 5. 9. 9. 9. 3. 7.]
[5. 1. 4. 4. 9. 3. 3.]
[1. 1. 4. 8. 9. 8. 3.]
[1. 4. 4. 8. 8. 8. 3.]]
1 求解算法代码（python）
代码自取：
# -*- coding: utf-8 -*-
# @author: caoyang
# @email: caoyang@stu.sufe.edu.cn
import time
import numpy
from pprint import pprint
from copy import deepcopy
from functools import lru_cache
FORMATION_ABBR_TO_NAME = {
"BDQX": "北斗七星阵",
"FS": "锋矢阵",
"SLCS": "双龙出水阵",
"JQHH": "九曲黄河阵",
"JS": "金锁阵",
"F": "方阵",
"XX": "玄襄阵",
"GX": "钩形阵",
"YZCS": "一字长蛇阵",
"SC": "三才阵",
"TM": "天门阵",
"HY": "混元阵",
"YY": "鸳鸯阵",
}
FORMATION_NAME_TO_ABBR = {_abbr: _name for _name, _abbr in FORMATION_ABBR_TO_NAME.items()}
# 生成给定日期的日历拼图
def generate_calendar_puzzle(month = 12, day = 3):
month_days = [31, 28, 31, 30, 31, 60, 31, 31, 30, 31, 30, 31]
calendar_puzzle = [[0] * 7 for i in range(7)]
for i in range(35 - month_days[month - 1]):
calendar_puzzle[6][7 - i - 1] = 1
calendar_puzzle[(day - 1) // 7 + 2][(day - 1) % 7] = 1
calendar_puzzle[0][6] = 1
calendar_puzzle[1][6] = 1
calendar_puzzle[(month - 1) // 6][(month - 1) % 6] = 1
return calendar_puzzle
# 定义阵型及其变体
def define_formation_variants(names):
abbrs = map(lambda _name: FORMATION_NAME_TO_ABBR[_name], names)
# 北斗七星阵
BDQX = [
[[1, 0], [1, 1], [0, 1], [0, 1]],
[[0, 1], [1, 1], [1, 0], [1, 0]],
[[1, 0], [1, 0], [1, 1], [0, 1]],
[[0, 1], [0, 1], [1, 1], [1, 0]],
[[0, 0, 1, 1], [1, 1, 1, 0]],
[[1, 1, 0, 0], [0, 1, 1, 1]],
[[0, 1, 1, 1], [1, 1, 0, 0]],
[[1, 1, 1, 0], [0, 0, 1, 1]],
]
# 锋矢阵
FS = [
[[1, 1, 1], [1, 0, 0], [1, 0, 0]],
[[1, 1, 1], [0, 0, 1], [0, 0, 1]],
[[0, 0, 1], [0, 0, 1], [1, 1, 1]],
[[1, 0, 0], [1, 0, 0], [1, 1, 1]],
]
# 双龙出水阵
SLCS = [
[[1, 1], [1, 0], [1, 1]],
[[1, 1], [0, 1], [1, 1]],
[[1, 1, 1], [1, 0, 1]],
[[1, 0, 1], [1, 1, 1]],
]
# 九曲黄河阵
JQHH = [
[[0, 1, 1], [0, 1, 0], [1, 1, 0]],
[[1, 1, 0], [0, 1, 0], [0, 1, 1]],
[[1, 0, 0], [1, 1, 1], [0, 0, 1]],
[[0, 0, 1], [1, 1, 1], [1, 0, 0]],
]
# 金锁阵
JS = [
[[1, 0], [1, 1], [1, 1]],
[[0, 1], [1, 1], [1, 1]],
[[1, 1, 1], [1, 1, 0]],
[[1, 1, 1], [0, 1, 1]],
[[1, 1], [1, 1], [1, 0]],
[[1, 1], [1, 1], [0, 1]],
[[1, 1, 0], [1, 1, 1]],
[[0, 1, 1], [1, 1, 1]],
]
# 方阵
F = [
[[1, 1, 1], [1, 1, 1]],
[[1, 1], [1, 1], [1, 1]],
]
# 玄襄阵
XX = [
[[1, 1, 1, 1], [1, 0, 0, 0]],
[[1, 1, 1, 1], [0, 0, 0, 1]],
[[1, 1], [0, 1], [0, 1], [0, 1]],
[[1, 1], [1, 0], [1, 0], [1, 0]],
[[1, 0, 0, 0], [1, 1, 1, 1]],
[[0, 0, 0, 1], [1, 1, 1, 1]],
[[0, 1], [0, 1], [0, 1], [1, 1]],
[[1, 0], [1, 0], [1, 0], [1, 1]],
]
# 钩形阵
GX = [
[[1, 0], [1, 0], [1, 1], [1, 0]],
[[0, 1], [0, 1], [1, 1], [0, 1]],
[[1, 1, 1, 1], [0, 1, 0, 0]],
[[1, 1, 1, 1], [0, 0, 1, 0]],
[[0, 1], [1, 1], [0, 1], [0, 1]],
[[1, 0], [1, 1], [1, 0], [1, 0]],
[[0, 1, 0, 0], [1, 1, 1, 1]],
[[0, 0, 1, 0], [1, 1, 1, 1]],
]
# 一字长蛇阵
YZCS = [
[[1, 1, 1, 1, 1]],
[[1], [1], [1], [1], [1]],
]
# 三才阵
SC = [
[[1, 1, 1], [0, 1, 0], [0, 1, 0]],
[[0, 1, 0], [0, 1, 0], [1, 1, 1]],
[[1, 0, 0], [1, 1, 1], [1, 0, 0]],
[[0, 0, 1], [1, 1, 1], [0, 0, 1]],
]
# 天门阵
TM = [
[[0, 1, 0], [1, 1, 1], [0, 1, 0]],
]
# 混元阵
HY = [
[[0, 1, 0], [0, 1, 1], [1, 1, 0]],
[[0, 1, 0], [1, 1, 0], [0, 1, 1]],
[[1, 0, 0], [1, 1, 1], [0, 1, 0]],
[[0, 0, 1], [1, 1, 1], [0, 1, 0]],
[[0, 1, 1], [1, 1, 0], [0, 1, 0]],
[[1, 1, 0], [0, 1, 1], [0, 1, 0]],
[[0, 1, 0], [1, 1, 1], [0, 0, 1]],
[[0, 1, 0], [1, 1, 1], [1, 0, 0]],
]
# 鸳鸯阵
YY = [
[[0, 1, 1], [1, 1, 0], [1, 0, 0]],
[[1, 1, 0], [0, 1, 1], [0, 0, 1]],
[[0, 0, 1], [0, 1, 1], [1, 1, 0]],
[[1, 0, 0], [1, 1, 0], [0, 1, 1]],
]
formation_variants = dict()
for abbr in abbrs:
formations = eval(abbr)
index = -1
new_abbr = abbr
while True:
if not new_abbr in formation_variants:
formation_variants[new_abbr] = list(map(lambda _formation: {"matrix": _formation}, formations))
break
else:
# 可能出现的重复阵型，添加不同的序号后缀作为命名区分
index += 1
new_abbr = f"{abbr}_{index}"
return formation_variants
# 使用动态规划：这里我们用编码，所以无需用到稀疏表示，matrix即可
def solve_dp(puzzle, # 原始日历拼图
formation_variants, # 可用阵型及其变形，形如：{"XX": List[Dict{matrix: List[List[Int]], sparse: List[Tuple(x, y)]}], "XXX": 类似前面}
for_solution = False, # 是否找到解法
):
# 将给定的puzzle矩阵转为puzzle_height×puzzle_width长度的编码向量（以零一字符串表示）
def _puzzle_to_code(_puzzle):
return ''.join([''.join(map(str, _puzzle_row)) for _puzzle_row in _puzzle])
# _puzzle_to_code的逆运算
def _code_to_puzzle(_puzzle_code):
_puzzle = numpy.zeros((puzzle_height, puzzle_width))
_pointer = -1
for _i in range(puzzle_height):
for _j in range(puzzle_width):
_pointer += 1
_puzzle[_i, _j] = _puzzle_code[_pointer]
return _puzzle
# 注意到一个puzzle通过旋转/翻转操作，一共会有8种等价的变体（自身与翻转）
# 取最大的编码向量（以零一字符串的数值作为表示）作为唯一编码值，以减少很多重复
# 特别地，每日演兵是一个正方阵，所以连行列都不需要区分，这在下面的formation编码中有很大的助益
# 最大编码值对应的拼图，即块集中在左上角
def _puzzle_to_unique_code(_puzzle):
_rotate_puzzle_copy = _puzzle.copy()
_rotate_puzzle_copy_flip = numpy.fliplr(_rotate_puzzle_copy)
_codes = [_puzzle_to_code(_rotate_puzzle_copy), _puzzle_to_code(_rotate_puzzle_copy_flip)]
# 旋转3次
for _ in range(3):
_rotate_puzzle_copy = numpy.rot90(_rotate_puzzle_copy)
_rotate_puzzle_copy_flip = numpy.rot90(_rotate_puzzle_copy_flip)
_codes.append(_puzzle_to_code(_rotate_puzzle_copy))
_codes.append(_puzzle_to_code(_rotate_puzzle_copy_flip))
return max(_codes)
# 生成formation编码（）的方法：
# - 将formation_matrix每行扩展到跟puzzle_width（零填充）
# - 然后类似_puzzle_to_code的方法，但是要把右侧的零给排除
# - _block_number表示用哪个数字表示块，一般用1，但是为了能看到最终求解的结果，还需要存一份区分不同阵型编码的（即colorful，五彩斑斓的）的阵型编码
def _formation_to_code(_formation_matrix, _block_number = 1):
_formation_matrix = numpy.array(_formation_matrix, dtype=int) * _block_number
_formation_matrix_expand = numpy.concatenate([_formation_matrix, numpy.zeros((_formation_matrix.shape[0], puzzle_width - _formation_matrix.shape[1]))], axis=1)
_formation_matrix_expand = numpy.asarray(_formation_matrix_expand, dtype=int)
_formation_code = ''.join([''.join(map(str, _formation_row)) for _formation_row in _formation_matrix_expand])
return _formation_code.rstrip('0')
# 将formation在指定的位置（pointer）插入puzzle
# 如果指定的位置无法插入，则返回False与空字符串
# 否则返回True和插入后的puzzle_code
def add_formation_code_to_puzzle_code(_puzzle_code, _formation_code, _pointer):
# print(_puzzle_code, len(_puzzle_code))
# print(_formation_code, len(_formation_code))
_result_code = str()
# 插入部分：_pointer, _pointer + 1, ..., _pointer + len(_formation_code) - 1
_start_pointer, _end_pointer = _pointer, _pointer + len(_formation_code)
for _i in range(_start_pointer, _end_pointer):
_formation_char_int = int(_formation_code[_i - _pointer])
_puzzle_char_int = int(_puzzle_code[_i])
if _formation_char_int == 0 or _puzzle_char_int == 0:
# 阵型和拼图至少有一个在当前位置是空的
_result_code += str(_formation_char_int + _puzzle_char_int)
else:
# 否则无法插入阵型
return False, None
# 补上头尾
_result_code = _puzzle_code[: _start_pointer] + _result_code + _puzzle_code[_end_pointer: ]
return True, _result_code
# 注意到，一个形状为(formation_height, formation_width)的阵型，只可能在以下的_pointer插入拼图：
# - _pointer = i × puzzle_width + j
# - 其中：i取值范围是(0, 1, ..., puzzle_height - formation_height)，j取值范围是(0, 1, ...., puzzle_width - formation_width)
def _generate_possible_pointer(_formation_height, _formation_width):
for _i in range(puzzle_height - _formation_height + 1):
for _j in range(puzzle_width - _formation_width + 1):
yield _i * puzzle_width + _j
# 递归算法
@lru_cache(None)
def _dp(_puzzle_unique_code, # Str 当前拼图的编码值（唯一编码值）
_remained_formation_ids, # Tuple 剩余可用的阵型编码
_for_solution = False, # 是否需要找到确切的解法
):
# 终止条件：_puzzle_unique_code全是1，或者_remained_formation_ids为空
if not _remained_formation_ids:
# 找到一组解
print("成功找到一组解！")
for _char in _puzzle_unique_code:
assert int(_char) > 0
if _for_solution:
pprint(_code_to_puzzle(_puzzle_unique_code))
with open("solution.txt", 'w', encoding="utf8") as f:
f.write(str(_code_to_puzzle(_puzzle_unique_code)))
return True
# 遍历每个可用的阵型
for _remained_formation_id in _remained_formation_ids:
# 遍历每个可用阵型的变体
_can_put_in = False
if for_solution:
formation_variant_codes = formation_codes_num[_remained_formation_id]
else:
formation_variant_codes = formation_codes[_remained_formation_id]
for _formation_variant_code, (_formation_height, _formation_width) in zip(formation_variant_codes, formation_sizes[_remained_formation_id]):
# 遍历每个可能可以插入的位置
for _possible_pointer in _generate_possible_pointer(_formation_height, _formation_width):
# 试着插入
_add_flag, _updated_puzzle_code = add_formation_code_to_puzzle_code(
_puzzle_code = _puzzle_unique_code,
_formation_code = _formation_variant_code,
_pointer = _possible_pointer,
)
# 成功：可以插入阵型
if _add_flag:
# 则迭代
_remained_formation_ids_list_copy = list(_remained_formation_ids)
_remained_formation_ids_list_copy.remove(_remained_formation_id)
_updated_remained_formation_ids = tuple(_remained_formation_ids_list_copy)
_result_flag = _dp(
_puzzle_unique_code = _updated_puzzle_code,
_remained_formation_ids = _updated_remained_formation_ids,
_for_solution = _for_solution,
)
_can_put_in = True
if _result_flag:
# 找到一个即可
return True
# 失败：此处不可以插入阵型
else:
pass
if not _can_put_in:
# 当前阵型以及它的所有变体无法在任何位置插入
return False
# 将puzzle转为矩阵
if isinstance(puzzle, list):
puzzle = numpy.array(puzzle, dtype=int)
puzzle_height, puzzle_width = puzzle.shape
assert puzzle_height == puzzle_width, "动态规划算法目前仅支持正方阵的求解"
total_formation = len(formation_variants)
print(f"拼图形状：{(puzzle_height, puzzle_width)}")
print(f"阵型总数：{total_formation}")
# 将阵型转为矩阵：List[List[Str(formation_code)]]
formation_codes = list() # 零一字符串（块统一用1表示）
formation_codes_num = list() # 每个阵型的块用不同的数字表示
formation_sizes = list() # 记录阵型的高和宽
for i, formation_name in enumerate(formation_variants):
formation_variant_codes = list()
formation_variant_codes_num = list()
formation_variant_sizes = list()
for formation_variant in formation_variants[formation_name]:
formation_matrix = formation_variant["matrix"]
formation_variant_codes.append(_formation_to_code(formation_matrix, _block_number = 1))
formation_variant_codes_num.append(_formation_to_code(formation_matrix, _block_number = i + 2))
formation_variant_sizes.append((len(formation_matrix), len(formation_matrix[0])))
formation_codes.append(formation_variant_codes)
formation_codes_num.append(formation_variant_codes_num)
formation_sizes.append(formation_variant_sizes)
_puzzle_unique_code = _puzzle_to_unique_code(puzzle)
# _dp(_puzzle_unique_code, _remained_formation_ids=tuple(range(total_formation)), _for_solution = False)
_dp(_puzzle_unique_code, _remained_formation_ids=tuple(range(total_formation)), _for_solution = for_solution)
# 运行每日练兵
def run():
# 生成今日拼图
month, day = int(time.strftime("%m")), int(time.strftime("%d"))
calendar_puzzle = generate_calendar_puzzle(month, day)
print(f"{month}月{day}日拼图：")
pprint(calendar_puzzle)
# 生成今日阵型
names = ["方阵", "北斗七星阵", "九曲黄河阵", "钩形阵", "金锁阵", "玄襄阵", "双龙出水阵", "锋矢阵"]
formation_variants = define_formation_variants(names)
solve_dp(calendar_puzzle, formation_variants, for_solution=True)
if __name__ == "__main__":
run()
2 思路细节
未完待续