پرش به محتویات

قرار دادن فیل روی صفحه شطرنج

تعداد راه‌های قرار دادن $K$ فیل روی یک صفحه شطرنج $N \times N$ را طوری بیابید که هیچ دو فیلی به یکدیگر حمله نکنند.

الگوریتم

این مسئله را می‌توان با استفاده از برنامه‌نویسی پویا حل کرد.

بیایید قطرهای صفحه شطرنج را به صورت زیر شماره‌گذاری کنیم: قطرهای سیاه اندیس‌های فرد و قطرهای سفید اندیس‌های زوج دارند و قطرها بر اساس تعداد خانه‌هایشان به ترتیب غیرنزولی شماره‌گذاری می‌شوند. در زیر مثالی برای یک صفحه شطرنج $5 \times 5$ آورده شده است.

$$\begin{matrix} \bf{1} & 2 & \bf{5} & 6 & \bf{9} \\\ 2 & \bf{5} & 6 & \bf{9} & 8 \\\ \bf{5} & 6 & \bf{9} & 8 & \bf{7} \\\ 6 & \bf{9} & 8 & \bf{7} & 4 \\\ \bf{9} & 8 & \bf{7} & 4 & \bf{3} \\\ \end{matrix}$$

D[i][j] را تعداد راه‌های قرار دادن j فیل روی قطرهایی با اندیس تا i که هم‌رنگ قطر i هستند، در نظر بگیرید. در این صورت i = 1...2N-1 و j = 0...K است.

ما می‌توانیم D[i][j] را تنها با استفاده از مقادیر D[i-2] محاسبه کنیم (۲ را کم می‌کنیم زیرا فقط قطرهای هم‌رنگ با قطر $i$ را در نظر می‌گیریم). دو راه برای به دست آوردن D[i][j] وجود دارد. یا همه j فیل را روی قطرهای قبلی قرار می‌دهیم: در این صورت D[i-2][j] راه برای این کار وجود دارد. یا یک فیل را روی قطر i و j-1 فیل را روی قطرهای قبلی قرار می‌دهیم. تعداد راه‌های انجام این کار برابر است با تعداد خانه‌های قطر i منهای j-1، زیرا هر یک از j-1 فیل قرار گرفته روی قطرهای قبلی، یک خانه از قطر فعلی را مسدود می‌کند. تعداد خانه‌ها در قطر i را می‌توان به صورت زیر محاسبه کرد:

int squares (int i) {
    if (i & 1)
        return i / 4 * 2 + 1;
    else
        return (i - 1) / 4 * 2 + 2;
}

حالت پایه ساده است: D[i][0] = 1 و D[1][1] = 1.

پس از محاسبه تمام مقادیر D[i][j]، پاسخ را می‌توان به صورت زیر به دست آورد: تمام تعداد ممکن فیل‌هایی که روی قطرهای سیاه قرار می‌گیرند (i=0...K) را با تعداد متناظر فیل‌ها روی قطرهای سفید (K-i) در نظر بگیرید. فیل‌های قرار گرفته روی قطرهای سیاه و سفید هرگز به یکدیگر حمله نمی‌کنند، بنابراین چیدمان‌ها را می‌توان به طور مستقل انجام داد. اندیس آخرین قطر سیاه 2N-1 و آخرین قطر سفید 2N-2 است. برای هر i، حاصل D[2N-1][i] * D[2N-2][K-i] را به پاسخ اضافه می‌کنیم.

پیاده‌سازی

int bishop_placements(int N, int K)
{
    if (K > 2 * N - 1)
        return 0;

    vector<vector<int>> D(N * 2, vector<int>(K + 1));
    for (int i = 0; i < N * 2; ++i)
        D[i][0] = 1;
    D[1][1] = 1;
    for (int i = 2; i < N * 2; ++i)
        for (int j = 1; j <= K; ++j)
            D[i][j] = D[i-2][j] + D[i-2][j-1] * (squares(i) - j + 1);

    int ans = 0;
    for (int i = 0; i <= K; ++i)
        ans += D[N*2-1][i] * D[N*2-2][K-i];
    return ans;
}