For the following sudoku-style puzzle, you are given the following 9-by-9 grid,
and you need to fill it in with zeros and ones satisfying the following conditions:
(i) Each row, each column, and each red or blue 3-by-3 box must contain exactly two ones and seven zeros.
(ii) No two ones can be in squares that touch horizontally, vertically, or diagonally. For example, the following is a solution to this puzzle:
a) In the following version of the puzzle there are ones on either end of the middle row of the center 3- by-3 region. How many possible solutions are there for completing the blank squares on this puzzle satisfying conditions (i) and (ii)?
b) Starting with all blank squares, what is the total number of solutions to this puzzle satisfying conditions (i) and (ii)?
Here are some thoughts:
For a) we know that from (i) and (ii), we must have the following:
Then we will have some cases here. I chose the cases to be the blue box on the left hand side. Since we have 4 empty spots in that blue box. Following the rules, we can have 4 possibilities; we can choose the following numbers for the empty spots:
0 1, 0 1 ; 1 0, 1 0; 1 0, 0 1; 0 1, 1 0.
For case 1," 0 1, 0 1" , it turned out that this case is impossible. Then for case 2, it turned out that there are way too many sub-cases.
So I wonder if there is a more efficient way of doing this problem?
Also, I think in order to solve c), we must do b), since using b) we can figure out the symmetrical cases for b).
In addition, for b), I thought about using permutation, for example, let
$a = \begin{matrix}
1 & 0 & 0 \\
\end{matrix} $
$b = \begin{matrix} 0 & 1 & 0 \\ \end{matrix} $
$c = \begin{matrix} 0 & 0 & 1 \\ \end{matrix} $
$d = \begin{matrix} 0 & 0 & 0 \\ \end{matrix} $
$e = \begin{matrix} 1 & 0 & 1 \\ \end{matrix} $
Then we can write the sudoku as a 3 x 3 matrix with certain restrictions. For example, we can't have a and c together.
But from here I'm not sure how to continue.
Any help will be appreciated! Thank you in advance!
To make things a bit simpler, I'm going to refer to the cells by numbering the rows 1-9 from top to bottom, and A-I from left to right (so A1 is top left, I1 is top right, and so forth).
First, as you noted, there must be a 1 in exactly one out of A4 and B4 (and similarly for 3 other pairs, AB6, HI4 and HI6). Notice that whichever one you choose, this will prevent you from placing a 1 in A3 or B3.
Next, consider the box A1-C3. You can put at most one 1 in A1, A2 and B1, so you must put at least one in column C. Then by symmetry you must place exactly one 1 in C1-C3, since you'll also be forced to place one in C7-C9.
You also have to put a 0 in D2, which means that in box D1-F3 either:
You can then note that options 2 and 3 greatly restrict your placement of 1s in columns C through G. In fact, option 2 leads very quickly to a contradiction, and option 3 is pretty quick to enumerate, and perhaps most interestingly forces box D7-F9 to take option 1 itself, so you can apply a similar symmetry argument to count the number of solutions where it takes option 3 and D1-F3 takes option 1.
That leaves just one set of cases - when both boxes D1-F3 and D7-D9 have a 1 in each of their top and bottom rows. Again, there's lots of symmetry - each one needs to have one of those 1s be in the centre column, and the others are in opposite columns, so if you remove symmetry then the possibilities are D1/E3 or D3/E1, and E7/F9 or E9/F7, of which there is still some redundancy.