チェックメイトをチェックする ようこそ、解決すべき別の問題があります。チェスと が好きなら、これはあなたにぴったりです!今日、私たちは王が戦場でもう一日生き残れるよう手助けし、かなりの量のコードも書きます。 コーディング それでは早速、問題を見てみましょう。ただし、始める前に、いつものように、2 つの免責事項を述べておきます。 これらの問題は、購読できる素晴らしいニュースレター「Dailycoding 問題」によって提供されます。 : ぜひチェックして、毎日の課題を解決してみてください! ここ 私は専門プログラマーではなく、自分の試み (および失敗) を共有するのが好きなだけです。より良いアイデアや解決策をお持ちの場合は、ぜひ共有してください。ぜひ取り組んでいただきたいと思っています。 問題 今日の問題は、最初は Oracle によって尋ねられました。     の行列 。 チェス盤上の駒の位置を表す 8 × 8 が表示されます ボード上の駒は黒のキングとさまざまな白の駒だけです。この行列を与えて、王が抑制されているかどうかを判断します。 各ピースの動きの詳細については、 ここ 。 たとえば、次の行列があるとします。   ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..   。 ビショップはキングを斜めに攻撃しているため、 True を返す必要があります 問題は非常に明らかなので、これ以上詳しく説明しません。ただし、いくつかの開始仕様が必要なだけです。 私たちはボード上ではなくグラフ上にいます。 。結果はまったく同じです。 問題によって与えられた各点をボード上のケースの中心と見なします 白のキングは他の 7 人のポーンと一緒に休暇に出かけました。キングとポーンはすべてのピースの中で最も退屈であり、それらを削除しても解決策はそれほど変わりません。 必要があります。つまり、キングが動かなければ次の白ターンでチェックされることになります。 このターンでキングがチェックされているかどうかを確認する 。重複する駒や間違った開始位置については検証しません。 位置は最初にゲームによって与えられます ソリューション まず最初に、駒と移動セットについて簡単にまとめます。  各駒の開始位置とその移動セットを考慮すると、 できます。 各駒の可能な次の手を「簡単に」計算 そして、彼らは皆、できるだけ早く王を捕まえることに興味があるので、 と推測できます。したがって、黒キングの位置もわかっているので、 。そうであれば、次の白のターン中に白の駒がそこに移動して黒のキングを捕らえます。 彼らの次の行動は黒の王を捕まえることになる 黒キングの位置が他の駒の次の可能な手の 1 つであるかどうかを確認するだけで済みます 状況は次のようになります。  上の写真では、さまざまな色で着色された白い側 と、その上で捕らえられるのを待っている黒い王を見ることができます (…そう願っています、混乱して申し訳ありません…)。したがって、たとえばビショップは (2,7) から開始して、(1,6)、(1,8)、(3,8)、(3,6)、(4,5)、(5、 4）など。 の各駒のあらゆる動き 最終的な結果には影響しないので、これらのピースの開始位置をランダムに決定しました。 ここでは 8x8 グラフ上にあり (明確にしておきますが、他の次元でも同様に機能します)、各ピースの開始座標がわかっているので、ピースの次の移動となる一連の座標 を構築できます。これを行うには、まず その座標を定義してから、 x、y 各駒のクラスを定義し、 そこからあらゆる可能な手を計算するルールを定義します。 ピース — ポーン ポーンから簡単に始めましょう。ちなみに、私はこれを で構築しています。Python は現時点で最も人気のある言語の 1 つであり、おそらく誰にとっても最も読みやすい言語だからです。ただし、これからフォローするには 。 この概念を非常にうまく説明しています。 Python クラスが何であるかを知る必要があります こちらです   https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py 簡単に説明しましょう。まず、  クラスとその座標 を 定義します。その後、そこからポーンの可能な動きを計算するために メソッドを定義します。ポーンの動きは比較的簡単なので、グリッドの外に移動しないことを確認した後、単純に変数 に追加し、  配列を返します。ここで、特にポーンに関して注意すべき点が 2 つあります。 class Pawn x,y __init__ possibleMoves moves moves 私たちが白プレイヤーとして自分のポーンを対戦相手に向かって前進させるのと同じように、白のポーンは下から上に移動すると考えます。これは実際には何も変わりません。ただ物事を整理しているだけです。 黒のキングをキャプチャすることに興味があるため、 。ポーンは斜めにのみキャプチャでき、駒を他の方向に動かすことは気にしないので、通常の動きをスキップできます。 意図的に通常の動きをスキップします これで、次のようにポーンの座標を指定して メソッドを呼び出すことで、ポーンの動きを簡単にチェックできます。  実行すると、  のような結果が得られます。   。 possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] [(6,3),(8,3)] また、上部で ことがわかります。そのため、他の次元のボードでアルゴリズムを実行するように変数を変更できる可能性があります。 グリッドの次元を変数として定義した さあ、塔に行きましょう。 塔 https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py もう一度、Tower クラスをその座標で初期化し、関数 を定義します。ここですべての可能な動きを収集するために に追加します。これはすべてのループの後に返されます。前と同様に、タワーの動きを確認するには、単純に 実行すると、次のような結果が得られます:   。 possibleMoves 、タワーの 2 つの軸上のすべての点の範囲を設定し、各単一の座標を変数 moves print(Tower(5,3).possibleMoves()) [(1,3), (2,3), (3,3), ..., (5,8)] 司教 今度は司教の出番です。   https://gist.github.com/NicolaM94/a6ae6f6138b78d550b2f2e27d5c453aa?embedable=true#file-bishop-py ビショップの動きはタワーよりも複雑なので、ここで何が起こっているのかを少し説明するかもしれません。基本的に 。クラスと init メソッドを宣言した後、2 つの変数を作成します。前と同様に と、軸に沿って移動中に収集したポイントを追跡するために使用される です。次に ループを使用して、グリッドの外に移動していないことを確認し、 と 。たとえば、開始位置から左上に移動したい場合は、  値を増加させながら、  値を減少させる必要があります。右下に移動したい場合は、  値を減分しながら 値を増分する必要があります。最後に、もう一度 を返すだけです。 、開始位置から開始して 2 つの対角軸上のポイントを収集する必要があります moves currentPos while 移動したい場所に応じて x y を増減します x y y x moves 女王 ここで、次のように考えることができます。タワーの動きが複雑で、ビショップがさらに複雑である場合、一体どうやってクイーンをコード化するのでしょうか?実際、クイーンの動きは、簡単なトリックを使用するだけで、コーディングが最も簡単です。それでは女王様に会いに行きましょう。   https://gist.github.com/NicolaM94/22bd55aab7a0976f4656403c3749a6ee?embedable=true#file-queen-py さて、ここで何が起こっているのでしょうか？まあ、考えてみれば、 。女王というより塔型の司教メカボットに近いですね。このため、彼女の動きのコーディングは非常に簡単です。彼女のクラスを宣言した後、 として彼女の を定義するだけです。 クイーンはビショップとタワーの動きを合わせたものと同じだ ビショップとタワーの可能な動きから生じる動きの結合配列 possibleMoves   関数でクラス インスタンスと インスタンスを呼び出すときに、それらのパラメーター と が として指定されるため、実際にはそれらがクイーンの座標であることに注意してください。 possibleMoves Bishop Tower x y self.x, self.y 騎士 さあ、騎士へ！   https://gist.github.com/NicolaM94/c19d2c41e4461c66fca54aab239ede9e?embedable=true#file-knight-py 私にとって騎士は最も特別なものです。彼のムーブセットは「L」字型のように奇妙です。そのため、それをコード化するための特に賢明で高速な方法は見つかりませんでした 計算するだけで、ムーブをハードコーディングすることになりました。 。最終的には、開始位置から彼が持つ可能性のある 8 つのムーブをそれぞれ 王様 王についてのいくつかの簡単な概念。キングを移動する必要はなく、チェックされているかどうかを示すだけなので、 。ただし、記事の最後では簡単な実装についても説明します。また、後で説明するように、コーディングはクイーンの動きセットを弱体化するほど単純ではありません。したがって、今のところは彼の動きをスキップして解決策を見てみましょう。 実際に彼の move-set を実装する必要はありません 解決策のコード 各駒の可能な位置がわかっていることを考えると、解決策は非常に簡単です。黒のキングの座標が 1 つ以上の他の駒の一連の動きの中にあるかどうかを確認するだけです。コーディングしてみよう！   https://gist.github.com/NicolaM94/75826a753105c3a3aecae4f6890b631a?embedable=true#file-check-py ここでは、変数 いくつかの座標として作成するだけです。次に、ピースごとに、構築したばかりのクラスのインスタンスを作成し、メソッド を呼び出して、その完全な動きのセットを計算します。   かどうかを確認します。存在する場合は、キングがその特定のピースによってチェックされていることを出力します。結果は次のようになります。 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! 上の乱雑な画像を参考にしましたが、実際に王が塔と騎士によってチェックされていることが確認できます。 チェックメイト 、それとも実際にチェックメイトなのかも計算したい場合はどうなるでしょうか?この目的のために、キングの一連の動きを計算する必要があります。 キングにまだ生き残るチャンスがあるのか   https://gist.github.com/NicolaM94/cca18293bedb2293bbc621e86236571f?embedable=true#file-king-py 少し説明しましょう。まず、前と同じようにクラスと座標を定義します。その後、  メソッドを作成し、キングの可能な手をコード化します (繰り返しになりますが、もっと速い方法があると確信していますが、可能な手は 8 つしかないので…)。その後、 、  のみを返します。 possibleMoves どの手が不正であるか (盤外への移動) をチェックし validMoves したがって、キングにまだ生き残るチャンスがあるかどうかを確認するには、 これを行うには、キングの動きと他の動きをループするだけです。 彼の可能な手のいずれかが別の一連の動きに含まれていないかを確認する必要があります。   https://gist.github.com/NicolaM94/9bdb64c10e2d039905e6353ed37cc101?embedable=true#file-checkmate-py つまり、私たちの王にはまだ生き残る希望があるのです！彼にとっては幸運だったと思います… 時間計算量 いつものように、このソリューションの時間計算量を簡単に説明します。 まず、各部分は であるため、そのインスタンスを初期化する時間を考慮する必要があります。 クラス のインスタンス のような駒は内部にループがなく、変数の次元に依存しないため、O(1) とみなすことができます。 ポーンやナイト この は少し注意が必要です。タワーには 4 つの for ループが含まれているため、その時間計算量は O(n) であるとすぐに考えることができますよね。実際、タワーがどのように動くかを考えてみると、 わかります。また、ボードは正方形であるため、タワーを移動するための空きケースが常に 14 個あります。したがって、その時間計算量は実際には O(1) であり、14 組の座標に対して一定である必要があります。以下に図の例を示します。  タワー ボード上のどこにタワーを配置しても、その動きは縦軸と横軸のフリーボードケースに限定されることが 残念ながら、 については同じことが言えません。ビショップの一連の動きはもう少し複雑であるようです。基本的に、ボード上のどこに配置されるかに応じて、7、9、11、または 13 の手があります。したがって、彼の一連の動きを計算するために必要なステップは彼の位置に基づいているため、O(n) の tc を考慮できます。  ビショップ タワーとビショップの一連の動きを組み合わせる必要があります。 ため、ビショップの TC がタワーの TC よりも優先されます。したがって、女王についても O(n) の tc を考慮する必要があります。 クイーンには、 時間計算量を評価する際には最悪のシナリオに焦点を当てる必要がある 最後に、 はハードコードされた一連の動きだけでなく、  。したがって、技術的には、キングの一連の手がどのような場合でも比較的小さい場合でも、ボード上の位置にも応じて、彼の tc を O(n) と見なす必要があります。 キングに for ループを使用する検証プロセスも含まれています この時点で、 。これにより、tc が一定の場合には問題は発生しません (タワーを例に挙げます。14 回の移動を計算し、それから最大 14 回他の移動をループするため、時間も固定であると考えることができます)。それでも、ループを追加しているので、tc が O(n) 以上になると問題が発生します。これは、移動数が増えるにつれてループも大きくなるからです。 ピースごとに for ループを使用して、黒王のチェック ステータスを確認し、出力します 最後に、 。これは、キングの移動数と他の駒の移動に応じて、確実に O(n²) の tc になります。  ダブル (内部) for ループを使用してチェック メイト を検証します それでおしまい;私の解決策があります。いくつかの点が可能な限り効率的ではないことは承知していますが、執筆中は完璧なソリューションを構築するよりもプロセスを説明するというアイデアが好きでした。 あなたはこのことについてどう思いますか？それについてあなたの意見を聞かせてください、そしてコメントであなたの解決策について話し合いましょう！ いつものように、この記事が気に入っていただけましたら、拍手を 1 ～ 2 回残して購読していただくか、可能であればこの種のアルゴリズムに興味がある可能性のある人と共有してください。最後まで読んでいただきありがとうございます。今回は、このソリューションの長さを考えると、いつも以上に長かったです。 いつものように、読んでいただきありがとうございます。

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Walkthroughs, tutorials, guides, and tips. This story will teach you how to do something new or how to do something better.

Read My Stories

このオーディオは、ストーリーの元の言語で制作されています。

長すぎる; 読むには

Make resilience your competitive advantage

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

About Author

コメント

ラベル

この記事は

Related Stories

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

ワークフローを10倍に向上させる方法: 必須アプリ17選

フロキのヴァルハラがインドのスリランカツアーのアソシエイトスポンサーに加わる

Telegram: クリプト島と本土を結ぶ橋

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

ワークフローを10倍に向上させる方法: 必須アプリ17選

フロキのヴァルハラがインドのスリランカツアーのアソシエイトスポンサーに加わる

Telegram: クリプト島と本土を結ぶ橋

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps

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