5
$\begingroup$

How often at most can "Sudoku" occur in a valid (9x9) sudoku?

  • create a valid sudoku
  • replace (all occurrences of) 5 of the numbers by the 5 letters in "sudoku". (and leave the other numbers untouched)
  • count the occurrences of "Sudoku" - consecutive in a straight line: i.e. horizontal, vertical or diagonal in any direction.

What is the maximum count achievable?

Improve this question
$\endgroup$
6
  • $\begingroup$ Is it allowed to replace a sixth letter with a second 'U'? Some novelty sudokus do feature repeated values in their number sets. Or are you strictly interested in replacing only 5 of the numbers for uniqueness? $\endgroup$
    – Stiv
    Commented Jul 23, 2023 at 9:03
  • 1
    $\begingroup$ I assume you mean 6th number? Then no, the idea is that the sudoku rules still apply especially one u in in each row/column/block. $\endgroup$
    – Retudin
    Commented Jul 23, 2023 at 9:11
  • $\begingroup$ Is this question about the answer being rot13(rvgure guerr be sbhe)? $\endgroup$
    – DL33
    Commented Jul 23, 2023 at 10:40
  • $\begingroup$ @DL33 That would indeed be the hard part $\endgroup$
    – Retudin
    Commented Jul 23, 2023 at 12:06
  • $\begingroup$ Do the letters have to be consecutive along the line? $\endgroup$
    – user1502040
    Commented Jul 23, 2023 at 13:00

1 Answer 1

Reset to default
5
$\begingroup$

Let the $9$ symbols be S, U, D, O, K, !, @, #, and \$. Because of the repeated U, we need only consider the $4$ diagonal directions and $4(1+2+3+4+3+2+1)=64$ possible placements. Via integer linear programming with a binary decision variable $x_{ijk}$ to indicate whether cell $(i,j)$ contains symbol $k$ and a binary decision variable $y_{ijvw}$ to indicate whether "sudoku" starts in cell $(i,j)$ and goes in direction $(v,w)$, the maximum number of occurrences of "sudoku" is

3.

\begin{matrix} \# &\color{red}S &! &K &$ &@ &D &U &O &\\ $ &D &\color{red}U &\color{blue}S &! &O &K &@ &\# &\\ @ &K &O &\color{red}D &\color{blue}U &\# &S &! &$ &\\ \color{orange}S &@ &K &U &\color{red}O &\color{blue}D &\# &$ &! &\\ ! &\color{orange}U &\# &$ &S &\color{red}K &\color{blue}O &D &@ &\\ O &$ &\color{orange}D &\# &@ &! &\color{red}U &\color{blue}K &S &\\ K &! &$ &\color{orange}O &D &S &@ &\# &\color{blue}U &\\ U &\# &S &@ &\color{orange}K &$ &! &O &D &\\ D &O &@ &! &\# &\color{orange}U &$ &S &K & \end{matrix}

It is clear that no two occurrences can share a U, so even without integer linear programming we have an upper bound of

$\lfloor 9/2 \rfloor = 4$.

By request, here is the SAS code I used:

proc optmodel;
   str target = 'SUDOKU';
   set SYMBOLS = /S U D O K '!' '@' '#' '$'/;
   num n = card(SYMBOLS);
   set ROWS = 1..n;
   set COLS = 1..n;
   set CELLS = ROWS cross COLS;
   set DIRECTIONS = {-1,1} cross {-1,1};
   set WORDS = {<i,j> in CELLS, <di,dj> in DIRECTIONS: <i+di*(length(target)-1),j+dj*(length(target)-1)> in CELLS};

   /* X[i,j,k] = 1 if cell <i,j> contains symbol k; 0 otherwise */
   var X {CELLS, SYMBOLS} binary;

   /* Y[i,j,di,dj] = 1 if word starts in cell <i,j> in direction <di,dj>; 0 otherwise */
   var Y {WORDS} binary;

   max NumWords = sum {<i,j,di,dj> in WORDS} Y[i,j,di,dj];

   con OneSymbolPerCell {<i,j> in CELLS}:
      sum {k in SYMBOLS} X[i,j,k] = 1;
   con RowCon {i in ROWS, k in SYMBOLS}:
      sum {j in COLS} X[i,j,k] = 1;
   con ColCon {j in COLS, k in SYMBOLS}:
      sum {i in ROWS} X[i,j,k] = 1;
   con BoxCon {ri in 1..n by sqrt(n), rj in 1..n by sqrt(n), k in SYMBOLS}:
      sum {i in ri..ri+sqrt(n)-1, j in rj..rj+sqrt(n)-1} X[i,j,k] = 1;
   con WordImpliesSymbol {<i,j,di,dj> in WORDS, k in 1..length(target)}:
      Y[i,j,di,dj] <= X[i+di*(k-1),j+dj*(k-1),char(target,k)];

   solve;

   str sol {ROWS, COLS};
   for {<i,j> in CELLS} do;
      for {k in SYMBOLS: X[i,j,k] > 0.5} do;
         sol[i,j] = k;
         leave;
      end;
   end;
   print sol;
quit;

If you ignore the extra four symbols and relax all the $=1$ constraints to $\le 1$ so that at most one symbol can appear per cell and each symbol can appear at most once per row/column/box, the maximum turns out to be

still 3.

If you further relax the problem by omitting the $\le 1$ box constraints except for U, the maximum turns out to be

still 3.

If you further relax the problem by omitting all the box constraints, the maximum turns out to be

4.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ "Integer linear programming says" without any reference to the particular program is an appeal to authority, and as such, not a valid argument. $\endgroup$
    – Bass
    Commented Jul 23, 2023 at 18:29
  • $\begingroup$ @Bass I can provide the objective and constraints if you want, but the usual sudoku constraints are well-known and the additional constraints are straightforward given the decision variables I defined. $\endgroup$
    – RobPratt
    Commented Jul 23, 2023 at 18:39
  • 2
    $\begingroup$ "My friend who is very good at sudoku says 3 is the maximum, and everyone knows the rules of sudoku anyway." (Please do share the code, because otherwise your answer is no better than this ridiculous oversimplification.) $\endgroup$
    – Bass
    Commented Jul 23, 2023 at 18:52
  • $\begingroup$ (Although I would much prefer an English language explanation on why the U's will necessarily collide even though there seems to be plenty of room for them in the grid). (Or in yet other words: knowing the answer is one thing. Knowing that the answer is correct is another. Knowing why the answer is correct is the important bit.) $\endgroup$
    – Bass
    Commented Jul 23, 2023 at 18:56
  • 1
    $\begingroup$ Regardless of which U's are overlapping, the other U's would share a row or column. $\endgroup$
    – AxiomaticSystem
    Commented Jul 23, 2023 at 21:25

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