程序员的算法趣题Q18: 水果酥饼日

时间：12-26来源：作者：点击数：56

1. 问题描述

日本每月的 22 日是水果酥饼日。因为看日历的时候， 22 日的上方刚好是 15日，也就是“‘22’这个数字上面点缀着草莓”(如果将日语的 15 拆为 1 和 5发音[イチゴ]，则与日语“草莓[イチゴ]”一词发音相同，而水果酥饼中最为著名的就是草莓酥饼)

切分酥饼的时候，要求切分后每一块上面的草莓个数都不相同。假设切分出来的 N 块酥饼上要各有“1~N 个（共 N(N ＋ 1)÷2 个草莓）”。但这里要追加一个条件，那就是“一定要使相邻的两块酥饼上的数字之和是平方数”。

举个例子，假设 N ＝ 4 时采用如下图的切法。这时，虽然 1 ＋ 3 ＝4 得到的是平方数，但“1 和 4” “2和 3” “2 和 4”的部分都不满足条件。

2. 解题分析--深度优先搜索

本题等价于这样一个问题：求[1…N]的一个圆排列（circular permutation）,使得任意相邻两个数之和为完全平方数。

作为一个直观的办法，可以考虑遍历[1,…,N]的圆排列，然后检验每一个圆排列是否满足条件。然后对N进行从小到大遍历，直到找到一个N使得对于这个N存在一个满足条件的圆排列。但是对于N来说，圆排列数等于(N-1)!(注意，由于圆排列的对称性，如果只考虑各个数的相对位置的话，N个线性排列对应于同一个圆排列)。对于略大的N这个需要遍历的排列数将无法忍受。

本题可以用深度优先搜索算法来解决。除了问题的表象以外，本题作为一个深度优先搜索问题与Q14非常相似，可以用几乎相同的方式解决。

从1开始，寻找与它的和能构成完全平方数的数（看作是1的子节点），然后针对1的子节点进一步寻找与它的和能构成完全平方数的子节点。。。

一个圆排列对应一个深度优先搜索路径。由于在圆排列中每个数只能用一次，所以用used和unused分别表示已经使用的数和尚未使用的数。进一步的exploration仅从unused中选取下一个探索对象，因此省掉了“是否已被访问过”的检查判断，另一方面，used是按照访问顺序存入被访问对象，所以其中存储的就是当前搜索的接龙顺序。used和unused都需要以栈的方式进行管理，因此如果用递归调用的方式实现的话，将它们作为递归函数的接口参数传递即可；如果用循环方式实现的话，则需要注意显式的入栈和出栈管理。

如果used的长度等于N，并且首尾的和也是完全平方数的话就表示找到了一个符号条件的圆排列。此时的used中存储的就是对应的圆排列。

与Q14不同的是，从任何一点开始搜索圆排列都是等价的，所以不需要针对起点遍历，固定从1开始即可。

算法流程（python-style伪代码）如下图所示：

以下是针对N=10和N=20的笔算示意图（如果可能的话，在纸上进行一些计算有助于建立对问题的直观感觉，我认为是非常有用。只不过N=20时居然能走这么远一开始没想到，否则的话可能就不敢挑战了）。

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Tue Sep  7 07:11:00 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
import itertools as it

class Solution:
    def cutFruitCake(self, N:int)->(bool,List):
        """
        Given an integer, find one circular permutation of 1...N, satisfying 
        the condition that the sum of each pair of neighbours is one complete 
        square number

        Parameters
        ----------
        N : int. 

        Returns : True or False to indicate whether such circular permutation exists, 
        and if True, the circular permutation        
        -------

        """
        squNum = [k*k for k in range(N)]
        def explore(used, unused):
            if len(used)==N and (used[0]+used[-1]) in squNum:
                # print(used)
                return True, used
            
            cur = used[-1]
            cutOK = False
            for k,nxt in enumerate(unused):
                if cur+nxt in squNum:
                    cutOK,finalCut = explore(used+[nxt], unused[:k]+unused[k+1:])
                    if cutOK:
                        return True,finalCut
            return False,[]
        used = [1]
        unused = [k for k in range(2,N+1)]
        return explore(used,unused)
    
if __name__ == '__main__':        
            
    sln    = Solution()            

    tStart = time.time()
    N = 2
    while (1):    
        cutOK, finalCut = sln.cutFruitCake(N)
        if cutOK:
            break
        print('N = {0}: Fail'.format(N))
        N += 1
        
    tCost  = time.time() - tStart
    print('The minimum integer satisfying the condition is:\nN={0}, tCost = {1:6.3f}(sec)'.format(N,tCost))   
    print('finalCut = {0}'.format(finalCut))