毎日のコーディング問題: コーディング スキルを使ってチェックメイトをチェックする

チェックメイトをチェックする

ようこそ、解決すべき別の問題があります。チェスとコーディングが好きなら、これはあなたにぴったりです!今日、私たちは王が戦場でもう一日生き残れるよう手助けし、かなりの量のコードも書きます。

それでは早速、問題を見てみましょう。ただし、始める前に、いつものように、2 つの免責事項を述べておきます。

• これらの問題は、購読できる素晴らしいニュースレター「Dailycoding 問題」によって提供されます。ここ: ぜひチェックして、毎日の課題を解決してみてください!
• 私は専門プログラマーではなく、自分の試み (および失敗) を共有するのが好きなだけです。より良いアイデアや解決策をお持ちの場合は、ぜひ共有してください。ぜひ取り組んでいただきたいと思っています。

問題

今日の問題は、最初は Oracle によって尋ねられました。

チェス盤上の駒の位置を表す8 × 8の行列が表示されます。ボード上の駒は黒のキングとさまざまな白の駒だけです。この行列を与えて、王が抑制されているかどうかを判断します。

各ピースの動きの詳細については、ここ。

たとえば、次の行列があるとします。

 ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..

ビショップはキングを斜めに攻撃しているため、 Trueを返す必要があります。

問題は非常に明らかなので、これ以上詳しく説明しません。ただし、いくつかの開始仕様が必要なだけです。

1. 私たちはボード上ではなくグラフ上にいます。問題によって与えられた各点をボード上のケースの中心と見なします。結果はまったく同じです。
2. 白のキングは他の 7 人のポーンと一緒に休暇に出かけました。キングとポーンはすべてのピースの中で最も退屈であり、それらを削除しても解決策はそれほど変わりません。
3. このターンでキングがチェックされているかどうかを確認する必要があります。つまり、キングが動かなければ次の白ターンでチェックされることになります。
4. 位置は最初にゲームによって与えられます。重複する駒や間違った開始位置については検証しません。

ソリューション

まず最初に、駒と移動セットについて簡単にまとめます。

各駒の開始位置とその移動セットを考慮すると、各駒の可能な次の手を「簡単に」計算できます。

そして、彼らは皆、できるだけ早く王を捕まえることに興味があるので、彼らの次の行動は黒の王を捕まえることになると推測できます。したがって、黒キングの位置もわかっているので、黒キングの位置が他の駒の次の可能な手の 1 つであるかどうかを確認するだけで済みます。そうであれば、次の白のターン中に白の駒がそこに移動して黒のキングを捕らえます。

状況は次のようになります。
上の写真では、さまざまな色で着色された白い側の各駒のあらゆる動きと、その上で捕らえられるのを待っている黒い王を見ることができます (…そう願っています、混乱して申し訳ありません…)。したがって、たとえばビショップは (2,7) から開始して、(1,6)、(1,8)、(3,8)、(3,6)、(4,5)、(5、 4）など。

最終的な結果には影響しないので、これらのピースの開始位置をランダムに決定しました。

ここでは 8x8 グラフ上にあり (明確にしておきますが、他の次元でも同様に機能します)、各ピースの開始座標がわかっているので、ピースの次の移動となる一連の座標x、yを構築できます。これを行うには、まず各駒のクラスを定義し、その座標を定義してから、そこからあらゆる可能な手を計算するルールを定義します。

ピース — ポーン

ポーンから簡単に始めましょう。ちなみに、私はこれをPythonで構築しています。Python は現時点で最も人気のある言語の 1 つであり、おそらく誰にとっても最も読みやすい言語だからです。ただし、これからフォローするにはクラスが何であるかを知る必要があります。こちらですこの概念を非常にうまく説明しています。

簡単に説明しましょう。まず、 class Pawnクラスとその座標x,yを__init__定義します。その後、そこからポーンの可能な動きを計算するためにpossibleMovesメソッドを定義します。ポーンの動きは比較的簡単なので、グリッドの外に移動しないことを確認した後、単純に変数movesに追加し、 moves配列を返します。ここで、特にポーンに関して注意すべき点が 2 つあります。

1. 私たちが白プレイヤーとして自分のポーンを対戦相手に向かって前進させるのと同じように、白のポーンは下から上に移動すると考えます。これは実際には何も変わりません。ただ物事を整理しているだけです。

2. 黒のキングをキャプチャすることに興味があるため、意図的に通常の動きをスキップします。ポーンは斜めにのみキャプチャでき、駒を他の方向に動かすことは気にしないので、通常の動きをスキップできます。

   
   

これで、次のようにポーンの座標を指定してpossibleMovesメソッドを呼び出すことで、ポーンの動きを簡単にチェックできます。 print(Pawn(7,2).possibleMoves())実行すると、 [(6,3),(8,3)]のような結果が得られます。 [(6,3),(8,3)] 。

また、上部でグリッドの次元を変数として定義したことがわかります。そのため、他の次元のボードでアルゴリズムを実行するように変数を変更できる可能性があります。

さあ、塔に行きましょう。

塔

もう一度、Tower クラスをその座標で初期化し、関数possibleMovesを定義します。ここですべての可能な動きを収集するために、タワーの 2 つの軸上のすべての点の範囲を設定し、各単一の座標を変数movesに追加します。これはすべてのループの後に返されます。前と同様に、タワーの動きを確認するには、単純にprint(Tower(5,3).possibleMoves())実行すると、次のような結果が得られます: [(1,3), (2,3), (3,3), ..., (5,8)] 。

司教

今度は司教の出番です。

ビショップの動きはタワーよりも複雑なので、ここで何が起こっているのかを少し説明するかもしれません。基本的に、開始位置から開始して 2 つの対角軸上のポイントを収集する必要があります。クラスと init メソッドを宣言した後、2 つの変数を作成します。前と同様にmovesと、軸に沿って移動中に収集したポイントを追跡するために使用されるcurrentPosです。次にwhileループを使用して、グリッドの外に移動していないことを確認し、移動したい場所に応じてxとyを増減します。たとえば、開始位置から左上に移動したい場合は、 x値を増加させながら、 y値を減少させる必要があります。右下に移動したい場合は、 y値を減分しながらx値を増分する必要があります。最後に、もう一度movesを返すだけです。

女王

ここで、次のように考えることができます。タワーの動きが複雑で、ビショップがさらに複雑である場合、一体どうやってクイーンをコード化するのでしょうか?実際、クイーンの動きは、簡単なトリックを使用するだけで、コーディングが最も簡単です。それでは女王様に会いに行きましょう。

さて、ここで何が起こっているのでしょうか？まあ、考えてみれば、クイーンはビショップとタワーの動きを合わせたものと同じだ。女王というより塔型の司教メカボットに近いですね。このため、彼女の動きのコーディングは非常に簡単です。彼女のクラスを宣言した後、ビショップとタワーの可能な動きから生じる動きの結合配列として彼女のpossibleMovesを定義するだけです。

possibleMoves関数でクラスBishopインスタンスとTowerインスタンスを呼び出すときに、それらのパラメーターxとyがself.x, self.yとして指定されるため、実際にはそれらがクイーンの座標であることに注意してください。

騎士

さあ、騎士へ！

私にとって騎士は最も特別なものです。彼のムーブセットは「L」字型のように奇妙です。そのため、それをコード化するための特に賢明で高速な方法は見つかりませんでした。最終的には、開始位置から彼が持つ可能性のある 8 つのムーブをそれぞれ計算するだけで、ムーブをハードコーディングすることになりました。

王様

王についてのいくつかの簡単な概念。キングを移動する必要はなく、チェックされているかどうかを示すだけなので、実際に彼の move-set を実装する必要はありません。ただし、記事の最後では簡単な実装についても説明します。また、後で説明するように、コーディングはクイーンの動きセットを弱体化するほど単純ではありません。したがって、今のところは彼の動きをスキップして解決策を見てみましょう。

解決策のコード

各駒の可能な位置がわかっていることを考えると、解決策は非常に簡単です。黒のキングの座標が 1 つ以上の他の駒の一連の動きの中にあるかどうかを確認するだけです。コーディングしてみよう！

ここでは、変数blackKingいくつかの座標として作成するだけです。次に、ピースごとに、構築したばかりのクラスのインスタンスを作成し、メソッドpossibleMovesを呼び出して、その完全な動きのセットを計算します。それを取得したら、 blackKing座標がそれらの移動セットに存在するかどうかを確認します。存在する場合は、キングがその特定のピースによってチェックされていることを出力します。結果は次のようになります。

 Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight!

上の乱雑な画像を参考にしましたが、実際に王が塔と騎士によってチェックされていることが確認できます。

チェックメイト

キングにまだ生き残るチャンスがあるのか、それとも実際にチェックメイトなのかも計算したい場合はどうなるでしょうか?この目的のために、キングの一連の動きを計算する必要があります。

少し説明しましょう。まず、前と同じようにクラスと座標を定義します。その後、 possibleMovesメソッドを作成し、キングの可能な手をコード化します (繰り返しになりますが、もっと速い方法があると確信していますが、可能な手は 8 つしかないので…)。その後、どの手が不正であるか (盤外への移動) をチェックし、 validMovesのみを返します。

したがって、キングにまだ生き残るチャンスがあるかどうかを確認するには、彼の可能な手のいずれかが別の一連の動きに含まれていないかを確認する必要があります。これを行うには、キングの動きと他の動きをループするだけです。

つまり、私たちの王にはまだ生き残る希望があるのです！彼にとっては幸運だったと思います…

時間計算量

いつものように、このソリューションの時間計算量を簡単に説明します。

まず、各部分はクラス のインスタンスであるため、そのインスタンスを初期化する時間を考慮する必要があります。

• ポーンやナイトのような駒は内部にループがなく、変数の次元に依存しないため、O(1) とみなすことができます。
• このタワーは少し注意が必要です。タワーには 4 つの for ループが含まれているため、その時間計算量は O(n) であるとすぐに考えることができますよね。実際、タワーがどのように動くかを考えてみると、ボード上のどこにタワーを配置しても、その動きは縦軸と横軸のフリーボードケースに限定されることがわかります。また、ボードは正方形であるため、タワーを移動するための空きケースが常に 14 個あります。したがって、その時間計算量は実際には O(1) であり、14 組の座標に対して一定である必要があります。以下に図の例を示します。

• 残念ながら、ビショップについては同じことが言えません。ビショップの一連の動きはもう少し複雑であるようです。基本的に、ボード上のどこに配置されるかに応じて、7、9、11、または 13 の手があります。したがって、彼の一連の動きを計算するために必要なステップは彼の位置に基づいているため、O(n) の tc を考慮できます。

• クイーンには、タワーとビショップの一連の動きを組み合わせる必要があります。時間計算量を評価する際には最悪のシナリオに焦点を当てる必要があるため、ビショップの TC がタワーの TC よりも優先されます。したがって、女王についても O(n) の tc を考慮する必要があります。

• 最後に、キングにはハードコードされた一連の動きだけでなく、 for ループを使用する検証プロセスも含まれています。したがって、技術的には、キングの一連の手がどのような場合でも比較的小さい場合でも、ボード上の位置にも応じて、彼の tc を O(n) と見なす必要があります。

  
  

この時点で、ピースごとに for ループを使用して、黒王のチェック ステータスを確認し、出力します。これにより、tc が一定の場合には問題は発生しません (タワーを例に挙げます。14 回の移動を計算し、それから最大 14 回他の移動をループするため、時間も固定であると考えることができます)。それでも、ループを追加しているので、tc が O(n) 以上になると問題が発生します。これは、移動数が増えるにつれてループも大きくなるからです。

最後に、ダブル (内部) for ループを使用してチェック メイト を検証します。これは、キングの移動数と他の駒の移動に応じて、確実に O(n²) の tc になります。

それでおしまい;私の解決策があります。いくつかの点が可能な限り効率的ではないことは承知していますが、執筆中は完璧なソリューションを構築するよりもプロセスを説明するというアイデアが好きでした。

あなたはこのことについてどう思いますか？それについてあなたの意見を聞かせてください、そしてコメントであなたの解決策について話し合いましょう！

いつものように、この記事が気に入っていただけましたら、拍手を 1 ～ 2 回残して購読していただくか、可能であればこの種のアルゴリズムに興味がある可能性のある人と共有してください。最後まで読んでいただきありがとうございます。今回は、このソリューションの長さを考えると、いつも以上に長かったです。

いつものように、読んでいただきありがとうございます。