CODEWITHSUNDEEP
algorithmmatrixpseudocode
Daniel Jakobsen Hallel
Daniel Jakobsen Hallel

Reputation: 584

Fill matrix with specific conditions

the question is what algorithm can find the amount of possibilities to fill a matrix with size N*M

that will include all numbers from 1 to N*M , in a way that it is sorted from left to right , up to down

for example:

for N = 2 , M = 3 the amount is 4

  1. 1 2 3

    4 5 6

  2. 1 3 5

    2 4 6

  3. 1 2 5

    3 4 6

  4. 1 2 4

    3 5 6

i tried to figure out some sort of pattern but with no success , this is homework , what i did realize is that in all cases the biggest number from N*M has to be in [N][M] and the lowest has to be in [0][0] , help would be much appreciated

Upvotes: 1

Views: 232

Answers (1)

svinja
svinja

Reputation: 5576

You forgot:

1 3 4
2 5 6

Code in c#:

    static int N = 5;
    static int M = 5;
    static int[,] Number;
    static int[] NumbersInRow;


    static int Put(int n)
    {
        if (n > N * M)
        {
            // If output of each solution is desired
            //for (int y = 0; y < N; y++)
            //{
            //    for (int x = 0; x < M; x++)
            //        Console.Write(Number[y, x] + "\t");

            //    Console.WriteLine();
            //}
            //Console.WriteLine();
            return 1;
        }

        int sum = 0;

        int numbersInLastRow = int.MaxValue;
        int currentRow = 0;
        while (currentRow < N)
        {
            int numbersInCurrentRow = NumbersInRow[currentRow];
            if (numbersInCurrentRow < numbersInLastRow && numbersInCurrentRow < M)
            {
                Number[currentRow, NumbersInRow[currentRow]] = n;
                NumbersInRow[currentRow]++;
                sum += Put(n + 1);
                NumbersInRow[currentRow]--;
                Number[currentRow, NumbersInRow[currentRow]] = 0;
            }
            numbersInLastRow = NumbersInRow[currentRow];
            currentRow++;
        }

        return sum;
    }

    static void Main(string[] args)
    {
        Number = new int[N, M];
        NumbersInRow = new int[N];
        Console.WriteLine(Put(1));
        Console.ReadLine();
    }

Explanation:

Place numbers on the board in order, starting with 1. When there are multiple correct placements for a number, split recursively and count all the solutions.

How do we know which are the correct placements for a number without trying every possible placement / using backtracking? A number can be put in the first empty position of any non-full row whose previous row has more numbers in it, assuming the "-1th" row has an infinite number of numbers in it. That's it. This way we never make a wrong move.

Note that this is symmetric - just like you can always put the next number into the first row if it isn't full, you can also put it into the first column.

The number of solutions grows extremely quickly:

2x2 - 2
3x3 - 42
4x4 - 24024
5x5 - 701149020

Upvotes: 2

Related Questions