/* The 200 hard instances used in the experiments of my thesis
   Format of an instance:
   1st line: index
   2nd line: size, width, optimal length, number of optimal solutions
   3rd & 4th lines: pairs
   5th line: a line break
       
                              Ling Zhao (zhao at cs.ualberta.ca)
                              Feb 16, 2002
*/

Instance 1:
3 3 75 2
110   1     0     
1     0     110     

Instance 2:
3 4 252 1
1101  0110  1     
1     11    110   

Instance 3:
3 4 216 1
1101  01    1     
010   1     101   

Instance 4:
3 4 132 1
1100  11    0     
1     0     110   

Instance 5:
3 4 119 1
1101  1     0     
01    1011  1     

Instance 6:
3 4 112 2
1101  1     0     
1     0     110   

Instance 7:
3 5 240 1
11101  110    1      
0110   1      1011   

Instance 8:
3 5 216 1
11011  110    1      
10110  1      1101   

Instance 9:
3 5 216 1
11101  101    1      
10110  1      1101   

Instance 10:
3 5 216 2
11011  011    1      
10110  1      1101   

Instance 11:
3 5 216 1
11011  0110   0      
01100  0      011    

Instance 12:
3 5 190 4
11011  0110   1      
1      11     110    

Instance 13:
3 5 189 1
11111  01011  1      
10     11     10101  

Instance 14:
3 5 182 1
11101  110    1      
1      1011   01101  

Instance 15:
3 5 168 1
11100  0000   0      
00     1      00111  

Instance 16:
3 5 156 1
11010  1      0      
1      0101   11     

Instance 17:
3 5 144 2
11010  1      0      
1      10     11010  

Instance 18:
3 5 120 1
11011  110    1      
0110   1      11011  

Instance 19:
3 5 119 1
11101  10     1      
101    1      11011  

Instance 20:
3 5 119 1
11101  110    1      
1      11011  10     

Instance 21:
3 5 119 1
11001  00     1      
001    1      10011  

Instance 22:
3 5 115 1
11111  1100   1      
0      11     0011   

Instance 23:
3 5 112 1
11111  01111  1      
11110  11     10111  

Instance 24:
3 5 112 2
11101  10     1      
1      1110   10     

Instance 25:
3 5 112 2
11011  10     1      
1      1011   10     

Instance 26:
3 5 112 2
11001  00     1      
1      1100   00     

Instance 27:
3 5 110 1
11101  101    1      
0110   1      11011  

Instance 28:
4 3 302 1
111  011  10   0    
110  1    100  11   

Instance 29:
4 3 273 1
110  100  1    0    
011  1    00   110  

Instance 30:
4 3 240 1
111  10   00   1    
1    100  1    011  

Instance 31:
4 3 217 1
110  100  1    0    
001  1    10   110  

Instance 32:
4 3 204 1
111  10   00   1    
1    110  1    000  

Instance 33:
4 3 192 1
111  101  00   1    
0    1    11   100  

Instance 34:
4 3 183 1
110  101  1    0    
0    11   100  01   

Instance 35:
4 3 170 1
110  01   00   1    
10   00   1    110  

Instance 36:
4 3 168 1
110  10   1    0    
01   0    100  11   

Instance 37:
4 3 160 1
110  101  1    0    
00   1    100  10   

Instance 38:
4 3 160 1
110  011  00   1    
00   1    1    100  

Instance 39:
4 3 155 1
111  110  011  0    
110  000  1    011  

Instance 40:
4 3 155 1
111  101  10   0    
0    1    010  110  

Instance 41:
4 3 155 2
110  101  100  1    
11   0    10   011  

Instance 42:
4 3 155 1
110  101  1    0    
0    00   101  11   

Instance 43:
4 3 154 1
110  010  1    0    
10   1    00   001  

Instance 44:
4 3 154 1
110  101  1    0    
0    11   00   01   

Instance 45:
4 3 150 1
111  111  10   0    
010  1    100  111  

Instance 46:
4 3 149 1
111  100  01   0    
00   1    00   100  

Instance 47:
4 3 149 1
110  010  1    0    
01   0    100  110  

Instance 48:
4 3 146 1
111  010  10   1    
11   11   011  101  

Instance 49:
4 3 146 1
110  11   01   0    
1    10   101  010  

Instance 50:
4 3 144 1
111  100  01   1    
1    11   001  110  

Instance 51:
4 3 144 1
110  100  01   1    
10   11   0    011  

Instance 52:
4 3 142 1
111  110  010  1    
1    01   1    011  

Instance 53:
4 3 140 1
111  100  10   0    
010  1    0    001  

Instance 54:
4 3 140 1
111  100  01   0    
0    11   0    010  

Instance 55:
4 3 140 1
110  10   01   0    
10   11   0    100  

Instance 56:
4 3 138 1
110  100  1    0    
10   0    00   011  

Instance 57:
4 3 138 1
110  101  1    0    
01   1    00   110  

Instance 58:
4 3 136 1
110  101  10   0    
010  1    100  01   

Instance 59:
4 3 136 2
110  100  01   1    
001  0    1    101  

Instance 60:
4 3 134 1
111  001  1    0    
10   0    01   11   

Instance 61:
4 3 134 1
110  1    1    0    
0    101  00   11   

Instance 62:
4 3 132 1
111  110  001  11   
100  1    01   111  

Instance 63:
4 3 132 1
110  100  1    0    
01   1    00   110  

Instance 64:
4 3 132 1
101  11   01   0    
1    10   00   01   

Instance 65:
4 3 131 1
111  10   0    0    
0    1    100  011  

Instance 66:
4 3 131 1
110  001  1    0    
10   0    01   11   

Instance 67:
4 3 126 1
111  101  1    0    
10   1    100  1    

Instance 68:
4 3 124 1
110  101  11   0    
010  1    011  11   

Instance 69:
4 3 120 1
111  01   00   0    
10   1    010  000  

Instance 70:
4 3 120 1
110  001  11   0    
100  1    0    011  

Instance 71:
4 3 120 1
110  010  1    0    
00   0    011  10   

Instance 72:
4 3 119 1
111  110  0    0    
00   0    001  11   

Instance 73:
4 3 119 1
110  011  01   0    
01   0    1    100  

Instance 74:
4 3 118 1
110  001  11   1    
11   1    0    101  

Instance 75:
4 3 117 1
110  011  00   1    
10   0    11   011  

Instance 76:
4 3 114 1
111  101  1    0    
1    11   100  01   

Instance 77:
4 3 112 1
111  011  001  1    
110  1    111  100  

Instance 78:
4 3 110 1
111  101  11   0    
100  1    011  11   

Instance 79:
4 3 110 1
111  110  1    0    
000  1    01   110  

Instance 80:
4 3 110 3
110  001  01   1    
010  0    1    101  

Instance 81:
4 3 110 2
110  10   1    0    
1    010  01   110  

Instance 82:
4 3 108 1
111  101  1    0    
0    1    00   10   

Instance 83:
4 3 108 2
110  011  1    0    
10   1    001  011  

Instance 84:
4 3 108 1
110  010  1    0    
10   0    0    110  

Instance 85:
4 3 108 1
110  11   11   0    
1    01   00   110  

Instance 86:
4 3 107 1
111  100  10   1    
1    11   110  01   

Instance 87:
4 3 106 2
111  110  101  1    
010  01   1    111  

Instance 88:
4 3 105 1
111  101  1    0    
10   1    00   01   

Instance 89:
4 3 105 1
110  001  01   1    
1    1    0    110  

Instance 90:
4 3 105 1
110  001  1    0    
1    1    001  01   

Instance 91:
4 3 104 1
111  000  1    0    
000  0    10   11   

Instance 92:
4 3 104 2
111  10   01   0    
0    010  1    001  

Instance 93:
4 3 104 1
110  100  1    0    
001  1    00   110  

Instance 94:
4 3 104 1
110  001  1    0    
10   1    00   011  

Instance 95:
4 3 103 2
110  001  00   1    
01   0    11   001  

Instance 96:
4 3 102 1
111  011  10   1    
100  1    110  111  

Instance 97:
4 3 102 1
111  110  011  1    
10   11   01   011  

Instance 98:
4 3 102 1
110  11   1    0    
1    101  100  110  

Instance 99:
4 3 100 1
110  11   11   0    
1    101  00   110  

Instance 100:
4 4 256 1
1101  001   1     0     
11    0101  0     10    

Instance 101:
4 4 206 1
1110  11    01    0     
1     011   1     010   

Instance 102:
4 4 200 1
1111  1101  10    1     
010   1     011   0101  

Instance 103:
4 4 198 1
1101  0110  11    0     
1     0     100   110   

Instance 104:
4 4 193 2
1110  10    10    1     
0     111   01    1101  

Instance 105:
4 4 192 3
1111  10    01    1     
10    11    0     0101  

Instance 106:
4 4 189 1
1110  1011  1010  1     
011   0101  1     1101  

Instance 107:
4 4 182 1
1110  100   1     0     
10    00    1000  1     

Instance 108:
4 4 178 1
1110  0001  10    1     
0     1     1     011   

Instance 109:
4 4 178 1
1111  101   010   1     
1101  1     1011  10    

Instance 110:
4 4 168 1
1111  101   010   1     
110   1     1011  10    

Instance 111:
4 4 168 1
1101  111   0     0     
1     0     100   11    

Instance 112:
4 4 164 1
1111  011   10    1     
1010  0     1     0101  

Instance 113:
4 4 162 1
1111  0011  01    1     
100   0     1     1010  

Instance 114:
4 4 162 1
1110  11    01    0     
1     0     11    100   

Instance 115:
4 4 159 1
1100  100   10    1     
1     111   0     011   

Instance 116:
4 4 156 1
1100  1     1     0     
1     0101  001   11    

Instance 117:
4 4 152 1
1110  1010  01    1     
0     1     0     1101  

Instance 118:
4 4 152 1
1111  100   0     0     
10    0     0100  11    

Instance 119:
4 4 150 1
1100  010   1     0     
1     1     0     110   

Instance 120:
4 4 145 1
1101  11    1     0     
1     110   1100  111   

Instance 121:
4 4 144 2
1100  1010  11    0     
1     0     0     011   

Instance 122:
4 4 144 1
1101  10    1     0     
01    0110  1001  1     

Instance 123:
4 4 144 1
1110  1011  11    0     
0     0     1101  1     

Instance 124:
4 4 142 1
1110  111   1     0     
1     1011  00    1110  

Instance 125:
4 4 140 1
1111  1110  1     0     
110   11    10    1110  

Instance 126:
4 4 138 1
1100  0101  1     0     
10    1     00    01    

Instance 127:
4 4 138 1
1110  000   11    1     
11    1     0     1101  

Instance 128:
4 4 136 1
1111  110   1     0     
10    11    0     1110  

Instance 129:
4 4 136 1
1111  011   10    1     
1110  0     1     0101  

Instance 130:
4 4 134 1
1100  101   010   0     
1     0     1     1010  

Instance 131:
4 4 134 1
1110  100   01    1     
0     1     0     110   

Instance 132:
4 4 133 1
1110  10    1     0     
10    11    0     0101  

Instance 133:
4 4 133 1
1110  010   00    0     
01    0     1110  0010  

Instance 134:
4 4 133 1
1110  110   01    1     
1     0     11    10    

Instance 135:
4 4 132 1
1111  1100  1     0     
0     0     100   1     

Instance 136:
4 4 132 1
1110  010   1     0     
0100  0     0111  10    

Instance 137:
4 4 132 1
1110  101   010   0     
1     0     1     1010  

Instance 138:
4 4 129 1
1111  1100  11    0     
00    1     0     110   

Instance 139:
4 4 129 1
1110  100   1     0     
01    1     00    1100  

Instance 140:
4 4 128 1
1111  011   10    1     
110   0     1     0101  

Instance 141:
4 4 128 1
1110  1001  01    0     
0     1     0     001   

Instance 142:
4 4 126 1
1111  101   10    0     
10    1     000   01    

Instance 143:
4 4 126 1
1110  000   01    1     
00    1     1     1110  

Instance 144:
4 4 126 1
1101  11    00    0     
11    0     1     0110  

Instance 145:
4 4 126 1
1101  110   1     0     
00    1     0011  01    

Instance 146:
4 4 125 1
1100  111   1     0     
1     0101  001   11    

Instance 147:
4 4 124 1
1110  11    10    0     
1     1010  0     011   

Instance 148:
4 4 121 1
1100  11    1     0     
1     0101  001   11    

Instance 149:
4 4 120 1
1111  1101  10    1     
101   1     011   0101  

Instance 150:
4 4 120 1
1101  0011  001   1     
00    11    0     1001  

Instance 151:
4 4 120 1
1001  1001  01    0     
10    1     0     001   

Instance 152:
4 4 120 1
1110  1011  1     0     
11    01    10    110   

Instance 153:
4 4 120 1
1110  0110  01    1     
00    0     1     011   

Instance 154:
4 4 120 1
1110  01    1     0     
00    1     1100  01    

Instance 155:
4 4 120 1
1100  001   10    1     
1     110   0     011   

Instance 156:
4 4 120 1
1110  1010  1     0     
0     1     00    10    

Instance 157:
4 4 119 1
1111  0111  1     0     
10    0     01    11    

Instance 158:
4 4 118 1
1001  11    10    0     
1     0     0     100   

Instance 159:
4 4 118 1
1110  101   1     0     
0     1     100   1     

Instance 160:
4 4 118 1
1101  01    1     0     
1     00    110   1011  

Instance 161:
4 4 118 1
1110  1001  1     0     
10    1     10    01    

Instance 162:
4 4 117 1
1101  0011  000   0     
0     00    1     0110  

Instance 163:
4 4 116 1
1001  01    00    1     
10    0     101   1001  

Instance 164:
4 4 116 1
1101  0011  001   1     
001   11    0     1001  

Instance 165:
4 4 116 1
1100  1010  1     0     
1     0     10    11    

Instance 166:
4 4 115 2
1110  01    1     0     
0     111   001   01    

Instance 167:
4 4 115 1
1111  001   10    0     
1010  1     0     001   

Instance 168:
4 4 114 1
1101  011   10    0     
1     000   0     110   

Instance 169:
4 4 114 1
1111  10    01    0     
0     0100  1     01    

Instance 170:
4 4 113 1
1101  010   1     0     
01    100   1011  1     

Instance 171:
4 4 112 1
1101  110   1     0     
1001  1     0011  01    

Instance 172:
4 4 112 1
1101  100   01    0     
0101  1     0     100   

Instance 173:
4 4 112 1
1110  1100  1     0     
0     1     10    11    

Instance 174:
4 4 112 1
1100  01    1     0     
1010  1     0     0011  

Instance 175:
4 4 112 3
1111  0100  1     0     
110   0     100   1     

Instance 176:
4 4 111 1
1110  1001  1     0     
00    1     01    10    

Instance 177:
4 4 110 1
1101  0101  1     0     
01    000   1011  1     

Instance 178:
4 4 110 1
1101  001   01    1     
0     0101  1     1010  

Instance 179:
4 4 109 1
1100  1001  010   0     
1     00    1     100   

Instance 180:
4 4 109 1
1110  0101  1     0     
111   1     10    011   

Instance 181:
4 4 109 1
1111  01    1     0     
100   0     0001  1     

Instance 182:
4 4 109 1
1100  01    1     0     
11    001   0     10    

Instance 183:
4 4 108 1
1101  11    1     0     
1     0101  0     110   

Instance 184:
4 4 108 1
1100  1010  00    1     
1     001   11    0101  

Instance 185:
4 4 107 1
1101  110   1     0     
1     010   110   1011  

Instance 186:
4 4 107 1
1101  1010  1     0     
01    1     00    10    

Instance 187:
4 4 107 1
1110  1101  1     0     
0100  01    1011  1     

Instance 188:
4 4 105 1
1110  1010  1     0     
0     101   001   1     

Instance 189:
4 4 105 1
1110  1010  1     0     
0     10    01    1     

Instance 190:
4 4 104 1
1110  001   01    0     
1     111   0     100   

Instance 191:
4 4 104 1
1111  1101  10    1     
0     1     011   0101  

Instance 192:
4 4 104 1
1110  001   1     0     
10    1     00    0011  

Instance 193:
4 4 103 1
1110  11    10    01    
1     1011  011   1     

Instance 194:
4 4 103 1
1111  1011  01    1     
10    1     110   1010  

Instance 195:
4 4 103 1
1101  0101  1     0     
1     01    00    10    

Instance 196:
4 4 102 1
1111  01    1     0     
100   0     0011  1     

Instance 197:
4 4 102 1
1110  1011  01    1     
010   1     110   1010  

Instance 198:
4 4 100 1
1110  11    1     0     
0     0010  110   1     

Instance 199:
4 4 100 1
1111  01    1     0     
1010  0     0001  1     

Instance 200:
4 4 100 1
1101  00    1     0     
110   1     0     100