일일 코딩 문제: 코딩 기술을 사용하여 체크메이트를 확인하세요

체크메이트를 확인하세요. 해결해야 할 또 다른 문제에 오신 것을 환영합니다! 체스와 코딩을 좋아한다면 이 앱이 바로 당신을 위한 것입니다! 오늘 우리는 왕이 전장에서 또 다른 하루를 살아남을 수 있도록 돕고, 또한 꽤 많은 코드를 작성할 것입니다.

그럼 더 이상 고민하지 말고 문제를 살펴보겠습니다. 하지만 시작하기 전에 항상 그렇듯이 두 가지 면책 조항이 있습니다.

• 이러한 문제는 구독할 수 있는 멋진 뉴스레터 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 으로 작성하고 있습니다. 왜냐하면 Python은 현재 가장 인기 있는 언어 중 하나이고 틀림없이 누구라도 가장 읽기 쉬운 언어이기 때문입니다. 그래도 앞으로 따라갈 수 있는 수업이 무엇인지 알아야 합니다 . 여기 이 개념에 대한 매우 깔끔한 설명입니다.

간단히 설명하자면, 먼저 class Pawn 클래스를 정의하고 x,y 좌표를 __init__ . 그런 다음, 거기에서 가능한 이동 수를 계산하기 위해 possibleMoves 메서드를 정의합니다. 폰 이동은 상대적으로 쉽기 때문에 그리드 밖으로 이동하지 않는지 확인한 후 이동 moves 에 추가하고 moves 배열을 반환하기만 하면 됩니다. 특히 폰에 대해 여기서 주목해야 할 두 가지 사항은 다음과 같습니다.

1. 우리는 흰색 플레이어가 상대방을 향해 폰을 앞으로 이동시키는 것처럼 흰색 폰이 아래에서 위로 이동한다고 간주합니다. 이것은 실제로 아무것도 바꾸지 않고 단지 상황을 정리하는 것뿐입니다.

2. 우리는 검은 왕을 잡는 데 관심이 있기 때문에 의도적으로 일반적인 움직임을 건너뜁니다 . 폰은 대각선으로만 캡처할 수 있고 조각을 다른 방향으로 움직이는 데 관심이 없기 때문에 정상적인 움직임을 건너뛸 수 있습니다.

   
   

이제 print(Pawn(7,2).possibleMoves()) 와 같이 좌표를 제공하고 possibleMoves 메서드를 호출하여 폰의 움직임을 간단히 확인할 수 있으며 [(6,3),(8,3)] 과 같은 결과를 얻어야 합니다. [(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 늘리거나 줄입니다 . 예를 들어, 시작 위치에서 왼쪽 위로 이동하려면 x 값을 증가시키면서 y 값을 감소시켜야 합니다. 오른쪽으로 아래로 이동하려면 x 값을 늘리고 y 값을 줄여야 합니다. 마지막으로 다시 한 번 moves 반환합니다.

여왕

이제 다음과 같이 생각할 수 있습니다. 타워 이동이 복잡하고 비숍이 훨씬 더 복잡하다면 도대체 여왕을 어떻게 코딩할 것인가? 사실, 퀸 동작은 간단한 트릭을 사용하면 코딩하기 가장 쉽습니다. 그럼 여왕님을 봅시다.

알겠습니다. 여기서 무슨 일이 일어나고 있나요? 뭐, 생각해보면 퀸은 비숍과 타워를 합친 것과 같은 움직임을 가지고 있다 . 그녀는 여왕이라기보다는 탑 모양의 주교 메카봇에 더 가깝습니다. 이런 이유로 그녀의 동작을 코딩하는 것은 정말 간단합니다. 그녀의 클래스를 선언한 후 우리는 그녀의 possibleMoves 비숍과 타워의 가능한 이동으로 인한 이동의 통합 배열 로 정의합니다.

possibleMoves 함수에서 Bishop 및 Tower 인스턴스 클래스를 호출하는 동안 해당 매개변수 x 및 y self.x, self.y 로 제공되므로 실제로는 퀸 좌표입니다.

기사

이제 기사에게!

기사는 나에게 가장 특별합니다. 그의 동작 세트는 "L"자 모양과 같이 이상하기 때문에 특별히 영리하거나 빠른 코딩 방법을 찾지 못했고 결국 시작 위치에서 가능한 8개의 동작을 각각 계산하여 동작을 하드 코딩하게 되었습니다.

왕

왕에 관한 몇 가지 간단한 개념. 우리는 킹을 움직일 필요가 없고 그가 체크되었는지 여부만 알려주기 때문에 실제로 그의 move-set을 구현할 필요는 없습니다 . 그러나 기사 끝부분에서는 간략한 구현도 살펴보겠습니다. 또한 나중에 살펴보겠지만 코딩은 여왕의 이동 세트를 너프하는 것만큼 간단하지 않습니다. 따라서 지금은 그의 움직임을 건너뛰고 해결책을 살펴보겠습니다.

솔루션 코드

각 조각에 대해 가능한 위치가 있다는 점을 고려하면 이제 해결책은 매우 간단합니다. 블랙 킹 좌표가 하나 이상의 다른 조각의 이동 집합에 있는지 확인하면 됩니다. 코딩해보자!

이제 간단히 두 개의 좌표로 변수 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쌍의 좌표에 대해 일정해야 합니다. 다음은 그래픽 예입니다.

• 불행하게도 우리는 Bishop 에 대해서도 같은 말을 할 수 없습니다. 일련의 동작은 좀 더 복잡해 보입니다. 기본적으로 보드의 위치에 따라 7, 9, 11 또는 13개의 동작이 있습니다. 따라서 그의 이동 세트를 계산하는 데 필요한 단계는 그의 위치를 기반으로 하므로 O(n)의 tc를 고려할 수 있습니다.

• 퀸은 타워와 비숍의 움직임이 결합된 세트가 필요합니다. 시간 복잡도를 평가하는 동안 최악의 시나리오에 초점을 맞춰야 하므로 비숍의 TC가 타워의 TC보다 우선합니다. 따라서 우리는 여왕에 대해서도 O(n)의 tc를 고려해야 합니다.

• 마침내 왕은 하드 코딩된 동작 세트를 갖게 되었지만 for 루프를 사용하는 검증 프로세스도 포함되었습니다 . 따라서 기술적으로 킹의 움직임 세트가 상대적으로 작더라도 보드에서의 위치에 따라 그의 tc를 O(n)으로 간주해야 합니다.

  
  

이 시점에서 우리는 각 조각에 대해 for 루프를 사용하여 Black king의 체크 상태를 확인하고 인쇄합니다 . 이는 tc가 일정한 경우 문제가 되지 않습니다(예를 들어 타워를 예로 들자면 14개의 동작을 계산한 다음 최대 14번을 반복하므로 고정 시간으로도 간주할 수 있습니다). 그래도 tc가 O(n) 이상이면 문제가 발생할 것입니다. 이동 횟수가 증가하는 동안 루프도 증가하므로 루프를 추가하기 때문입니다.

마지막으로, 체크 메이트를 확인하기 위해 이중(내부) for 루프를 사용합니다 . 이는 킹의 이동 횟수와 다른 말의 이동에 따라 확실히 O(n²)의 tc가 될 것입니다.

그게 다야; 내 해결책이 있어요. 일부 사항은 최대한 효율적이지 않다는 점을 잘 알고 있지만 글을 쓰는 동안 완벽한 솔루션을 구축하는 것보다 프로세스를 설명하는 아이디어가 마음에 들었습니다.

이것에 대해 어떻게 생각하세요? 이에 대한 여러분의 의견을 알려주시고 댓글로 해결책을 논의해 보세요!

언제나 그렇듯이, 기사가 마음에 드셨다면 한두 번 박수를 남겨주시고 구독해 주시고, 가능하다면 이런 종류의 알고리즘에 관심이 있는 사람과 공유해 주세요! 끝까지 읽어주셔서 감사합니다. 이번에는 이 솔루션의 길이가 생각보다 길어졌습니다!

언제나 그렇듯, 읽어주셔서 감사합니다.