32
$\begingroup$

In this puzzle you should fill the imaginary small squares in each row and column up to the number that is written next to it with water. You can't fill a square if the squares connected to it(under and left and right of it-without any limits between them)are empty. And one more point is that you can't fill a square that under it is an empty square because the water falls down because of gravity.(you should pay attention to simple physics laws) There are 2 wrong examples: you can't fill half of a imaginary square

you should pay attention to simple physics laws

And this is the question! : fill it with the rules mentioned above!

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
$\endgroup$
  • 1
    $\begingroup$ BTW, My intuition says that this problem is NP-Complete. Would appreciate if somebody could prove or disprove that. $\endgroup$ – Victor Stafusa Dec 16 '14 at 0:48
  • 1
    $\begingroup$ I could reduce it to a gigantic boolean formula with 83 variables, and I could eliminate only 3 variables so far. :( $\endgroup$ – Victor Stafusa Dec 16 '14 at 3:51
  • 2
    $\begingroup$ Victor: it's NP-complete. Even on a 1-by-n grid, you can encode subset sum. The puzzle in the OP is basically an instance of multidimensional subset sum anyway. $\endgroup$ – Lopsy Dec 16 '14 at 4:10
  • 1
    $\begingroup$ Does “fill the imaginary small squares in each row and column up to the number that is written next to it with water” mean that a row with a 4 by it will have 4 squares with water and 8 without? And a column with a 7 below it will have 7 cells with water and 5 without? $\endgroup$ – James Waldby - jwpat7 Dec 16 '14 at 6:20
  • 2
    $\begingroup$ @FlorianF: Wish I'd seen your question earlier. The answer is: if the legs must be simultaneously filled, the puzzle has no solution. If the legs do not need to be simultaneously filled, the puzzle does have a solution. Hence I'm going to boldly assume that the elephant's legs can be independently filled. $\endgroup$ – COTO Dec 16 '14 at 14:13
19
$\begingroup$

The solution is as follows:

        enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ Nice one. I was still in the "manual attempt", but funny enough I started with the assumption that #9 would only have either of its bottom pieces filled? Why? Intuition - the puzzle was very well made, so it was likely to contain a trick and that looked like very suitable place for this... $\endgroup$ – BmyGuest Dec 16 '14 at 16:00
  • $\begingroup$ @BmyGuest: Your intuition paid off nicely. ;) $\endgroup$ – COTO Dec 16 '14 at 16:50
  • $\begingroup$ I feel so impressive by your JavaSolver solution. Too briliant. :;D $\endgroup$ – Nai Dec 10 '15 at 9:38
12
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Not understandable for me >.<\ $\endgroup$ – Nai Dec 10 '15 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.