正方形密鋪問題

問題概述

給定數字 n，希望將以下的數字方塊完全填滿一個正方形：

• 1 × 1 共 1 塊
• 2 × 2 共 2 塊
• 3 × 3 共 3 塊
• ... 直到 n × n 共 n 塊

這些方塊的總面積符合數學公式：

1³ + 2³ + ⋯ + n³ = (n(n+1)2)2

這代表這些方塊的總面積剛好等於一個邊長為 n(n+1)/2 的正方形，但面積吻合不保證排得進去——如何擺放才能不留空隙或重疊，是一個組合最佳化問題。

不是每個 n 都有解

面積永遠吻合，但解不一定存在。窮盡搜尋的結果是：

n = 2 到 n = 7 一組解也沒有，全都已經窮盡驗證過。到了 n = 8 卻突然有一萬八千多組。

n = 9 恰好對應 2025：

1³ + 2³ + ⋯ + 9³ = (9 × 102)2 = 45² = 2025

需要 45 塊方塊填滿 45 × 45 的棋盤。

上面那一百組是怎麼來的

n = 9 的全部解從來沒有被數完，總數至今未知。頁面上這 100 組是隨機抽樣，不是前 100 組，也不是全部；彼此之間已經去掉旋轉與鏡像的重複，所以每一張都真的不一樣——這 100 組光是開頭五塊就有 91 種不同的組合。

求解策略

一、永遠填最左上的空格

每一步都找出當下最靠左上的空格，在那裡放一塊，放不下就回溯。這樣不必考慮「要填哪裡」，只剩「要放多大」。

這條規則後來變成整份資料格式的地基。因為每一塊的位置都由前面的選擇唯一決定，一組解只需要記下 45 個邊長，座標可以完全重算——這就是為什麼一百組解在網頁裡只佔 4.8 KB、可以直接內嵌而不必下載。上面那張圖就是瀏覽器照同一條規則把數字序列重演回座標畫出來的。

二、位元棋盤

一列棋盤存成一個 64 位元整數，45 個格子剛好放得下。檢查能不能放，從逐格掃 O(s²) 變成幾次位元遮罩比對；找下一個空格，從掃過全盤 2025 格變成兩個指令。

這一步完全沒有改變搜尋樹——走訪的節點數一個不差，只是每個節點便宜了十幾倍。

三、嘗試順序：窮盡與抽樣要用相反的策略

選定格子之後，剩下的問題是「先試大的還是先試小的」。答案取決於你要什麼。

要數完全部解時，先試大的比較好。反正整棵樹都要走完，順序不影響總量，而大方塊會更快把盤面逼到矛盾、更早回溯。

只要任何一組解時，先試大的是最糟的選擇。在 n = 9 它會一頭栽進一大片無解的區域，單執行緒得掃過 43 億個節點、大約 55 秒才爬得出來。改成每個節點把可用邊長洗牌，再配一個節點預算、超過就整盤重來，中位數降到約 1.3 秒。

慢的從來不是這個問題，是走訪的順序。

四、平行化

把搜尋樹展開到固定深度，得到數十萬個互不相干的子樹，分給所有核心。抽樣模式則更單純：第 i 組解由第 i 個子種子決定，各算各的。

這也讓結果可以重現——同一個種子永遠給出同一批解，與用幾個執行緒無關。網頁上這 100 組因此不會每次重新產生就換一批。

執行時間

在 AMD Ryzen 9 5950X（16 核 32 執行緒）上：