Q38 全員が大きく移動する席替え

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    static void Main()
    {
        Solve(2, 3);
        Solve(4, 4);
    }

    static void Solve(int pHabaX, int pHabaY)
    {
        int AllBitOn = (1 << (pHabaX * pHabaY)) - 1;

        // 座標のList
        var PointList = new List<PointDef>();
        for (int LoopX = 0; LoopX <= pHabaX - 1; LoopX++) {
            for (int LoopY = 0; LoopY <= pHabaY - 1; LoopY++) {
                PointDef WillAdd;
                WillAdd.X = LoopX;
                WillAdd.Y = LoopY;
                PointList.Add(WillAdd);
            }
        }

        // 場合の数[使用済盤面のハッシュ値]なDP表
        long[] PrevDP = new long[AllBitOn + 1];
        PrevDP[0] = 1;

        // 移動元のループ
        foreach (PointDef FromPos in PointList) {
            long[] CurrDP = new long[AllBitOn + 1];

            // 移動先のループ
            foreach (PointDef ToPos in PointList) {
                if (FromPos.X == ToPos.X) continue;
                if (FromPos.Y == ToPos.Y) continue;

                for (int I = 0; I <= AllBitOn; I++) {
                    if (PrevDP[I] == 0) continue;
                    int[,] CurrBanArr = DeriveBanArr(I, pHabaX, pHabaY);
                    if (CurrBanArr[ToPos.X, ToPos.Y] == 1) continue;

                    CurrBanArr[ToPos.X, ToPos.Y] = 1;
                    long Hash = GetHash(CurrBanArr, pHabaX, pHabaY);
                    CurrDP[Hash] += PrevDP[I];
                }
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine("横幅{0},縦幅{1}では{2}通り", pHabaX, pHabaY, PrevDP.Sum());
    }

    // 使用済盤面のハッシュ値を返す
    static int GetHash(int[,] pBanArr, int pHabaX, int pHabaY)
    {
        var BinList = new List<int>();
        for (int LoopX = 0; LoopX <= pHabaX - 1; LoopX++) {
            for (int LoopY = 0; LoopY <= pHabaY - 1; LoopY++) {
                BinList.Add(pBanArr[LoopX, LoopY]);
            }
        }
        BinList.Reverse();
        var sb = new System.Text.StringBuilder();
        BinList.ForEach(pX => sb.Append(pX));
        return Convert.ToInt32(sb.ToString(), 2);
    }

    // ハッシュ値から使用済盤面を復元
    static int[,] DeriveBanArr(int pHash, int pHabaX, int pHabaY)
    {
        int[,] BanArr = new int[pHabaX, pHabaY];

        string BinStr = Convert.ToString(pHash, 2);
        int NeedLen = pHabaX * pHabaY;
        BinStr = BinStr.PadLeft(NeedLen, '0');

        string RevStr = new string(BinStr.ToCharArray().Reverse().ToArray());

        int CurrInd = 0;
        for (int LoopX = 0; LoopX <= pHabaX - 1; LoopX++) {
            for (int LoopY = 0; LoopY <= pHabaY - 1; LoopY++) {
                BanArr[LoopX, LoopY] = RevStr[CurrInd] - '0';
                CurrInd++;
            }
        }
        return BanArr;
    }
}

実行結果

横幅2,縦幅3では4通り
横幅4,縦幅4では3089972673通り

解説

移動済の座標を1、移動済でない座標を0としたハッシュ値で、
ビットDPで解いてます。