4
$\begingroup$

The following image shows two valid Sudokus. The first was copied verbatim off Wikipedia, and the second was obtained by rotating 90 degrees.

Any two distinct valid Sudokus must differ in at least four cells. Given a completed Sudoku a legal "move" consists in changing exactly four cells to form another Sudoku grid.

Is it possible to transform the first grid to the second grid using only legal moves?

(for partial credit: can you succeed if legal moves allowed changing up to 6 cells instead of 4?)

enter image description here

$\endgroup$
3
  • $\begingroup$ text version of both please? $\endgroup$ Aug 19 '20 at 10:39
  • $\begingroup$ Can you give a clearer explanation (preferably with an example) of a "legal move"? $\endgroup$
    – Rob Watts
    May 19 at 7:36
  • $\begingroup$ Apologies for late reply: Left diagram = 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179 Right diagram = 329748165 ... etc (rotate 90 degrees) Example legal move: swap 6/7 in rows 1 and 4 $\endgroup$
    – happystar
    May 23 at 10:09
0
$\begingroup$

Observation:

Take for example the 5 in the top left. To make a valid move which changes this number, the 5 needs to reappear somewhere else in the same row, the same column and the same 3x3 square, so that defines two or three other cells which much change.
If you choose three other cells, the one for the 3x3 square now has two 5s in both the row and the column, so that doesn't work.
So either the cell you choose for the row or column must be in the 3x3 square as well, and the fourth cell you change must form a rectangle with the 5 in the top left and the other two cells you chose to change. Also, opposite corners of the rectangle have the same value. An example where this is possible is the rectangle of 5s and 4s formed on the seventh row and eighth row, fourth and ninth column.
The problem is that such an operation, if it exists in the grid, would mean the grid doesn't have a unique solution anymore, unless one of the initial clues is using one of those cells. So these situations are comparatively rare, and it's unlikely a random sudoku can be transformed to one where (almost) all values have changed, but I have no proof yet.

$\endgroup$
4
  • 1
    $\begingroup$ The situation is even worse than you describe. Your example move using the 5 and 2 would leave the 3x3 boxes invalid, though your other example works. $\endgroup$ Aug 19 '20 at 11:11
  • $\begingroup$ Eh ... you're right, the first example isn't valid. The second one is ... $\endgroup$
    – Glorfindel
    Aug 19 '20 at 11:13
  • $\begingroup$ Clarification: by "valid sudoku" I mean a completed puzzle that obeys the normal rules. It does not mean an incomplete puzzle with only one solution $\endgroup$
    – happystar
    Aug 19 '20 at 12:39
  • $\begingroup$ One thing to consider is that making one "legal move" can open up another one - if you use the 6s and 7s in the first and fourth rows, then the 6s and 8s in the first and last rows could be used. $\endgroup$
    – Rob Watts
    May 19 at 22:41

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.