<p><strong>EDIT</strong>: I quickly completed the amateur proof that I started a few months ago and never finished.</p>

<p><a href="http://www.nearly42.org/vdisk/cstheory/binaryp.pdf" rel="nofollow noreferrer">You can download it in PDF format</a> on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome.</p>

<hr>

<p>I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example the OR, SPLIT and TURN gadgets are:</p>

<p><img src="https://i.sstatic.net/bfOa4.png" alt="enter image description here"></p>

<p>I built/checked the gadgets using a simple constraint solver program.</p>

<p>The uniqueness of each row/column (rule 2) can be achieved marking them with a unique "binary number" using a 2x2 block that acts like a "digit":</p>

<pre><code>01 = 0   10 = 1
10       01
</code></pre>

<p>And the equal number of 1s and 0s (rule 3) can be achieved mirroring the whole puzzle, and inverting the 0s with 1s (using special walls in the middle that allow the transition without breaking the rules):</p>

<pre><code>  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....
</code></pre>

<p>So deciding if a partially filled $N \times N$ Binary Puzzle board has a solution, is NP-hard.</p>

<p>Like other similar puzzles it's not immediate to say that it is in NP (see for example <a href="https://cstheory.stackexchange.com/questions/5784/what-is-the-complexity-of-possibly-succinct-nurikabe">the discussion on succinct Nurikabe on cstheory</a>). However if the initial board is given as a full string $\{0,1,\bot\}^{N \times N}$ (the representation is not succinct), and you drop the the unique solution constraint (which is another rule of the game), then the problem is in NP (and thus NP-complete). </p>

CC BY-SA 3.0
2013-03-24T20:18:53.207Z
I guess you mean planar circuit SAT?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-24T20:42:36.733Z
I mean Planar type 1 3CNF (the bipartite graph between the 3CNF clauses and variables is planar). One gadget is used to simulate a T/F assignment, another is used to force a T on each clause, 2 OR gadgets are used to simulate the two ORs of each clause and the SPLIT to split and "carry" the signal from the assignments to the clauses. Now I'm trying to complete the paper, as soon as I finish it, I'll post the link in the answer.
Marzio De Biasi
CC BY-SA 3.0
2013-03-24T22:26:26.637Z
So, you are reducing from the NP-complete planar cubic bipartite monotone 1-in-3 SAT problem. right?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-24T23:18:34.833Z
No, "type 1" means the particular planar 3CNF formula used (there is a slight difference between type 1 and type 2). I used a similar reduction to prove the [NP-completeness of the puzzle game Tent](http://www.fractalmuse.org/cstheory/the-complexity-of-camping/); you can take a look to that paper, however I think that in 1-2 days I'll publish a complete proof of the binary sudoku problem - a.k.a. binary puzzle (I just completed the snapshots of the gadgets) (and I hope you'll take a look at it to see if it really works :-)
Marzio De Biasi
CC BY-SA 3.0
2013-03-25T00:00:29.493Z
Good luck, I can't wait.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-27T17:07:58.747Z
@MohammadAl-Turkistany: I completed the proof, if you want you can download and check it if it is correct
Marzio De Biasi
CC BY-SA 3.0
2013-03-28T12:05:19.863Z
Thanks a lot. I will look at it and give you a feedback.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-04-09T15:14:47.100Z
@MohammadAl-Turkistany: did you look at it? Do you have refutations/suggestions/improvements ?
Marzio De Biasi
CC BY-SA 3.0
2013-04-09T15:33:00.760Z
Sorry, not yet. I will give you my feedback ASAP.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-03-23T20:28:36.730Z
2016-03-19T20:20:17.657Z
2017-04-13T12:32:28.117Z
Marzio De Biasi
<p>Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows.</p>

<ol>
<li>Each row and each column must contain an equal number of zeros and ones.</li>
<li>Each row and each column is unique.</li>
<li>No row or column contains consecutive triples of zeros or ones ($1 1 1$ is a consecutive triple of ones).</li>
</ol>

<p>The input is a $N \times N$ square partially filled with zeros and ones. To solve the puzzle, each cell in the $N \times N$ square must be filled by either $0$ or $1$ while respecting the above rules. I was not able to find any intractability result for solving the Binary Sudoku puzzle.</p>

<blockquote>
  <p>How hard is solving the Binary Sudoku puzzle? Is it NP-complete?</p>
</blockquote>

<p>Also, I'm interested in the complexity of a related problem.</p>

<p>Given a fully filled $N \times N$ square that respects only rules 1 and 2 above,</p>

<blockquote>
  <p>how hard is it to find a permutation of rows and columns such that the resulting square respects rule 3?</p>
</blockquote>

CC BY-SA 3.0
2013-03-23T22:22:02.257Z
It's not the same problem so I'll leave this as a comment rather than an answer, but there's an NP-hardness result for single-digit subproblems of the standard kind of Sudoku puzzle in my paper http://arxiv.org/abs/1202.5074
David Eppstein
CC BY-SA 3.0
2013-05-08T08:23:23.830Z
As the author of a binary puzzle (this problem) app, I can offer you an observation (not a proof): all instances of this puzzle seen in practice can be solved in polynomial time, but there are instances that *appear* not to be solvable that way, namely exactly those instances where you reach a state where none of the three rules directly force a cell to take a specific value (ie it seems that you have to "try something" and maybe backtrack to that point).
user555045
<cc.complexity-theory><np-hardness><puzzles>
How hard is binary Sudoku puzzle?
Mohammad Al-Turkistany
# How hard is binary Sudoku puzzle?

(Asked by: username_0 on 2013-03-23)

Sudoku is a well-known puzzle that is NP-complete. Binary Sudoku is a variant that only allows the numbers $0$ and $1$. The rules are as follows.

1. Each row and each column must contain an equal number of zeros and ones.
2. Each row and each column is unique.
3. No row or column contains consecutive triples of zeros or ones ($1 1 1$ is a consecutive triple of ones).

The input is a $N \times N$ square partially filled with zeros and ones. To solve the puzzle, each cell in the $N \times N$ square must be filled by either $0$ or $1$ while respecting the above rules. I was not able to find any intractability result for solving the Binary Sudoku puzzle.

> How hard is solving the Binary Sudoku puzzle? Is it NP-complete?

Also, I'm interested in the complexity of a related problem.

Given a fully filled $N \times N$ square that respects only rules 1 and 2 above,

> how hard is it to find a permutation of rows and columns such that the resulting square respects rule 3?

**Tags:** cc.complexity-theory, np-hardness, puzzles

> **Comments:**
> **username_1**: It's not the same problem so I'll leave this as a comment rather than an answer, but there's an NP-hardness result for single-digit subproblems of the standard kind of Sudoku puzzle in my paper http://arxiv.org/abs/1202.5074  
> **username_2**: As the author of a binary puzzle (this problem) app, I can offer you an observation (not a proof): all instances of this puzzle seen in practice can be solved in polynomial time, but there are instances that *appear* not to be solvable that way, namely exactly those instances where you reach a state where none of the three rules directly force a cell to take a specific value (ie it seems that you have to "try something" and maybe backtrack to that point).  

---

## 1 answers

### Answer by username_3 on 2013-03-23. Score: 14 | Accepted answer

EDIT: I quickly completed the amateur proof that I started a few months ago and never finished.
You can download it in PDF format on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome.

I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example the OR, SPLIT and TURN gadgets are:

I built/checked the gadgets using a simple constraint solver program.
The uniqueness of each row/column (rule 2) can be achieved marking them with a unique "binary number" using a 2x2 block that acts like a "digit":
01 = 0   10 = 1
10       01

And the equal number of 1s and 0s (rule 3) can be achieved mirroring the whole puzzle, and inverting the 0s with 1s (using special walls in the middle that allow the transition without breaking the rules):
  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

So deciding if a partially filled $N \times N$ Binary Puzzle board has a solution, is NP-hard.
Like other similar puzzles it's not immediate to say that it is in NP (see for example the discussion on succinct Nurikabe on cstheory). However if the initial board is given as a full string $\{0,1,\bot\}^{N \times N}$ (the representation is not succinct), and you drop the the unique solution constraint (which is another rule of the game), then the problem is in NP (and thus NP-complete).

> **Comments:**
> **username_0**: I guess you mean planar circuit SAT?  
> **username_3**: I mean Planar type 1 3CNF (the bipartite graph between the 3CNF clauses and variables is planar). One gadget is used to simulate a T/F assignment, another is used to force a T on each clause, 2 OR gadgets are used to simulate the two ORs of each clause and the SPLIT to split and "carry" the signal from the assignments to the clauses. Now I'm trying to complete the paper, as soon as I finish it, I'll post the link in the answer.  
> **username_0**: So, you are reducing from the NP-complete planar cubic bipartite monotone 1-in-3 SAT problem. right?  
> **username_3**: No, "type 1" means the particular planar 3CNF formula used (there is a slight difference between type 1 and type 2). I used a similar reduction to prove the [NP-completeness of the puzzle game Tent](http://www.fractalmuse.org/cstheory/the-complexity-of-camping/); you can take a look to that paper, however I think that in 1-2 days I'll publish a complete proof of the binary sudoku problem - a.k.a. binary puzzle (I just completed the snapshots of the gadgets) (and I hope you'll take a look at it to see if it really works :-)  
> **username_0**: Good luck, I can't wait.  
> **username_3**: @MohammadAl-Turkistany: I completed the proof, if you want you can download and check it if it is correct  
> **username_0**: Thanks a lot. I will look at it and give you a feedback.  
> **username_3**: @MohammadAl-Turkistany: did you look at it? Do you have refutations/suggestions/improvements ?  
> **username_0**: Sorry, not yet. I will give you my feedback ASAP.  

---

