On Packing Squares into a Rectangle

Stefan Hougardy
Research Institute for Discrete Mathematics, University of Bonn

January 2010, update: April 2014



In 1966 Leo Moser (1966) posed the following problem: What is the smallest number A such that every set of squares of total area 1 can be accommodated in some rectangle of area A?
Moon and Moser (1967) proved A≤2. This was improved by Kleitman and Krieger (1970) to 1.733 and in a further paper (1975) to 1.633. The best value known so far is due to Novotný (1996) who proved A<1.53. In our paper On Packing Squares into a Rectangle we improve this to A<1.4. Below we present proofs for different values of A downto 1.4 and a simple program that allows to verify the proofs.
Update (April 2014): Using essentially the same approach but faster rectangle packing algorithms we have improved meanwhile the value of A to less than 1.37.



value for A
proven value*
filename
file size
#cases
discretization
runtime**
MD5 hash
1.50
1.5
Proof_1.50_6
3,049,854 Bytes
31,934
64
89s
2f29985e64458c65a9d2c08deb2c0c17
1.49
6102/4096 < 1.48975
Proof_1.49_6
3,990,103 Bytes
40,947
64
220s
d4570ec1b14416ad19e6b2145455ca3c
1.48
6060/4096 < 1.47950
Proof_1.48_6
5,423,131 Bytes
54,425
64
481s
250cccbd6fce2f57eba8a3ec7fe31e18
1.47
6020/4096 < 1.46973
Proof_1.47_6
7,274,098 Bytes
71,381
64
2,262s
31a406031914fccca554c842856ec8b6
1.46
5980/4096 < 1.45997
Proof_1.46_6
10,067,060 Bytes
96,136
64
 21,923s
e3c28c3430c1a258ce0ec4c1856bbcf0
1.45
5936/4096 < 1.44922
Proof_1.45_6 13,781,783 Bytes
127,807
64
 181,412s
ed93800618b91206b7e1450f8e5f4ec8
1.44
5896/4096 < 1.43946
Proof_1.44_6
19,284,428 Bytes
173,536
64
1,074,894s
1157cc60480e56321d12a1dedd292413
1.43
23427/16384 < 1.42988
Proof_1.43_7
190,815,860 Bytes
1,700,408
128
70,167s
5714e429ec9c3229f151328ea4690950
1.42
23265/16384 < 1.41999
Proof_1.42_7
280,570,966 Bytes
2,437,097
128
327,091s
95863a500cd4fe0a0386173c13d79f09
1.41
23100/16384 < 1.40992
Proof_1.41_7
421,289,825 Bytes
3,558,634
128
1,105,542s
8c556807a2730f3f7069c6cbe36e7098
1.40
22936/16384 < 1.39991
Proof_1.40_7 654,480,156 Bytes
5,365,339
128
5,562,752s
3889005c92133fb4f4bd451d03294057
1.37 (update 2014)
5611/4096 < 1.36988
NewProof_1.37_6
3,213,447,608 Bytes
14,078,192
64
535,764s


*The proven value for A is in most cases slightly smaller. Here we provide the precise value.
**Runtime in seconds on a 3GHz Intel Xeon using 1 core
To download a proof simply click on its name. 

CheckProof.cpp is a simple C++ program to verify the correctness of the proofs. It can be compiled using the gcc compiler and should compile with most other C++-compilers too.

Stefan Hougardy's homepage