@x
The program prints the number of solutions and the total number of link
updates. It also prints every $n$th solution, if the integer command
line argument $n$ is given. A second command-line argument causes the
full search tree to be printed; a third argument makes the output
even more verbose, and a fourth argument gives you maximum verbosity.
@y
Instead of finding all solutions, this variant of the program estimates
the size of the search tree and the number of updates on each level.
The first command-line argument tells the number of random trials to
be made, and the second is a seed value for the random number generator.
If a third argument appears, you get to see the branching decisions.
@z
@x
#include <string.h>
@y
#include <string.h>
#include "gb_flip.h"
@z
@x
  if (verbose) sscanf(argv[1],"%d",&spacing);
  @<Initialize the data structures@>;
  @<Backtrack through all solutions@>;
  printf("Altogether %d solutions, after %.15g updates.\n",count,updates);
  if (verbose) @<Print a profile of the search tree@>;
@y
  if (verbose) {
    sscanf(argv[1],"%d",&reps);
    if (verbose>1) sscanf(argv[2],"%d",&seed);
  }@+else verbose=1;
  gb_init_rand(seed);
  @<Initialize the data structures@>;
  for (r=1;r<=reps;r++)
    @<Do the Monte Carlo backtrack estimation@>;
  @<Print the estimated search tree profile@>;  
@z
@x
int verbose; /* $>0$ to show solutions, $>1$ to show partial solutions too */
@y
int verbose; /* $>2$ to show more gory details */
int reps=1;
int seed;
int r;
double profile_est[max_level];
double upd_prof_est[max_level];
@z
@x
@<Backtrack through all solutions@>=
level=0;
forward: @<Set |best_col| to the best column for branching@>;
if (best_col->len<best_col->lim) goto backdown;
best_col->lim--;
cur_node=choice[level]=best_col->head.down;
if (best_col->lim==0) specs[level]=0, cover(best_col);
else first_tweak[level]=cur_node,
     specs[level]=(best_col->len <<16)+best_col->lim;
advance:@+if (best_col->lim) {
    if (best_col->len<=best_col->lim) goto backup;
    tweak(cur_node);
  }@+else if (cur_node==&(best_col->head)) goto backup;
if (verbose>1) {
  printf("L%d:",level);
  print_choice(level);
}
@<Cover or partially cover all other columns of |cur_node|'s row@>;
if (root.next==&root) @<Record solution and |goto recover|@>;
level++;
goto forward;
backup:@+if (best_col->lim==0) uncover(best_col);
else untweak(first_tweak[level]);
best_col->lim++;
backdown:@+if (level==0) goto done;
level--;
cur_node=choice[level];@+best_col=cur_node->col;
recover:
  @<Uncover or partially uncover all other columns of |cur_node|'s row@>;
cur_node=choice[level]=cur_node->down;@+goto advance;
done:if (verbose>3)
  @<Print column lengths, to make sure everything has been restored@>;
@y
@<Do the Monte...@>=
{
  register double factor=1.0;
  level=0;
forward: profile_est[level]+=(factor-profile_est[level])/(double)r;
  @<Set |best_col| to the best column for branching@>;
  updates=0, mincost++;
  if (best_col->len<best_col->lim) mincost=0;
  else {
    best_col->lim--;
    cur_node=best_col->head.down;
    if (best_col->lim==0) specs[level]=0, cover(best_col);
    else first_tweak[level]=cur_node,
       specs[level]=(best_col->len <<16)+best_col->lim;
  }    
  if (mincost) {
    int common_updates=updates;
    updates=0;
    if (best_col->lim==0) {
      for (j=gb_unif_rand(mincost);j;j--) cur_node=cur_node->down;
    }@+else {
      tweak(cur_node);
      for (j=gb_unif_rand(mincost);j;j--)
        cur_node=cur_node->down,tweak(cur_node);
    }
    choice[level]=cur_node;
    if (verbose>2) {
      printf("L%d:",level);
      print_choice(level);
    }
    @<Cover or partially cover...@>;
    updates=common_updates+mincost*updates;
  }
  upd_prof_est[level]+=(factor*updates-upd_prof_est[level])/(double)r;
  factor*=mincost;
  level++;
  if (factor && root.next!=&root) goto forward;
  @<Restore all the data to original condition@>;
}
@z
@x
  profile[level][mincost]++;
@y
@z
@x
@*Index.
@y
@ @<Restore all the data to original condition@>=
for (j=level;profile_est[j];j++)
  profile_est[j]-=profile_est[j]/(double)r,
  upd_prof_est[j]-=upd_prof_est[j]/(double)r;
if (!factor) level--;
while (level>0) {
  level--;
  cur_node=choice[level];@+best_col=cur_node->col;
  @<Uncover or partially uncover...@>;
  if (best_col->lim==0) uncover(best_col);
  else untweak(first_tweak[level]);
  best_col->lim++;
}

@ @<Print the estimated search tree profile@>=
{
  register double tot_nodes=0.0,tot_updates=0.0;
  for (level=0;level<=maxl;level++) {
    printf("Level %d: %20.1f nodes, %20.1f updates\n",
           level,profile_est[level],upd_prof_est[level]);
    tot_nodes+=profile_est[level];
    tot_updates+=upd_prof_est[level];
  }
  printf("Total %20.1f nodes, %20.1f updates.\n",tot_nodes,tot_updates);
}
  
@*Index.
@z