问题描述

这个问题的目标是编写一个程序，该程序将接收1到5个如下所示的拼图块，并在可能的情况下对它们进行排列，以组成一个正方形。这里展示了一组示例拼图块。 （此处应是有拼图块的图示，但文本中未给出具体描述，故保留原文说明）

在尝试从这组拼图块组成正方形时，拼图块不能从其原始方向进行旋转或翻转。必须使用所有的拼图块来组成正方形。对于一组拼图块，可能存在多个可能的解决方案，并且即使对于一组存在解决方案的拼图块，也不是每一种排列方式都能成功组成正方形。使用上述示例拼图块的示例如下所示。 （此处应是有使用示例拼图块组成正方形的图示，但文本中未给出具体描述，故保留原文说明）

输入

此程序的输入文件包含几个需要解决的拼图（即拼图块的集合）。文件的第一行是第一个拼图中拼图块的数量。然后通过列出一行来指定每个拼图块，该行包含两个整数，分别表示拼图块的行数和列数，接着是一行或多行指定拼图块形状的内容。形状说明由$0$和$1$字符组成，其中$1$字符表示拼图的实体形状（$0$字符仅仅是占位符）。例如，上面的拼图块$A$将按如下方式指定：

2 3
111
101

拼图块应按照在拼图中遇到的顺序进行编号。也就是说，一个拼图中的第一个拼图块是第1号拼图块，下一个是第2号拼图块，依此类推。可以假定所有拼图块都是有效的，并且不大于4行4列。

最后一个拼图块的最后一行后面的那一行包含下一个拼图中拼图块的数量，同样后面接着是该拼图的拼图块，依此类推。当输入文件中表示拼图块数量的位置出现数字$0$时，表示输入文件结束。

输出

如果可能有解决方案，你的程序应该按照下面示例所示的格式报告解决方案。应该创建一个4行4列的正方形，每个拼图块占据其在解决方案中的位置。第1号拼图块的实体部分应该用$1$字符替换，第2号拼图块的实体部分用$2$字符替换，依此类推。每个拼图的解决方案之间应该用一个空行分隔。对于没有可能解决方案的拼图，只需报告 “No solution possible”。

输入数据1

4
2 3
111
101
4 2
01
01
11
01
2 1
1
1
3 2
10
10
11
4
1 4
1111
1 4
1111
1 4
1111
2 3
111
001
5
2 2
11
11
2 3
111
100
3 2
11
01
01
1 3
111
1 1
1
0

输出数据1

1112
1412
3422
3442

No solution possible

1133
1153
2223
2444

来源

美国中西部1995年竞赛