2021圣诞拼图活动-Writeup

活动截止前排名

在活动结束后，2021/12/26 22:24:41，yy 选手以2222835ms的成绩跃居第 3 名。谢谢参与我们的活动，顺位为第 5 名。

题目介绍

做题者需要提交一条路径，使图块能复原成功。路径由UDLR字符组成，上为 U 下为 D 左为 L 右为 R，路径长度限制在80字符以内。

接下来分享下各位的 writeup。

f11st's wp

登录后拿到题目，4*4 拼图，难度不大。先上 PS 切分图片，给每个图块按顺序加标注，然后手动拼图后得到图块真实位置的索引（真·人工智能

搜索完成，共用时：2.600806474685669 秒
RRDDRDLULURRULDLDLUURRRDLLDRULDDRULUURDRULLDRRDLLLDRURULLDDRULURRDLDRURU
所需步数为：72
共搜索状态数：3927

# A*代码来自于https://github.com/Alec-lt/Puzzle_Game
# main.py
from State import Node, MinBinHeapq, Step
import time
from copy import deepcopy


class Solution():
    def __init__(self, puzzle):
        # 列表元素总数，分块总数
        self.number = 16
        # 图的数组保存形式
        self.map = puzzle
        # 白块的位置
        self.white = -1

        # 方向
        # 0  1  2  3
        # 上 下 左 右
        self.direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        self.step_direction = [0, 1, 2, 3]

        # 分割维度
        self.dim = 4

        # A_star算法相关变量
        self.fac = []
        self.step_dict = {}
        self.hash_visited = {}
        self.steps = []
        self.ai_fac()

        # 计数君
        self.hhhh = 0

    def ai_manhattan(self, map_list=[]):
        """
        曼哈顿距离计算
        :return: distance
        """
        distance = 0
        for i in range(self.dim*self.dim):
            if map_list[i] == 0:
                continue
            cx = int(i / self.dim)
            cy = int(i % self.dim)
            gx = int((map_list[i]-1) / self.dim)
            gy = int((map_list[i]-1) % self.dim)
            distance += (abs(cx-gx) + abs(cy-gy))

        return 10 * distance

    def ai_fac(self):
        """
        计算阶乘数列
        :return: None
        """
        self.fac.append(1)
        for i in range(1, 26):
            self.fac.append(i*self.fac[i-1])

    def ai_to_hash(self, state=[]):
        """
        哈希化
        :param state: 状态数组
        :return: 哈希值
        """
        result = 0
        length = len(state)

        for i in range(length):
            k = 0
            for j in range(i+1, length):
                if state[i] > state[j]:
                    k += 1
            result = result + k*self.fac[length-i-1]

        return result

    def ai_step_print(self, hash_node):
        k = self.step_dict.get(hash_node)
        if k.pre == -1:
            return
        self.ai_step_print(k.pre)
        self.steps.append(k.ch)

    def ai_a_star(self):
        """
        执行A_star算法
        :return: None
        """

        q = MinBinHeapq()
        sta = Node(self.map)
        old_hash = self.ai_to_hash(sta.map)
        new_step = Step(-1, -1)
        self.step_dict.setdefault(old_hash, deepcopy(new_step))
        self.hash_visited.setdefault(old_hash, 1)

        q.push(deepcopy(sta))

        while not q.empty():
            self.hhhh += 1
            sta = deepcopy(q.pop())

            if sta.man_distance == -1:
                sta.man_distance = self.ai_manhattan(sta.map)

            if sta.man_distance == 0:
                self.ai_step_print(self.ai_to_hash(sta.map))
                break

            s = sta.map.index(0)
            sx = int(s / self.dim)
            sy = int(s % self.dim)
            old_man_distance = sta.man_distance
            old_g_value = sta.g_value
            old_hash = self.ai_to_hash(sta.map)

            for i in range(4):

                mi = sx + self.direction[i][0]
                mj = sy + self.direction[i][1]

                if mi < 0 or mi >= self.dim or mj < 0 or mj >= self.dim:
                    continue

                m = mi * self.dim + mj

                sta.map[s], sta.map[m] = sta.map[m], sta.map[s]

                # 通过字典 查看哈希值(状态)是否被访问过
                new_hash = self.ai_to_hash(sta.map)

                if self.hash_visited.get(new_hash) is None:
                    self.hash_visited.setdefault(new_hash, 1)

                    sta.man_distance = self.ai_manhattan(sta.map)
                    sta.g_value = old_g_value + 1

                    new_step.pre, new_step.ch = old_hash, i
                    self.step_dict.setdefault(new_hash, deepcopy(new_step))

                    q.push(deepcopy(sta))

                    sta.man_distance = old_man_distance
                    sta.g_value = old_g_value

                sta.map[s], sta.map[m] = sta.map[m], sta.map[s]

            del sta

        self.hash_visited.clear()
        del q

    def ai_work(self):
        """
        自动还原展示
        步数依据：self.steps = [...]
        :return: None
        """

        # 步数的相关数据清空
        self.step_dict.clear()
        self.steps.clear()

        self.white = self.map.index(0)

        start = time.time()
        self.ai_a_star()
        end = time.time()
        print('搜索完成，共用时：', (end - start), '秒')
        # print(self.steps)
        desc = ''
        for i in self.steps:
            if i == 0:
                desc += 'D'
            elif i == 1:
                desc += 'U'
            elif i == 2:
                desc += 'R'
            elif i == 3:
                desc += 'L'
        print(desc)
        print('所需步数为：', len(self.steps))
        print('共搜索状态数：', self.hhhh)
        self.hhhh = 0


if __name__ == '__main__':
    s = Solution([5, 1, 6, 8, 2, 11, 7, 13, 15, 14, 3, 4, 10, 16, 12, 0])
    s.ai_work()

# State.py
import gc


class Node(object):
    def __init__(self, map_list=[], man_distance=-1, g_value=0):
        """
        结点类  (i, j)为白块的位置
        :param map_list: 存取状态
        :param man_distance: 曼哈顿距离
        """
        self.map = map_list[:]
        self.man_distance = man_distance
        self.g_value = g_value


class Step(object):
    def __init__(self, pre=-1, ch=-1):
        """
        步类
        :param pre: 上一个步类结点
        :param ch: 方向
        """
        self.pre = pre
        self.ch = ch


class MinBinHeapq(object):
    """
    最小堆
    """
    def __init__(self):
        self.size = 0
        self.data = []

        node = Node()
        self.data.append(node)

    def pre_up(self, i):
        """
        上升结点
        :param i: 上升的结点编号
        :return:  void
        """
        while i // 2 > 0:
            if self.data[i].man_distance + self.data[i].g_value < self.data[i // 2].man_distance + self.data[i // 2].g_value:
                self.data[i // 2], self.data[i] = self.data[i], self.data[i // 2]
            i = i // 2

    def push(self, k):
        """
        插入结点操作
        :param k: 插入结点类
        :return: void
        """
        self.data.append(k)
        self.size += 1
        self.pre_up(self.size)

    def pre_down(self, i):
        """
        元素下潜
        :param i: 当前元素编号
        :return: void
        """
        while (i*2) <= self.size:
            mc = self.min_child(i)
            if self.data[i].man_distance + self.data[i].g_value > self.data[mc].man_distance + self.data[mc].g_value:
                self.data[i], self.data[mc] = self.data[mc], self.data[i]
            i = mc

    def min_child(self, i):
        """
        寻找最小的子孩子
        :param i: 当前结点的编号
        :return: 最小孩子的编号
        """
        if i * 2 + 1 > self.size:
            return i * 2
        else:
            if self.data[i*2].man_distance + self.data[i*2].g_value < self.data[i*2 + 1].man_distance + self.data[i*2 + 1].g_value:
                return i * 2
            else:
                return i * 2 + 1

    def pop(self):
        """
        弹出元素，先把头一个存一下，用最后一个的值赋值
        删除最后一个元素，最后再进行元素下潜
        :return: 结点类
        """
        value = self.data[1]
        self.data[1] = self.data[self.size]
        self.size = self.size - 1
        self.data.pop()
        # gc.collect()
        return value

    def empty(self):
        """
        判空
        :return: 空 True 非空 False
        """
        if self.size == 0:
            return True
        return False

crystal's wp

接下来是解题阶段：

这是个经典的拼板游戏，叫 15puzzle。把每一个方块编号：从左到右从上到下依次是 1-16号。

[[3,6,9,4],[2,15,7,10],[13,5,16,11],[14,1,12,8]]

这里为了让程序能跑需要变了一下，把黑色用 0（0 代表可移动的位置）代替，把 16 和黑色原本的编号换一下就是；

[[3,6,9,4],[2,15,7,10],[13,0,5,11],[14,1,12,8]]

[[1, 2, 3, 4], [0, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 5]]

具体的解法是用 a* 算法。可参考 github 上的代码。

输出结果需要经过转化，最终输出题目要求的格式

（编者注：由于篇幅原因不贴代码了）

gorgeousdays' wp

基本采用半代码加半人工的方式来实现。

下载原图，采用 cv2 进行分隔得到 16 张小图，通过图的上下左右四边的像素，并计算 16 张图片之间的相似度，加以人工分析得到图片的正确顺序，最后复原得到原图。得到原 index 与 1-16index 之间的对应关系。

import cv2
import numpy as np
import matplotlib.pyplot as plt
img=cv2.imread("chamd5.png")
img.shape


for i in range(4):
    for j in range(4):
        temp_img = np.zeros([125, 125, 3], np.uint8)
        temp_img=img[125*i:125*(i+1),125*j:125*(j+1)]
        cv2.imwrite("imgs/img"+str(i)+str(j)+".jpg",temp_img)

index=[]
left=[]
right=[]
up=[]
down=[]
for i in range(4):
    for j in range(4):
        temp_img=cv2.imread("imgs/img"+str(i)+str(j)+".jpg")
        index.append(i*4+j+1)
        left.append(temp_img[63][0])
        right.append(temp_img[63][124])
        up.append(temp_img[0][63])
        down.append(temp_img[124][63])
 
temp_img=cv2.imread("imgs/img"+str(0)+str(0)+".jpg")
plt.imshow(temp_img)

def diff(pixel1,pixel2):
    return (int(pixel1[0])-int(pixel2[0]))**2+(int(pixel1[1])-int(pixel2[1]))**2+(int(pixel1[2])-int(pixel2[2]))**2

ban=11
def getleft(index,left,right):
    min_value=1e5
    right_index=-1
    for i in range(16):
        if(i==index or i==ban):
            continue
        if(diff(left[index],right[i])<min_value):
            min_value=diff(left[index],right[i])
            right_index=i
    print("pic "+str(index)+" 's' left is pic "+str(right_index)+" and the diff value is "+str(min_value))
    return (right_index,min_value)
def getright(index,left,right):
    min_value=1e5
    left_index=-1
    for i in range(16):
        if(i==index or i==ban):
            continue
        if(diff(right[index],left[i])<min_value):
            min_value=diff(right[index],left[i])
            left_index=i
    print("pic "+str(index)+" 's' right is pic "+str(left_index)+" and the diff value is "+str(min_value))
    return (left_index,min_value)
def getup(index,up,down):
    min_value=1e5
    up_index=-1
    for i in range(16):
        if(i==index or i==ban):
            continue
        if(diff(up[index],down[i])<min_value):
            min_value=diff(up[index],down[i])
            up_index=i
    print("pic "+str(index)+" 's' up is pic "+str(up_index)+" and the diff value is "+str(min_value))
    return (up_index,min_value)
def getdown(index,up,down):
    min_value=1e5
    down_index=-1
    for i in range(16):
        if(i==index or i==ban):
            continue
        if(diff(down[index],up[i])<min_value):
            min_value=diff(down[index],up[i])
            down_index=i
    print("pic "+str(index)+" 's' down is pic "+str(down_index)+" and the diff value is "+str(min_value))
    return (down_index,min_value)

ans_left=[]
ans_right=[]
ans_up=[]
ans_down=[]
for i in range(16):
    if(i==ban):
        ans_left.append((-1,0))
        continue
    ans_left.append(getleft(i,left,right))
for i in range(16):
    if(i==ban):
        ans_right.append((-1,0))
        continue
    ans_right.append(getright(i,left,right))
for i in range(16):
    if(i==ban):
        ans_up.append((-1,0))
        continue
    ans_up.append(getup(i,up,down))
for i in range(16):
    if(i==ban):
        ans_down.append((-1,0))
        continue
    ans_down.append(getdown(i,up,down))
    
for i in range(16):    
    flag=0
    if(ans_down[i][1]>1000):
        flag+=1
    if(ans_down[i][1]>1000):
        flag+=1
    if(ans_down[i][1]>1000):
        flag+=1
    if(ans_down[i][1]>1000):
        flag+=1
    if(flag>2):
        print(i)

import numpy as np
import cv2
import matplotlib.pyplot as plt
# splicing the images
img = np.zeros([500, 500, 3], np.uint8)
#true_index=[12,10,7,1,11,5,3,4,6,7,8,9,0,13,14,15,2]
#true_index=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
true_index=[9,5,1,3,13,11,15,4,2,16,12,6,14,7,10,8]
true_index=[i-1 for i in true_index]
for i in range(4):
    for j in range(4):
        temp_img=cv2.imread("imgs\img"+str(i)+str(j)+".jpg")
        index=true_index[i*4+j]
        true_i=int(index/4)
        true_j=int(index%4)
        print(true_i,true_j)
        img[125*true_i:125*(true_i+1),125*true_j:125*(true_j+1)]=temp_img[:,:]
cv2.imwrite("trueimg.jpg",img)
plt.imshow(img)

以上代码实现功能为图片的复原。

from random import *   
from tkinter import *   
step_number = 0     #设置步数的变量，初始值为0
def Button_Click_2(x,y):      #按钮点击事件函数
        """声明空白按钮行列号和步数的变量为全局变量"""
        global row_of_space  
        global col_of_space    
        global step_number
        """判断判断点击按钮旁是否为空白按钮，是则交换位置"""
        if abs(x-row_of_space) + abs(y-col_of_space) == 1:  
            step_number += 1    #将步数赋值
            label_step_number['text'] = '步数:' + str(step_number)  #将步数变量导入label控件
            """交换按钮位置"""
            buttons[row_of_space,col_of_space]['text'] = buttons[x,y]['text']
            if(row_of_space>x and col_of_space==y):
                print("D")
            elif(row_of_space<x and col_of_space==y):
                print("U")
            elif(row_of_space==x and col_of_space>y):
                print("R")
            elif(row_of_space==x and col_of_space<y):
                print("L")
            buttons[x,y]['text']  = ' ' 
            row_of_space = x            
            col_of_space = y
            n = 0  
            for row in range(4):
                for col in range(4):
                    """对比所有按钮序列是否正确，不正确则跳出函数"""
                    if buttons[row,col]['text'] != numbers[n]:  
                        return
                    n += 1
            """所有按钮判断完毕赢得游戏胜利"""
            label_welcomes['text'] = '你赢了'
 
"""创建华容道游戏窗口"""
root = Tk()                      #创建图形化用户界面实例
root.title('数字华容道')         #设置窗口标题
root.geometry("400x400")    #将窗口大小设为高400宽400
root.configure(bg = 'black') #将窗口背景设为黑色
root.resizable(width = False,height = False)    #设置窗口为不可拉伸
"""设置欢迎语的label控件"""
label_welcomes = Label(root,text = '欢迎来到数字华容道',bg = 'black',fg = 'red',font = ("Arial",13))    #设置label控件的属性
label_welcomes.place(x = 20,y = 10,width = 250,height = 40)  #设置label控件位置
"""设置显示操作方式的label控件"""
label_operation = Label(root,text = '单击数字',bg = 'black',fg = 'white',font = ("Arial",10))
label_operation.place(x = 3,y = 40,width = 50,height = 30)
label_operation_2 = Label(root,text = '移动方块',bg = 'black',fg = 'white',font = ("Arial",10))
label_operation_2.place(x = 3,y = 60,width = 50,height = 30)
"""设置显示步数的label控件"""
label_step_number = Label(root,text = '步数:' + str(step_number),bg = 'black',fg = 'yellow',font = ("Arial",10))
label_step_number.place(x = 3,y = 20,width = 50,height = 30)
 

root.attributes("-topmost", True)
row_of_space = 0    #存放空白按钮的行号 
col_of_space = 0    #存放空白按钮的列号
buttons = {}      #存放数字按钮的数组
numbers = ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15',' '] #所有数字文本的列表 
shuffle(numbers)     #打乱数字列表中的数字顺序

numbers=['8','10','7','14','6','12','16','2','4','15',' ','13','3','1','5','9']
"""制造数字华容道方阵"""

for row in range(4): 
    for col in range(4):
        """创建数字按钮，并将行列号传入该按钮的点击事件函数"""
        button = Button(root,command = lambda x = row,y = col:Button_Click_2(x,y),bg = 'black',fg = 'green',font = ("Arial",35))
        buttons[row,col] = button   #将按钮导入数组
        button['text'] = numbers.pop()    #设置按钮上的文本
        button.place(x = 60 + col * 60,y = 60 + row * 60,width = 50,height = 50)    #设置数字按钮大小
        if button['text'] == ' ':        #判断是否为空白按钮，如果是，则记录到空白按钮行列号变量
            row_of_space = row
            col_of_space = col
numbers = ['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15',' ']   #还原数字列表 
root.mainloop() #显示窗口

solazola's wp

1. 可以不断reset，找一张比较容易拼的，然后用打印机打印出来。

3. 自己先把这十六个拼成最终图形，然后依次标上号码（从1到16），然后还原成题目初始的图形再拼。这样做的好处是，不用盯着图形拼了（图形不好分辨），只盯着数字拼就可以。

小时候玩过这种实体拼图板。全凭感觉拼。一小时怎么着也能拼出来了。如果想快的的话，b 站搜"数字华容道"。有很多技巧可以加快速度。

yy's wp

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/