九宮格（Lo Shu Square）問(wèn)題

將1到9的數(shù)字按照一定方式填入九宮格內(nèi)。使得每一列、每一行以及兩條對(duì)角線上的值都相等。

在重慶等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專(zhuān)注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè) 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站策劃,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),營(yíng)銷(xiāo)型網(wǎng)站建設(shè),外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè),重慶網(wǎng)站建設(shè)費(fèi)用合理。

全排列（遞歸）

首先，用枚舉法，生成各種(3, 3)的二維數(shù)組：

def perm(li):
    """遞歸實(shí)現(xiàn)列表的全排列
    如果輸入是[1]，那么返回[[li],]表示有一種排列
    如果輸入是[1, 2]，期望的返回的是[[1, 2], [2, 1]]，這是要之后的遞歸實(shí)現(xiàn)的
    """
    if len(li) <= 1:
        return [li]
    ret = []
    for i in range(len(li)):
        s1 = li[i:i + 1]  # 取出一個(gè)元素，組成一個(gè)列表
        rest = li[:i] + li[i + 1:]  # 剩余的元素組成一個(gè)列表
        p = perm(rest)
        for j in p:  # 迭代每一種排列
            ret.append(s1 + j)  # 和之前取出的1個(gè)元素進(jìn)行拼接
    return ret

簡(jiǎn)單驗(yàn)證一下：

>>> perm([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

遞歸算法比較費(fèi)時(shí)，如果是9個(gè)數(shù)字的全排列，要1秒左右。如果數(shù)組更大比如(4, 4)就幾乎跑不完了：

995 ms ± 12.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

檢查函數(shù)

各種求和，然后進(jìn)行檢查：

def is_lo_shu_square(arr):
    """接收numpy的二維數(shù)組"""
    if np.shape(arr)[0] != np.shape(arr)[1]:
        return  False
    d = np.shape(arr)[0]
    n = np.sum(arr) / d
    for i in np.sum(arr, axis=0):
        if i != n:
            return False
    for i in np.sum(arr, axis=1):
        if i != n:
            return False
    if np.sum(np.eye(d, dtype=int) * arr) != n:  # 檢查對(duì)角線
        return False
    if np.sum(np.eye(d, dtype=int)[::-1] * arr) != n:  # 檢查次對(duì)角線
        return False
    return True

簡(jiǎn)單驗(yàn)證一下：

>>> np.array(([1, 1], [1, 1]))
array([[1, 1],
       [1, 1]])
>>> a = np.array(([1, 1], [1, 1]))
>>> is_lo_shu_squar(a)
True

計(jì)算結(jié)果

>>> li = [i+1 for i in range(9)]
>>> for i in perm(li):
    a = np.array(i).reshape(3, 3)
    if is_lo_shu_square(a):
        print(a)

[[2 7 6]
 [9 5 1]
 [4 3 8]]
[[2 9 4]
 [7 5 3]
 [6 1 8]]
[[4 3 8]
 [9 5 1]
 [2 7 6]]
[[4 9 2]
 [3 5 7]
 [8 1 6]]
[[6 1 8]
 [7 5 3]
 [2 9 4]]
[[6 7 2]
 [1 5 9]
 [8 3 4]]
[[8 1 6]
 [3 5 7]
 [4 9 2]]
[[8 3 4]
 [1 5 9]
 [6 7 2]]

全排列（非遞歸）

標(biāo)準(zhǔn)庫(kù)itertools里提供了排列的函數(shù)，算法比較復(fù)雜j就不研究了，順便還有組合的函數(shù)：

import itertools
>>> list(itertools.permutations([1, 2, 3], 3))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
>>> list(itertools.combinations([1, 2, 3], 2))
[(1, 2), (1, 3), (2, 3)]

計(jì)算還是一樣的：

>>> li = [i+1 for i in range(9)]
>>> for i in itertools.permutations(li, 9):
    a = np.array(i).reshape(3, 3)
    if is_lo_shu_square(a):
        print(a)

[[2 7 6]
 [9 5 1]
 [4 3 8]]
[[2 9 4]
 [7 5 3]
 [6 1 8]]
[[4 3 8]
 [9 5 1]
 [2 7 6]]
[[4 9 2]
 [3 5 7]
 [8 1 6]]
[[6 1 8]
 [7 5 3]
 [2 9 4]]
[[6 7 2]
 [1 5 9]
 [8 3 4]]
[[8 1 6]
 [3 5 7]
 [4 9 2]]
[[8 3 4]
 [1 5 9]
 [6 7 2]]

整個(gè)計(jì)算過(guò)程的執(zhí)行時(shí)間大致是從8秒提高到了6秒。時(shí)間上沒(méi)有本質(zhì)的區(qū)別，并且如果要去計(jì)算更大的列表的全排列，比如16個(gè)元素的，兩種算法都是執(zhí)行不完的。
不過(guò)非遞歸算法節(jié)省內(nèi)存，整個(gè)過(guò)程中內(nèi)存的分配不會(huì)有大的變化。而遞歸算法對(duì)內(nèi)存的開(kāi)銷(xiāo)是巨大的。

16宮格

上面的算法雖然也支持計(jì)算16宮格，但是算法復(fù)雜度太高，至少我的電腦上運(yùn)行不出結(jié)果來(lái)。第一步16個(gè)元素的全排列就計(jì)算不完，2億億次（16! = 20,922,789,888,000）。
很明顯有些情況計(jì)算之后就能排除很多類(lèi)似的情況。

數(shù)字分組（行的和相等）

先把16個(gè)數(shù)，分成4組，每組的和都相等，這就是將來(lái)每行的數(shù)字的集合：

def square_list(d):
    """選項(xiàng)4組數(shù)組，每組數(shù)組組成一行，并且和相等
    返回所有行的和都符合的二維元祖
    """
    nums = [i + 1 for i in range(d * d)]
    sum_line = sum(nums) // d
    # lines = itertools.combinations(nums, d)  # 4階共有1820個(gè)
    lines = (i for i in itertools.combinations(nums, d) if sum(i) == sum_line)  # 篩選后4階共有86個(gè)

    for square in itertools.combinations(lines, d):
        s = set()
        for line in square:
            for n in line:
                s.add(n)
        if len(s) == d*d:
            yield square  # 4階共有392個(gè)

這步能篩選出392種組合等待續(xù)操作。

調(diào)整每行的元素排列（列的行相等）

把上面的每種組合用下面的方法再做一次遍歷。每行的數(shù)字互相調(diào)整位置，使得每列的和也相等：

def square_list2(square, sum_line=None, skip=0, squares=None):
    """調(diào)整每行數(shù)字的排列，找到能使每列數(shù)字之和也相等的二維元祖
    返回的是所有列的和也都符合的二維元祖，
    這步之后4階能篩選出22896個(gè)
    :param square:
    :param sum_line: 第一次遞歸的時(shí)候計(jì)算出來(lái)
    :param skip: 第一次調(diào)整第0列，之后遞增
    :return:
    """
    column_count = len(square[0])
    if skip >= column_count:  # 遞歸的退出條件
        if squares is None:
            squares = []
        squares.append(square)
        return squares
    row_count = len(square)
    if sum_line is None:
        sum_line = sum(square[0])
    # 遍歷所有的情況，交換元素直到一列的和等于sum_line，
    # 然后遞歸調(diào)用處理后面的列，直到處理完所有的列
    for li in index_list(row_count, column_count-skip):
        sq = [list(i) for i in square]
        sum_list = []
        for i in range(row_count):
            sum_list.append(sq[i][li[i]+skip])
        if sum(sum_list) == sum_line:
            for j in range(row_count):
                sq[j][0+skip], sq[j][li[j]+skip] = sq[j][li[j]+skip], sq[j][0+skip]
            sq_tpl = tuple((tuple(i) for i in sq))
            squares = square_list2(sq_tpl, sum_line, skip + 1, squares)
    return squares

def index_list(lenth, notation):
    """返回一個(gè)下標(biāo)的列表
    被square_list2調(diào)用，遍歷每一行取一個(gè)值的所有情況
    """
    counter = 0
    while True:
        n = counter
        li = []
        for i in range(lenth):
            n, index = divmod(n, notation)
            li.append(index)
        if n == 0:
            yield li[::-1]
            counter += 1
        else:
            break

這里用了遞歸。另外遍歷下標(biāo)的index_list函數(shù)用了取模取余的方式，做的是類(lèi)似10進(jìn)制轉(zhuǎn)4進(jìn)制，然后每一位就是一個(gè)下標(biāo)，最后把列表反轉(zhuǎn)之后返回了。
最后一個(gè)篩選出22896個(gè)數(shù)組，每個(gè)都是行和列的和都相等的。

調(diào)整行之間的排序（斜線相等）

這步不做計(jì)算了，只是遍歷。一個(gè)4行調(diào)整行之間的排列，一共是24種排列，也就是之前的基礎(chǔ)上的24倍的量，還是可以接受的。這里就是4個(gè)元素的全排列了：

def square_list3(square):
    """調(diào)整行與行之間的排列順序，
    4階的全排列是24種情況，所以會(huì)再多24倍數(shù)的情況要遍歷
    每行以及每列的和都相等了，這樣調(diào)整會(huì)影響到斜線計(jì)算的結(jié)果"""
    return itertools.permutations(square, 4)

驗(yàn)證函數(shù)

之前已經(jīng)把可能符合條件的數(shù)組篩選到五十多萬(wàn)個(gè)了，這里只要再寫(xiě)一個(gè)函數(shù)做最終的驗(yàn)證就能把結(jié)果篩選出來(lái)了。這里要驗(yàn)證行的和、列的和、斜線的和。斜線的和不只是對(duì)角線，每個(gè)方向4條斜線一共8條斜線。另外再驗(yàn)證4個(gè)角和中心4塊的和，不過(guò)這2步不影響結(jié)果，行和列是之前的篩選條件，也不影響結(jié)果，只是驗(yàn)證結(jié)果正確。只要是通過(guò)斜線的計(jì)算把不符合的再篩掉一批：

def is_lo_shu_square4(arr):
    """接收numpy的二維數(shù)組"""
    if np.shape(arr)[0] != np.shape(arr)[1]:
        return False
    d = np.shape(arr)[0]
    n = np.sum(arr) / d
    for i in np.sum(arr, axis=0):
        if i != n:
            return False
    for i in np.sum(arr, axis=1):
        if i != n:
            return False
    # 檢查所有的斜線，包括對(duì)角線
    for i in range(d):
        if np.sum((np.eye(d, k=i, dtype=int) + np.eye(d, k=i-d, dtype=int)) * arr) != n:
            return False
        if np.sum((np.eye(d, k=i, dtype=int)[::-1] + np.eye(d, k=i-d, dtype=int)[::-1]) * arr) != n:
            return False
    # 到此能找到384個(gè)
    # 檢查4個(gè)角的4個(gè)數(shù)的和也要符合要求，不影響結(jié)果
    if np.sum(arr[:2, :2]) != n:
        return False
    if np.sum(arr[:2, -2:]) != n:
        return False
    if np.sum(arr[-2:, :2]) != n:
        return False
    if np.sum(arr[-2:, -2:]) != n:
        return False
    # 在檢查最中間的4個(gè)格子的和，不影響結(jié)果
    if np.sum(arr[1:3, 1:3]) != n:
        return False
    return True

48個(gè)完美解

所有符合要求的數(shù)組一共384個(gè)，這里只輸出(0, 0)和(1, 1)的位置上是1的48個(gè)數(shù)組：

def main():
    count = 0
    for square in square_list(4):
        # 有可能返回空，因?yàn)椴皇敲恳环N組合都一定能得到豎排和相等的矩陣
        squares2 = square_list2(square)
        if squares2:
            for square2 in squares2:
                for square3 in square_list3(square2):
                    a = np.array(square3)
                    if is_lo_shu_square4(a):
                        if a[0][0] == 1 or a[1][1] == 1:
                            count += 1
                            print(a)
    print(count)

下面貼上所有的48個(gè)數(shù)組，其他的數(shù)組只是這個(gè)基礎(chǔ)上的轉(zhuǎn)置和雙奇雙偶變換（把數(shù)組橫向或縱向位移2個(gè)單位）的結(jié)果：

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

16宮格的完美解：
將16個(gè)自然數(shù)1至16填入16宮格中，是4橫、4豎、8斜的4數(shù)之和相等，且等于組成14個(gè)正方形的4個(gè)頂點(diǎn)的數(shù)之和（這個(gè)沒(méi)驗(yàn)證）。共48個(gè)解。
完美解的16宮格模型如下：

當(dāng)年奧數(shù)教的16宮格還不是這里的完美解：

小結(jié)

用到了很多零碎的知識(shí)：

• 排列、組合
• 遞歸（比較搞腦筋）
• 取模、取余（用著不難，關(guān)鍵是要想到用這個(gè)方法來(lái)遍歷所有下標(biāo)的情況來(lái)解決問(wèn)題）
• 列表的反轉(zhuǎn)（這個(gè)算是小技巧）
• 次對(duì)角線全1的矩陣（做一次反轉(zhuǎn)即可）
• 二維數(shù)組轉(zhuǎn)90度（還是列表反轉(zhuǎn)的技巧，反轉(zhuǎn)加轉(zhuǎn)置后就是，這里沒(méi)用到）
• 線性代數(shù)（只是簡(jiǎn)單的用乘法算一下對(duì)角線上的數(shù)字之和）
• 16宮格的48個(gè)完美解（當(dāng)年老師奧數(shù)只教了1種）

新聞名稱：九宮格問(wèn)題、16宮格
轉(zhuǎn)載源于：http://m.rwnh.cn/article46/jcjshg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、定制網(wǎng)站、自適應(yīng)網(wǎng)站、網(wǎng)站策劃、App設(shè)計(jì)、微信公眾號(hào)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)