2 차원 배열 확인 (8 여왕 퍼즐)

StackOverflow https://stackoverflow.com/questions/384874

  •  23-08-2019
  •  | 
  •  

문제

내 문제는 여덟 여왕 퍼즐과 매우 유사합니다.

예를 들어 2 차원 배열 (n x n)이 있습니다.

0,0,0,0,1 y
0,0,0,0,0 |
0,0,0,0,0 V
0,0,0,1,0
0,0,0,0,0
x->

나는 수평, 수직 및 대각선으로 1의 발생을 확인하고 있습니다.

\,0,|,0,/
0,\,|,/,0
-,-,1,-,-
0,/,|,\,0
/,0,|,0,\

목록에 "1"의 (x, y) 위치 만 저장하는 것에 대해 생각하고 있습니다. 

[[4,0],[3,3]]

수학적으로 해결하고 "1"의 모든 위치를 다른 위치 (x1, y1) <--> (x2, y2),

만약에 x1 == x2 또는 y1 == y2 we have a collision! 확인하지 않으면 :

x2 == x1 + z;
y2 == y1 + z;
x2 == x1 - z;
y2 == y1 - z;

(???)

여기서 z는 +/-입니다 ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

내 문제는 대각선 충돌을 확인하는 것입니다. 더 좋은 방법이 있습니까 ???

도움이 되었습니까?

해결책

가능한 한 가지 해결책 :

def collision(x1, y1, x2, y2):
    return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)

즉, 두 지점이 동일한 수평 행, 동일한 수직 행 또는 동일한 대각선 (수직 거리 == 수평 거리)에있는 경우 충돌이 있습니다.

다른 팁

설명은 정확한 표지 문제의 인스턴스처럼 들리며 알고리즘 KNUTH CALL 알고리즘 x. 나는 구현했다 자바 스크립트의 스도쿠 솔버 이 기술을 사용합니다. Python에서도 구현을 찾을 수 있습니다.

수학적으로 해결하지 못하면 먼저 1S, 모든 열 및 마지막으로 모든 대각선 라인에 대해 모든 행을 확인하면 훨씬 빠를 것이라고 생각합니다.

다음은 간단한 방식으로 대각선을 테스트하는 코드입니다. (JavaScript입니다, 죄송합니다!)

var count = 0;
for (column = -n; column < n; column++) {
    for (row = 0; row < n; row++) {
            // conditions for which there are no valid coordinates.
            if (column + row > 6) {
                break;
            }
            if (column < 0) {
                continue;

            if (field[row][column] == 1) {
                count++;
                if (count == 2)
                    break; // collision
            }
    }
}

이 방법은 복잡성을 가질 것입니다 O(n^2), 당신이 제안한 것은 복잡성을 가지고 있습니다. O(n^2 + k^2) (k는 1s의 수) if k 항상 작습니다. 이것은 문제가되지 않아야합니다.

실제로 n 차원 공간이 있다고 가정하면 아마도이 충돌 감지기를 사용할 수 있습니다.

def collision(t1, t2):
    return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2

당신이 좋아하는 아티브와 함께 한 쌍의 튜플을 통과 시키면, 두 지점이 n 차원 대각선에 놓여 있으면 사실이 되돌아 갈 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top