<p>I call <code>Fill3</code> the following simple game: the input is a $n \times n$ grid;</p>

<ul>
<li>every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0, 90, 180 or 270 degrees;</li>
<li>every cell (except the FIXED) contains three green squares that according to the cell's type can be placed in several different <em>valid configurations</em> (see figure);</li>
</ul>

<p>The aim of the game is to choose a valid configuration for each cell (the type and the rotation cannot be changed) in such a way that no two green squares are adjacent (vertically or horizontally). The game is NP-complete (a quick reduction is from planar 3SAT).</p>

<p><img src="https://i.sstatic.net/LKvTA.jpg" alt="enter image description here">
Valid configurations for each type of cell.</p>

<p>But the cell types are obviously a direct transposition of the four gadgets used in the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.6525&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">bounded planar Nondetermnistic Constraint Logic (NCL)</a> and the valid configurations match  the constraints of the corresponding vertices in a constraint graph (blue/red arrows in the figure). </p>

<p>I'm wondering if a direct quick reduction from NCL is possible. It is immediate to reduce a planar constraint graph to a <code>Fill3</code> game (CHOICE cells with a "free" endpoint can be used to build straight links and 90° turns). But in a bounded planar NCL problem $P$ the edges are reversed <strong>dinamically</strong> (though an edge can be reversed at most once) and the aim is to reverse a single edge; on the contrary the game <code>Fill3</code> is <strong>static</strong>. A possible approach is: build the corresponding <code>Fill3</code> game from $P$; "break" the edge that must be reversed (eventually expanding the board) and force it in the final direction using FIXED cells. Then one way is easy: if $P$ is solvable, the corrisponding <code>Fill3</code> game has a solution (represented by the final configuration of the constraint graph); but <strong>the other way is more problematic</strong>:</p>

<blockquote>
If <code>Fill3</code> has a (static) solution $s$, can we say that a (dynamic) solution for the corresponding planar bounded NCL problem $P$ always exist (i.e. a sequence of valid edge reversals)? And how to prove it formally?
</blockquote>

CC BY-SA 3.0
2012-07-26T12:50:17.517Z
What is the difference between a blue arrow and a red arrow?
Tyson Williams
CC BY-SA 3.0
2012-07-26T14:28:38.830Z
@TysonWilliams: the blue is a weight-2 edge, the red is a weight-1 edge in the corresponding NCL vertice. But in the NCL framework they are joined with a red-blue vertex with an inflow constraint of 1, so the final effect is that at least one of two edges must point "inward"; and this is the same behaviour that is achieved when we put two Fill3 cells side by side: if the two green blocks are adjacent (invalid configuration) then the corresponding directions in the juction are both "outward".
Marzio De Biasi
<cc.complexity-theory><np-hardness><puzzles>
Reduction from planar bounded NCL to a static puzzle game
Marzio De Biasi
# Reduction from planar bounded NCL to a static puzzle game

(Asked by: username_0 on 2012-07-25)

I call `Fill3` the following simple game: the input is a $n \times n$ grid;

* every cell of the grid has a type: OR, AND, CHOICE, FANOUT and FIXED and can be rotated 0, 90, 180 or 270 degrees;
* every cell (except the FIXED) contains three green squares that according to the cell's type can be placed in several different *valid configurations* (see figure);

The aim of the game is to choose a valid configuration for each cell (the type and the rotation cannot be changed) in such a way that no two green squares are adjacent (vertically or horizontally). The game is NP-complete (a quick reduction is from planar 3SAT).

![enter image description here](https://i.sstatic.net/LKvTA.jpg)
Valid configurations for each type of cell.

But the cell types are obviously a direct transposition of the four gadgets used in the [bounded planar Nondetermnistic Constraint Logic (NCL)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.134.6525&rep=rep1&type=pdf) and the valid configurations match the constraints of the corresponding vertices in a constraint graph (blue/red arrows in the figure).

I'm wondering if a direct quick reduction from NCL is possible. It is immediate to reduce a planar constraint graph to a `Fill3` game (CHOICE cells with a "free" endpoint can be used to build straight links and 90° turns). But in a bounded planar NCL problem $P$ the edges are reversed **dinamically** (though an edge can be reversed at most once) and the aim is to reverse a single edge; on the contrary the game `Fill3` is **static**. A possible approach is: build the corresponding `Fill3` game from $P$; "break" the edge that must be reversed (eventually expanding the board) and force it in the final direction using FIXED cells. Then one way is easy: if $P$ is solvable, the corrisponding `Fill3` game has a solution (represented by the final configuration of the constraint graph); but **the other way is more problematic**:

> If `Fill3` has a (static) solution $s$, can we say that a (dynamic) solution for the corresponding planar bounded NCL problem $P$ always exist (i.e. a sequence of valid edge reversals)? And how to prove it formally?

**Tags:** cc.complexity-theory, np-hardness, puzzles
> **Comments:**
> **username_1**: What is the difference between a blue arrow and a red arrow?  
> **username_0**: @TysonWilliams: the blue is a weight-2 edge, the red is a weight-1 edge in the corresponding NCL vertice. But in the NCL framework they are joined with a red-blue vertex with an inflow constraint of 1, so the final effect is that at least one of two edges must point "inward"; and this is the same behaviour that is achieved when we put two Fill3 cells side by side: if the two green blocks are adjacent (invalid configuration) then the corresponding directions in the juction are both "outward".  

---

## 0 answers

