From Wikimization
An Eternity II puzzle problem formulation 
is discussed thoroughly in section 4.6.0.0.15 of book Convex Optimization & Euclidean Distance Geometry.
This 
matrix is obtained by presolving a 864,593 
1,048,576 system.
This Matlab binary contains three successive reductions, each equivalent to this larger system:
and 
is the million column Eternity II matrix having redundant columns removed,
and 
has columns removed corresponding to known zero variables,
and 
has columns removed not in smallest face (containing 
) of polyhedral cone 
,
- zero_varbs: row-vector identifying 57,840 columns removed from
to make 
- zero_varbs_cone: row-vector identifying 53,666 more columns removed from to make
;
i.e., those columns not belonging to smallest face of 
containing .
The following linear program is a very difficult problem:
Matrix is sparse having only 782,087 nonzeros.
All entries of are integers from the set 
.
Vector 
has only 358 nonzeros.
Vector 
is left unspecified because it is varied later in a
Convex Iteration to find a minimal cardinality solution 
. Minimal cardinality of this Eternity II problem is equal to number of puzzle pieces, 256. Any minimal cardinality solution is binary and solves the Eternity II puzzle. Constraints bound the variable from above by 
.
The technique, convex iteration, requires no modification (and works very well) when applied instead to mixed integer programming (MIP, not discussed in book). There is no modification to the linear program statement except 256 variables are declared binary.