1 #!/usr/bin/env perl
   2 
   3 $pigeons=shift;
   4 $holes=shift;
   5 
   6 $pigeons > 0 and $holes > 0 or die "Usage: $0 m n\n";
   7 @formula=();
   8 
   9 # Variables:
  10 # x1,1 ~ 1
  11 # ...
  12 # xm,1 ~ m
  13 # x1,2 ~ m+1
  14 # ...
  15 # xm,2 ~ 2*m
  16 # ...
  17 # x1,n ~ (n-1)*m+1
  18 # ...
  19 # xm,n ~ n*m
  20 #
  21 # So: xi,j ~ (j-1)*m+i
  22 
  23 # Each pigeon has to be put into some hole.
  24 for($i=1; $i <= $pigeons; $i++) {
  25   @clause=();
  26   for($j=1; $j <= $holes; $j++) {
  27     push(@clause, ($j-1)*$pigeons + $i);
  28   }
  29   push(@formula,join(" ",@clause) . " 0");
  30 }
  31 
  32 # At most one pigeon per hole.
  33 
  34 for($i=1; $i <= $pigeons; $i++) {
  35   for($j=1; $j <= $holes; $j++) {
  36     for($k=1; $k <= $pigeons; $k++) { 
  37       if($k != $i) {
  38         push(@formula,sprintf("-%d -%d 0", ($j-1)*$pigeons + $i , ($j-1)*$pigeons + $k ));
  39       }
  40     }
  41   }
  42 }
  43 
  44 printf("p cnf %d %d\n",$pigeons*$holes,$#formula+1);
  45 foreach (@formula)
  46   {
  47   print "$_\n";
  48   }