U
U
user1112222017-03-27 01:12:35
Algorithms
user111222, 2017-03-27 01:12:35

How to find the number of options for filling a latin square?

A Latin square is an N×N square, each cell of which contains a number from 1 to N so that the following conditions are met: in each row and column, each digit occurs once.
The input is a square matrix, some cells are filled with numbers. It is necessary to determine in how many ways it is possible to complete the matrix in such a way that the condition of the Latin square is satisfied.

Answer the question

In order to leave comments, you need to log in

1 answer(s)
V
Vladimir Olohtonov, 2017-03-27
@sgjurano

It seems like it turned out to be true:
Number of permutations of the first row * number of permutations of rows from the second to n.
n! * (n-1)!
Proof of correctness: since we need to compose n rows in such a way that each of the columns has exactly 1 occurrence of each of the numbers, it is fair to consider the rows as cycles of length n. Consider all possible permutations of the first row, there are n!, for each of the permutations we will construct n cycles, this can be done in 1 way, fix the position of the first row, mix the rest in all possible ways, there are (n-1)!, total n!*(n-1 )! options. There are no duplicates among them, since the first line is unique. Each row contains all numbers, since they are cycles, and each column also contains all numbers, since each row is one of all possible cyclic permutations.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question