# ETOOBUSY đźš€ minimal blogging for the impatient

# Aquarium - more cooperation from constraints

TL;DR

Making only one constraint cooperate is a good start, but we can do better. And we will!

The code for this post can be found in stage 6.

# Getting the most out of row and column constraints

Letâ€™s take a look at the following row in a possible puzzle:

```
+---------------+-------+-----------------------+
| | | |
4 | | | |
| | | |
| +-------+~~~~~~~+-------+ +-------+
```

Can we infer anything from it? Yes, definitely!

Letâ€™s first observe that the three-cells block on the right can either be completely empty, or completely full. Thereâ€™s no half-way, because the rules of the game tell us so.

At this point we can ask ourselves: can it be empty? Certainly not! If we
miss this precious three-cells spot, we will be left with only 3 candidate
cells on this row for holding water, which is *never* going to address the
need to have 4 spots filled with water. As a consequenceâ€¦ it *must* be
filled with water:

```
+---------------+-------+-----------------------+
| | |~~~~~~~~~~~~~~~~~~~~~~~|
4 | | |~~~~~~~~~~~~~~~~~~~~~~~|
| | |~~~~~~~~~~~~~~~~~~~~~~~|
| +-------+~~~~~~~+-------+~~~~~~~+-------+
```

Now we can also do a similar reasoning about the two-cells spot on the left,
which - again - itâ€™s take-all or leave-all. Can it *possibly* be part of the
solution? Surely not! If we include it, we end up with 5 filled cells in
this row, which is not allowed. Hence, we *must* set this spot to empty:

```
+---------------+-------+-----------------------+
| | |~~~~~~~~~~~~~~~~~~~~~~~|
4 | X X | |~~~~~~~~~~~~~~~~~~~~~~~|
| | |~~~~~~~~~~~~~~~~~~~~~~~|
| +-------+~~~~~~~+-------+~~~~~~~+-------+
```

Now, of course, thereâ€™s only one way to fulfil the constraint, i.e. put water in the remaining unknown cell:

```
+---------------+-------+-----------------------+
| |~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~|
4 | X X |~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~|
| |~~~~~~~|~~~~~~~~~~~~~~~~~~~~~~~|
| +-------+~~~~~~~+-------+~~~~~~~+-------+
```

This was an easy line, because we were able to figure it out completely by
itself. Life is not always *this* easy, but this trick is surely interesting
to consider and get some pruning from our extensive search.

There is also a *similar* - although less powerful - version of this
constraint that can be applied to column-wise constraints. Can you figure it
out?

# Letâ€™s code this

The following function turn the insights of the previous section into code:

```
1 sub adjust_by_row ($puzzle) {
2 my ($n, $items_by_row, $field, $status)
3 = $puzzle->@{qw< n items_by_row field status >};
4 my $acted = 0;
5 for my $i (0 .. $n - 1) {
6 my $needed = $items_by_row->[$i];
7 my $available = $n;
8 my %available_by_id;
9 for my $j (0 .. $n - 1) {
10 $needed-- if $status->[$i][$j] > 0;
11 $available-- if $status->[$i][$j];
12 my $id = $field->[$i][$j];
13 push $available_by_id{$id}->@*, $j unless $status->[$i][$j];
14 }
15 die 'unfeasible' if $needed < 0;
16 die 'unfeasible' if $needed > $available;
17 for my $id (keys %available_by_id) {
18 my $av = $available_by_id{$id};
19 if ($av->@* > $needed) { # can't serve this here
20 $status->[$i][$_] = -1 for $av->@*;
21 $acted++;
22 }
23 elsif ($available - $av->@* < $needed) { # need this
24 $status->[$i][$_] = 1 for $av->@*;
25 $acted++;
26 }
27 }
28 }
29 return $acted;
30 }
```

Rows are analyzed from top to bottom (line 5). It would also work in reverse, because this constraint is only focused on one row at a time.

There are two sweeps:

- the first sweep (lines 9..14) analyze the row and get some data: how many
*unknown*spots (named*available*) are there, both in total and by aquarium id, as well as how many of them still need to be allocated some water (variable`$needed`

). - the second sweep implements the insight of the previous section, both
*inclusively*and*exclusively*:- lines 19..22 check whether a specific aquarium would overflow the need, excluding it if this is the case (just like the example of the two-cells spot in the previous section);
- lines 23..26 check whether excluding a specific aquarium would result in an excessive loss of available spots, and forces its inclusion if it does (just liek the example of the three-cells spot in the previous section).

Between the two sweeps there is a sanity check: if the number of needed cells dropped below 0, it means that we filled too many cells; otherwise, if itâ€™s beyond the number of available unknown spots, we are never going to fulfil this constraint. In both cases we throw an exception.

# Letâ€™s code the column-wise pruning constraint too

As anticipated, there is a weaker version of the deduction-by-constraint trick that can be applied to columns, here is the code for it:

```
1 sub adjust_by_col ($puzzle) {
2 my ($n, $items_by_col, $field, $status)
3 = $puzzle->@{qw< n items_by_col field status >};
4 my $acted = 0;
5 for my $j (0 .. $n - 1) {
6 my $needed = $items_by_col->[$j];
7 my $available = $n;
8 my %available_by_id;
9 for my $i (0 .. $n - 1) {
10 $needed-- if $status->[$i][$j] > 0;
11 $available-- if $status->[$i][$j];
12 my $id = $field->[$i][$j];
13 push $available_by_id{$id}->@*, $i unless $status->[$i][$j];
14 }
15 die 'unfeasible' if $needed < 0;
16 die 'unfeasible' if $needed > $available;
17 for my $id (keys %available_by_id) {
18 my $av = $available_by_id{$id};
19 if ($available - $av->@* < $needed) { # need this
20 my $take = $needed - ($available - $av->@*);
21 $status->[pop $av->@*][$j] = 1 for 1 .. $take;
22 $available -= $take;
23 $needed -= $take;
24 $acted++;
25 }
26 elsif ($av->@* > $needed) { # remove excess
27 $status->[shift $av->@*][$j] = -1 while $av->@* > $needed;
28 $acted++;
29 }
30 # there should be more to this
31 }
32 }
33 return $acted;
34 }
```

As before, we have an outer loop sweeping through columns, then two sequential inner loops sweeping through rows. The first of these two inner loops collects data, the second makes the inferences and updates the status if possible. Again, there is a sanity check in between.

# Letâ€™s put these new constraints at work

The two new constraints together are an enhanced version of the previous constraint about row and column values, so we can remove the old one and put thest two instead:

```
sub apply_constraints ($puzzle) {
my $changes = -1;
while ($changes != 0) {
$changes = 0;
$changes += adjust_water_level($puzzle);
$changes += adjust_by_col($puzzle);
$changes += adjust_by_row($puzzle);
}
}
```

# How does it go?

Things are getting definitely better with this enhancement, the 6x6 are now
all tackled, the 10x10 are fine up to level *normal* and we might get a
10x10 *hard* puzzle solved in a reasonable time if we get particularly
lucky.

This is an example for a 10x10 *normal*:

But letâ€™s not start suc**AHEM** *get too excited* yet: most of the 10x10
hard problems are still too slow, and we have to address the 15x15, the
daily, the weekly and the monthly puzzles yet!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*