Commits

Anonymous committed f5c142e

Implement a bug fix for the fully-expand black region.

Comments (0)

Files changed (2)

nurikabe-solver/Games-Nurikabe-Solver/lib/Games/Nurikabe/Solver/Board.pm

 
                 my %adjacent_unknowns;
 
+                my $this_black_region_cells_count = 0;
+
                 # TODO : abstract all BrFS searches into a common code.
                 QUEUE_LOOP:
                 while (my $coords = shift(@queue))
                     }
 
                     $q_c->already_processed(1);
+                    $this_black_region_cells_count++;
+
                     $self->_vicinity_loop(
                         $coords,
                         sub {
                 }
 
                 my @k = keys(%adjacent_unknowns);
-                if (@k == 1)
+
+                # Make sure we don't expand a black region that contains
+                # all known black cells in the board, because these cells
+                # may well as be white.
+                if (($this_black_region_cells_count < 
+                    $self->_found_totals->{$NK_BLACK})
+                        && (@k == 1)
+                )
                 {
                     # Bingo - this black region only has one cell to expand to.
                     $self->_mark_as_black($adjacent_unknowns{$k[0]});
                     $found = 1;
                 }
             }
+
+            return;
         }
     );
 

nurikabe-solver/Games-Nurikabe-Solver/t/solve1.t

 use strict;
 use warnings;
 
-use Test::More tests => 84;
+use Test::More tests => 85;
 
 use Test::Differences;
 
         "Expanded cells contain (4,2)",
     );
 }
+
+# Test the expand_black_regions does not expand when all the black cells are
+# fully connected, because otherwise these cells may be white.
+{
+    my $string_representation = <<"EOF";
+Width=5 Height=5
+[] [6] [] [] []
+[] [] [] [2] []
+[] [] [] [] []
+[] [1] [] [] []
+[] [] [] [2] []
+EOF
+
+    my $board =
+        Games::Nurikabe::Solver::Board->load_from_string(
+            $string_representation
+        );
+
+    foreach my $method (qw(
+        surround_island
+        surrounded_by_blacks
+        distance_from_islands
+        fully_expand_island
+        expand_black_regions
+        adjacent_whites
+        expand_black_regions
+        fully_expand_island
+        expand_black_regions
+        ))
+    {
+        my $moves = $board->_solve_using( { name => $method } );
+
+        if (!@$moves)
+        {
+            die "No moves for method $method.";
+        }
+    }
+
+    my $moves = $board->_solve_using(
+        {
+            name => "expand_black_regions",
+            params => {},
+        }
+    );
+
+    # TEST
+    eq_or_diff (
+        $moves,
+        [],
+        "No moves were done as the black region is fully connected."
+    );
+}