1
$\begingroup$

I thought of this problem when playing Sudoku. Let A = {1,2,3,4}. I have to make a 4x4 box (i.e. the size of A in both dimensions) and fill it with data such that no dimension has repetition. How many solutions I can make such that repetition in all the 4 vertical, 4 horizontal, and 2 diagonal directions is 0?

Example solution without repeated data:

1    3    4    2
2    4    3    1
3    1    2    4
4    2    1    3

Example solution with repeated data:

1    2    3    4
2    1    4    3
3    4    1    2
4    3    2    1

Although the data are distinct in the horizontal and vertical directions, they repeat along the diagonals.

For n=1 there is a single possible solution. For n=2 and n=3 there are no possible solutions for 0 repetition. How many solutions are possible for n=4?

Improve this question
$\endgroup$
5
  • $\begingroup$ Probably you meant "repetition" instead of "redundancy" $\endgroup$
    – justhalf
    Sep 21 at 6:19
  • $\begingroup$ Yes sir i meant repetition $\endgroup$
    – HelptimeCode
    Sep 21 at 6:31
  • 3
    $\begingroup$ OEIS A274806 $\endgroup$
    – Daniel Mathias
    Sep 21 at 8:02
  • 1
    $\begingroup$ That sequence says 48 for n=4. Note that you can permute/relabel the numbers in n! ways, so there are really only 2, and this is given in A274171. $\endgroup$
    – Jaap Scherphuis
    Sep 21 at 8:28
  • $\begingroup$ @bobble I was playing Soduku and i started analysing $\endgroup$
    – HelptimeCode
    Sep 22 at 5:43

1 Answer 1

Reset to default
6
$\begingroup$

For any solution, we can relabel the numbers so that the top row reads 1,2,3,4. Given that, there are only

two ways to fill the bottom left square (must be a 2 or 3). Each of these options then forces the remaining squares on the antidiagonal, and then the first column follows, and then the rest of the board as well:

1 2 3 4   1 2 3 4   1 2 3 4
. . . .   . . 1 .   3 4 1 2
. . . .   . 3 . .   4 3 2 1
2 . . .   2 . . .   2 1 4 3

1 2 3 4   1 2 3 4   1 2 3 4
. . . .   . . 2 .   4 3 2 1
. . . .   . 1 . .   2 1 4 3
3 . . .   3 . . .   3 4 1 2

This means there are

$2\cdot4!=48$ solutions.

Improve this answer
$\endgroup$
5
  • $\begingroup$ the for n=5 will it be 3*5! sir ? $\endgroup$
    – HelptimeCode
    Sep 21 at 9:51
  • 1
    $\begingroup$ @HelptimeCode Apparently it will be 8*5!. After filling the top row and bottom left corner (3 ways) there are now several possibilities for filling the antidiagonal and the rest of the board. I don't know of any way to figure out the 8 solutions without searching through every possibility. For n=4 that was quite easy, but for n=5 that is beginning to get complicated. For larger n it would be best done by computer. $\endgroup$
    – Jaap Scherphuis
    Sep 21 at 9:55
  • 2
    $\begingroup$ @JaapScherphuis For n=5 with top row fixed there are 2 options for center square, then 2 ways to fill the bottom corners. Half of the remaining squares are forced, leaving an obviously binary choice for completion. $\endgroup$
    – Daniel Mathias
    Sep 21 at 11:22
  • $\begingroup$ is there anything to compute the diagonals ? $\endgroup$
    – HelptimeCode
    Sep 21 at 11:22
  • $\begingroup$ @HelptimeCode Choose center $x$ first, then there are only 2 choices for corner $y$ and 2 ways to complete the grid from there. There is no simple formula, just refer to the values shown in OEIS. $\endgroup$
    – Daniel Mathias
    Sep 21 at 11:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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