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

检查将死

欢迎欢迎提出另一个问题来解决！如果您喜欢下棋和编码：这个适合您！今天我们要帮助国王在战场上多活一天，还要写一大堆代码。

因此，事不宜迟，让我们看看我们的问题。不过，在开始之前，一如既往，有两个免责声明：

• 这些问题由精彩的时事通讯 Daily Coding Problem 提供，您可以订阅它这里：检查一下并尝试解决您的日常挑战！
• 我不是专家程序员，只是一个喜欢分享他的尝试（和失败）的人。如果您有更好的想法或解决方案，我们非常欢迎您分享：我很乐意看到您解决它！

问题

今天的问题最初是Oracle问的。

您将看到一个8 x 8的矩阵，表示棋盘上棋子的位置。棋盘上唯一的棋子是黑王和各种白棋子。给定这个矩阵，确定国王是否处于检查状态。

有关每个棋子如何移动的详细信息，请参见这里.

例如，给定以下矩阵：

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

您应该返回True ，因为主教正在对角线攻击国王。

问题很清楚，就不多说了。不过，我们只需要一些起始规范：

1. 我们在图表上，而不是在板上：我们将把问题给出的每个点视为板上案例的中心。结果是一样的；
2. 白色国王和其他 7 个棋子去度假了：国王和棋子是所有棋子中最无聊的，移除它们不会改变我们的解决方案；
3. 我们需要验证国王是否在这一回合处于检查状态，这意味着如果他不移动，在下一个白色回合将被采取；
4. 位置最初由游戏给出：我不会去验证重叠的棋子或错误的起始位置。

解决方案

首先，快速回顾一下棋子和走法：

给定每个棋子的起始位置和他的移动集，我们可以“轻松”计算每个棋子的每个可能的下一步移动。

既然他们都对尽快擒王感兴趣，那么我们可以假设他们的下一步行动将是擒拿黑王。因此，由于我们也知道黑王的位置，我们只需要检查黑王的位置是否是其他棋子可能的下一步之一。如果是，在下一个白色回合中，白色棋子将移动到那里以捕获黑色国王。

情况看起来像这样：
在上面的图片中，您可以看到（……我希望如此，对混淆感到抱歉……）白边上每块棋子的每一步可能的移动，用不同的颜色着色，上面的黑王等待被捕获。因此，例如主教，从 (2,7) 开始，可以移动到 (1,6)、(1,8)、(3,8)、(3,6)、(4,5)、(5, 4）等等。

我只是随机决定了这些棋子的起始位置，因为这不会影响最终结果。

由于我们在一个 8x8 图形上（要清楚，任何其他维度都将以相同的方式工作）并且我们有每个棋子的起始坐标，我们可以构建一系列坐标x，y ，这将是我们棋子的下一步移动。为此，我们首先为每个棋子定义一个类，定义它的坐标，然后定义规则来计算从那里开始的每一个可能的移动。

棋子——典当

让我们从简单的 Pawn 开始。顺便说一下，我正在用Python构建它，因为它是目前最流行的语言之一，而且可以说是最易读的语言。尽管如此，您仍需要知道从现在开始能够遵循的类是什么。这是对这个概念的一个非常简洁的解释。

简单说明一下：我们先定义class Pawn类，并__init__它的坐标x,y 。之后，我们定义possibleMoves方法来计算 pawn 从那里可能的移动。 pawn 移动相对容易，所以我们只需将它们添加到变量moves中，在检查它不会移动到我们的网格之外之后，然后返回moves数组。这里要注意两件事，特别是对于 pawn：

1. 我们认为白色棋子从底部移动到顶部，就像我们是白色玩家将我们的棋子向前移动到我们的对手一样。这并没有真正改变任何东西，它只是让事情井井有条。

2. 我们有意跳过正常移动，因为我们有兴趣捕获黑王：由于棋子只能沿对角线捕获而我们不关心向其他方向移动棋子，我们可以跳过它的正常移动。

   
   

现在我们可以通过给它的坐标并调用possibleMoves方法来简单地检查 pawn 的移动，就像这样： print(Pawn(7,2).possibleMoves())我们应该得到类似[(6,3),(8,3)] 。

此外，您可以在顶部看到我们将网格维度定义为变量，因此我们可以更改它们以在其他维度的板上运行算法。

现在让我们继续前进到塔楼。

塔

同样，我们用它的坐标初始化 Tower 类并定义函数possibleMoves 。为了在这里收集所有可能的移动，我们对塔两个轴上的所有点进行了排列，并将每个坐标添加到变量moves中，该变量将在所有循环后返回。和以前一样，要检查塔的移动，我们可以简单地print(Tower(5,3).possibleMoves())我们应该得到这样的东西： [(1,3), (2,3), (3,3), ..., (5,8)] 。

主教

现在轮到主教了。

Bishop 的移动比塔更复杂，所以我们可能会解释一下这里发生的事情。基本上我们需要收集从其起始位置开始的两个对角轴上的点。在声明了类和 init 方法之后，我们创建了两个变量：和以前一样的moves和currentPos ，它们将用于跟踪我们在沿其轴移动时收集的点。现在使用while循环，并检查我们是否没有移动到我们的网格之外，我们相应地增加和减少x和y到我们想要移动的地方。例如，如果我们想从它的起始位置向左上移动，我们需要在增加y值的同时减少x值。如果我们想向右下移，我们需要增加x值，同时减少y值，依此类推。最后，我们再次返回moves 。

皇后

现在你可能会想：如果塔的移动很复杂，象甚至更多，我们到底要如何编写皇后的代码？实际上，皇后的动作是最容易编码的，只需借助一个简单的技巧即可。那就去见女王吧。

好吧，这是怎么回事？好吧，如果我们考虑一下，女王拥有象和塔组合的相同动作。她更像是一个塔形的主教机甲机器人而不是女王。因此，编写她的动作非常简单。在声明她的类之后，我们简单地将她的possibleMoves定义为由主教和塔的可能移动产生的移动联合数组。

请注意，在possibleMoves函数中调用类Bishop和Tower实例时，它们的参数x和y被指定为self.x, self.y ，因此它们实际上是皇后坐标。

骑士

现在到骑士！

骑士对我来说是最特别的。他的走法很奇怪，像“L”形，所以我没有找到一种特别聪明或快速的编码方法，我最终硬编码了它的走法，简单地计算他从起始位置开始的 8 种可能走法中的每一种。

国王

关于国王的几个简短概念。由于我们不需要移动国王，只是给出他是否过牌，所以我们真的不需要实施他的移动集。但是，我们还将在文章结尾看到一个简短的实现。此外，编码它并不像削弱女王的移动设置那么简单，我们稍后会看到。所以现在，让我们跳过他的动作，看看解决方案。

解决方案代码

鉴于我们有每个棋子的可能位置，现在解决方案非常简单：我们只需要检查黑王坐标是否在一个或多个其他棋子的移动集合中。让我们编码吧！

我们现在简单地创建一个变量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 呢？为此，我们需要计算国王的一组着法。

让我们描述一下。首先，我们像以前一样定义类和坐标。之后，我们创建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，具体取决于国王的步数和其他棋子的步数。

就是这样;这是我的解决方案。我很清楚有些点并不是尽可能高效，但在写作时我更喜欢描述过程的想法，而不是构建完美的解决方案。

你怎么看待这件事？给我你的意见，让我们在评论中讨论你的解决方案！

与往常一样，如果您喜欢这篇文章，请拍一两下并订阅，或者如果可以的话，与可能对此类算法感兴趣的人分享！感谢您阅读到最后，这次比以往任何时候都更能给出这个解决方案的长度！

一如既往，感谢阅读。