0741 - 紅魔のお嬢様はチェスがお好き〜エイトクイーン〜

あらすじ

幻想郷のとある場所にある、紅魔館。

ここには、主の吸血鬼のレミリア・スカーレットと居候のパチュリー・ノーレッジ、その他の使用人たちなどが住んでいる。

パチュリーはこの紅魔館の大図書館で生活しており、日がな毎日本を読みふけっていた。

そんなパチュリーのもとに、魔法の森の魔法使いであるアリス・マーガトロイドが遊びに来ていた・・・

ストーリー

〜大図書館にて〜

パチュリー：「ねぇ、アリス」

アリス　　　：「何かしら？」

パチュリー：「この前レミィが何かおもしろいチェスの遊び方はないかと聞いてきたのよ。普通のチェスに飽きたみたいでね」

アリス　　　：「あらそうなの？でも、パチュリーなら色々なことを知ってるから、何か考えつきそうじゃない？」

パチュリー：「いやよ。面倒くさいもの。チェスはチェスで楽しめばいいでしょう？飽きたなら他の遊びをすればいいってレミィに言っておいたわ。

　　　　　　　・・・でも、アリスなら何か思いつくかなと思ってね」

アリス　　　：「私に丸投げしないでよ。でも、いいことを思いついたわ」

パチュリー：「さすがアリスね。どんな遊び方なの？」

アリス　　　：「パチュリー、”エイトクイーン”って知ってる？」

パチュリー：「ええ、知ってるわよ。８×８のチェスの盤面に８つのクイーンを配置するゲームよね。でも、縦・横・斜め・・・つまりクイーンの

　　　　　　　行動範囲に他のクイーンが配置されていてはならない、そうよね？」

アリス　　　：「ええその通りよ。さすがパチュリーね」

パチュリー：「なるほどね。でも、それじゃあすぐに終わってしまわない？レミィはあれでなかなか頭がいいから」

アリス　　　：「確かにそれだけじゃつまらないし、すぐ終わってしまうから、クイーンをちゃんと配置できるパターン数を数えてもらいましょう。

　　　　　　　それなら結構時間がかかるわよ」

パチュリー：「そうね、そうしましょう。小悪魔、聞いていたわよね？答えを知らなきゃレミィに答え合わせができないから、

　　　　　　　エイトクイーンのパターン数を数えておいて頂戴」

図書館にはパチュリーの使い魔の小悪魔がおり、膨大な数の蔵書を全て一人で管理していた。

小悪魔　　：「ええー！？そんなぁ〜パチュリー様、それってすごく大変なんじゃないですか〜？」

アリス　　　：「頑張ってね♪こあちゃん♪」

小悪魔　　：「アリスさんまでぇ〜」

小悪魔はパターン数を数えるとかなりの時間がかかってしまうことを、悪魔の勘で無意識のうちに察している。

そこで、あなたは小悪魔のためにエイトクイーンのパターン数を求めるプログラムを作ってほしい。

問題概要

nが与えられるため、n*nの盤面にn個のクイーンが縦・横・斜めに重ならないように配置するパターン数を出力せよ。

入力

n

盤面の大きさnが与えられる。

出力

配置のパターン数を１行に出力せよ。最後に改行すること。

制約

全ての入力ケースについて以下を満たす。

• 1 ≦ n ≦ 12

---

入出力例

入力例

5

出力例

10

解説

左右反転や回転したパターンも、別々のパターンとして考える。

作者から

たぶん問題制作者のコードは完璧ではないので、ei1630より速いコードをじゃんじゃん書いてください。

また、ただのif文、switch文で答えを通した輩は、アリス同盟の”百合”部門の”マリアリ”課の”マリアリが俺のジャスティス”派に強制加盟してもらいます。