fill this grid with water!

Question

In this puzzle you have to fill with water some cells of the grid. The number of filled squares in each row and column is written next to it.

You can't fill a square if the squares connected to it (under, left and right) in the same region are empty. Also, you can't fill a square if the square under it is empty because the water would fall down (you should pay attention to simple physics laws such as gravity).

Here are 2 wrong examples:

1 - you can't fill half of a imaginary square:

2 - you should pay attention to gravity:

And this is the question:

This puzzle has been invented by Sharif university's students.

EDIT: If OP doesn't mind, here is the grid in ASCII form. Regions are represented by letters A-Z and numbers 0-3.

AAABCCDDDDEE
FABBBCGGEEEH
FAAICCGJJEHH
IIIIKGGLJJJH
IMIKKKKLLNNH
MMMMKOPPLLNQ
MRROOOPSSNNQ
TRUOUPPPSSNQ
TRUUUVWPXYYY
RRZZZVWWXX0Y
1ZZ2VVVWX00Y
1112222W3300

Answer 1

The solution is as follows:

        

My Java-based solver is viewable here.

The solver is a quasi-brute-forcer with efficient backtracking. The major headache was that I initially assumed both "wells" in piece 9 were simultaneously full or empty. However, no solution exists for either of these cases. Much time was spent trying to figure out what was wrong with the blasted solver that kept (correctly) returning "no solution", "no solution".

After reconsidering my assumption and hard-coding in one of the ugliest hacks in the history of ugly hacks, the solver yielded the above solution in slightly under a second.

Special thanks to Tryth for a flood-fillable graphic, and to Victor, whose lengthy analysis instantly convinced me that converting this problem to SAT (which was my first inclination as well) would not have been a fun way to solve this problem.

Answer 2

NOTE, THIS IS A PARTIAL AND INCOMPLETE ANSWER.

First step, lets give a letter to each area (we have 30 areas, so we need to be case-sensitive):

$$ \begin{array}{cccccccccccc} z & z & z & C & A & A & D & D & D & D & B & B \\ y & z & C & C & C & A & w & w & B & B & B & v \\ y & z & z & u & A & A & w & x & x & B & v & v \\ u & u & u & u & s & w & w & t & x & x & x & v \\ u & r & u & s & s & s & s & t & t & p & p & v \\ r & r & r & r & s & n & m & m & t & t & p & q \\ r & j & j & n & n & n & m & o & o & p & p & q \\ k & j & l & n & l & m & m & m & o & o & p & q \\ k & j & l & l & l & g & c & m & h & i & i & i \\ j & j & f & f & f & g & c & c & h & h & e & i \\ a & f & f & b & g & g & g & c & h & e & e & i \\ a & a & a & b & b & b & b & c & d & d & e & e \\ \end{array}$$

Now, lets number each one accordingly to its water-level:

$$ \begin{array}{cccccccccccc} z_3 & z_3 & z_3 & C_2 & A_3 & A_3 & D_1 & D_1 & D_1 & D_1 & B_3 & B_3 \\ y_2 & z_2 & C_1 & C_1 & C_1 & A_2 & w_3 & w_3 & B_2 & B_2 & B_2 & v_4 \\ y_1 & z_1 & z_1 & u_3 & A_1 & A_1 & w_2 & x_2 & x_2 & B_1 & v_3 & v_3 \\ u_2 & u_2 & u_2 & u_2 & s_3 & w_1 & w_1 & t_3 & x_1 & x_1 & x_1 & v_2 \\ u_{1a} & r_3 & u_{1b} & s_2 & s_2 & s_2 & s_2 & t_2 & t_2 & p_4 & p_4 & v_1 \\ r_2 & r_2 & r_2 & r_2 & s_1 & n_3 & m_4 & m_4 & t_1 & t_1 & p_3 & q_3 \\ r_1 & j_4 & j_4 & n_2 & n_2 & n_2 & m_3 & o_2 & o_2 & p_2 & p_2 & q_2 \\ k_2 & j_3 & l_2 & n_1 & l_2 & m_2 & m_2 & m_2 & o_1 & o_1 & p_1 & q_1 \\ k_1 & j_2 & l_1 & l_1 & l_1 & g_3 & c_4 & m_1 & h_3 & i_3 & i_3 & i_3 \\ j_1 & j_1 & f_2 & f_2 & f_2 & g_2 & c_3 & c_3 & h_2 & h_2 & e_3 & i_2 \\ a_2 & f_1 & f_1 & b_2 & g_1 & g_1 & g_1 & c_2 & h_1 & e_2 & e_2 & i_1 \\ a_1 & a_1 & a_1 & b_1 & b_1 & b_1 & b_1 & c_1 & d_1 & d_1 & e_1 & e_1 \\ \end{array}$$

Now, we take every different symbol as a variable. We can reduce this to a boolean formula with 83 variables: $a_1, a_2, b_1, b_2, c_1, c_2, c_3, c_4, d_1, e_1, e_2, e_3, f_1, f_2, g_1, g_2, g_3, h_1, h_2, h_3, i_1, i_2, i_3, j_1, j_2, j_3, j_4, k_1, k_2, l_1, l_2, m_1, m_2, m_3, m_4, n_1, n_2, n_3, o_1, o_2, p_1, p_2, p_3, p_4, q_1, q_2, q_3, r_1, r_2, r_3, s_1, s_2, s_3, t_1, t_2, t_3, u_{1a}, u_{1b}, u_2, u_3, v_1, v_2, v_3, v_4, w_1, w_2, w_3, x_1, x_2, y_1, y_2, z_1, z_2, z_3, A_1, A_2, A_3, B_1, B_2, B_3, C_1, C_2, D_1$

Lets mount the formula. First the gravity constraints, they have the format $(\delta_{i+1} \to \delta_i)$, which can be simplified to $(\lnot\delta_{i+1} \lor \delta_i)$. We have 53 gravity constraints:

$$ \begin{array}{cccccccccc} (\lnot a_2 \lor a_1) & \land & (\lnot b_2 \lor b_1) & \land & (\lnot c_2 \lor c_1) & \land & (\lnot c_3 \lor c_2) & \land & (\lnot c_4 \lor c_3) & \land \\ (\lnot e_2 \lor e_1) & \land & (\lnot e_3 \lor e_2) & \land & (\lnot f_2 \lor f_1) & \land & (\lnot g_2 \lor g_1) & \land & (\lnot g_3 \lor g_2) & \land \\ (\lnot h_2 \lor h_1) & \land & (\lnot h_3 \lor h_2) & \land & (\lnot i_2 \lor i_1) & \land & (\lnot i_3 \lor i_2) & \land & (\lnot j_2 \lor j_1) & \land \\ (\lnot j_3 \lor j_2) & \land & (\lnot j_4 \lor j_3) & \land & (\lnot k_2 \lor k_1) & \land & (\lnot l_2 \lor l_1) & \land & (\lnot m_2 \lor m_1) & \land \\ (\lnot m_3 \lor m_2) & \land & (\lnot m_4 \lor m_3) & \land & (\lnot n_2 \lor n_1) & \land & (\lnot n_3 \lor n_2) & \land & (\lnot o_2 \lor o_1) & \land \\ (\lnot p_2 \lor p_1) & \land & (\lnot p_3 \lor p_2) & \land & (\lnot p_4 \lor p_3) & \land & (\lnot q_2 \lor q_1) & \land & (\lnot q_3 \lor q_2) & \land \\ (\lnot r_2 \lor r_1) & \land & (\lnot r_3 \lor r_2) & \land & (\lnot s_2 \lor s_1) & \land & (\lnot s_3 \lor s_2) & \land & (\lnot t_2 \lor t_1) & \land \\ (\lnot t_3 \lor t_2) & \land & (\lnot u_2 \lor u_{1a}) & \land & (\lnot u_2 \lor u_{1b}) & \land & (\lnot u_3 \lor u_2) & \land & (\lnot v_2 \lor v_1) & \land \\ (\lnot v_3 \lor v_2) & \land & (\lnot v_4 \lor v_3) & \land & (\lnot w_2 \lor w_1) & \land & (\lnot w_3 \lor w_2) & \land & (\lnot x_2 \lor x_1) & \land \\ (\lnot y_2 \lor y_1) & \land & (\lnot z_2 \lor z_1) & \land & (\lnot z_3 \lor z_2) & \land & (\lnot A_2 \lor A_1) & \land & (\lnot A_3 \lor A_2) & \land \\ (\lnot B_2 \lor B_1) & \land & (\lnot B_3 \lor B_2) & \land & (\lnot C_2 \lor C_1) & & & & & \\ & \\ \end{array}$$

Now, we should model the constraint for each row. For any given line with $x$ variables, there would be $2^x$ possible ways to value the variables. So, for the 1st and 12th rows there are 32 possible ways to choose the variables for each one. For the 4th row, there are 64 ways. For the 2nd, 5th, 6th, 7th and 10th rows there are 128 ways. For the 3rd, 9th and 11th rows there are 256 ways. For the 8th row there are 512 ways. However, only the ways that satisfy the given number for each line should be considered.

1st row: $$ \begin{array}{cccccccccccc} ( & z_3 & \land & C_2 & \land & \lnot A_3 & \land & \lnot D_1 & \land & \lnot B_3 & ) & \lor \\ ( & \lnot z_3 & \land & \lnot C_2 & \land & A_3 & \land & \lnot D_1 & \land & B_3 & ) & \lor \\ ( & \lnot z_3 & \land & \lnot C_2 & \land & \lnot A_3 & \land & D_1 & \land & \lnot B_3 & ) & \\ \end{array}$$

4th row: $$ \begin{array}{cccccccccccc} ( & u_2 & \land & s_3 & \land & \lnot w_1 & \land & \lnot t_3 & \land & \lnot x_1 & \land & \lnot v_2 & ) & \lor \\ ( & u_2 & \land & \lnot s_3 & \land & \lnot w_1 & \land & t_3 & \land & \lnot x_1 & \land & \lnot v_2 & ) & \lor \\ ( & u_2 & \land & \lnot s_3 & \land & \lnot w_1 & \land & \lnot t_3 & \land & \lnot x_1 & \land & v_2 & ) & \lor \\ ( & \lnot u_2 & \land & s_3 & \land & w_1 & \land & t_3 & \land & \lnot x_1 & \land & v_2 & ) & \lor \\ ( & \lnot u_2 & \land & s_3 & \land & \lnot w_1 & \land & t_3 & \land & x_1 & \land & \lnot v_2 & ) & \lor \\ ( & \lnot u_2 & \land & \lnot s_3 & \land & w_1 & \land & \lnot t_3 & \land & x_1 & \land & \lnot v_2 & ) & \lor \\ ( & \lnot u_2 & \land & \lnot s_3 & \land & \lnot w_1 & \land & t_3 & \land & x_1 & \land & v_2 & ) & \\ \end{array}$$

12th row: $$ \begin{array}{cccccccccccc} ( & a_1 & \land & \lnot b_1 & \land & c_1 & \land & d_1 & \land & \lnot e_1 & ) & \lor \\ ( & a_1 & \land & \lnot b_1 & \land & c_1 & \land & \lnot d_1 & \land & e_1 & ) & \lor \\ ( & \lnot a_1 & \land & b_1 & \land & \lnot c_1 & \land & d_1 & \land & \lnot e_1 & ) & \lor \\ ( & \lnot a_1 & \land & b_1 & \land & \lnot c_1 & \land & \lnot d_1 & \land & e_1 & ) & \\ \end{array}$$

Note: I did not modeled the other rows. Too tired.

For each column there are exact 12 variables, so we can value each column in 4096 different ways. Again, only a few satisfy the given numbers. Further, violations to the gravity constraints should obviously be discarded.

Note: I did not modeled the columns. Too tired.

In the end we get a boolean formula like this:

$$\text{gravity constraints} \land \text{1st row constraints} \land \text{2nd row constraints} \land \text{3rd row constraints} \land \text{4th row constraints} \land \text{5th row constraints} \land \text{6th row constraints} \land \text{7th row constraints} \land \text{8th row constraints} \land \text{9th row constraints} \land \text{10th row constraints} \land \text{11th row constraints} \land \text{12th row constraints} \land \text{1st column constraints} \land \text{2nd column constraints} \land \text{3rd column constraints} \land \text{4th column constraints} \land \text{5th column constraints} \land \text{6th column constraints} \land \text{7th column constraints} \land \text{8th column constraints} \land \text{9th column constraints} \land \text{10th column constraints} \land \text{11th column constraints} \land \text{12th column constraints}$$

And then we will need to "just" solve that boolean formula.

To simplify the formula, at the 1st row, we can see that:

$z_3 = C_2$
$A_3 = B_3$

At the 12th row, we can see that:

$b_1 = \lnot a_1$
$c_1 = a_1$
$d_1 = \lnot e_1$

So, with this we can reduce the number of variables from 83 to 78.

Note: I will stop by now. Too tired.

Answer 3

It was fun, but took a lot of time, so:

My solution, now with comment (and adapted to fix some oversights)

EDIT: I added step-by step pictures of the first quarter (first 5 pictures) of the puzzle. note: The flawed logic of the fourth deduction is improved here

The more condense original solution:

Picture 1: Plan: Exclude possibilities one by one, using situations that may lead quickly to contradiction

• very wet or dry rows/columns
• rows with few options (top row: 3, bottom row: 4)
• wet rows directly above dry rows (7 above 4, 6 above 4)
• and adjacent dry + wet columns (4-8, 4-7)

Obvious first candidate : tile 13: If the indicated tiles are wet, the rest is dry, including 11,12,14 on the row above. Only 4 tiles (the red) can thus be wet there - contradiction -> 13 is dry on those 2 rows.

Picture 2: On the top row , only blue, only orange or only yellow is wet. Assume blue. Then the 4-8 columns are now 2-7 and all 5 (dark blue) tiles that give the 7 more water must be used. This also makes light blue wet, and the rest of column 3 and 4 must then be dry. Especially, in the bottom row 28 and 29 will be dry, allowing only the 5 red tiles to be wet. - contradiction -> 1 is dry on the top row.

Picture 3: Assume 25 is fully filled with water. Then 21 is fully dry, and also 18 or 20. T get to 7 on the row above 16 mus be wet there. Thus the bottom of 16 is wet, and 18 and 20 are completely dry. All remaining tiles of column 2 and 5 must then be wet, leading to contradiction on the bottom row.

Picture 4: Assume 9 is wet on row 4 (part 1) The 4-8 columns are now 3-8, and 5 of the 6 possibilities to reduce this (dark blue) must be used. If 21 is used, only 1 of the 4 yellow tiles can be used , and column 2 cannot reach 6. So the rest is used.

Picture 5: Assume 9 is wet on row 4 (part 2) Thus 3 and 11 must be fully wet, as well as the bottom of 22. This defines row 1,4 and 5 fully, which forces water due to varies column constraints , and 30 to be dry. Row 10 now forces 23 and 26 to be dry there, and then column 7 the bottom of 16 to be wet and the rest of row 8 to be dry. Now both orange tiles need to be wet. - contradiction -> 9 is dry on row 4. In addition (column 2), the bottom half of 18 must be wet.

Picture 6: Assume 11 is mostly dry (part 1)
Then 14 and the bottom of 10 must be wet due to row 4+5. This leaves 1 remaining wet tile (a pink) for column 11, i.e. not at the top row; i.e in the top row only 4 is wet. All 4 now remaining spots in column 5 to compensate the difference in column 4 and 5 (dark blue) must be used, and 15 must be dry.

Picture 7: Assume 11 is mostly dry (part 2)
The rest of row 9 must be dry. On row 8, block 16 and 20 are then dry, and column 6 has 6 dry tiles. - contradiction -> 11 is wet on row 5.

Picture 8: Assume 29 is not completely dry (part 1)
Then (row 12) 28 and 23 are dry. With that (1 dry missing in column 2 and 3) we must add some water to 1, 18 and 26.
Now assume 21 is dry, then (column 3) 2 and 26 cannot both be fully dry and thus (column 4) 15 cannot be wet on row 7.
If (row 10) 26 is wet, the rest is dry and row 9 cannot have 4 wet tiles, so 26 is partly dry, and the rest of column 5 wet.
Then we can fill in row 1, with a contradiction on row 2. Thus 21 must be partly blue.

Picture 9: Assume 29 is not completely dry (part 2)
Since 21 is partly wet, the rest of row 9 is dry.
16 dry makes 18,19 and 14 wet on row 7 (1 dry spot left); 21 wet on row 8 1 dry spot left and 12 wet in column 8, which makes the rest of column 5 dry.
column 6 (1 dry left) and 7 (1 wet left) define 3 and 7 further.

Picture 10: Assume 29 is not completely dry (part 3)
At row 4 10 must be wet, which makes the top of 24 dry, which makes the rest of row 10 wet, which makes the rest of column 11 dry.
Now (row 1 and 2) 4 , and the rest of 2 must be wet, thus bot the red tiles blue, and row11 cannot have 7 wet tiles. - contradiction -> 29 is dry. In addition 28 and 23 are wet on row 12.

Picture 11: Assume 16 is wet on row 8
Now (column 8) 23 is dry on row 10, and (row 9) 21 is dry, which makes at least one yellow area wet, which makes the top of 26 dry.
The rest of column 5 must be wet, which leads to contradiction on row 1 or 2. -> 16 is dry up to row 8.

Picture 12: assume 12 is wet on row 5
Then the rest of row 5 (esp. 8) is dry, which (row 4) makes the bottom of 10 wet.
If 7 is completely dry: (column 7) 23 must have water in column 7 and 12 must be completely wet, leading to contradiction in column 8. This forces row 4.
If 21 is fully dry: (column 5) 2,15 and 26 must be wet, leading to contradiction in column 4, so its base is wet, and the rest of row 9 dry. In row 8 this makes 20 dry, and thus 21 and 19 wet.
In column 5: 2 and 26 cannot both be wet because of column 3, and 15 cannot be wet together with either (column4), so only one of the red tiles is wet, which makes 8 in column 5 impossible - contradiction -> 12 is dry at row 5

Picture 13: assume 15 is dry
Then 14,18 and 19 must be wet in that row, and (column 6) the bottom of 3 and 22 must be wet, thus (row 10) the top of 26 dry, and thus (column 5) the bottom of 21 wet.
The rest of row 9 must be dry, then the rest of column 6 wet, then the rest of row 4 dry. Now (row1) 5 has to be wet, and the red tile must be dry according to its row, but wet according to its column. - contradiction -> 15 is wet from row 7.

Picture 14: Assume 21 is dry
Then the rest of row 8 is wet, and since (column 4) 2 and 26 can not both be wet, so are all other tiles of column 5. Then row 1 forces 5 to be wet, making 2 dry, making 26 wet.
This makes the top of 22,23 and 24 dry, giving row 9 9 dry tiles. - contradiction -> the bottom of 21 is wet.

Picture 15: 2,6 and the rest of row 9 are dry. Row 8 then adds water to 21 and 19 and column 2 to 1 and 18. Due to row 11, the bottom of 22 is wet.

Picture 16: assume 7 is dry (part 1)
Column 7 now makes 4 and the rest of 23 wet, row 2 makes 5 wet, and row 4 its remaining tiles.

Picture 17: assume 7 is dry (part 2)
The rest of ro1 1 is dry, and then the rest of column 5 and 6 wet. This leaves 1 wet tile in row 3 and 5.
Now the top of 18 must be other than the the green tiles, and thus the same as the other two purple tiles. Purple must be dry because of row 1, the top 19 must aslo be dry (column 8), making the rest of row 7 (yellow) wet, and thus too much of row 8.

Picture 18: With the bottom of 7 wet , row 4 can be finished, then column5, then row 1 and column 6

Picture 19: We can now add some dry tile-pairs to row 2 and 3, and a wet tile-pair to row 6. After that we can finish column 8 and (column 12) add water to 17.

Picture 20: Row 8 makes 14 dry, which allows us to finish Column 11, column 10, then row 7 and 7 , and then the rest.

Answer 4

You can solve the problem via integer linear programming as follows. Let $N=\{1,\dots,12\}$, and let $r_i$ and $c_j$ be the required row and column sums, respectively. For $(i,j)\in N \times N$, let $a_{i,j}$ be the region that contains cell $(i,j)$. Let $D=\{(1,0),(0,-1),(0,1)\}$ be the set of gravity directions (down, left, and right), and let $$G=\{(i,j,d_i,d_j)\in N \times N \times D: (i+d_i,j+d_j)\in N \times N \land a_{i,j} = a_{i+d_i,j+d_j}\}$$ index the gravity constraints. For $(i,j)\in N \times N$, let binary decision variable $x_{i,j}$ indicate whether cell $(i,j)$ contains water. The problem is to find a feasible solution to the linear constraints: \begin{align} \sum_j x_{i,j} &= r_i &&\text{for $i\in N$} \tag1 \\ \sum_i x_{i,j} &= c_j &&\text{for $j\in N$} \tag2 \\ x_{i,j} &\le x_{i+d_i,j+d_j} &&\text{for $(i,j,d_i,d_j)\in G$} \tag3 \\ \end{align} Constraints $(1)$ and $(2)$ enforce the row and column sums. Constraint $(3)$ enforces gravity: $x_{i,j} \implies x_{i+d_i,j+d_j}$.

The resulting problem has $144$ variables and $198$ constraints and yields the following unique solution: