Skip to main content
added 51 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

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. Let 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:

enter image description here

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. 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, 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:

enter image description here

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:

enter image description here

added 3 characters in body
Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

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. 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, 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: enter image description here

enter image description here

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. 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, 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: enter image description here

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. 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, 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:

enter image description here

Source Link
RobPratt
  • 14.4k
  • 1
  • 31
  • 59

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. 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, 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: enter image description here