正方形密鋪問題

$1^3 + 2^3 + \cdots + 9^3 = 45^2 = 2025$
Solution
/ 4775

問題概述

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

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

$$1^3 + 2^3 + \cdots + n^3 = \left(\frac{n(n+1)}{2}\right)^2$$

這代表這些方塊的總面積能剛好填滿一個邊長為 n(n+1)/2 的正方形，但如何擺放才能不留空隙或重疊，則是一個組合最佳化問題。

挑戰與解法

數學背景

由於 $1^3 + 2^3 + \cdots + n^3$ 的總和形成一個完全平方數，因此理論上存在可能的填充方式。例如當 n = 9 時：

$$1^3 + 2^3 + \cdots + 9^3 = \left(\frac{9 \times 10}{2}\right)^2 = 45^2 = 2025$$

需要 45 塊不同大小的正方形來填滿 45 × 45 棋盤。

主要挑戰

求解策略

本專案使用回溯 + 剪枝來搜尋所有可能的密鋪解法，並應用以下最佳化策略：

  1. 回溯 + 剪枝：每次嘗試放置方塊時，若發現無法滿足條件，則立即回溯，避免無效計算。
  2. 大方塊優先策略：先放入大方塊（如 n × n），再放小方塊，有助於減少搜尋空間。
  3. 啟發式搜尋：每次選擇下一個要填的空格時，優先選擇靠左上角的空位，以維持有序排列。

執行時間

在 AMD Ryzen 9 5950X 執行

n = 8:

n = 9: