12
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 arxiv.org/abs/1202.5074 $\endgroup$
    – David Eppstein
    Mar 23, 2013 at 22:22
  • 1
    $\begingroup$ 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). $\endgroup$
    – harold
    May 8, 2013 at 8:23
  • $\begingroup$ Hey i have been trying to make a programmes to solve binary puzzles except that I have a hard time completing the very hard binary puzzles and would need a hint on resolving it. My program can easily do all the binary problemes except the very hard ones $\endgroup$
    – user38142
    Mar 19, 2016 at 3:26

1 Answer 1

Reset to default
14
$\begingroup$

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:

enter image description here

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).

Improve this answer
$\endgroup$
9
  • $\begingroup$ I guess you mean planar circuit SAT? $\endgroup$
    – Mohammad Al-Turkistany
    Mar 24, 2013 at 20:18
  • $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Mar 24, 2013 at 20:42
  • $\begingroup$ So, you are reducing from the NP-complete planar cubic bipartite monotone 1-in-3 SAT problem. right? $\endgroup$
    – Mohammad Al-Turkistany
    Mar 24, 2013 at 22:26
  • $\begingroup$ 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; 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 :-) $\endgroup$
    – Marzio De Biasi
    Mar 24, 2013 at 23:18
  • $\begingroup$ Good luck, I can't wait. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 25, 2013 at 0:00

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.