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