체스에서 우리는 기사가 특별한 방식으로 점프할 수 있다는 것을 알고 있습니다. 가로 2칸, 세로 1칸 또는 세로 2칸, 가로 1칸을 각 방향으로 움직일 수 있어 완전한 움직임은 영문 'L'과 같습니다.
이 문제에서는 빈 체스 판과 판의 어느 위치에서 시작하는 기사가 있습니다. 우리의 임무는 기사가 판의 모든 사각형을 방문할 수 있는지 여부를 확인하는 것입니다. 모든 사각형을 방문할 수 있을 때 시작 지점에서 해당 위치에 도달하는 데 필요한 점프 수를 배치합니다.
이 문제에는 여러 가지 해결책이 있을 수 있지만 가능한 한 가지 해결책을 찾아보도록 하겠습니다.
입력 및 출력
입력:체스판 크기. 일반적으로 8입니다. (8 x 8은 일반 체스판 크기입니다.) 출력:기사의 움직임입니다. 각 셀에는 시작 위치를 나타내는 숫자가 있으며 기사는 이동하는 셀에 도달합니다. 0 59 38 33 30 17 8 63 37 34 31 60 9 62 29 16 58 1 36 39 32 27 18 7 35 48 41 26 61 10 15 28 2 42 57 52 3 22 13 24 5 51 46 55 44 53 4 21 12
알고리즘
isValid(x, y, 솔루션)
입력 - x와 y와 솔루션 행렬을 배치합니다.
출력 - (x,y)가 제자리에 있고 아직 할당되지 않았는지 확인하십시오.
0 ≤ x ≤ 보드 크기 및 0 ≤ y ≤ 보드 크기이고 (x, y)가 비어 있으면 시작하여 trueEnd를 반환합니다.
knightTour(x, y, 이동, 솔, xMove, yMove)
입력 - (x, y) 위치, 이동 횟수, 솔루션 매트릭스, 가능한 x 및 y 이동 목록.
출력 - 업데이트된 솔루션 매트릭스가 있는 경우
move =Board Size * Board Size이면 시작, //모든 사각형을 방문하면 k에 대해 true를 반환합니다. + yMove[k] isValid(xNext, yNext, sol)가 true이면 sol[xNext, yMext] :=move if KnightTour(xNext, yNext, move+1, sol, xMove, yMove)가 true를 반환하고 그렇지 않으면 제거 sol[xNext, yNext]에서 backtrack으로 이동하여 falseEnd를 반환합니다.
예시
#include#include #define N 8 namespace std;int sol[N][N];bool isValid(int x, int y, int sol[N][N]) { // 확인 장소가 범위 내에 있고 아직 할당되지 않았습니다. return ( x>=0 &&x =0 &&y 출력
<이전> 0 59 38 33 30 17 8 6337 34 31 60 9 62 29 1658 1 36 39 32 27 18 735 48 41 26 61 20 15 2842 4957 13 24 551 46 55 44 53 4 21 12