#!/usr/bin/perl -w
use strict;
#
# Read a file containing a number puzzle and try to solve it
#
#
# Updates
#
# 3/4/2013 -- Changed to only do advanced checks if no other work has been done on this board pass
# 2/21/2013 -- Boosted size of the sets we check in the esoteric section, from 4 elements up to 8
#
my $fname;

my @board;			# 81 entries, row-major order
my @possibility_lists;		# Array of arrays, each array contains all possible values for entry
my @perm_tags;			# Set => entry has a permanent value, from the file.

my @possibilities;		# Raw counts, before anything's filled in; used in assessing the board
##my @double_index;		# Use this to investigate the low-possibility squares first
				# Used in the pure guess/backtrack solver, not in this version

my $positive_first = 0;
my $board_size = 81;
my $row_length = 9;
my $dig_last = 9;
my $dig_first = 1;
my $dig_blank = 0;
##my $silent = 1;
##my $do_sort = 1;
##my $square_sort = 1;
my $show_solution = 1;
##my $do_natural = 1;
my $do_for_build = 0;		# Set => we're running under the builder; suppress most output
##my $hybrid_mode = 1;		# Set => call the natural solver after each guess
my $throttle_level = 10;

my $ns_do_positive_only = 0;
my $ns_do_positive_check = 0;
my $ns_do_positive_multiset_check = 0;
my $ns_do_object_to_object_squashes = 0;
my $ns_do_full_positive_constraints = 0;
my $ns_do_backtracking = 0;
my $all_at_once = 0;
my $just_possibilities = 0;

# The pass 4 stat tables
my $squash_val_in_obj_actions = 0;
my $exterior_freedom_zaps = 0;
my $interior_freedom_zaps = 0;
my @irregular_multiset_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
my $irregular_external_record = "";
my @irregular_interior_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
my $irregular_internal_record = "";
my $productive_squashes = 0;

# The pass 3 stat tables
my @regular_internal_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
my $regular_internal_record = "";
my @regular_external_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
my $regular_external_record = "";

my $have_assesssed = 0;
my $first_live_cell_count;
my $first_average;
my $first_hi_lo_ratio;
my $solver_level = 0;

my $displayed_l3_actions = 0;
my $l3_did_something = 0;
my $l4_did_something = 0;

my $l3_star_adjustment = 0;
my $l4_star_adjustment = 0;
my $l5_star_adjustment = 0;

my @solved_cells_at_level = ();	# Count of cells solved, indexed by solver level

my @cell_freedoms;		# Up here so we can see it in the debug routines

# ****************************************************************

my $debug = 0;
sub dbprint ($) {
    my ($arg) = @_;
    if ($debug) { print $arg; }
}

# ****************************************************************
# Check to see if the board has been completely filled in

sub win_check () {
    my $done = 1;
    foreach my $i (0..$board_size-1) {
	if (! $board[$i]) {
	    $done = 0;
	    last;
	}
    }
    return $done;
}

# ****************************************************************
# Build an "avail set" containing all digits starting at a given value
# Returns a pointer to the list.

sub make_avail_range ($) {
    my ($start) = @_;
    my @fl;
    if (!$start) { $start = $dig_first; }

    foreach my $val ($start .. $dig_last) {
	push @fl, $val;
    }
    return \@fl;
}

# ****************************************************************
# Get the entry list for a row, column, or square.
# Append the entries to an array, which is passed in by reference.
# Don't call these inside "hot" routines -- do it inline instead.

sub cells_for_row ($$) {
    my ($row, $cells) = @_;

    my $first_index = $row_length * $row;
    foreach my $ind ($first_index .. $first_index + $row_length - 1) {
	push @{$cells}, $ind;
    }
}

sub cells_for_column ($$) {
    my ($col, $cells) = @_;

    for (my $ind = $col; $ind < $board_size; $ind += $row_length) {
	push @{$cells}, $ind;
    }
}

sub cells_for_square ($$) {
    my ($square, $cells) = @_;

    my $start_row = 3 * int ($square / 3);
    my $start_col = 3 * ($square % 3);
    for my $r ($start_row .. $start_row + 2) {
	my $base = $r * $row_length;
	for my $c ($start_col .. $start_col + 2) {
	    push @{$cells}, $base+$c;
	}
    }
}

# ****************************************************************
# Make an avail set from a digit list
# Returns a pointer to the avail set

## SCORCHING HOT -- inline it where possible

sub avail_set_from_dig_list ($) {
    my ($list_ptr) = @_;
    my @avail;
    foreach my $v ($dig_first .. $dig_last) {
	if ($$list_ptr[$v]) {
	    push @avail, $v;
	}
    }
    return \@avail;
}

# ****************************************************************
# Build an "avail set" for a particular row
# Rows are numbered from zero
# Returns a pointer to the avail set
#
# VERY HOT so we just take a digit string and clear digits which
# appear in the row; that should be faster.
# Returns the count of entries which changed (or anyway a flag
# indicating that something changed)

sub avail_set_for_row ($$) {
    my ($row,$dig_list) = @_;
    my $changed = 0;

    my $first_index = $row_length * $row;
    foreach my $ind ($first_index .. $first_index + $row_length - 1) {
	if ($board[$ind]) {
	    if ($$dig_list[$board[$ind]]) {
		$changed++;
		$$dig_list[$board[$ind]] = 0;
	    }
	}
    }
    return $changed;
}

# ****************************************************************
# Build an "avail set" for a particular column
# Columns are numbered from zero.
# Returns a pointer to the avail set
#
# HOT

sub avail_set_for_column ($$) {
    my ($col, $dig_list) = @_;
    my $changed = 0;

    for (my $ind = $col; $ind < $board_size; $ind += $row_length) {
	if ($board[$ind]) {
	    if ($$dig_list[$board[$ind]]) {
		$changed++;
		$$dig_list[$board[$ind]] = 0;
	    }
	}
    }
    return $changed;
}

# ****************************************************************
# Build an "avail set" for a particular square in the board
# Squares are numbered from 0 to 8, in row-major order.
# Each "square" contains a 3x3 block of entries from the board.
#
# HOT

sub avail_set_for_square ($$) {
    my ($square, $dig_list) = @_;
    my $changed = 0;

    my $start_row = 3 * int ($square / 3);
    my $start_col = 3 * ($square % 3);
    for my $r ($start_row .. $start_row + 2) {
	my $base = $r * $row_length;
	for my $c ($start_col .. $start_col + 2) {
	    if ($board[$base + $c]) {
		if ($$dig_list[$board[$base+$c]]) {
		    $changed++;
		    $$dig_list[$board[$base+$c]] = 0;
		}
	    }
	}
    }
    return $changed;
}

# ****************************************************************
# Combine two avail sets and return a new one.

sub intersect_avail_sets ($$) {
    my ($set_a, $set_b) = @_;
    my $len_a = scalar(@$set_a);
    my $len_b = scalar(@$set_b);
    my @new_set;
    my $i = 0;
    my $j = 0;
    # Walk through both sets simultaneously recording all matches
    while ($i < $len_a && $j < $len_b) {
	if ($$set_a[$i] == $$set_b[$j]) {
	    push @new_set, $$set_a[$i];
	    $i++;
	    $j++;
	} elsif ($$set_a[$i] > $$set_b[$j]) {
	    $j++;
	} elsif ($$set_a[$i] < $$set_b[$j]) {
	    $i++;
	}
    }
    return \@new_set;
}

# ****************************************************************
# Utilities for finding the row, column, and square for a board entry

sub row_of_entry ($) {
    my ($entry) = @_;
    return int ($entry / $row_length);
}

sub column_of_entry ($) {
    my ($entry) = @_;
    return $entry % $row_length;
}

sub square_of_entry ($) {
    my ($entry) = @_;
    my $sq_row = int (row_of_entry($entry) / 3);
    my $sq_col = int (column_of_entry($entry) / 3);
    return $sq_col + ($sq_row * 3);
}

sub row_col_to_entry ($$) {
    my ($row,$col) = @_;
    return $col + ($row * $row_length);
}

sub square_member_to_entry ($$) {
    my ($square, $member) = @_;
    my $sq_col = $square % 3;	# Row and column in the 3x3 grid of squares
    my $sq_row = int ($square / 3);

    my $base_col = $sq_col * 3;	# Row and column of the first board entry in this square
    my $base_row = $sq_row * 3;

    my $member_col = $base_col + ($member % 3); # Offset from the base member of this particular member
    my $member_row = $base_row + int ($member / 3);

    return row_col_to_entry ($member_row, $member_col);
}

# ****************************************************************
# Dump all freedoms for all cells, in blocks of three per line.

sub dump_all_freedoms () {
    my $cnt = 0;
    my $cell_num = 0;
    if (! scalar(@cell_freedoms)) {		# If freedoms haven't been set up use the possibility array
	print "Raw possibilities for all cells:\n";
	foreach my $poss (@possibility_lists) {
	    if (! $cnt) {
		printf ("   %2d: ", $cell_num);
	    }
	    $cell_num++;
	    print "(";
	    my $sp = "";
	    foreach my $p (@$poss) {
		print "${sp}$p";
		$sp = " ";
	    }
	    print ") ";
	    $cnt++;
	    if ($cnt >= 3) {
		print "\n";
		$cnt = 0;
	    }
	}
    } else {
	print "Freedoms for all cells:\n";
	foreach my $cn (0..80) {
	    my $poss = $cell_freedoms[$cn];
	    if (! $cnt) {
		printf ("   %2d: ", $cn);
	    }
	    print "(";
	    my $sp = "";
	    foreach my $i (1..9) {
		my $p = $$poss[$i];
		if ($p) {
		    print "${sp}$i";
		    $sp = " ";
		}
	    }
	    print ") ";
	    $cnt++;
	    if ($cnt >= 3) {
		print "\n";
		$cnt = 0;
	    }
	}
    }
}

# ****************************************************************
# Assess the difficulty of the board by using the possibility counts
# and, possibly, other metrics

my $old_live_count = 81;	# Start with a full board

sub assess_difficulty () {
    my @sorted_poss;
    my @poss_counts = (0,0,0,0,0,0,0,0,0,0);
    my $poss_sum = 0;
    my $max_poss = 0;
    my $min_poss = 9;

    my $direct_live_count = 0;
    foreach my $i (0..$board_size-1) {
	my $p = $possibilities[$i];
	if ($p) {
	    if ($perm_tags[$i]) { print "OOPS -- entry $i is permanent with nonzero possibilities\n"; }
	    push @sorted_poss, $p;
	    if ($p > $max_poss) { $max_poss = $p; }
	    if ($p < $min_poss) { $min_poss = $p; }
	}
	$poss_counts[$p]++;
	$poss_sum += $p;
	if (! $board[$i]) {
	    $direct_live_count++;
	    if (! $p) {
		my $pt = $perm_tags[$i];
		print "OOPS -- Entry $i is live but has zero possibilities; pt=$pt\n";
	    }
	}
    }
    @sorted_poss = sort {$a <=> $b} @sorted_poss;

    my $live_count = scalar(@sorted_poss);
    my $average = $live_count ? ($poss_sum + 0.0) / ($live_count + 0.0) : 0.0;

    my $half_ind = int($live_count / 2);
    my $quarter_ind = int($live_count / 4);
    my $median = $sorted_poss[$half_ind];
    my $quartile = $sorted_poss[$quarter_ind];

    if ($direct_live_count != $live_count) {
	print "OOPS -- live count: $live_count; direct count: $direct_live_count\n";
    }

    printf "\n" .
	    "Live cells:    $live_count\n" .
	    "Max freedoms:  $max_poss\n" .
	    "Min freedoms:  $min_poss\n" .
	    "Average:       %.2f\n" .
	    "Median:        $median\n" .
	    "Quartile:      $quartile\n", $average;
    print "Freedom counts:\n";
    foreach my $i (1..$max_poss) {
	my $fc = $poss_counts[$i];
	print "   $i:  $fc cells\n";
    }

    my $r5_7 = $poss_counts[5] + $poss_counts[6] + $poss_counts[7] + $poss_counts[8] + $poss_counts[9];
    my $r1_3 = $poss_counts[1] + $poss_counts[2] + $poss_counts[3];
    print "Range, 1-3 freedoms: $r1_3;  5-7 freedoms: $r5_7\n";
    if ($r1_3) {
	printf "Ratio, 5-7 to 1-3: %.2f\n", ($r5_7 + 0.0)/($r1_3 + 0.0);
    }
    print "\n";

    if ($debug) {
	dump_all_freedoms;
    }

    if (! $have_assesssed) {	# If this is the first time, retain some things for use in the final summary
	$have_assesssed = 1;
	$first_live_cell_count = $live_count;
	$first_average = $average;
	$first_hi_lo_ratio = $r1_3 ? ($r5_7 + 0.0)/($r1_3 + 0.0) : 0;
    }

    # And return the reduction in cell count versus last time
    my $delta_live_cells = $old_live_count - $live_count;
    $old_live_count = $live_count;
    return $delta_live_cells;
}

# ****************************************************************
# Find the "raw" possibility counts for all cells

sub find_possibility_counts () {

    foreach my $entry (0..$board_size-1) {

	my $val_in_board = 0;	# For checking

	if ($perm_tags[$entry]) {
	    $val_in_board = $board[$entry]; # Remove it temporarily
	    $board[$entry] = 0;
	    $perm_tags[$entry] = 0;

	    ##$possibilities[$entry] = 0;
	    ##$possibility_lists[$entry] = [ $board[$entry] ];
	}

	my $row = row_of_entry ($entry);
	my $column = column_of_entry ($entry);
	my $square = square_of_entry ($entry);

	my @dig_list = (0,1,1,1,1,1,1,1,1,1);

	avail_set_for_row ($row, \@dig_list);
	avail_set_for_column ($column, \@dig_list);
	avail_set_for_square ($square, \@dig_list);

##	    my $avail_set = make_avail_range ($dig_first);
##
##	    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_row ($row));
##	    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_column ($column));
##	    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_square ($square));

	if (! $val_in_board) {	# Now, did we actually have a value here?  If not just use what we found
	    my $avail_set = avail_set_from_dig_list (\@dig_list);
	    $possibilities[$entry] = scalar(@$avail_set);
	    $possibility_lists[$entry] = $avail_set;

	    if (! scalar(@$avail_set)) {
		print "WHOOPS!  Bad board! No solution!\n";
		print "Entry $entry is blank and has no possible values!\n";
		exit;
	    }
	} else {		# Had a value.  Check to see if it's on the list.
	    if (! $dig_list[$val_in_board]) {
		print "WHOOPS!  Bad board! No solution!\n";
		print "Entry $entry, value $val_in_board, is no good!\n";
		print "Possibilities for $entry: ";
		foreach my $i (1..9) { if ($dig_list[$i]) { print "$i "; }}
		print "\n";
		exit;
	    }
	    # Put it back the way it was

	    $board[$entry] = $val_in_board;
	    $perm_tags[$entry] = 1;
	    $possibilities[$entry] = 0;
	    $possibility_lists[$entry] = [ $val_in_board ];
	}
    }
}

# ****************************************************************
# Find the next possible value for a board entry.
# If no more values are possible, clear the board entry and return false.

## sub step_board_entry ($) {
##     my ($entry) = @_;
##     if ($perm_tags[$entry]) {
## 	die "Attempting to step a permanent board entry";
##     }
##     if ($entry < 0 || $entry >= $board_size) {
## 	die "step_board_entry:  Entry $entry: Stepped off the board!";
##     }
##     my $val = $board[$entry];
##     if (!defined($val)) { die "Undefined value in board entry $entry"; }
## 
##     my $row = row_of_entry ($entry);
##     my $column = column_of_entry ($entry);
##     my $square = square_of_entry ($entry);
## 
##     $board[$entry] = 0;		# Clear this entry.
## 
##     if ($val >= $dig_last) { return undef; }
## 
##     my @dig_list = (1,1,1,1,1,1,1,1,1,1);
## 
##     avail_set_for_row ($row, \@dig_list);
##     avail_set_for_column ($column, \@dig_list);
##     avail_set_for_square ($square, \@dig_list);
## 
##     my $next_val;
##     foreach my $v ($val+1 .. 9) {	# Find the first nonzero value on the list
## 	if ($dig_list[$v]) {
## 	    $next_val = $v;
## 	    last;
## 	}
##     }
## 
## ##    my $avail_set = avail_set_from_dig_list (\@dig_list);
## 
## ##    my $avail_set = make_avail_range ($val+1);
## ##
## ##    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_row ($row));
## ##    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_column ($column));
## ##    $avail_set = intersect_avail_sets ($avail_set, avail_set_for_square ($square));
## 
##     if (!defined($next_val)) { return undef; }
##     
##     $board[$entry] = $next_val;
##     return $next_val;
## }

# ****************************************************************
# Print the board

sub print_board () {
    foreach my $row (0..8) {
	if ($row && !($row % 3)) { print "\n"; }
	foreach my $column (0..8) {
	    my $entry = $row * $row_length + $column;
	    if ($column && !($column % 3)) { print " "; }
	    my $val = $board[$entry] ? $board[$entry] : "-";
	    print "$val ";
	}
	print "\n";
    }

    foreach my $i (0..$board_size-1) {
	if ($board[$i] && !$perm_tags[$i]) {
	    dbprint "Entry $i has value $board[$i] but is not permament\n";
	} elsif (!$board[$i] && $perm_tags[$i]) {
	    dbprint "Entry $i is empty but is marked permament\n";
	}
    }
}

# ****************************************************************
# Read the starting file and set up the board

sub setup_board () {
    foreach my $i (0 .. $board_size-1) {
	$board[$i] = 0;
	$perm_tags[$i] = 0;
    }
    my $row_base = 0;
    my $row_count = 0;
    open FL, "<$fname" or die "Can't open input file $fname\n";
    if (! $just_possibilities) {
	print "Starting board:\n\n";
    }
    while (<FL>) {
	my $line = $_;
	if ($line =~ /^\s*\#/) { # Skip comment lines
	    next;
	}
	if ($line =~ /^\s*$/) {	# Skip blank lines
	    next;
	}
	if ($line =~ /\s*(\S+)\s+(\S+)\s+(\S+)\s+(\S+)\s+(\S+)\s+(\S+)\s+(\S+)\s+(\S+)\s+(\S+)/) {
	    if (! $just_possibilities) {
		print $line;
	    }
	    my @row = ($1, $2, $3, $4, $5, $6, $7, $8, $9);
	    dbprint ("Read row: $1, $2, $3, $4, $5, $6, $7, $8, $9\n");
	    dbprint ("Row: @row\n");
	    foreach my $i (0..8) {
		if ($row[$i] =~ /^(?:-+)|0$/) {
		    $board[$row_base + $i] = 0;
		} elsif ($row[$i] =~ /^[1-9]$/) {
		    $board[$row_base + $i] = $row[$i];
		    $perm_tags[$row_base + $i] = 1;
		} else {
		    die "Index $i, entry $row[$i]: Line in file not understood: '$line'\n";
		}
	    }
	    $row_base += $row_length;
	    $row_count ++;
	}
    }
    if ($row_count != 9) { die "Wrong number of rows in file: $row_count\n"; }
    close FL or die "Error closing input file $fname\n";
    if (! $just_possibilities) {
	print "\n";
    }
}

# ****************************************************************
# Natural solver routines
# ****************************************************************

my $guess_entry;
my $guess_index;

my @row_stack;			# The stacks of objects
my @col_stack;
my @square_stack;

my @row_on_stack = (0,0,0,0,0,0,0,0,0,0);		# The flags -- so we don't double-push them
my @col_on_stack = (0,0,0,0,0,0,0,0,0,0);
my @square_on_stack = (0,0,0,0,0,0,0,0,0,0);

my $row_push_count = -100;
my $col_push_count = -100;
my $square_push_count = -100;
my $total_push_count = -100;
my $pushed_on_this_pass = 0;

my $total_row_push_count = 0;
my $total_col_push_count = 0;
my $total_square_push_count = 0;
my $grand_total_push_count = 0;

my $backtrack_steps = 0;
my $guess_steps = 0;

# ****************************************************************
# Push everything onto a huge stack so we can recurse after
# guessing.
# This is a horrible mess because the arrays of lists need to be
# copied entry by entry -- a shallow copy won't do, we need a deep copy.
#
# Note that the row, column, and square stacks should be EMPTY when we
# push or pop the state.
#

my @pushed_board;
my @pushed_possibility_lists;
my @pushed_perm_tags;
my @pushed_cell_freedoms;
my @pushed_guess_entry;		# Entry we're guessing on
my @pushed_guess_index;		# Index of freedom we're picking

my $board_push_depth = 0;	# How deep we've gone
my $max_board_push_depth = 0;

# Deep copy each two-level array into a local object,
# then push a reference to the local object
# Otherwise we end up with pushed references to the live subarrays
# which is certainly not what we want.

sub push_state () {
    if (scalar(@row_stack) > 0
	|| scalar(@col_stack) > 0
	|| scalar(@square_stack) > 0) {

	my $rs = scalar(@row_stack);
	my $cs = scalar(@col_stack);
	my $ss = scalar(@square_stack);

	die "Pushing state and row/col/square stacks not empty: $rs, $cs, $ss";
    }

    my @saved_board = @board;	# Copy the board and push it
    push @pushed_board, \@saved_board;

    my @saved_possibility_lists;
    foreach my $poss (@possibility_lists) {
	my @one_poss = @$poss;
	push @saved_possibility_lists, \@one_poss;
    }
    push @pushed_possibility_lists, \@saved_possibility_lists;

    my @saved_perm_tags = @perm_tags;
    push @pushed_perm_tags, \@saved_perm_tags;

    my @saved_cell_freedoms;
    foreach my $fr (@cell_freedoms) {
	my @saved_fr = @$fr;
	push @saved_cell_freedoms, \@saved_fr;
    }
    push @pushed_cell_freedoms, \@saved_cell_freedoms;

    push @pushed_guess_entry, $guess_entry;
    push @pushed_guess_index, $guess_index;

    $board_push_depth++;
    if ($board_push_depth > $max_board_push_depth) {
	$max_board_push_depth = $board_push_depth;
    }
    dbprint "push_state returning at level $board_push_depth\n";
    return $board_push_depth;
}

# Easier than pushing:  We pop the reference to a copy of
# the original array, and then just assign it to the array,
# as a shallow array copy.  Since the reference on the stack
# is gone we don't end up double referencing anything.

sub pop_state () {

    if (! $board_push_depth) {
	print "pop_state: Overpopped state stack!\n";
	return -1;
    }

    @row_stack = ();
    @col_stack = ();
    @square_stack = ();

    @row_on_stack = (0,0,0,0,0,0,0,0,0,0);		# The flags -- so we don't double-push them
    @col_on_stack = (0,0,0,0,0,0,0,0,0,0);
    @square_on_stack = (0,0,0,0,0,0,0,0,0,0);

    my $saved_board = pop @pushed_board;
    @board = @$saved_board;

    my $saved_possibility_lists = pop @pushed_possibility_lists;
    @possibility_lists = @$saved_possibility_lists;

    my $saved_perm_tags = pop @pushed_perm_tags;
    @perm_tags = @$saved_perm_tags;

    my $saved_cell_freedoms = pop @pushed_cell_freedoms;
    @cell_freedoms = @$saved_cell_freedoms;

    $guess_entry = pop @pushed_guess_entry;
    $guess_index = pop @pushed_guess_index;

    $board_push_depth--;
    dbprint "pop_state returning at level $board_push_depth\n";
    return $board_push_depth;
}


# ****************************************************************
# Quickie helper to dump the push counts

sub dump_push_counts () {
    print "Row pushes:    $row_push_count\n" .
	  "Col pushes:    $col_push_count\n" .
	  "Square pushes: $square_push_count\n" .
	  "Total pushes:  $total_push_count\n";
}

# ****************************************************************
# Stack management routines

sub push_row ($) {
    my ($r) = @_;
    if (! $row_on_stack[$r]) {
	push @row_stack, $r;
	$row_on_stack[$r] = 1;
	$row_push_count++;
	$total_push_count++;
	$pushed_on_this_pass++;
	##if ($debug) { print "pushed row $r\n"; dump_push_counts(); }
    }
}

sub push_col ($) {
    my ($r) = @_;
    if (! $col_on_stack[$r]) {
	push @col_stack, $r;
	$col_on_stack[$r] = 1;
	$col_push_count++;
	$total_push_count++;
	$pushed_on_this_pass++;
	##if ($debug) { print "pushed column $r\n"; dump_push_counts(); }
    }
}

sub push_square ($) {
    my ($r) = @_;
    if (! $square_on_stack[$r]) {
	push @square_stack, $r;
	$square_on_stack[$r] = 1;
	$square_push_count++;
	$total_push_count++;
	$pushed_on_this_pass++;
	##if ($debug) { print "pushed square $r\n"; dump_push_counts(); }
    }
}

sub pop_row () {
    if (!scalar(@row_stack)) {
	return undef;
    }
    my $r = shift @row_stack;
    $row_on_stack[$r] = 0;
    return $r;
}

sub pop_col () {
    if (!scalar(@col_stack)) {
	return undef;
    }
    my $r = shift @col_stack;
    $col_on_stack[$r] = 0;
    return $r;
}

sub pop_square () {
    if (!scalar(@square_stack)) {
	return undef;
    }
    my $r = shift @square_stack;
    $square_on_stack[$r] = 0;
    return $r;
}

# ****************************************************************
# Push the row, column, and square of an entry

sub push_objects_for_entry ($) {
    my ($entry) = @_;
    push_row (row_of_entry($entry));
    push_col (column_of_entry($entry));
    push_square (square_of_entry($entry));
}

# ****************************************************************
# Set up the freedoms array list,
# and initialize the FIFOs.
#
# Note that, when we run multiple passes with progressively more sophisticated
# heuristics, this is called before each pass, and it clears out *everything*.
#
# In particular, even though the board itself isn't zeroed,
# the 'freedoms' array is zapped each time, and all work is done
# over again with the freedoms starting as simple possibility lists.
# That may not be what was expected!  (Actually we're trying changing that, as of 2/20/2013)
#

my $setup_happened = 0;

sub setup_natural_solver() {
    my $zap_freedoms = 0;

    # First time through, set up the freedoms array, too.
    if (! $setup_happened) {
	$setup_happened = 1;
	$zap_freedoms = 1;
    }

    @row_stack = ();
    @col_stack = ();
    @square_stack = ();

    @row_on_stack = (0,0,0,0,0,0,0,0,0,0);		# The flags -- so we don't double-push them
    @col_on_stack = (0,0,0,0,0,0,0,0,0,0);
    @square_on_stack = (0,0,0,0,0,0,0,0,0,0);

    
    if ($zap_freedoms) {
	@cell_freedoms = ();

	foreach my $entry (0..$board_size-1) {
	    my $fr = [0,1,1,1,1,1,1,1,1,1];
	    if ($board[$entry]) { # Is this entry filled in?
		$fr = [0,0,0,0,0,0,0,0,0,0];
		$$fr[$board[$entry]] = 1;
	    } else { # Initialize the freedoms based on the preset board entries
		my $row = row_of_entry ($entry);
		my $col = column_of_entry ($entry);
		my $square = square_of_entry ($entry);

		avail_set_for_row ($row, $fr);
		avail_set_for_column ($col, $fr);
		avail_set_for_square ($square, $fr);
	    }

	    $cell_freedoms[$entry] = $fr; # Freedoms are indexed by digit value, 1 through 9
	}
    }

    foreach my $i (0..$board_size-1) { # Fill the stacks
	push_objects_for_entry ($i);
    }
    $row_push_count = 0;
    $col_push_count = 0;
    $square_push_count = 0;
    $total_push_count = 0;
}

# ****************************************************************
# Just push the full board, without changing any of the counts or setting anything else up

sub just_push_all_objects() {

    my $old_rpc = $row_push_count;
    my $old_cpc = $col_push_count;
    my $old_spc = $square_push_count;
    my $old_tpc = $total_push_count;

    @row_stack = ();
    @col_stack = ();
    @square_stack = ();

    @row_on_stack = (0,0,0,0,0,0,0,0,0,0);		# The flags -- so we don't double-push them
    @col_on_stack = (0,0,0,0,0,0,0,0,0,0);
    @square_on_stack = (0,0,0,0,0,0,0,0,0,0);

    
    foreach my $i (0..$board_size-1) { # Fill the stacks
	push_objects_for_entry ($i);
    }

    $row_push_count = $old_rpc;
    $col_push_count = $old_cpc;
    $square_push_count = $old_spc;
    $total_push_count = $old_tpc;
}

# ****************************************************************
# Count the active cells in an object

sub count_obj_active_cells (@) {
    my (@obj) = @_;
    my $obj_active_cells = 0;
    foreach my $c (@obj) {
	if (! $board[$c]) {
	    $obj_active_cells ++;
	}
    }
    return $obj_active_cells;
}

# ****************************************************************
# Check multisets.  We look for two classes:
#
# a) If k cells each have exactly the same k possibilities, then those
#    k values must be contained in those cells and we can eliminate them
#    from the freedom sets for all other cells in the object.
#
# b) If k values each occur in exactly the same k cells, and no others,
#    then those k cells must have those values, and we can eliminate all
#    other values from the freedom sets for those k cells.

sub check_positive_multisets ($$@) {
    my ($changed_entries,$cell_lists_for_vals,@obj) = @_;

    if ($debug) {
	print "check_positive_multisets, obj: ";
	foreach my $e (@obj) { print "$e "; }
	print "\n";
    }

    # Start by using the cell_lists_for_vals table.  We'll use that to find out if
    # any set of N values can only appear in one of N cells; if so we can use that to
    # eliminate other freedoms for those cells.
    # To do this we need to invert the table, so we can look up the set of values which
    # correspond to each cell list.

    my %vals_for_cell_sets; # Lists of values, hashed by sets of cells which can have that value
    foreach my $v (1..9) {
	my $clist = $$cell_lists_for_vals[$v]; # Cells for this value
	if ($debug) {
	    print "Cell list for value $v: ";
	    foreach my $c (@$clist) { print "$c "; }
	    print "\n";
	}
	my $key = "";
	foreach my $c (@$clist) {
	    $key .= $key eq "" ? "$c" : " $c"; # Convert them to a string
	}
	if (defined $vals_for_cell_sets{$key}) { # And append this cell to that entry
	    push @{$vals_for_cell_sets{$key}}, $v;
	} else {
	    $vals_for_cell_sets{$key} = [$v];
	}
    }
    #
    # NB -- The table vals_for_cell_sets now contains one entry for each set of cells
    # which, together, "own" at least one value in common.
    # The entry, whose key is that set of cells, contains a list of values those cells "own".
    # Each cell in the key for that entry may, however, appear in other keys in the table too,
    # if not all the values it can take on are shared with the same set of cells.
    #
    # We'll now walk through the table and check to see if some keys are the same length as their
    # value lists.  For any which are, the cells in the key "own" as many values as their cardinality,
    # and since they *must* take on all values they own, they haven't got room to take on any other
    # values.  So, we clear their "extra" freedoms.
    #
    foreach my $key (keys %vals_for_cell_sets) { # Now check for N-long keys with N-element entries
	my @cells = split / /, $key;
	my $n = scalar(@cells);
	my $vlist = $vals_for_cell_sets{$key};
	if ($n > 1 && scalar(@$vlist) == $n) { # Whoops! These cells must contain these values!
	    my $was_productive = 0;
	    if ($debug) {
		print "Found key $key, length $n, with value set: ";
		foreach my $c (@$vlist) { print "$c "; }
		print "\n";
	    }
	    foreach my $entry (@cells) {
		my $freedoms = $cell_freedoms[$entry]; # Get the freedom list for the cell
		foreach my $v (@$vlist) {
		    $$freedoms[$v] = 0; # Start by CLEARING these so we can easily check for others
		}
		if ($debug) {
		    print "Freedoms for cell $entry: ";
		    foreach my $f (@$freedoms) { print "$f "; }
		    print "\n";
		}
		foreach my $f (@$freedoms) { # If any are nonzero then we've got a changed cell here
		    if ($f) {
			dbprint "Found a change for key $key, entry $entry; pushing entry\n";
			push @{$changed_entries}, $entry;
			$was_productive = 1;
			last;
		    }
		}
		@$freedoms = (0,0,0,0,0,0,0,0,0,0); # Clear the freedoms
		foreach my $v (@$vlist) {
		    $$freedoms[$v] = 1; # And finally set the ones which are allowed
		}
	    }
	    if ($was_productive) { # If it was productive, record a statistic or two
		$regular_internal_hits[$n] ++;
		if (length $regular_internal_record > 0) {
		    $regular_internal_record .= ", ";
		}
		my $oac = count_obj_active_cells (@obj);
		$regular_internal_record .= "${n}/${oac}";
	    }
	}
    }


    # Next we'll use any N-tuples of cells which share N values to restrict the freedoms
    # of other cells in the object, since we know that, if these N cells span N values, those
    # values can't occur elsewhere as well.
    # For this, we need to invert the cell constraint table.

    my %cells_for_constraints;
    foreach my $entry (@obj) { # Build the table mapping constraint sets to cells
	my $freedoms = $cell_freedoms[$entry];
	my $fr_string = ""; # Convert the freedoms to a character string
	foreach my $f (1..9) {
	    if ($$freedoms[$f]) { $fr_string .= "$f"; }
	}
	if (defined $cells_for_constraints{$fr_string}) {
	    push @{$cells_for_constraints{$fr_string}}, $entry;
	} else {
	    $cells_for_constraints{$fr_string} = [$entry];
	}
    }

    foreach my $key (keys %cells_for_constraints) {
	my $n = length $key;
	my $clist = $cells_for_constraints{$key};
	if ($n > 1 && ($n == scalar(@$clist))) {
	    my $was_productive = 0;
	    if ($debug) {
		print "Key $key, length $n, has cells: ";
		foreach my $c (@$clist) { print "$c "; }
		print "\n";
		print "Will restrict other cells in object\n";
	    }
	    # We need to know if we actually change anything, and we don't want to scan
	    # clist for every cell in the object.  So, we start by zapping out the
	    # freedoms for the cells in clist.  Then, we scan the object and zap
	    # out these freedoms for any cell which has them, recording changed cells.
	    # Finally we put them back for the cells in clist.

	    foreach my $c (@$clist) {
		$cell_freedoms[$c] = [0,0,0,0,0,0,0,0,0,0];
	    }
	    my @vals = split //,$key; # We will need to scan each value in the key
	    foreach my $entry (@obj) {
		my $freedoms = $cell_freedoms[$entry]; # Get the freedom list for the cell
		if ($debug) {
		    print "Freedoms for cell $entry: ";
		    foreach my $f (@$freedoms) { print "$f "; }
		    print "\n";
		}
		foreach my $v (@vals) {
		    if ($$freedoms[$v]) {
			dbprint "Found: cell $entry has freedom $v -- clearing and pushing cell\n";
			$$freedoms[$v] = 0;
			push @{$changed_entries}, $entry;
			$was_productive = 1;
		    }
		}
	    }
	    # Finally we need to put back the freedoms for the cells which need them.
	    foreach my $v (@vals) {
		foreach my $c (@$clist) {
		    dbprint "Restoring freedom $v for entry $c\n";
		    ${$cell_freedoms[$c]}[$v] = 1;
		}
	    }
	    if ($was_productive) { # Record some stats
		$regular_external_hits[$n] ++;
		if (length $regular_external_record > 0) {
		    $regular_external_record .= ", ";
		}
		my $oac = count_obj_active_cells(@obj);
		$regular_external_record .= "${n}/${oac}";
	    }
	}
    }
}

# ****************************************************************
# Build all subsets of size K of an array in another array.
# Each subset is a subarray.
# This operates by simple recursion:  It picks off the first element,
# and calls itself to form all subsets of size <= k of the rest of the list.
# It copies the returned sets onto its own list, and then copies the same
# sets, this time with the element it had picked off inserted at the front
# of each of the subsets.  Note that this actually only recurses, at most,
# eight levels (once per element in an object, or once per value in a
# freedom set).  There are no additional calls to itself.  The doubling
# of the tree at each step happens when it pushes the set of subsets which
# were returned, and then _also_ pushes the same sets with the "head" element
# prepended to it.
#
# As it goes, it returns only subsets of <= k elements.  This keeps the
# intermediate bulge down to something manageable (I hope).
#
# At the end, at top level, it filters out subsets of < k elements before
# returning the combined list.

sub all_subsets ($$;$) {
    my ($k, $set, $start_index) = @_;
    if (!defined($start_index)) { $start_index = 0; }

    if ($debug) {
	print "all_subsets: k=$k, start_index=$start_index, set: ";
	foreach my $c (@$set) { print "$c "; }
	print "\n";
    }

    my @subsets;

    if ($start_index >= scalar(@$set) || # Starting at the end of the array? No elements left.
	$k > scalar(@$set)) {		 # Or requested subset size is bigger than the set?
	push @subsets, [];
	return \@subsets;
    }

    my $head = $$set[$start_index];			   # Pick off the head element
    my $sub_subs = &all_subsets ($k, $set, $start_index+1); # Recurse; get all subsets from here to the right.
    foreach my $sub (@$sub_subs) {
	push @subsets, $sub;   # Push each subset which was returned
	if (scalar(@$sub) <= $k-1) {      # In addition, if it's small enough, add another element.
	    my @copy = @$sub;		  # Need to make a copy of this!
	    unshift @copy, $head;	      # Put our "head" item on the front (so it's in order)
	    push @subsets, \@copy;	      # And put it on the list.
	}
    }

    if (0 && $debug) {
	print "Returned back to start_index $start_index: Subsets found:\n";
	foreach my $i (0..$#subsets) {
	    print "  $i: ";
	    my $ss = $subsets[$i];
	    foreach my $c (@$ss) { print "$c "; }
	    print "\n";
	}
    }

    if (! $start_index) {	# Is this the top level invocation?  If so filter out undersize sets
	my @all_sets = @subsets;
	@subsets = ();
	foreach my $s (@all_sets) {
	    if (scalar(@$s) == $k) {
		push @subsets, $s;
	    }
	}
	if ($debug) {
	    print "Final (filtered) subsets found:\n";
	    foreach my $i (0..$#subsets) {
		print "  $i: ";
		my $ss = $subsets[$i];
		foreach my $c (@$ss) { print "$c "; }
		print "\n";
	    }
	}
    }
    return \@subsets;
}

# ****************************************************************
# Squash a particular value throughout an object, except at the
# cell locations which are passed in.
# Returns a flag indicating whether it did anything.

sub squash_val_in_obj ($$@) {
    my ($v, $clist, @obj) = @_;
    my $productive = 0;

    if ($debug) {
	print "squash_val_in_obj: val=$v, clist: ";
	foreach my $c (@$clist) { print "$c "; }
	print "; obj: ";
	foreach my $c (@obj) { print "$c "; }
	print "\n";
    }

    my %cell_indices;		# Invert the object, so we can find entries by cell number
    foreach my $i (0..$row_length-1) {
	$cell_indices{$obj[$i]} = $i;
    }

    foreach my $c (@$clist) {
	my $ind = $cell_indices{$c};
	$obj[$ind] = -1;	# Zap out the cells in the object which "own" the value
    }

    # The object list now only contains cells which can't take on value v.
    foreach my $c (@obj) {
	if ($c < 0) {next;}
	my $freedoms = $cell_freedoms[$c];
	if ($$freedoms[$v]) {	# Did this cell have this freedom?
	    if ($debug) {
		print "Freedoms for cell $c: (";
		foreach my $f (@$freedoms) {
		    print "$f ";
		}
		print ")\n";
	    }
	    $$freedoms[$v] = 0;	# If so remove it, and rescan the row, col, and square of the cell.
	    dbprint "squash_val_in_obj:  Clearing freedom $v in cell $c, and pushing row, col, square\n";
	    push_objects_for_entry ($c);
	    $squash_val_in_obj_actions ++; # Note that we did something
	    $productive = 1;
	}
    }
    return $productive;
}

sub squash_val_in_row ($$) {
    my ($v, $clist) = @_;
    my $base_cell = $$clist[0];
    if ($debug) {
	print "squash_val_in_row: value=$v, clist = ";
	foreach my $c (@$clist) { print "$c "; }
	print "\n";
    }

    my $row = row_of_entry ($base_cell);
    my @obj;
    cells_for_row ($row, \@obj);

    return squash_val_in_obj ($v, $clist, @obj);
}

sub squash_val_in_col ($$) {
    my ($v, $clist) = @_;
    my $base_cell = $$clist[0];
    if ($debug) {
	print "squash_val_in_col: value=$v, clist = ";
	foreach my $c (@$clist) { print "$c "; }
	print "\n";
    }

    my $col = column_of_entry ($base_cell);
    my @obj;
    cells_for_column ($col, \@obj);

    return squash_val_in_obj ($v, $clist, @obj);
}

sub squash_val_in_square ($$) {
    my ($v, $clist) = @_;
    my $base_cell = $$clist[0];
    if ($debug) {
	print "squash_val_in_square: value=$v, clist = ";
	foreach my $c (@$clist) { print "$c "; }
	print "\n";
    }

    my $square = square_of_entry ($base_cell);
    my @obj;
    cells_for_square ($square, \@obj);
    if ($debug) {
	print "Values in square: ";
	foreach my $c (@obj) {print "$c ";}
	print "\n";
    }

    return squash_val_in_obj ($v, $clist, @obj);
}

# ****************************************************************
# There are three situations we check for here.  None of these are common
# and as of 5/12/08 we have yet to see a sudoku in which these checks were
# necessary.  There are three:
#
# a) There are K cells in the object whose united freedom sets contain K values.
#    In that case we know those K values must occur in those K cells, and we can
#    eliminate them from all other cells in the object.  An example of this is three
#    cells whose freedoms are restricted to (1,2), (2,3), and (1,3) respectively.
#    Since the freedom lists aren't identical this case won't be caught by the earlier
#    check we did for multisets.
#    For speed (and simplicity) we may do this check only for 3-cell sets.
#    It's irrelevant for
#    2-cell sets (they're caught by the multiset check done earlier) and it's very
#    rare that such a 4-cell set will do anything useful for us.
#
# b) There are K values which can only occur in a set of K cells in the object.
#    In this case know those cells must be have those K values, and we can eliminate
#    other values from the freedom sets of those cells. (We can't conclude anything
#    new about the rest of the object, however, until we update all freedoms and
#    run the next pass.)
#    If the cell set is identical for each value, this will be caught by the multiset
#    check.  The case we're interested in here is when the sets are not identical.
#    So, for instance, the freedom sets for cells 1,2,3 might be
#    (4,5,6), (5,7), and (6,7) respectively; then we know cells 1,2,3 must take the
#    values (5,6,7) and we can eliminate value 4 from the freedom list for cell 1.
#    As with the previous check we may do this just for 3-cell sets.
#
# c) In a row or column, a value is restricted to the region
#    contained in a single square.  Thus we know that the value must occur in
#    the intersection of the row/column and square (a 3-cell region).
#    We can use that to eliminate the value from the freedom lists for other
#    cells in the square.
#
#    Conversely, if we find the same situation when scanning a square, we can
#    eliminate the value from the freedom lists for other cells in the row/column.
#
#    Note that while (a) and (b) are independent, (c) may be able to do more after
#    the (a) and (b) checks have been run; hence we make check (c) last.
#

sub make_esoteric_checks ($$$$@) {
    my ($changed_entries,$cell_lists_for_vals,$cell_counts_for_vals,$eso_level,@obj) = @_;

    if ($debug) {
	print "make_esoteric_checks: object: ";
	foreach my $c (@obj) { print "$c "; }
	print "\n";
    }

    my %inverted_obj;
    foreach my $i (0..$row_length-1) { # Build a table of indices, indexed by entry, for use later
	$inverted_obj{$obj[$i]} = $i;
    }

    # Figure out what kind of object this is (we've lost that information at this level)
    my $is_row = 0;
    my $is_col = 0;
    my $is_square = 0;

    if ($obj[8] == $obj[0] + 8) {
	$is_row = 1;
    } elsif ($obj[8] == $obj[0] + (8 * $row_length)) {
	$is_col = 1;
    } else {
	$is_square = 1;
    }

    #
    # We only do the heavy irregular set checks as our final resort before backtrack-solving.
    #
    if ($eso_level > 1) {
	# a) First esoteric check, as described above:
	# -- We form the set of cells with no more than "k" freedoms, where we may
	#    limit "k" to three.  (Hopefully this will be
	#    a substantially smaller set than the full object!)
	# -- We then form all subsets of three cells.
	# -- Finally we combine the freedoms for each subset.
	# -- Any combined freedom set which has just 3 values is then used to reduce
	#    the freedoms for the rest of the row.

	my $oac = count_obj_active_cells (@obj);

	foreach my $k (3 .. $oac-1) { # Maybe we'll do it for 4-way as well...
	    if ($pushed_on_this_pass) { last; } # Only proceed if NOTHING has been found so far on this pass
	    dbprint "Checking for $k-way multisets with irregular freedom sets\n";
	    my @k_cells;
	    foreach my $c (@obj) {
		my $cf_count = 0;
		my $cf = $cell_freedoms[$c]; # This is a list of flags, one for each freedom
		foreach my $f (1..9) {
		    if ($$cf[$f]) {
			$cf_count ++;
		    }
		}
		if ($cf_count > 1 && $cf_count <= $k) {
		    dbprint "  .. Pushing cell $c into set with freedoms\n";
		    push @k_cells, $c;
		}
	    }
	    if (scalar(@k_cells) == 0) {
		dbprint " .. No candidates for k=$k\n";
		next;
	    }
	    my $k_subsets = all_subsets ($k, \@k_cells);
	    for my $subset (@$k_subsets) { # Check each subset in turn to see if it's "complete"
		my %combined_freedoms;
		foreach my $cell (@$subset) { # Add freedoms of each cell to the hash table
		    my $freedoms = $cell_freedoms[$cell];
		    foreach my $f (1..9) {
			if ($$freedoms[$f]) {
			    $combined_freedoms{$f} = 1;
			}
		    }
		}
		if ($debug) {
		    print "Merged freedoms for (";
		    foreach my $c (@$subset) { print "$c "; }
		    print "): ";
		    foreach my $key (keys %combined_freedoms) { print "$key "; }
		    print "\n";
		}
		my $hit_on_subset = 0;
		if (scalar(keys %combined_freedoms) == $k) { # If they're equal we've got a hit.
		    dbprint "Got a hit on irregular multiset, size $k -- scanning exterior cells\n";
		    my %subset_map; # Clearing the freedoms in all other cells is pain.
		    foreach my $c (@$subset) {
			$subset_map{$c} = 1; # Build a hash table to let us check entries one by one
		    }
		    foreach my $entry (@obj) { # Now let's scan the whole object
			if ($subset_map{$entry}) { next; } # Skip the ones in the subset
			my $freedoms = $cell_freedoms[$entry];
			foreach my $f (keys %combined_freedoms) {
			    if ($$freedoms[$f]) {
				dbprint "Zapped out freedom $f, entry $entry, in irregular multiset check\n";
				$$freedoms[$f] = 0; # Zap it out
				push_objects_for_entry ($entry);
				$exterior_freedom_zaps ++;
				$hit_on_subset = 1;
			    }
			}
		    }
		}
		if ($hit_on_subset) {
		    $irregular_multiset_hits[$k] ++;
		    if (length $irregular_external_record > 0) {
			$irregular_external_record .= ", ";
		    }
		    $irregular_external_record .= "${k}/${oac}";
		}
	    }
	}

	# b) Second esoteric check, as described above:
	#    This is sort of the inverse of the previous check.
	# -- Form the set of cells for each value (invert the freedoms table)
	# -- Form the set of all values with <= k cells
	# -- Form all K-ary subsets of that value set
	# -- Form the combined cell set for each value subset
	# ++ Any subset with <= k cells can be used to reduce those cells to just
	#    that subset of values.

	my @cells_for_value = ([],[],[],[],[],[],[],[],[],[]);
	foreach my $c (@obj) {	# Form the cell list for the values
	    my $freedoms = $cell_freedoms[$c];
	    foreach my $f (1..9) { # Push each cell onto each cell list for each value on its freedom list
		if ($$freedoms[$f]) {
		    push @{$cells_for_value[$f]}, $c
		}
	    }
	}

	foreach my $k (2 .. $oac-1) { # In fact this can do something useful with just 2 cells, and up to 8.
	    if ($pushed_on_this_pass) { last; } # Only proceed if NOTHING has been found so far on this pass
	    my $got_hit = 0;
	    dbprint "Checking for $k-way freedom sets which are contained in $k cells\n";
	    # Now find the set of all values with no more than k cells, and all subsets of k members.
	    my @k_cell_values;
	    foreach my $v (1..9) {
		my $cells = $cells_for_value[$v];
		my $c_count = scalar (@$cells);
		if ($c_count > 1 && $c_count <= $k) {
		    push @k_cell_values, $v;
		}
	    }
	    if (scalar(@k_cell_values) == 0) {
		dbprint " .. No candidates for k=$k\n";
		next;
	    }
	    if ($debug) {
		print "Values with no more than $k cells: ";
		foreach my $v (@k_cell_values) { print "$v "; }
		print "\n";
	    }
	    my $k_cell_value_subsets = all_subsets ($k, \@k_cell_values);

	    # Now iterate over all subsets.  For each one we'll find the combined cell set
	    # and, if it's no bigger than k, we can zap out extra freedoms for the cells in it.

	    foreach my $subset (@$k_cell_value_subsets) {
		my %subset_cell_map; # Set of all cells which include parts of the subset
		foreach my $v (@$subset) {
		    my $cells = $cells_for_value[$v];
		    foreach my $entry (@$cells) { # Add all cells for this value to the combined map
			$subset_cell_map{$entry} = 1;
		    }
		}
		if (scalar(keys %subset_cell_map) == $k) {
		    my %subset_value_map; # Map to let us check quickly to see if a value is in the set
		    foreach my $v (@$subset) {
			$subset_value_map{$v} = 1
		    }
		    if ($debug) {
			print "Got a hit on value sets (interior check) -- checking cell freedoms\n";
			print "  Cells: ";
			foreach my $c (keys %subset_cell_map) { print "$c "; }
			print "; Values: ";
			foreach my $v (keys %subset_value_map) { print "$v "; }
			print "\n";
		    }

		    foreach my $entry (keys %subset_cell_map) {
			my $freedoms = $cell_freedoms[$entry];
			foreach my $f (1..9) {
			    if (! $$freedoms[$f]) {
				next; # Skip any freedoms which aren't set on this cell
			    }
			    if ($subset_value_map{$f}) {
				next; # Members of the value are OK too.
			    }
			    # Others aren't and must be cleared.
			    dbprint "Clearing freedom $f for entry $entry\n";
			    $$freedoms[$f] = 0;
			    push_objects_for_entry ($entry);
			    $interior_freedom_zaps++;
			    $got_hit = 1;
			}
		    }
		}
	    }
	    if ($got_hit) {
		$irregular_interior_hits[$k] ++;
	    }
	}
    }

    # c) Third esoteric check:
    #
    # Check for values restricted to the intersection of a square and row/column
    foreach my $v (1..9) {	# Check each value
	if ($pushed_on_this_pass) { last; } # Only proceed if NOTHING has been found so far on this pass
	my $ccount = $$cell_counts_for_vals[$v];
	if ($ccount < 2 || $ccount > 3) {
	    next;
	}
	my $clist = $$cell_lists_for_vals[$v];
	my $entry0_index = $inverted_obj{$$clist[0]};
	my $obj0_row = int($entry0_index / 3); # The "row" within the object, numbered 0..2
	my $obj0_col = $entry0_index % 3; # The "col" within the object, numbered 0..2
	my $row_match = 1;
	my $col_match = 1;

	# Check to see if rows all match and/or columns all match
	foreach my $c (1..$ccount-1) { # Skip the first one -- that's what we're checking against
	    my $c_index = $inverted_obj{$$clist[$c]};
	    my $c_row = int($c_index / 3);
	    my $c_col = $c_index % 3;
	    if ($c_row != $obj0_row) { $row_match = 0; }
	    if ($c_col != $obj0_col) { $col_match = 0; }
	}

	my $squashed_something = 0;
	if (($is_row || $is_col) && $row_match) {
	    $squashed_something = squash_val_in_square ($v, $clist);
	} elsif ($is_square && $row_match) {
	    $squashed_something = squash_val_in_row ($v, $clist);
	} elsif ($is_square && $col_match) {
	    $squashed_something = squash_val_in_col ($v, $clist);
	}
	if ($squashed_something) {
	    $productive_squashes ++;
	}
    }
}

# ****************************************************************
# Constrain the object based on the necessity that we have all
# digits represented.  Return the number of elements which changed.
# The passed list should be nine entry indices.
# Our arrays which are indexed by value are, indeed, indexed by value,
# but since they're zero based they have 10 entries of which the first is
# not used.

sub ns_positive_avail_set (@) {
    my (@obj) = @_;

    if ($debug) {
	print "ns_positive_avail_set: ";
	foreach my $e (@obj) { print "$e "; }
	print "\n";
    }

    my @cell_counts_for_vals = (0,0,0,0,0,0,0,0,0,0);	# Number of cells which can have each value
    my @cell_lists_for_vals = ([],[],[],[],[],[],[],[],[],[]);	# List of cells which can have each value

    my @changed_entries;

    foreach my $entry (@obj) {	# Fill the lists of cells indexed by values
	my $val = $board[$entry];
	if ($val) {		# Already filled in?
	    $cell_counts_for_vals[$val]++;
	    dbprint "Val $val, entry $entry, already set, appending entry to list for value\n";
	    push @{$cell_lists_for_vals[$val]}, $entry;
	} else {
	    foreach $val (1..9) {
		if (${$cell_freedoms[$entry]}[$val]) {
		    $cell_counts_for_vals[$val]++;
		    dbprint "Val $val, entry $entry, value on constraint list, append entry to list for value\n";
		    push @{$cell_lists_for_vals[$val]}, $entry;
		}
	    }
	}
    }
    foreach my $val (1..9) {	# Check for any singletons: Values which occur in only one cell
	if (! $cell_lists_for_vals[$val]) {
	    print "ns_positive_avail_set: Bad board; no value $val for object (";
	    my $space = "";
	    foreach my $c (@obj) {print "${space}${c}"; $space = " ";}
	    print ")\n";
	    return 0;		# In this case we've lost -- we can't proceed
	} elsif ($cell_counts_for_vals[$val] == 1) {
	    dbprint "Found singleton value: $val\n";
	    my $entry = ${$cell_lists_for_vals[$val]}[0];
	    if (! $board[$entry]) {
		dbprint "Positive check won, limiting entry $entry to the value $val\n";
		$board[$entry] = $val;
		$perm_tags[$entry] = 1;
				# And update the freedoms for this cell -- must be just one
		$cell_freedoms[$entry] = [0,0,0,0,0,0,0,0,0,0]; # Clear them all
		${$cell_freedoms[$entry]}[$val] = 1; # And set just one.
		push @changed_entries, $entry;
	    } elsif ($debug) {
		print " .. it was already pinned\n";
	    }
	}
    }

    # No joy so far?  If we're supposed to do unlimited checking, go to the next level.

    if (!@changed_entries && $ns_do_positive_multiset_check && !$pushed_on_this_pass) {
	check_positive_multisets (\@changed_entries, \@cell_lists_for_vals, @obj);
	if (scalar(@changed_entries)) {
	    $l3_did_something ++;
	}
    }

    if (!@changed_entries && $ns_do_object_to_object_squashes && !$pushed_on_this_pass) {
	make_esoteric_checks (\@changed_entries, \@cell_lists_for_vals, \@cell_counts_for_vals, 1, @obj);
	if (scalar(@changed_entries)) {
	    $l4_did_something ++;
	}
    }

    if (!@changed_entries && $ns_do_full_positive_constraints && !$pushed_on_this_pass) {
	make_esoteric_checks (\@changed_entries, \@cell_lists_for_vals, \@cell_counts_for_vals, 2, @obj);
	if (scalar(@changed_entries)) {
	    $l4_did_something ++;
	}
    }

    # Finally push everything which might be affected back onto the stack
    foreach my $e (@changed_entries) {
	dbprint "ns_positive_avail_set: Pushing row, col, and square for entry $e\n";
	push_objects_for_entry ($e);
    }
    return 1;
}

# ****************************************************************
# Given a list of entries, update the freedoms for each, and note if
# anything changed.
# Returns 1 if all is well, whether or not progress was made.
# Returns 0 if the board is NG and we're locked up

sub ns_process_object (@) {
    my (@obj) = @_;

    # Loop over entries, updating their freedoms and checking for newly "pinned" cells

    if (! $ns_do_positive_only) {
	foreach my $entry (@obj) {
	    if ($board[$entry]) { next; } # Skip entries whose values are already "fixed"

	    my $row = row_of_entry ($entry);
	    my $col = column_of_entry ($entry);
	    my $square = square_of_entry ($entry);

	    my $cf = $cell_freedoms[$entry];
	    my $changes = 0;
	    $changes += avail_set_for_row ($row, $cf);
	    $changes += avail_set_for_column ($col, $cf);
	    $changes += avail_set_for_square ($square, $cf);

	    # NB -- We may have objects with just one freedom which haven't been picked up and
	    # made permanent, so regardless of changes made to the freedoms, we check the
	    # counts here.

	    my $freedom_count = 0;
	    my $last_freedom = -1;
	    foreach my $i (1..9) {
		my $flag = $$cf[$i];
		if ($flag) {
		    $freedom_count++;
		    $last_freedom = $i;
		    if ($freedom_count > 1) {
			last;
		    }
		}
	    }

	    if (! $freedom_count) { # No freedoms?  Then the board is NG.
		print "ns_process_object:  Jammed; entry $entry has no freedoms\n";
		return 0;
	    }

	    if ($changes || $freedom_count == 1) { # If something changed, rescan rows and colums, and count freedoms for entry
		push_row ($row);
		push_col ($col);
		push_square ($square);

		if ($freedom_count == 1) { # Just one freedom?  This entry is pinned.
		    $board[$entry] = $last_freedom;
		    $perm_tags[$entry] = 1;
		    dbprint "ns_process_object: Set entry $entry to value $last_freedom\n";
		}
	    }
	}
    }

    # We've updated the freedom lists for all cells in the object at this point.
    # Now we can perform the "positive" checks, which are based on the need
    # to have all nine values represented in the object, rather than the constraint
    # that no value may appear twice in the object.

    if ($ns_do_positive_check || $ns_do_positive_only) { # Doing positive checks, too?
	return ns_positive_avail_set (@obj);
    }
    return 1;
}

# ****************************************************************
# Process one row/column/square.  Extract the list of entries for it and
# pass to the general object processor.

sub ns_process_row ($) {
    my ($row) = @_;
    dbprint "ns_process_row ($row)\n";

    my @entries;
    foreach my $col (0..8) {
	my $entry = row_col_to_entry ($row, $col);
	push @entries, $entry;
    }
    return ns_process_object (@entries);
}

sub ns_process_col ($) {
    my ($col) = @_;
    dbprint "ns_process_col ($col)\n";

    my @entries;
    foreach my $row (0..8) {
	my $entry = row_col_to_entry ($row, $col);
	push @entries, $entry;
    }
    return ns_process_object (@entries);
}

sub ns_process_square ($) {
    my ($square) = @_;
    dbprint "ns_process_square ($square)\n";

    my @entries;
    foreach my $member (0..8) {
	my $entry = square_member_to_entry ($square, $member);
	push @entries, $entry;
    }
    return ns_process_object (@entries);
}

# ****************************************************************
# Guess, so we can move forward on a non-constraint-based board

sub ns_guess () {

    dbprint "ns_guess\n";

    #
    # Were we already working on a guess?  Then just step to the next freedom for the cell.
    # If we run out of possibilities for the cell, then the board is jammed, and
    # we're done; we can't proceed.
    #
    # If we're being invoked recursively for a second or higher guess, then
    # we'll find the board entry for the current guess already filled in.
    #
    my $fr;			# Freedoms for the guess cell
    if (defined($guess_entry) && ! $board[$guess_entry]) {
	dbprint " Old guess: $guess_entry, old index: $guess_index\n";
	$fr = $cell_freedoms[$guess_entry];
	my $next_index = -1;
	foreach my $i ($guess_index+1 .. 9) { # Look for the next available value for the cell
	    if ($$fr[$i]) {
		$next_index = $i;
		last;
	    }
	}
	if ($next_index < 0) { return 0; } # Oops! No more possibilities!
	dbprint "Setting new guess index: $next_index\n";
	$guess_index = $next_index;
	print "Guessing again at entry ${guess_entry}\n";
    } else {
	#
	# No guess in use => we need to find the best cell to use and go from there
	#

	dbprint "No old guess; looking for a new one\n";
	my $min_freedoms = 10;
	my $best_entry;
	foreach my $entry (0..$board_size-1) {
	    if ($board[$entry]) { next; } # Skip entries which are already filled in

	    $fr = $cell_freedoms[$entry];
	    my $fc = 0;
	    foreach my $i (1..9) {if ($$fr[$i]) { $fc++; }}
	    if ($fc < $min_freedoms) {
		$min_freedoms = $fc;
		$best_entry = $entry;
		dbprint "Found better entry: $entry, freedom count: $fc\n";
		if ($min_freedoms <= 1) { 
		    print "WHOOPS!  Cell $entry has $fc freedoms but wasn't filled in!\n";
		    print_board();
		    die "Mangled board";
		}
	    }
	}
	if (! defined($best_entry)) { # Didn't find anything?? The board is totally filled in.
	    print "WHOOPS! No cells found with which to guess -- the board is filled in!\n";
	    return 0;
	}
	$guess_entry = $best_entry;
	$fr = $cell_freedoms[$guess_entry];
	if ($debug) {
	    print "Freedoms for chosen guess: ";
	    foreach my $v (1..9) {print "$$fr[$v] ";}
	    print "\n";
	}
	my $f;
	foreach $f (1..9) {
	    if ($$fr[$f]) {
		$guess_index = $f;
		last;
	    }
	}
	dbprint "Final guess: $guess_entry, value $guess_index\n";
	my $fc = 81 - count_live_cells();
	print "Guessing at count $fc, cell $guess_entry, with ${min_freedoms} possibilities\n";
    }

    #
    # At this point we have picked the entry to work on but haven't changed the board.
    # Push our state so we can get back here later if we need to backtrack.
    #
    push_state();

    #
    # Finally update the state of the board and return.
    #
    $guess_steps ++;
    $board[$guess_entry] = $guess_index;
    #
    # I *think* we need to set the permanent tag here, though we certainly didn't used to do so. -- 2013-03-24
    # Actually I think we should ditch the permanent tags altogether but that's more work.
    #
    $perm_tags[$guess_entry] = 1;
    push_objects_for_entry $guess_entry;
    return 1;
}

# ****************************************************************
# Count the live cells in the board

sub count_live_cells () {
    my $lc = 0;
    foreach my $c (@board) {
	if (!$c) {
	    $lc ++;
	}
    }
    return $lc;
}

# ****************************************************************
# The backtracker.  Just restore the state and call the guess code.
#

sub ns_backtrack () {
    dbprint "ns_backtrack\n";
    my $live_cells_before = count_live_cells();
    while (1) {
	dbprint "Stepping back...\n";
	if (pop_state() < 0) {
	    dbprint " .. Noplace to go back to -- exhausted possibilities; backtrack failed\n";
	    return 0;
	}

	my $live_cells_after = count_live_cells();
	my $stepped_back_by = $live_cells_after - $live_cells_before;
	my $filled_cells = 81 - $live_cells_after;
	print "Backtracking to count $filled_cells:  Stepped back by $stepped_back_by cells\n";

	$backtrack_steps ++;

	my $guess_ok = ns_guess();
	if ($guess_ok) {
	    dbprint " .. Successfully took another guess at level $board_push_depth -- backtrack won\n";
	    return 1;
	}
	dbprint " .. Exhausted guesses at level $board_push_depth\n";
    }
}

# ****************************************************************
# Natural solver driver

sub natural_solver ($) {
    my ($mode) = @_;

    print "Natural solver starting(mode=$mode); board:\n";

    my $starting_cells = 0;	# Count them up front, so we know how much work we did
    foreach my $c (@board) { if (!$c) {$starting_cells++;} }

    $ns_do_positive_only = 0;

    if ($mode eq "constraints_only") {
	$ns_do_positive_check = 0;
    } elsif ($mode eq "positive_only") {
	$ns_do_positive_check = 0;
	$ns_do_positive_only = 1;
    } elsif ($mode eq "partial_positive") {
	if ($throttle_level > 1) {
	    $ns_do_positive_check = 1;
	}
    } elsif ($mode eq "positive_with_multiset") {
	if ($throttle_level > 1) {
	    $ns_do_positive_check = 1;
	    if ($throttle_level > 2) {
		$ns_do_positive_multiset_check = 1;
	    }
	}
    } elsif ($mode eq "esoteric1") {
	if ($throttle_level > 1) {
	    $ns_do_positive_check = 1;
	    if ($throttle_level > 2) {
		$ns_do_positive_multiset_check = 1;
		if ($throttle_level > 3) {
		    $ns_do_object_to_object_squashes = 1;
		}
	    }
	}
    } elsif ($mode eq "esoteric2") {
	if ($throttle_level > 1) {
	    $ns_do_positive_check = 1;
	    if ($throttle_level > 2) {
		$ns_do_positive_multiset_check = 1;
		if ($throttle_level > 3) {
		    $ns_do_object_to_object_squashes = 1;
		    if ($throttle_level > 4) {
			$ns_do_full_positive_constraints = 1;
		    }
		}
	    }
	}
    } elsif ($mode eq "all_information") {
	if ($throttle_level > 1) {
	    $ns_do_positive_check = 1;
	    if ($throttle_level > 2) {
		$ns_do_positive_multiset_check = 1;
		if ($throttle_level > 3) {
		    $ns_do_object_to_object_squashes = 1;
		    if ($throttle_level > 4) {
			$ns_do_full_positive_constraints = 1;
		    }
		}
	    }
	}
	# If we want to throttle AND allow backtracking we need to change this.
	if ($throttle_level > 5) {
	    $ns_do_backtracking = 1;
	}
    } else {
	die "natural_solver: Argument $mode not understood\n";
    }

    if ($show_solution) {
	print_board();
    }

    setup_natural_solver();

    my $soln_count = 0;

    while (1) {
	my $botch = 0;		# Set => the board locked up
	my $old_push_count = -1; # We're going to iterate pushing everything and doing it again until it stabilizes
	$pushed_on_this_pass = -1;
	while ($pushed_on_this_pass && ! $botch) {
	    if ($pushed_on_this_pass > 0) { # Not the first time through?
		just_push_all_objects;
	    }
	    $pushed_on_this_pass = 0;
	    my $did_something = 1;
	    CONSTRAIN_OBJECTS: while ($did_something) {
		$did_something = 0;

		while (scalar(@row_stack)) {
		    $did_something = 1;
		    if (! ns_process_row (pop_row())) {
			dbprint "Botch after ns_process_row\n";
			$botch = 1;
			last CONSTRAIN_OBJECTS;
		    }
		}

		while (scalar(@col_stack)) {
		    $did_something = 1;
		    if (! ns_process_col (pop_col())) {
			dbprint "Botch after ns_process_col\n";
			$botch = 1;
			last CONSTRAIN_OBJECTS;
		    }
		}

		while (scalar(@square_stack)) {
		    $did_something = 1;
		    if (! ns_process_square (pop_square())) {
			dbprint "Botch after ns_process_square\n";
			$botch = 1;
			last CONSTRAIN_OBJECTS;
		    }
		}
	    }
	}

	if ($l3_did_something || !$displayed_l3_actions) {
	    if ($l3_did_something) {
		$displayed_l3_actions = 1; # If we've shown a nonzero result, no need to show zeroes later on.
	    }
	    print "    l3 actions:    $l3_did_something\n";
	    foreach my $h (1..9) {
		if ($regular_external_hits[$h]) {
		    my $hc = $regular_external_hits[$h];
		    print "      $hc useful external multiset operations at size $h\n";
		}
	    }
	    if (length $regular_external_record > 0) {
		print "      L3 external record: ${regular_external_record}\n";
	    }
	    foreach my $h (1..9) {
		if ($regular_internal_hits[$h]) {
		    my $hc = $regular_internal_hits[$h];
		    print "      $hc useful internal multiset operations at size $h\n";
		}
	    }
	    if (length $regular_internal_record > 0) {
		print "      L3 internal record: ${regular_internal_record}\n";
	    }
	    # Clear these again -- we've seen them, no need to see them again.
	    @regular_external_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
	    @regular_internal_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
	    $regular_external_record = "";
	    $regular_internal_record = "";
	    $l3_star_adjustment += $l3_did_something;
	    $l3_did_something = 0;
	}

	## The l4 action count isn't actually maintained, so don't bother to print it.
	## "    l4 actions:    $l4_did_something\n";

	# Blew out => if we were in guess country, backtrack.
	if ($botch) {
	    dbprint "Botched -- calling backtrack\n";
	    if (ns_backtrack()) {
		dbprint "Backtrack won -- going around again\n";
		next;
	    }
	    return 0;		# Can't backtrack => give up
	}

	if (win_check()) {	# We try for TWO solutions.
	    $soln_count++;
	    if ($soln_count > 1) {
		print "\n**SECOND** solution:\n";
		if ($show_solution) { print_board(); }
		last;
	    } else {
		print "Solved.\n";
		print "\nSolution:\n";
		if ($show_solution) { print_board(); }
		if ($guess_steps > 0) {
		    print "\n    Guess steps:     $guess_steps\n" .
			"    Backtrack steps: $backtrack_steps\n" .
			"    Max depth:       $max_board_push_depth\n" .
		        "    Final depth:     $board_push_depth\n\n";
		}
		if (ns_backtrack()) {
		    print "\nLooking for another solution.\n";
		    next;
		} else {
		    last;
		}
	    }
	}

	# Got here => we need to guess

	if (! $ns_do_backtracking) { # If we're not guessing, then we're done.
	    dbprint "win_check failed -- we couldn't solve it\n";
	    last;
	}

	dbprint "win_check failed -- going to have to guess\n";

	if (! ns_guess()) {	# Note that ns_guess handles the need to backtrack to find the next guess
	    return 0;
	}
    }
    
    print "\n";
    dump_push_counts();
    if ($ns_do_object_to_object_squashes) {
	print "Object squash operations:       $squash_val_in_obj_actions\n";
	if ($productive_squashes) {
	    print "    $productive_squashes total squash operations\n";
	    $l4_star_adjustment += $productive_squashes;
	    $productive_squashes = 0;
	}
    }
    if ($ns_do_full_positive_constraints) {
	print "Exterior multiset freedom zaps: $exterior_freedom_zaps\n";
	for my $j (1..9) {
	    if ($irregular_multiset_hits[$j]) {
		my $hc = $irregular_multiset_hits[$j];
		$l5_star_adjustment += $hc;
		print "    $hc productive irregular multiset hits of size $j\n";
	    }
	}
	if (length $irregular_external_record > 0) {
	    print "    Irregular external record: ${irregular_external_record}\n";
	}
	@irregular_multiset_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0); # Clear it again
	print "Interior multiset freedom zaps: $interior_freedom_zaps\n";
	for my $j (1..9) {
	    if ($irregular_interior_hits[$j]) {
		my $hc = $irregular_interior_hits[$j];
		print "    $hc productive irregular internal hits of size $j\n";
	    }
	}
	@irregular_interior_hits = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0); # Clear it again
    }
    print "\n";

    $total_row_push_count += $row_push_count;
    $total_col_push_count += $col_push_count;
    $total_square_push_count += $square_push_count;
    $grand_total_push_count += $total_push_count;

    my $result_code = 1;	# 1 => no errors, but may or may not have won
    if (win_check()) {
	print "Natural solver done; we won.\n";
##	print "Solution:\n";
	$result_code = 2;	# 2 => we won
    } else {
	my $ending_cells = 0;
	foreach my $c (@board) {if (!$c) {$ending_cells++;}}
	my $diff = $starting_cells - $ending_cells;
	print "Natural solver done; filled in $diff cells on this pass; board:\n";
	if ($show_solution) {
	    print_board();
	}
    }
##    if ($show_solution) {
##	print_board();
##    }
    return $result_code;
}

# ****************************************************************
# End natural solver routines
# ****************************************************************
# Process arguments

while ($_ = shift) {
    my $arg = $_;
    if ($arg =~ /^-silent/) {
	##$silent = 1;
    } elsif ($arg =~ /^-verbose/) {
	##$silent = 0;
    } elsif ($arg =~ /-no_sort/) {
	##$do_sort = 0;
    } elsif ($arg =~ /-do_sort/) {
	##$do_sort = 1;
    } elsif ($arg =~ /-no_square/) {
	##$square_sort = 0;
    } elsif ($arg =~ /-no_show/) {
	$show_solution = 0;
    } elsif ($arg =~ /-no_natural/) {
	## $do_natural = 0;
    } elsif ($arg eq "-no_hybrid") {
	##$hybrid_mode = 0;
    } elsif ($arg =~ /-level/) {
	$throttle_level = shift;
    } elsif ($arg =~ /-positive_first/) {
	$positive_first = 1;
    } elsif ($arg =~ /-all_at_once/) {
	$all_at_once = 1;
    } elsif ($arg =~ /-for_build/) {
	$do_for_build = 1;
    } elsif ($arg eq "-possibilities") {
	$just_possibilities = 1;
    } elsif ($arg =~ /-debug/) {
	$debug = 1;
    } elsif (!defined($fname)) {
	$fname = $_;
    } else {
	die "Argument $arg not understood\n";
    }
}

##if ($debug) { $silent = 0; }

# ****************************************************************
# Drive the program

setup_board();

if ($just_possibilities) {	# In this case just dump the possibility list, for use by the board builder.
    find_possibility_counts();
    print "(";
    foreach my $i (0..$board_size-1) {
	if ($i) { print ",\n "; }
	print "[";
	if ($board[$i]) {
	    print "$board[$i]";
	} else {
	    my $comma = "";
	    my $poss_list = $possibility_lists[$i];
	    foreach my $v (@$poss_list) {
		print "${comma}$v";
		$comma = ", ";
	    }
	}
	print "]";
    }
    print ")\n";
    exit;
}

    if (! $do_for_build) {
	if (!$all_at_once) {
	    find_possibility_counts();
	    assess_difficulty();
	    my $count_at_this_level = 0;

	    if ($positive_first) {
		natural_solver("positive_only");
	    }

	    if (! win_check()) {
		$solver_level = 1;
		natural_solver("constraints_only");
	    }

	    $count_at_this_level = $old_live_count;
	    my $csl = $solver_level;
	    if (! win_check() && $throttle_level > $solver_level) {
		find_possibility_counts();
		print "\nBoard assessment after first pass:\n";
		$count_at_this_level = assess_difficulty();
		$solver_level = 2;
		natural_solver("partial_positive");
	    }
	    $solved_cells_at_level[$csl] = $count_at_this_level;

	    $count_at_this_level = $old_live_count;
	    $csl = $solver_level;
	    if (! win_check() && $throttle_level > $solver_level) {
		find_possibility_counts();
		print "\nBoard assessment after second pass:\n";
		$count_at_this_level = assess_difficulty();
		$solver_level = 3;
		natural_solver("positive_with_multiset");
	    }
	    $solved_cells_at_level[$csl] = $count_at_this_level;

	    $count_at_this_level = $old_live_count;
	    $csl = $solver_level;
	    if (! win_check() && $throttle_level > $solver_level) {
		find_possibility_counts();
		print "\nBoard assessment after third pass:\n";
		$count_at_this_level = assess_difficulty();
		$solver_level = 4;
		natural_solver("esoteric1");
	    }
	    $solved_cells_at_level[$csl] = $count_at_this_level;

	    $count_at_this_level = $old_live_count;
	    $csl = $solver_level;
	    if (! win_check() && $throttle_level > $solver_level) {
		find_possibility_counts();
		print "\nBoard assessment after fourth pass:\n";
		$count_at_this_level = assess_difficulty();
		$solver_level = 5;
		natural_solver("esoteric2");
	    }
	    $solved_cells_at_level[$csl] = $count_at_this_level;

	}
	if (! win_check()) {
	    find_possibility_counts();
	    if (!$all_at_once) {
		print "\nBoard assessment after fifth pass:\n";
		$solver_level = 6;
	    }
	    my $solved_count = assess_difficulty();
	    $solved_cells_at_level[5] = $solved_count;
	    natural_solver("all_information");
	}

	print "\nGrand totals:\n" .
	    "    Row pushes:         $total_row_push_count\n" .
	    "    Col pushes:         $total_col_push_count\n" .
	    "    Square pushes:      $total_square_push_count\n" .
	    "    Grand total pushes: $grand_total_push_count\n\n";

	if ($solver_level > 1) {
	    print "Solved cells at each level:  ";
	    my $sep = "";
	    foreach my $l (1..5) {
		my $sc = $solved_cells_at_level[$l];
		if (defined ($sc)) {
		    print "${sep}${l}:${sc}";
		    $sep = ", ";
		}
	    }
	    print "\n";
	}

	if ($guess_steps > 0) {
	    print "    Guess steps:     $guess_steps\n" .
		"    Backtrack steps: $backtrack_steps\n" .
		"    Max depth:       $max_board_push_depth\n" .
		"    Final depth:     $board_push_depth\n\n";
	}
	    
    } else {
	natural_solver("positive_with_multiset");
	if (!win_check()) {
	    print "Having trouble here -- running level 6\n";
	    natural_solver "all_information";
	}
    }

my $offset_live_cells =	-55.0;
my $scale_live_cells =	0.37;
my $offset_average =	0.0;
my $scale_average =	1.0;
my $offset_ratio =	-0.5;
my $scale_ratio =	3.0;
my $offset_solver =	-2.0;
my $scale_solver =	1.0;

my $star_1 =		1.5;
my $star_2 =		3.25;
my $star_3 =		4.5;
my $star_4 =		10.0;
my $star_5 =		13.0;

if (! $do_for_build) {

    my $raw_rating = ($offset_live_cells + $first_live_cell_count) * $scale_live_cells +
	($offset_average + $first_average) * $scale_average +
	($offset_ratio + $first_hi_lo_ratio) * $scale_ratio +
	($offset_solver + $solver_level) * $scale_solver;

    my $rating_level_adjustment = 0;

    if ($solver_level > 2) {	# Adjust the raw rating for high-level boards

	my $offset_l1_l2 = -20.0;
	my $scale_l1_l2 = -0.1;	# Note that this is NEGATIVE

	my $offset_l3_star_adjustment = 0.0;
	my $scale_l3_star_adjustment = 0.5;

	my $offset_l4_star_adjustment = 0.0;
	my $scale_l4_star_adjustment = 1.0;

	my $offset_l5_star_adjustment = 0.0;
	my $scale_l5_star_adjustment = 1.5;

	my $l1_l2 = $solved_cells_at_level[1] + $solved_cells_at_level[2];
	
	$rating_level_adjustment =
	    ($offset_l1_l2 + $l1_l2) * $scale_l1_l2 +
	    ($offset_l3_star_adjustment + $l3_star_adjustment) * $scale_l3_star_adjustment + 
	    ($offset_l4_star_adjustment + $l4_star_adjustment) * $scale_l4_star_adjustment + 
	    ($offset_l5_star_adjustment + $l5_star_adjustment) * $scale_l5_star_adjustment;
    }

    my $total_raw_rating = $raw_rating + $rating_level_adjustment;

    my $stars = $total_raw_rating < $star_1 ? 1 :
	$total_raw_rating < $star_2 ? 2 :
	$total_raw_rating < $star_3 ? 3 :
	$total_raw_rating < $star_4 ? 4 :
	$total_raw_rating < $star_5 ? 5 :
	6;
	
    print "\n";
    print  "Solver level: $solver_level\n";
    printf "Raw rating:   %.2f\n", $raw_rating;
    if ($rating_level_adjustment) {
	printf "Level adjustment:  %.2f\n", $rating_level_adjustment;
    }
    print  "Stars:        $stars\n";
}

print "\nDone.\n\n";