Missing Piece 2001

Time limit1sMemory limit128 MB

Summary

Decide whether a sliding-tile board reaches a target layout within N moves and report the smallest such move count.

Level: Medium7 of 10
Topics: Backtracking, BFS, Graph
Solved: No attempts yet

Problem

Wiltin' Badley rebuilt the old sliding number puzzle and sells it as Missing Piece 2001. The box comes with a program that tells the player up front how hard a given puzzle is. The player types in the starting layout and the layout to reach, and the program decides whether the puzzle can be solved within a chosen number of moves. When it can, the program also reports the smallest number of moves that reaches the target layout. You have to write that program.

The user supplies the board size, the number of moves to solve within, the starting layout, and the target layout. Boards of other sizes are sold separately, so the program has to handle any size.

One move takes a piece that touches the missing piece X above, below, left, or right of it and slides that piece into the empty square. A piece that does not touch the missing piece cannot move, and the only directions of movement are up, down, left, and right.

Input

The input holds up to 10 data sets and always holds at least one. No blank line separates one data set from the next.

Each data set has four parts.

Start line: a single line START D N, where $3 \le D \le 10$ and $0 \le N \le 15$ .
Initial board layout: a $D \times D$ matrix of the integers from 1 to $D^2 - 1$ together with an X for the missing piece. This is the board before the solving attempt.
Solved board layout: a $D \times D$ matrix in the same format, giving the board that counts as solved.
End line: a single line END

$D$ is the side length of the board and $N$ is the number of moves the player wants to solve the puzzle within. Both layouts hold every number from 1 to $D^2 - 1$ exactly once and exactly one X, with no number missing and none repeated.

Output

Print one line per data set, with a single blank line between consecutive output sets.

If the target layout can be reached within the given number of moves, the answer string is SOLVABLE and the number after it is the smallest number of moves that reaches the target layout. Otherwise the answer string is NOT SOLVABLE and the number after it is the input value $N$ , echoed back.

Each line has this format.

<Answer String> WITHIN <Number Moves> MOVES

WITHIN and MOVES are printed literally, and the word MOVES is used even when the count is 1.

Examples1

Example 1

Input

START 3 4
1 5 2
4 X 3
7 8 6
1 2 3
4 5 6
7 8 X
END
START 3 3
1 2 3 
7 X 8
6 5 4
1 2 3 
8 X 4
7 6 5
END
START 4 10
1 X 2 4
5 6 3 7
9 10 11 8
12 13 14 15
1 2 3 4
5 6 7 8
9 10 X 11
12 13 14 15
END

Expected output

SOLVABLE WITHIN 4 MOVES

NOT SOLVABLE WITHIN 3 MOVES

SOLVABLE WITHIN 5 MOVES