7
$\begingroup$

The rules of Binary Sudoku are quite simple. It is very similar to regular Sudoku, except here we try to fill a 9x9 board with only black and white tiles following the below rules:

  1. Every row, column, and $3$x$3$ box (the same nine $3$x$3$ boxes as in regular Sudoku) must have 2 black tiles — no more and no less, which leaves 7 remaining white tiles.
  2. Black tiles can never be adjacent to other black tiles (this includes diagonally adjacent, so every tile has 8 adjacent neighbors).

Warm-up question: How many possible completed boards are there, given we start out with the two black tiles in the middle $3$x$3$ box as shown below?

Grid with two black tiles in central 3x3 box

Challenging (final) question: Starting with an empty board, how many possible different completed boards are there?

$\endgroup$
4
  • 2
    $\begingroup$ FYI, this is more well-known as Star Battle. $\endgroup$
    – Deusovi
    Commented Jan 24, 2022 at 3:14
  • $\begingroup$ Are computer-aided solutions allowed? $\endgroup$
    – bobble
    Commented Jan 24, 2022 at 5:50
  • 2
    $\begingroup$ So it's not this Binary Sudoku... $\endgroup$ Commented Jan 24, 2022 at 21:45
  • $\begingroup$ @bobble My bad, there's no fun in solving the puzzle with a computer, I should have made it more clear by adding a tag, but try to find a non-computer method of solving this puzzle! $\endgroup$
    – menalaus
    Commented Jan 25, 2022 at 0:55

1 Answer 1

12
$\begingroup$

There's no , and it was easy enough to hack my Kyoto CNF generator to produce a SAT instance for the problem: a 9×9 bit array where each row, column and box has two 1s and no two adjacent variables may be both 1.

Solving the instance showed that there are exactly nine non-isomorphic (up to rotations/reflections of the whole grid) solutions: Of these only two satisfy the constraint of the first question (marked by a blue centre box). All solutions are totally asymmetric except the central one (which has 4 equivalents), yielding 68 solutions in all, 6 of which satisfy the first question's constraint.


proof:

This is basically a manual SAT proof, where the first level of cases is the centre cell star configuration (I use Hensel notation for the names). Blue, pink and white stars (mostly) indicate choices while blue backgrounds indicate solutions; note that box centres can never be starred because that would leave no room for the second star.

Case n is very easy to knock out by forced star placement. For k R5C9 is not a star because that alongside the (WLOG placed) R5C6 kills all locations for a second star in box 6, so [a star is in] R5C1 and R4C3. Subsequent assumptions, contradictions and inferences are as follows:
1. Assume [there is] not [a star in] R9C123, then R8C3 and R7/8C1, then R13C2, × (contradiction). (Slash means "or" and concatenation means "and".)
2. Assume R9C1, then R17C2 (col 2 slots), then R3C3, ×.
3. Assume R9C3, then R17C2 (col 2 slots), not R8C6, R7C6, R8C79, ×. Hence R9C2.
4. Assume R7C1, then R1C2, R3C3, ×. Hence R7C2.
5. The two stars in col 5 cannot both be in box 8. Suppose one is, then it is R9C5, then R7C6 and R8C79, ×. Hence R13C5 (box 2).
6. Assume R9C4, then not R7C8 (second star of box 9 extinguished, or E9), then R7/8C7. But either choice gives E8. Hence R8C4. 7. Assume R7C7, then R8C9, R1C8, R3C7, R4C8, ×. R8C7 gives E8, so R9C7, R7C6, R8C9.
8. Assume R8C9, then × as in 7., so R6C8.
9. Assume R4C9. This forces a complete solution (#4 in the solution summary above). Hence (for further solutions) R4C8.
10. 9. forces R3C1, at which point exactly two of R2C379 may be true and the remaining column is starred in row 1. This yields #7, #8 and #9.

1. With case c R5C19, then R4C37 are forced. Not R9C5, so R8/9C4 and R8/9C6, so R13C5. Assume R1C2, then R3C1, R7C2, R9C3 and two stars cannot be packed into box 8 (×). Hence the stars in col 2 (and 8 by symmetry) must go in box 7 (9) and R8C46.
2–5 are just short further cases that either lead to solutions #1, #2, #3 or a contradiction.

1. In case i assume (WLOG) R46C1, then R19C2, R37C3, WLOG R1C4, R2C9, R2C7 and R3C5, R7C5/6 and R9C5/6, R8C79, R79C5. But then col 5 has three stars, ×. Hence at least one of R46C2 is true, as is R46C8.
2. Assume these stars are cis, i.e. R6C28. Exactly one star then lies in each of the four pairs of R8/9C1379, forcing R7C46, R9C37, R8C19.
3. Still with the assumption from 2. assume R4C1. This forces the whole of solution #6, so for further search we assume R4C28.
4. The latter inference above (built on 2.) leads to row 3 having only one star, ×. The case induced by the choice in 2. has been exhausted.
5. We move on to the trans case, i.e. R6C2 and R4C8. To avoid repeating the cis case we have R4C1 and R6C9. Assume both stars in col 3 are in box 1, then R9C2 and R7C1, ×. Hence exactly one star in col 3 is in box 9.
6. Assume R9C3, which forces R1C2 and R8C1. Assume further R7C46, easily forcing a whole grid filled... but col 9 contains three stars, ×.
7. Given the first choice in 6. there must be R8C9; together with the whole of 6. this implies R7C7, then R6C9, R1C8, R3C7, R4C8, ×. Hence on col 3 R8C3, and by symmetry R2C7.
8. Assume R9C1, then R1C2, R3C3, R2C9, R2C7 and R3C5, R1C5, R79C6. But then col 6 has three stars, ×. Hence R8C1 and by symmetry R2C9. 9. From the end of 8. solution #5 is forced all the way.

$\endgroup$
2
  • $\begingroup$ Nice! Can you find a no-computer justification to these solutions and why they are the only ones? $\endgroup$
    – menalaus
    Commented Jan 25, 2022 at 0:58
  • $\begingroup$ @menalaus done, and you just lost The Game. $\endgroup$ Commented Jan 25, 2022 at 8:45

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