minimum output match hamming weight; enforce argument ordering

[matchsticks-search.git] / main.c

diff --git a/main.c b/main.c
index 57a979654f705bd01912fe773cd01668a92ddb07..97b4bbbcc2071972bbc5ce38d7e1b09ef2bc6479 100644 (file)
--- a/main.c
+++ b/main.c
@@ -5,7 +5,9 @@
  *
  * Invoke as   ./main n m
  *
- * The algorithm is faster if the arguments are ordered so that n > m.
+ * The arguments must be ordered so that n > m:
+ *   n is the number of (more, shorter) input matches of length m
+ *   m is the number of (fewer, longer) output matches of length n
  */
 
 /*
@@ -84,7 +86,10 @@
  *
  * We further winnow the set of possible adjacency matrices, by
  * ensuring the same bit is not set in too many entries of adjmatrix
- * (ie, as above, only considering output sticks).
+ * (ie, as above, only considering output sticks); and by ensuring
+ * that it is not set in too few: each output stick must consist
+ * of at least two fragments since the output sticks are longer than
+ * the input ones.
  *
  * And, we want to do the search in order of increasing maximum
  * hamming weight.  This is because in practice optimal solutions tend
@@ -453,6 +458,13 @@ static void optimise(bool doprint) {
   if (!ok)
     goto out;
 
+  for (j=0; j<m; j++)
+    if (weight[j] < 2) {
+      PRINTF(" nominham");
+      goto out;
+    }
+
+
   /*
    * We formulate our problem as an LP problem as follows.
    * In this file "n" and "m" are the matchstick numbers.
@@ -712,6 +724,7 @@ int main(int argc, char **argv) {
   assert(argc==3);
   n = atoi(argv[1]);
   m = atoi(argv[2]);
+  assert(n > m);
 
   prep();