程序员的算法趣题Q65: 图形的一笔画

1. 问题描述

2. 解题分析

3*4的网格共有12个格子，每个格子可以任选以上4种模块之一，共有4^12=16777216种。嗯，相当惊人的一个基数，没有有效的缩小范围或者计算优化策略的话，会需要化很长的时间。不过，先来一个最基本的方案吧—先确保温饱，再追求小康。。。

2.1 一笔画的条件

这是一个图论中的一个经典问题。可以追溯到哥尼斯堡七桥问题，当年欧拉大神以解决这个问题为契机创立了图论这一数学分支。事实上，这个问题还有个炫酷的名字叫做欧拉路径问题：欧拉路径就是一条能够不重不漏地经过图上的每一条边的路径。进一步，而若这条路径的起点和终点相同，则将这条路径称为欧拉回路。

关于图论就不瞎BB了（说多了怕露馅^-^），简单地说结论：对于一个无向连通图，（边的）无重复遍历的充要条件是度数为奇数的顶点的个数为0或者2。“连通图的边的无重复遍历”的通俗版本就是一笔画。其中度数就是每个顶点所连接的边的个数。“有向图”是什么情况不记得了，反正跟本题无关，先不管了。

这个知识点是解决本问题的先决条件。当然即便不知道这个知识点也是可以解的，就是针对每个图形去做遍历搜索也是可以判定是否满足一笔画的条件，但是那样的话你需要的计算时间就会再高几个数量级。

2.2 各模块的顶点度数

上面所述4种图形的4个顶点的度数分别为（[左上顶点，右上顶点，左下顶点，右下顶点}）：

左上模块：{2,2,2,2}

右上模块：{3,2,2,2}

左下模块：{2,3,3,2}

右下模块：{3,3,3,3}

注意，右下模块的中间还有一个顶点，但是该顶点的度数为4，不会影响一笔画判断，所以可以忽略。

2.3 如何计算整个拼图的各顶点度数

可以分三大类顶点考虑：

第1类：四个角顶点(corner vertex)

其度数只跟一个块有关。比如说左上角顶点的度数就是左上角块的左上角顶点的度数；右上角顶点的度数就是右上角块的右上角顶点的度数；。。。余者类推

第2类：四条边上的顶点(edge vertex)

其度数跟两个块有关，是两个块的对应顶点的度数之和减1（因为有一条边重叠了）。至于对应顶点是哪个，取决于是在那条边上。

第3类：中间的顶点(interior vertex)

其度数跟上下左右的四个块有关，是四个块的对应顶点的度数之和减4（因为共4条边重叠了）。四个块的对应顶点分别是左上块的右下顶点，右上块的左下顶点，左下块的右上顶点，右下块的左上顶点。

2.4 算法流程

粗暴的遍历循环。。。

在统计某一种拼图模式的奇度数的顶点个数时，如果超过了2就表明肯定无法一笔画，可以提前退出。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Tue Oct 26 07:39:28 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
from   collections import deque
import itertools as it
import numpy as np

print(__doc__)

H = 3
W = 4
block_degrees = np.array([[2,2,2,2],  # top-left, top-right, bottom-left, bottom-right
                          [3,2,2,3],
                          [2,3,3,2],
                          [3,3,3,3]])

tStart  = time.perf_counter()     
ok_count = 0
for k,cfg in enumerate(it.product([0,1,2,3],repeat=H*W)):    
    # Generate a new board configuration
    board = np.reshape(np.array(cfg),(H,W))
    # print(board)
    if k%100000 == 0:
        print('k = ',k)

    
    # Count the degrees of each vertex
    num_of_odd_degree = 0
    bad_cfg = False
    for i in range(H+1):
        for j in range(W+1):
            if (i,j) == (0,0): # top-left corner vertex
                num_degrees = block_degrees[board[0,0],0]
            elif (i,j) == (0,W):# top-right corner vertex
                num_degrees = block_degrees[board[0,W-1],1]
            elif (i,j) == (H,0):# bottom-left corner vertex
                num_degrees = block_degrees[board[H-1,0],2]
            elif (i,j) == (H,W):# bottom-right corner vertex
                num_degrees = block_degrees[board[H-1,W-1],3]
            elif i==0:#top edge vertexs
                num_degrees = block_degrees[board[0,j-1],1] + block_degrees[board[0,j],0] - 1
            elif i==H:#bottom edge vertexs
                num_degrees = block_degrees[board[H-1,j-1],3] + block_degrees[board[H-1,j],2] - 1
            elif j==0:#left edge vertexs
                num_degrees = block_degrees[board[i-1,0],2] + block_degrees[board[i,0],0] - 1
            elif j==W:#right edge vertexs
                num_degrees = block_degrees[board[i-1,W-1],3] + block_degrees[board[i,W-1],1] - 1
            else: # Interior vertexs
                num_degrees  = block_degrees[board[i-1,j-1],3]  #up-left block
                num_degrees += block_degrees[board[i-1,j],2]    #up-right block
                num_degrees += block_degrees[board[i,j-1],1]    #down-left block
                num_degrees += block_degrees[board[i,j],0]      #down-right block
                num_degrees -= 4
            
            if num_degrees%2 == 1:
                num_of_odd_degree += 1
            if num_of_odd_degree > 2:
                bad_cfg = True
                break
        if bad_cfg:
            break
    if not(bad_cfg or num_of_odd_degree==1):
        ok_count += 1

tCost  = time.perf_counter() - tStart
print('(H,W)=({0},{1}), count={2}, tCost={3:6.3f}(sec)'.format(H,W,ok_count,tCost))
                        

输出：(H,W)=(3,4), count=6400, tCost=215.661(sec)

4. 后记

运行很慢，在预料之中。

欲知如何优化，且听下回分解。。。