4440 - 게임 : Knight의 경로 (난이도:고급)
Time Limit: 1s
Memory Limit: 128MB
- Description
Knight's Tour는 고대 퍼즐이다. 목적은 Knigt를 움직여 체스보드에 어떤 위치에서든 출발하여 모든 위치를 향해 가는 것이다. Knight는 오직 L모양으로 움직일 수 만 있다(직진 두번 좌,우 중 한번)
이 문제에서는 시작위치는 0,0으로 고정되어 있다. 우리가 할 일은 서로 다른 map의 시작위치에서 knight tour가 가능한지 확인하는 일이다.
가능하면 True
불가능하면 False
를 출력하시오.
(Game: Knight’s Tour) The Knight’s Tour is an ancient puzzle. The objective is to move a knight, starting from any square on a chessboard, to every other square once, as shown in Figure 18.15a. Note that the knight makes only L-shaped moves (two spaces in one direction and one space in a perpendicular direction). As shown in Figure 18.15b, the knight can move to eight squares. Write a program that displays the moves for the knight, as shown in Figure 18.15c. When you click a cell, the knight is placed at the cell. This cell will be starting point for the knight. Clicking the Solve button to display the path for a solution.
- Input
Line 1 : a b ( a : 행, b : 열 / 판의 크기, 0 < a,b < 10)
- Output
Line 1 : Knight's tour 가능 여부(True, False)
- Sample Input
-
8 8
- Sample Output
-
True
- Hint
(Hint: A brute-force approach for this problem is to move the knight from one square to another available square arbitrarily. Using such an approach, your program will take a long time to finish. A better approach is to employ some heuristics. A knight has two, three, four, six, or eight possible moves, depending on its location. Intuitively, you should attempt to move the knight to the least accessible squares first and leave those more accessible squares open, so there will be a better chance of success at the end of the search.)
- Source
JAVA2015 PE18.32