8-16 8王妃問題で対称解を除外

問題

8-7 8王妃問題で対称解を除外して、解を表示する。

再帰の技法の31ページの練習問題を参考にさせていただきました。

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] Ban = new int[9, 9];

        var stk = new Stack<int[,]>();
        stk.Push((int[,])Ban.Clone());

        var answerList = new List<int[,]>();

        while (stk.Count != 0) {
            Ban = stk.Pop();

            int ouhiCnt = 0;
            for (int X = 1; X <= 8; X++) {
                for (int Y = 1; Y <= 8; Y++) {
                    if (Ban[Y, X] == 1) ouhiCnt++;
                }
            }

            if (ouhiCnt == 8) {
                answerList.Add(Ban);
                continue;
            }

            for (int Y = 1; Y <= 8; Y++) {
                if (IsValid(Ban, Y, ouhiCnt + 1)) {
                    int[,] cloneArr = (int[,])Ban.Clone();
                    cloneArr[Y, ouhiCnt + 1] = 1;
                    stk.Push(cloneArr);
                }
            }
        }

        int answerCnt = 0;
        for (int I = 0; I <= answerList.Count - 1; I++) {
            bool IsOK = true;

            for (int J = 0; J < I; J++) {
                if (IsDuplicate(answerList[I], answerList[J])) {
                    IsOK = false; break;
                }
            }
            if (IsOK == false) continue;

            Console.WriteLine();
            Console.WriteLine("answer" + (++answerCnt).ToString());
            for (int Y = 1; Y <= 8; Y++) {
                for (int X = 1; X <= 8; X++) {
                    Console.Write(answerList[I][Y, X]);
                }
                Console.WriteLine();
            }
        }
    }

    static bool IsValid(int[,] pBan, int targetY, int targetX)
    {
        //横チェック
        for (int X = 1; X <= 8; X++)
            if (pBan[targetY, X] == 1) return false;

        //左下チェック
        for (int X = targetX, Y = targetY; 1 <= X && X <= 8 && 1 <= Y && Y <= 8; X--, Y++)
            if (pBan[Y, X] == 1) return false;

        //左上チェック
        for (int X = targetX, Y = targetY; 1 <= X && X <= 8 && 1 <= Y && Y <= 8; X--, Y--)
            if (pBan[Y, X] == 1) return false;
        return true;
    }

    static bool IsDuplicate(int[,] pBan1, int[,] pBan2)
    {
        //左右反転
        bool wkResult = true;
        for (int Y = 1; Y <= 8; Y++)
            for (int X = 1; X <= 8; X++)
                if (pBan1[X, Y] != pBan2[9 - X, Y]) wkResult = false;
        if (wkResult) return true;

        //上下反転
        wkResult = true;
        for (int Y = 1; Y <= 8; Y++)
            for (int X = 1; X <= 8; X++)
                if (pBan1[X, Y] != pBan2[X, 9 - Y]) wkResult = false;
        if (wkResult) return true;

        //点対称
        wkResult = true;
        for (int Y = 1; Y <= 8; Y++)
            for (int X = 1; X <= 8; X++)
                if (pBan1[X, Y] != pBan2[9 - X, 9 - Y]) wkResult = false;
        if (wkResult) return true;

        return false;
    }
}

実行結果

省略
answer23
00000100
00100000
00001000
00000001
10000000
00010000
01000000
00000010

answer24
00100000
00001000
01000000
00000001
10000000
00000010
00010000
00000100

解説

左右反転や上下反転などで対称解が存在するかをチェックしてます。