5
$\begingroup$

I have designed a new type of sudoku-like puzzle, done on a 5*5 grid, with the following rules:

  • each row and column contains one and only one of each integer 1-5
  • each row and column contains one and only one of each colour (eg red, blue, yellow, green, black)
  • there is one and only one of each integer-colour combination (eg one blue 3)

It is easy to create a solved colour-sudoku. One simply cycles through the integers in one direction (first row is 12345, second row is 23451, third row is 34512 etc) and cycles through the colours in the opposite direction (first row is ABCDE, second row is EABCD, third row is DEABC).

One can then conduct various transformations of this solution:

  • interchanging any two colours with each other, or interchanging any two numbers
  • swapping any two rows or columns
  • rotating the board

I have several questions relating to colour sudokus:

  1. What is the minimum number of squares which must be filled in order to determine a unique solution? I have done it with 5, but might it be done with fewer?

  2. Are there other solutions which cannot be generated through the transformations described above? If so, how many?

  3. How would the answers to the above questions change if we played on a different size of grid?

Edit: this is a board in which 5 determines a unique solution. The large numbers in bold are the starting numbers. enter image description here It is easy to deduce that '2A' must go in the top right corner (all other rows and columns have either a '2' or an 'A'). This enables us to figure out where '4A' and '5A' go, and also '2B' and '2E'. It's pretty straightforward after that.

$\endgroup$
  • $\begingroup$ In the small chance you didn't know, these are called Graeco-Latin squares. I was hoping the wiki article has an answer to your question 2, but sadly it didn't. $\endgroup$ – antkam Dec 3 at 14:48
  • $\begingroup$ Thanks Antkam, I didn't know that actually. I didn't realise it was also possible to do it with the constraint on the diagonals. And it is obvious, but I also hadn't thought that my solution doesn't work for even n. $\endgroup$ – Thomas Delaney Dec 4 at 17:09
  • $\begingroup$ Haha, well sorry to disappoint you, but Euler thought of this before you did! ;) (and others before even him.) Anyway, I hadn't read carefully the first time, and didn't realize you don't have the diagonal constraint. In that case, it's entirely possible that there is a $6\times 6$ solution for you, while none exists for Euler. $\endgroup$ – antkam Dec 4 at 19:33
  • $\begingroup$ @antkam do you play league of legends? $\endgroup$ – mathworker21 Dec 7 at 1:55
  • $\begingroup$ @mathworker21 - huh? no. is there a user named "antkam"? if so, that's not me :) $\endgroup$ – antkam Dec 7 at 22:31
5
$\begingroup$

$5$ clues is the minimum to force a unique solution on a $5 \times 5$ board. You showed that there is indeed a way to force a unique solution with $5$ clues, and below is a proof that you cannot force a unique solution with less than $5$ clues.

If you have $4$ clues, and two of the clues are in the same row (or column), then there will be two rows (or two columns) that have no clues, and those rows (columns) can be swapped for any solution to obtain another solution. So, if you could do it with only $4$ clues, you definitely want all clues to be in different rows and columns.

Likewise, if you have two clues with the same number (or color), then there will be two numbers (or colors) that are not used any of the clues, and hence you can swap those numbers (colors) for any solution to obtain another solution. So, if you could do it with only $4$ clues, you definitely want all clues to be of all different numbers and all different colors.

Without loss of generalization, we can therefore say that the clues are $1A$, $B2$, $C3$, and $D4$, and also without loss of generalization we can assume the clues are placed as follows (remember that with the clues in all different rows and columns, we can keep swapping any two rows and columns to end up in this configuration):

\begin{array}{|c|c|c|c|c|} \hline A1&.&.&.&.\\ \hline .&B2&.&.&.\\ \hline .&.&C3&.&.\\ \hline .&.&.&D4&.\\ \hline .&.&.&.&.\\ \hline \end{array}

So, if we can find wo solutions to this puzzle, then we know that $4$ clues can never force a unique solution. And indeed there are two solutions:

\begin{array}{|c|c|c|c|c|} \hline A1&E3&D2&B5&C4\\ \hline E4&B2&A5&C1&D3\\ \hline D5&A4&C3&E2&B1\\ \hline B3&C5&E1&D4&A2\\ \hline C2&D1&B4&A3&E5\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|} \hline A1&E4&D5&B3&C2\\ \hline E3&B2&A4&C5&D1\\ \hline D2&A5&C3&E1&B4\\ \hline B5&C1&E2&D4&A3\\ \hline C4&D3&B1&A2&E5\\ \hline \end{array}

Note that the second solution is the first solution mirrored along the diagonal with the clues (which itself can be achieved through a single rotation together with a vertical or horizontal mirroring, i.e. swapping of rows or columns). Indeed, I didn't have to provide two solutions at all to make the point that the $4$ clues as indicated cannot force a unique solution, since given that all the clues are on the diagonal, then if it has any solution at all, then it has a mirror solution as well.

This last observation partially answers your third question as well: the argument I gave above clearly generalizes to show that every $n \times n$ puzzle of this kind will require at least $n$ clues to force a unique solution: with $n-1$ clues, they have to be, without loss of generalization, all along the diagonal, and hence if there is any solution at all, there will always be another.

OK, but can you always force a unique solution with exactly $n$ clues? That is still an open question ... we know it works for $n=5$, but frankly I doubt you can do it for $n>5$.

As far as your second question goes, I found four valid boards that cannot be obtained from one another through swapping colors, numbers, row, columns, or doing any rotation or mirroring:

\begin{array}{|c|c|c|c|c|} \hline A1&B3&C4&D5&E2\\ \hline D4&A2&B5&E3&C1\\ \hline E5&D1&A3&C2&B4\\ \hline B2&C5&E1&A4&D3\\ \hline C3&E4&D2&B1&A5\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|} \hline A1&B3&C4&D5&E2\\ \hline D3&A2&E5&C1&B4\\ \hline E4&C5&A3&B2&D1\\ \hline B5&E1&D2&A4&C3\\ \hline C2&D4&B1&E3&A5\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|} \hline A1&B3&C2&D5&E4\\ \hline C4&A2&E5&B1&D3\\ \hline B5&D4&A3&E2&C1\\ \hline E3&C5&D1&A4&B2\\ \hline D2&E1&B4&C3&A5\\ \hline \end{array}

\begin{array}{|c|c|c|c|c|} \hline A1&B3&C2&D5&E4\\ \hline C5&A2&D4&E3&B1\\ \hline B4&E5&A3&C1&D2\\ \hline E2&D1&B5&A4&C3\\ \hline D3&C4&E1&B2&A5\\ \hline \end{array}

I am pretty sure that all other valid boards can be transformed into one of these $4$ through swapping colors, numbers, row, columns, or doing any rotation or mirroring. For example, the two earlier boards can be seen to be of the third type by putting all the $A$'s along he diagonal in order, followed by a diagonal mirroring. So, I am pretty sure the answer to your second question is $4$.

$\endgroup$
  • $\begingroup$ It seems that the five clues in the question determine the entire grid. I find only one place to put 4A, which then leaves only one place for 5A and forces the upper left corner to be 4C, with 1E to the right of 5A; then under 4C we must have 5E and 3D; 1C above 4B and 5D above 1C; 3B under 2A. Then 3C can only be at the bottom of column 4, so the cell to the left of that must be 5B and the cell to the right 4D; 5C above that to finish the fifth column, left of 5C is 4E, left of that 1D, and the last two cells in the top row are then determined. $\endgroup$ – David K Dec 3 at 3:52
  • $\begingroup$ @DavidK Yes. The OP added that board after my question at the end of my post, and it is clear it forces a unique solution. So I just edited my Answer to reflect this. $\endgroup$ – Bram28 Dec 3 at 13:29
  • $\begingroup$ Oops, I didn't check the edit times. Still, I think it was worth the exercise to list a sequence in which the grid can be filled without guessing. $\endgroup$ – David K Dec 3 at 13:33
  • $\begingroup$ @DavidK Quite so! And if you're up for a challenge: see how few clues you can use to force a unique solution for a $6 \times 6$ board ... I am pretty certain it will be more than $6$ ... and I suspect it in fact has to be more than $7$. So ... see if you can get $8$ clues to determine a $6 \times 6$ board. $\endgroup$ – Bram28 Dec 3 at 17:20

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.