chiark / gitweb /
Check max Hamming weight in the other direction.
authorSimon Tatham <anakin@pobox.com>
Sat, 8 Mar 2014 14:10:06 +0000 (14:10 +0000)
committerSimon Tatham <anakin@pobox.com>
Sat, 8 Mar 2014 14:10:06 +0000 (14:10 +0000)
commitea5f3526c7c05c153a9c7c49e91c9ac649560fba
tree3071c07ef92eb3db69cdac6d398eb07da69ec480
parent0169095a9c345a65ee9e091df63a0e52d3910d1d
Check max Hamming weight in the other direction.

Once we've already got a solution, we can further winnow the set of
possible adjacency matrices, by ensuring the same bit is not set in
too many entries of adjmatrix (since if it were, some length-n stick
would have to be divided into enough pieces to make one at most the
already-known best result). This adds complexity to each step of the
recursion over possible matrices, but by early pruning it seems to cut
down the number of steps by rather more; I estimate a factor of four
speedup in pursuit of (n,m)=(10,7).
Makefile
main.c