独立钻石跳棋问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

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

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

Input

输入数据的第一行中有1个正整数n(n≤32),表示棋盘的初始布局中有n个棋子。第2 行起每行2 个数,分别是n个棋子的位置。最后1 行是棋盘上最终剩下的棋子所在的位置。

Output

将计算出的下棋步法依次输出。每行有2 对方格坐标(a,b)和(c,d),表示从方格(a,b)跳到方格(c,d)。问题无解时输出“No solution!”。

Sample Input

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

Sample Output

(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)

Hint

 

Source