2073_AL077独立钻石跳棋问题

独立钻石跳棋的棋盘上有33个方格，每个方格中可放1枚棋子。棋盘中最多可摆放32枚棋子。下棋的规则是任一棋子可以沿水平或垂直方向跳过与其相邻的棋子进入空着的方格并吃掉被跳过的棋子。试设计一个算法，对于任意给定的棋盘布局，找出一种下棋方法，使得最终棋盘上只剩下一个棋子。

图1  独立钻石跳棋

对于给定的独立钻石跳棋的棋盘初始布局，和棋盘上最终剩下的棋子所在的位置(x,y)，计算一种遵循下棋的规则下棋方法，使最终棋盘上仅在位置(x,y)处有一枚棋子。当(x,y)=(0,0)时，表示不指定棋子的最终位置。棋子位置的坐标定义如下。

图2  棋子位置的坐标

输入的第一行中有一个正整数n，表示棋盘的初始布局中有n个棋子。

第二行起每行两个数，分别是n个棋子的位置。最后一行是棋盘上最终剩下的棋子所在的位置。

依次输出下棋步法：每行两对方格坐标(a,b)和(c,d)，表示从方格(a,b)跳到方格(c,d)。问题无解时输出 "No solution"

8
4 1
5 2
5 3
6 3
3 4
4 4
4 5
4 6
0 0

(3,4) (5,4)
(4,6) (4,4)
(4,4) (6,4)
(6,4) (6,2)
(6,2) (4,2)
(4,1) (4,3)
(5,3) (3,3)