检查将死 欢迎欢迎提出另一个问题来解决！如果您喜欢下棋和 ：这个适合您！今天我们要帮助国王在战场上多活一天，还要写一大堆代码。 编码 因此，事不宜迟，让我们看看我们的问题。不过，在开始之前，一如既往，有两个免责声明： 这些问题由精彩的时事通讯 Daily Coding Problem 提供，您可以订阅它 ：检查一下并尝试解决您的日常挑战！ 这里 我不是专家程序员，只是一个喜欢分享他的尝试（和失败）的人。如果您有更好的想法或解决方案，我们非常欢迎您分享：我很乐意看到您解决它！ 问题 今天的问题最初是Oracle问的。     的 您将看到一个 8 x 8 矩阵，表示棋盘上棋子的位置。棋盘上唯一的棋子是黑王和各种白棋子。给定这个矩阵，确定国王是否处于检查状态。 有关每个棋子如何移动的详细信息，请参见 这里 . 例如，给定以下矩阵：   ...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..   您应该返回 True ，因为主教正在对角线攻击国王。 问题很清楚，就不多说了。不过，我们只需要一些起始规范： 我们在图表上，而不是在板上： 。结果是一样的； 我们将把问题给出的每个点视为板上案例的中心 白色国王和其他 7 个棋子去度假了：国王和棋子是所有棋子中最无聊的，移除它们不会改变我们的解决方案； 我们需要 ，这意味着如果他不移动，在下一个白色回合将被采取； 验证国王是否在这一回合处于检查状态 ：我不会去验证重叠的棋子或错误的起始位置。 位置最初由游戏给出 解决方案 首先，快速回顾一下棋子和走法：  给定每个棋子的起始位置和他的移动集，我们可以“轻松” 。 计算每个棋子的每个可能的下一步移动 既然他们都对尽快擒王感兴趣，那么我们可以假设 。因此，由于我们也知道黑王的位置，我们 。如果是，在下一个白色回合中，白色棋子将移动到那里以捕获黑色国王。 他们的下一步行动将是擒拿黑王 只需要检查黑王的位置是否是其他棋子可能的下一步之一 情况看起来像这样：  在上面的图片中，您可以看到（……我希望如此，对混淆感到抱歉……）白边上 ，用不同的颜色着色，上面的黑王等待被捕获。因此，例如主教，从 (2,7) 开始，可以移动到 (1,6)、(1,8)、(3,8)、(3,6)、(4,5)、(5, 4）等等。 每块棋子的每一步可能的移动 我只是随机决定了这些棋子的起始位置，因为这不会影响最终结果。 由于我们在一个 8x8 图形上（要清楚，任何其他维度都将以相同的方式工作）并且我们有每个棋子的起始坐标，我们可以构建一系列坐标  ，这将是我们棋子的下一步移动。为此，我们首先 定义它的坐标，然后 x，y 为每个棋子定义一个类， 定义规则来计算从那里开始的每一个可能的移动。 棋子——典当 让我们从简单的 Pawn 开始。顺便说一下，我正在用 构建它，因为它是目前最流行的语言之一，而且可以说是最易读的语言。尽管如此， 。 对这个概念的一个非常简洁的解释。 Python 您仍需要知道从现在开始能够遵循的类是什么 这是   https://gist.github.com/NicolaM94/ae4e0e850250a6974042b0ac72be7585?embedable=true#file-pawn-py 简单说明一下：我们先定义 类，并 它的坐标  。之后，我们定义 方法来计算 pawn 从那里可能的移动。 pawn 移动相对容易，所以我们只需将它们添加到变量 中，在检查它不会移动到我们的网格之外之后，然后返回 数组。这里要注意两件事，特别是对于 pawn： class Pawn __init__ x,y possibleMoves moves moves 我们认为白色棋子从底部移动到顶部，就像我们是白色玩家将我们的棋子向前移动到我们的对手一样。这并没有真正改变任何东西，它只是让事情井井有条。 我们 ，因为我们有兴趣捕获黑王：由于棋子只能沿对角线捕获而我们不关心向其他方向移动棋子，我们可以跳过它的正常移动。 有意跳过正常移动 现在我们可以通过给它的坐标并调用 方法来简单地检查 pawn 的移动，就像这样：  我们应该得到类似  。 possibleMoves print(Pawn(7,2).possibleMoves()) [(6,3),(8,3)] 此外，您可以在顶部看到 ，因此我们可以更改它们以在其他维度的板上运行算法。 我们将网格维度定义为变量 现在让我们继续前进到塔楼。 塔 https://gist.github.com/NicolaM94/7897939bdd7933cb09d8915b7b8bc0b5?embedable=true#file-tower-py 同样，我们用它的坐标初始化 Tower 类并定义函数  。为了在这里收集所有可能的移动 中，该变量将在所有循环后返回。和以前一样，要检查塔的移动，我们可以简单地 我们应该得到这样的东西：   。 possibleMoves ，我们对塔两个轴上的所有点进行了排列，并将每个坐标添加到变量 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  Bishop 的移动比塔更复杂，所以我们可能会解释一下这里发生的事情。基本上 。在声明了类和 init 方法之后，我们创建了两个变量：和以前一样的 和  ，它们将用于跟踪我们在沿其轴移动时收集的点。现在使用 循环，并检查我们是否没有移动到我们的网格之外，我们相应地 和 。例如，如果我们想从它的起始位置向左上移动，我们需要在增加 值的同时减少 值。如果我们想向右下移，我们需要增加 值，同时减少 值，依此类推。最后，我们再次返回  。 我们需要收集从其起始位置开始的两个对角轴上的点 moves currentPos while 增加和减少 x y 到我们想要移动的地方 y x x y 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 种可能走法中的每一种 国王 关于国王的几个简短概念。由于我们不需要移动国王，只是给出他是否过牌， 。但是，我们还将在文章结尾看到一个简短的实现。此外，编码它并不像削弱女王的移动设置那么简单，我们稍后会看到。所以现在，让我们跳过他的动作，看看解决方案。 所以我们真的不需要实施他的移动集 解决方案代码 鉴于我们有每个棋子的可能位置，现在解决方案非常简单：我们只需要检查黑王坐标是否在一个或多个其他棋子的移动集合中。让我们编码吧！   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! 我使用上面的凌乱图像作为参考，所以你可以检查国王是否真的被塔和骑士检查过。 检查队友 如果我们还想计算 ，或者它实际上是 check mate 呢？为此，我们需要计算国王的一组着法。 国王是否还有生存的机会   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 循环来验证将死 就是这样;这是我的解决方案。我很清楚有些点并不是尽可能高效，但在写作时我更喜欢描述过程的想法，而不是构建完美的解决方案。 你怎么看待这件事？给我你的意见，让我们在评论中讨论你的解决方案！ 与往常一样，如果您喜欢这篇文章，请拍一两下并订阅，或者如果可以的话，与可能对此类算法感兴趣的人分享！感谢您阅读到最后，这次比以往任何时候都更能给出这个解决方案的长度！ 一如既往，感谢阅读。

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

該音頻是用故事的原始語言製作的！

日常编码问题：使用您的编码技巧检查将死

About Author

註釋

標籤

这篇文章刊登在

Related Stories

Floki 的 Valhalla 成为印度环斯里兰卡赛事联合赞助商

创建以用户为中心的加密产品：客户反馈的重要性

从论坛到信息流：社交媒体算法如何塑造数字互动

Claude Sonnet 3.5 系统提示泄漏：法医分析

Floki 的 Valhalla 成为印度环斯里兰卡赛事联合赞助商

创建以用户为中心的加密产品：客户反馈的重要性

从论坛到信息流：社交媒体算法如何塑造数字互动

Claude Sonnet 3.5 系统提示泄漏：法医分析

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps