[프로그래밍]희소행렬을 이용한 기사의여행(knight`s tour)

소개글

8×8 체스 판에서 기사의 L-형태의 움직임을 이용하여 임의의 시작점에서 출발하여 각 위치를 오직 한 번만 방문하여 모두 64개의 위치를 방문하는 문제이다. 그리고 마지막에 한번 더 움직여서 처음 위치로 돌아올 필요는 없다.

컴파일 실행환경

비줄얼c++

본문내용

■ 첫 번째 이동
□ 처음 시작점을 입력 받음
□ nexti[l] = i + ktmov1[]을 이용하여 이동
□ 체스판이 범위 내에 있는지 검사해서 맞으면 두 번째 이동을 검사

■ 기사가 이동할 수 있는 위치를 찾음.
□ tempi=nexti[] + ktmov1[]을 이용하여 이동
□ 체스판이 범위내에 있는지 검사해서 맞으면 spos를 증가

■ index값 구하기
□ spos를 exit[]배열에 넣음.
□ min()함수를 이용하여 최소값의 인덱스를 찾음.

■ 체스판에 수를 입력
□ nexti[index]값을 i에 넣어서 체스판에 값을 입력
□ 마지막 남은 0은 64가 들어가야하므로 smarray[].value를 검사해서 64를 넣음.
□ 인덱스를 찾는 함수에서 인덱스를 찾지 못하면 while문을 나옴.
□ smarray[].value를 출력

참고 자료

없음