1

問題は、サイズ N*M の行列を満たす可能性の量を見つけることができるアルゴリズムは何かということです

これには 1 から N*M までのすべての数値が含まれ、左から右、上から下にソートされます

例えば：

N = 2 、M = 3 の場合、量は 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

私はある種のパターンを理解しようとしましたが、成功しませんでした.これは宿題です. [0][0] で、助けていただければ幸いです

4

1 に答える 1

2

あなたが忘れてしまった：

1 3 4
2 5 6

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();
    }

説明：

1 から順番に数字をボードに配置します。同じ数字の正しい配置が複数ある場合は、再帰的に分割し、すべての解を数えます。

可能なすべての配置を試したりバックトラッキングを使用したりせずに、数字の正しい配置をどのように知ることができますか? 「-1 番目」の行に無限の数があると仮定すると、前の行にさらに多くの数値がある、満杯でない行の最初の空の位置に数値を入れることができます。それでおしまい。このようにして、私たちは決して間違った動きをしません。

これは対称的であることに注意してください。満杯でない場合はいつでも次の数字を最初の行に入れることができるのと同じように、最初の列に入れることもできます。

ソリューションの数は非常に急速に増加します。

2x2 - 2
3x3 - 42
4x4 - 24024
5x5 - 701149020
于 2012-12-17T16:15:27.910 に答える