솔리테어 체스 퍼즐 해결 0, 0, 0], [0,

최근에는 Solitaire Chess 라고 알려진 퍼즐 게임을 소개했습니다 . 여기에 규칙을 요약하겠습니다.

  • 보드는 4×4 바둑판입니다.
  • 모든 조각은 같은 색상 (팀 없음)이며 모든 조각은 다른 조각을 캡처 할 수 있습니다.
  • 모든 움직임은 캡처해야합니다. 빈 사각형으로 이동하지 않습니다.
  • 끝에 정확히 한 조각이 남아 있어야합니다.
  • 모든 조각은 체스에서와 똑같이 움직입니다. 폰은 대각선 방향으로 캡처 할 수 있습니다 (기술적으로 ferz ). 모르는 사람들을 위해 운동 다이어그램을 포함 시켰습니다.
  • 다른 체스 규칙 (예 : 수표, 거세 등)은 여기에 적용되지 않습니다. 캡처에 관한 모든 것입니다.

왕 (K)

K * . . | * K * . | * * * .
* * . . | * * * . | * K * .
. . . . | . . . . | * * * .
. . . . | . . . . | . . . .

여왕 (Q)

Q * * * | * Q * * | * * * .
* * . . | * * * . | * Q * *
* . * . | . * . * | * * * .
* . . * | . * . . | . * . *

루크 (R)

R * * * | * R * * | . * . .
* . . . | . * . . | * R * *
* . . . | . * . . | . * . .
* . . . | . * . . | . * . .

주교 (B)

B . . . | . B . . | * . * .
. * . . | * . * . | . B . .
. . * . | . . . * | * . * .
. . . * | . . . . | . . . *

기사 (N)

N . . . | . N . . | . . . *
. . * . | . . . * | . N . .
. * . . | * . * . | . . . *
. . . . | . . . . | * . * .

폰 (P)

P . . . | . P . . | * . * .
. * . . | * . * . | . P . .
. . . . | . . . . | * . * .
. . . . | . . . . | . . . .

입출력

참고로 Solitaire Chess 웹 페이지의 샘플 퍼즐이 사용됩니다.

. . . .
. B . .
R P . .
. . . N

해결책은 기사와 함께 폰을 가져다가 루크와 함께 기사를 데리고 마침내 루크와 함께 감독을 데려가는 것입니다.

입력

입력은 세 가지 형식 중 하나 여야합니다. 가장 편리한 것을 자유롭게 선택할 수 있습니다.

  • .....B..RP.....N바꿈이 있거나없는 등의 문자열입니다 . 공백을 나타내는 문자는 중 하나가 아닌 문자 일 수 있습니다 KQRBNP.
  • 요소가 문자 또는 숫자 인 목록 (또는 평평한 목록) 목록 : [['.', '.', '.', '.'], ['.', 'B', '.', '.'], ['R', 'P', '.', '.'], ['.', '.', '.', 'N']]또는 [[0, 0, 0, 0], [0, 4, 0, 0], [3, 6, 0, 0], [0, 0, 0, 5]]. 전자의 경우 공백을 나타내는 문자가 아닌 문자 일 수 있습니다 KQRBNP. 후자의 경우, 나는 이전의 움직임 목록에서 순위에 해당하는 숫자를 조각으로주었습니다 ( 1왕, 4주교,6 전당포 등). 번호 매기기를 자유롭게 변경할 수 있습니다.
  • 각 요소의 형식이 다음 [x, y, 'c']과 같은 좌표 목록입니다 [[1, 2, 'B'], [0, 1, 'R'], [1, 1, 'P'], [3, 0, 'N']].

목록 기반 입력 형식 중 하나를 선택하면 구분 기호와 구분 기호는 합리적이고 이해할 수있는 문자 일 수 있습니다.

산출

출력은 일련의 이동 또는 일련의 보드 상태 여야합니다. 일부 퍼즐에는 둘 이상의 솔루션이 있습니다. 당신은 그들 중 하나 또는 전부를 출력 할 수 있습니다. 일련의 보드 상태를 출력하기로 선택한 경우, 각 보드는 적절한 구분 기호 (예 : 개행 문자)와 함께 세 가지 입력 형식 중 하나 여야합니다.

일련의 이동을 출력하도록 선택하면 다음과 같이 좌표 쌍 쌍의 목록으로 표시되어야합니다 [[[3,0], [1,1]], [[0,1], [1,1]], [[1,1], [1,2]]]. [0,0]왼쪽 하단 모서리를 나타내며, 구분 및 구분 문자는 합리적인 선택이 될 수 있습니다.

주어진 보드를 해결할 수없는 경우 잘못된 값 ( 0, 빈 문자열 등)을 출력하십시오 . 주어진 보드의 조각이 2 개 미만이면 동작이 정의되지 않습니다.

테스트 사례

참고 : 출력은 좌표 쌍 목록으로 만 제공됩니다. 다른 형식은 정확성을 확인하기가 매우 쉽기 때문에 가능한 모든 출력 형식을 입력하는 느낌이 들지 않았습니다. 또한 둘 이상의 솔루션이있는 퍼즐의 경우 하나의 가능성 만 제공됩니다.

입력 1 :

. . . N
. . . .
. R . .
. . B .

...N.....R....B.

[['.', '.', '.', 'N'], ['.', '.', '.', '.'], ['.', 'R', '.', '.'], ['.', '.', 'B', '.']]

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

[[3, 3, 'N'], [1, 1, 'R'], [2, 0, 'B']]

출력 1 :

[[[2,0], [1,1]], [[1,1], [3,3]]]

입력 2 :

. . . .
. B . .
R P . .
. . . N

.....B..RP.....N

[['.', '.', '.', '.'], ['.', 'B', '.', '.'], ['R', 'P', '.', '.'], ['.', '.', '.', 'N']]

[[0, 0, 0, 0], [0, 4, 0, 0], [3, 6, 0, 0], [0, 0, 0, 5]]

[[1, 2, 'B'], [0, 1, 'R'], [1, 1, 'P'], [3, 0, 'N']]

출력 2 :

[[[3,0], [1,1]], [[0,1], [1,1]], [[1,1], [1,2]]]

입력 3 :

. N R .
B . . .
N . . B
. . P .

.NR.B...N..B..P.

[['.', 'N', 'R', '.'], ['B', '.', '.', '.'], ['N', '.', '.', 'B'], ['.', '.', 'P', '.']]

[[0, 5, 3, 0], [4, 0, 0, 0], [5, 0, 0, 4], [0, 0, 6, 0]]

[[1, 3, 'N'], [2, 3, 'R'], [0, 2, 'B'], [0, 1, 'N'], [3, 1, 'B'], [2, 0, 'P']]

출력 3 :

[[[2,0], [3,1]], [[0,1], [1,3]], [[0,2], [1,3]], [[2,3], [1,3]], [[3,1], [1,3]]]

입력 4 :

. . . N
. . . R
R B B .
N P P .

...N...RRBB.NPP.

[['.', '.', '.', 'N'], ['.', '.', '.', 'R'], ['R', 'B', 'B', '.'], ['N', 'P', 'P', '.']]

[[0, 0, 0, 5], [0, 0, 0, 3], [3, 4, 4, 0], [5, 6, 6, 0]]

[[3, 3, 'N'], [3, 2, 'R'], [0, 1, 'R'], [1, 1, 'B'], [2, 1, 'B'], [0, 0, 'N'], [1, 0, 'P'], [2, 0, 'P']]

출력 4 :

[[[2,1], [3,2]], [[1,1], [3,3]], [[3,2], [1,0]], [[3,3], [0,0]], [[0,1], [0,0]], [[0,0], [1,0]], [[1,0], [2,0]]]

입력 5 :

P . . .
. R . .
R . R .
. R . .

P....R..R.R..R..

[['P', '.', '.', '.'], ['.', 'R', '.', '.'], ['R', '.', 'R', '.'], ['.', 'R', '.', '.']]

[[6, 0, 0, 0], [0, 3, 0, 0], [3, 0, 3, 0], [0, 3, 0, 0]]

[[0, 3, 'P'], [1, 2, 'R'], [0, 1, 'R'], [2, 1, 'R'], [1, 0, 'R']]

출력 5 :

[[[0,3], [1,2]], [[1,2], [2,1]], [[2,1], [1,0]], [[1,0], [0,1]]]

입력 6 :

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

.P.NK.....B...RQ

[['.', 'P', '.', 'N'], ['K', '.', '.', '.'], ['.', '.', 'B', '.'], ['.', '.', 'R', 'Q']]

[[0, 6, 0, 5], [1, 0, 0, 0], [0, 0, 4, 0], [0, 0, 3, 2]]

[[1, 3, 'P'], [3, 3, 'N'], [0, 2, 'K'], [2, 1, 'B'], [2, 0, 'R'], [3, 0, 'Q']]

출력 6 :

[[[3,0], [2,0]], [[2,0], [2,1]], [[3,3], [2,1]], [[2,1], [1,3]], [[0,2], [1,3]]]


답변

하스켈 226 195 191 188 바이트

모든 솔루션의 목록을 반환합니다. 각 솔루션은 이동 목록입니다. 솔루션이 없으면 빈 목록을 반환합니다.

Lynn 덕분에 4 바이트를 절약했습니다.

온라인으로 사용해보십시오

m"P"=[2]
m"N"=[5]
m"K"=[1,2]
m"R"=[1,4,9]
m"B"=[2,8,18]
m _=m"B"++m"R"
l%x=[z|z<-l,fst z/=x]
f[_]=[[]]
f l=[(i,j):r|(i@(s,t),a)<-l,(j@(u,v),_)<-l,(s-u)^2+(t-v)^2`elem`m a,r<-f$(j,a):l%i%j]

용법:

main = do
    print $ f [((3, 3), "N"), ((1, 1), "R")]
    putStrLn""
    mapM_ print $ f [((3, 3), "N"), ((1, 1), "R"), ((2, 0), "B")]
    putStrLn""
    mapM_ print $ f [((1, 2), "B"), ((0, 1), "R"), ((1, 1), "P"), ((3, 0), "N")]
    putStrLn""
    mapM_ print $ f [((1, 3), "P"), ((3, 3), "N"), ((0, 2), "K"), ((2, 1), "B"), ((2, 0), "R"), ((3, 0), "Q")]

산출:

[]

[((2,0),(1,1)),((1,1),(3,3))]

[((3,0),(1,1)),((0,1),(1,1)),((1,1),(1,2))]

[((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2))]
[((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2))]
[((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2))]
[((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2))]
[((1,3),(0,2)),((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((1,3),(0,2)),((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((1,3),(0,2)),((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((1,3),(0,2)),((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2))]
[((1,3),(0,2)),((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2))]
[((3,3),(2,1)),((2,1),(1,3)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3))]
[((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2))]
[((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3))]
[((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2))]
[((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2))]
[((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2))]
[((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2))]
[((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2))]
[((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2))]
[((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((0,2),(1,3))]
[((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((1,3),(0,2))]
[((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((1,3),(0,2)),((2,0),(0,2))]
[((3,3),(2,1)),((3,0),(2,1)),((1,3),(0,2)),((2,1),(2,0)),((2,0),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((2,1),(1,3))]
[((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2)),((1,3),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(1,3)),((0,2),(1,3))]
[((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2)),((2,1),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((2,1),(1,3)),((2,0),(0,2)),((0,2),(1,3))]
[((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2)),((0,2),(1,3))]
[((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2)),((1,3),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((1,3),(0,2)),((2,0),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2)),((2,1),(0,2))]
[((3,3),(2,1)),((3,0),(2,0)),((1,3),(0,2)),((2,1),(0,2)),((2,0),(0,2))]
[((0,2),(1,3)),((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3))]
[((0,2),(1,3)),((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]
[((0,2),(1,3)),((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]
[((0,2),(1,3)),((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]
[((2,1),(3,0)),((0,2),(1,3)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3))]
[((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3)),((0,2),(1,3))]
[((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((0,2),(1,3)),((3,3),(1,3))]
[((2,1),(3,0)),((2,0),(3,0)),((0,2),(1,3)),((3,0),(3,3)),((3,3),(1,3))]
[((2,0),(2,1)),((1,3),(0,2)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((2,0),(2,1)),((0,2),(1,3)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]
[((2,0),(2,1)),((3,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))]
[((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))]
[((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))]
[((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))]
[((2,0),(2,1)),((3,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))]
[((3,0),(3,3)),((3,3),(1,3)),((1,3),(0,2)),((0,2),(2,0)),((2,0),(2,1))]
[((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((1,3),(3,3))]
[((3,0),(2,1)),((1,3),(0,2)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,1)),((0,2),(1,3)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]
[((3,0),(2,1)),((2,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))]
[((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))]
[((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))]
[((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))]
[((3,0),(2,1)),((2,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))]
[((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))]
[((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))]
[((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))]
[((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))]
[((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))]
[((3,0),(2,0)),((2,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))]
[((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))]
[((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))]
[((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))]
[((3,0),(2,0)),((2,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))]
[((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,0)),((1,3),(0,2)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))]
[((3,0),(2,0)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2))]
[((3,0),(2,0)),((1,3),(0,2)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((2,1),(1,3)),((2,0),(0,2)),((0,2),(1,3))]
[((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2)),((0,2),(1,3))]
[((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2)),((1,3),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2)),((2,0),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((0,2),(1,3)),((2,1),(1,3))]
[((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2)),((1,3),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(1,3)),((0,2),(1,3))]
[((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((1,3),(0,2)),((2,1),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2)),((2,0),(0,2))]
[((3,0),(2,0)),((3,3),(2,1)),((1,3),(0,2)),((2,0),(0,2)),((2,1),(0,2))]
[((3,0),(2,0)),((0,2),(1,3)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]

답변

자바 스크립트 (ES6), 372 361 358 바이트

(여전히) 최적화가 필요합니다. 그러나 여기에 첫 번째 두 번째 세 번째 시도가 있습니다.

b=>{for(n=-4,b=[...b];n<36;b.splice(n+=8,0,0,0,0,0));l=[];(M=(P,u,Z,z,L)=>{for(P=u=n;u--;)
for((z=[640,164928,641,259,899,898]["PNBRQK".indexOf(b[u])])&&P++,L=1,s=z&1;z>>=1;L++)for(Z
=u;z&1&!((Z+=L)&n)&&(b[Z]<'A'||!(M(l.push([b[Z],[u&3,31-u>>3],b[u],[Z&3,31-Z>>3]]),b[Z]=b[u
],b[u]='.'),b[u]=b[Z],b[Z]=l.pop()[0]))&&s||(L=-L,Z=u,L<0););P-37||console.log(l)})()}

출력 형식:

// Puzzle #1
[["B", [2, 0], "R", [1, 1]], ["B", [1, 1], "N", [3, 3]]]

예:

let F =
b=>{for(n=-4,b=[...b];n<36;b.splice(n+=8,0,0,0,0,0));l=[];(M=(P,u,Z,z,L)=>{for(P=u=n;u--;)for((z=[640,164928,641,259,899,898]["PNBRQK".indexOf(b[u])])&&P++,L=1,s=z&1;z>>=1;L++)for(Z=u;z&1&!((Z+=L)&n)&&(b[Z]<'A'||!(M(l.push([b[Z],[u&3,31-u>>3],b[u],[Z&3,31-Z>>3]]),b[Z]=b[u],b[u]='.'),b[u]=b[Z],b[Z]=l.pop()[0]))&&s||(L=-L,Z=u,L<0););P-37||console.log(l)})()}

console.log("Puzzle #1");
F("...N.....R....B.");
console.log("Puzzle #2");
F(".....B..RP.....N");

답변