Sudoku Puzzle Solver with Dual Display

1
2//#define Test_Only                                   // define to   truncate test/demo list
3
4  
5/*
6 * Puzzles are loaded into both the puzzle   grid and the solution grid
7 * Entries of numbers 1-9 are loaded into initial   puzzle grid and solution grid
8 * Entries of numbers 11-19 are loaded ONLY into   the solution grid (used to check puzzle algorithms)
9 * Remember to true up Puzzles   Number total to match
10 * Each puzzle is one-dimensional (0-80) and loaded into   each row and column by Test_Transfer routine
11 * PROGMEM is used to conserve global   variable space (non-program-storage space)
12 * Some basic information on solving   techiques is included as a comment after the puzzle definitions
13 */
14 
15
16const   byte Easy  [81 ] PROGMEM =                         // easy  - solvable    *****
17{    3,12,17,19,4,11,8,15,16,
18    16,5,4,7,12,8,9,13,11,
19    1,8,19,15,16,3,7,14,2,
20     12,1,16,18,19,14,5,7,3,
21    17,14,5,11,13,16,2,18,19,
22    9,3,8,12,15,17,11,6,14,
23     4,19,1,6,18,15,13,2,7,
24    18,16,2,3,17,9,4,1,15,
25    15,17,3,14,1,12,16,19,8};        
26
27const byte HR_1  [81 ] PROGMEM =                         // test   hidden rectangle and has a WXYZ wing clear too
28{   3,9,4,6,8,2,1,5,7,
29    6,1,8,7,3,5,4,2,9,
30     5,2,7,4,19,11,3,6,8,
31    1,5,3,19,4,7,12,18,6,
32    4,7,12,5,6,8,19,3,1,
33    8,6,19,11,12,13,7,4,5,
34   7,3,6,8,11,4,15,19,2,
35    9,4,5,12,17,16,18,11,3,
36     2,8,1,13,15,19,16,17,4};       
37
38const byte HR_2  [81 ] PROGMEM =                         //   test hidden rectangle also
39{   16,9,11,4,5,13,2,18,17,
40    3,15,2,7,8,11,16,9,14,
41    7,14,18,2,9,16,15,1,13,
42    9,3,5,1,2,8,7,4,6,
43   18,7,14,6,13,9,11,12,15,
44    12,11,16,5,14,7,18,13,9,
45   1,2,9,3,7,5,4,6,8,
46    5,6,3,8,1,4,9,17,12,
47    4,8,7,9,6,2,3,5,1};   
48
49const byte WXYZ  [81 ] PROGMEM =                         //   WXYZ Wing test
50{   7,1,19,18,4,13,15,12,16,
51   5,6,14,2,11,7,18,3,19,
52     8,2,13,16,15,9,7,14,11,
53    6,5,7,4,13,11,2,9,18,
54   2,14,8,19,6,15,3,11,7,
55    19,3,1,7,18,2,14,6,15,
56   14,19,6,3,7,18,11,15,12,
57   11,7,2,5,19,4,6,8,3,
58     3,18,5,11,2,6,19,7,4};      
59
60const byte Forbidding_1  [81 ] PROGMEM =                          // test forbidding chain with group node 
61{   12,6,18,15,1,3,7,14,9,
62   5,4,11,19,17,8,13,6,2,
63   13,7,9,6,2,14,8,15,11,
64   11,8,13,2,4,15,9,7,16,
65   17,19,4,11,13,16,5,2,8,
66   16,2,15,17,8,9,14,1,13,
67   18,13,17,14,16,2,11,9,5,
68   4,5,12,13,19,11,16,8,7,
69    19,11,6,8,5,17,12,3,14};      
70/*
71const byte   Forbidding_2  [81 ] PROGMEM =                         // test forbidding chain with   group node  (not loaded now)
72{  17,5,2,4,3,1,9,6,18,
73  18,3,6,17,19,12,14,1,5,
74    1,9,14,18,16,15,13,2,17,
75  2,11,17,13,14,19,15,18,6,
76  9,4,18,16,15,17,12,13,11,
77    5,6,13,11,12,18,7,4,9,
78  3,17,9,12,18,16,11,15,14,
79  6,12,5,19,1,14,18,17,13,
80    14,8,11,5,17,13,6,9,12};      
81*/
82
83const byte XC1  [81 ] PROGMEM =                         //     Tests of X Chain
84{   2,7,11,18,6,13,5,4,19,
85    19,5,14,1,2,7,13,8,16,
86    13,16,18,4,15,19,2,7,11,
87    18,11,19,13,4,6,7,5,2,
88   16,2,7,5,19,8,4,1,13,
89     5,14,13,7,1,2,9,16,8,
90   1,3,6,2,7,4,8,9,5,
91    7,8,5,19,13,1,16,2,4,
92     14,19,2,16,18,15,1,13,7};    
93
94const byte XC2  [81 ] PROGMEM =                         //     Tests of X Chain
95{   3,17,4,5,2,11,19,8,16,
96   11,18,6,14,9,13,15,17,12,
97    19,5,12,18,7,16,3,11,14,
98    15,14,17,6,8,9,11,2,3,
99  12,19,11,7,3,4,16,15,18,
100    18,6,3,1,5,2,7,14,19,
101   14,1,15,9,6,18,12,13,17,
102   17,12,9,13,4,15,18,6,11,
103     6,13,8,2,1,7,14,19,5}; 
104
105const byte XC3  [ 81] PROGMEM =                         //     Tests of X Chain
106{   12,14,16,3,5,1,7,8,19,
107   8,5,7,6,2,9,3,4,1,
108    1,19,13,8,7,4,16,15,2,
109    5,13,9,1,6,2,8,17,4,
110  6,8,1,15,4,17,2,19,13,
111     14,17,12,19,13,8,1,6,15,
112   7,1,8,14,19,13,15,2,16,
113    19,12,15,17,1,16,14,13,8,
114     13,6,14,12,8,15,19,1,7};    
115
116const byte UR_3a  [81 ] PROGMEM =                         //   check UR3
117{   9,12,4,15,7,16,18,1,13,
118    1,3,7,12,18,9,6,14,15,
119    6,15,8,14,13,1,12,9,7,
120     5,1,9,17,12,13,4,6,8,
121   2,7,3,16,14,18,1,5,9,
122   4,8,6,9,1,5,7,3,2,
123     17,16,2,13,5,14,19,18,1,
124    13,19,1,8,16,12,15,17,14,
125    18,4,5,1,9,17,13,2,6};       
126
127const byte Medium_1[81 ]PROGMEM =                        // medium   - solvable  
128{   19,1,16,2,13,5,17,14,8,
129    17,2,4,9,8,16,11,13,5,
130    13,5,8,7,14,1,19,2,16,    
131    6,19,5,3,17,2,14,8,1,
132    2,18,7,1,16,14,3,15,9,
133    14,13,1,5,19,8,2,6,17,
134     11,14,2,6,15,7,8,19,13,
135    8,16,13,14,1,19,5,17,2,
136    15,17,9,18,2,3,16,1,14};
137
138const   byte Medium_2 [81 ]PROGMEM =                        // medium 2
139{   13,19,15,16,4,7,12,1,18,
140     17,2,18,5,11,13,19,14,6,
141    14,16,11,9,12,18,17,13,5,   
142    12,15,3,11,19,14,18,6,17,
143     19,17,4,8,16,12,11,15,13,
144    11,18,6,13,17,15,4,9,2,
145    16,4,12,17,3,19,15,18,11,
146     8,11,19,12,15,6,13,7,14,
147    5,13,17,4,18,1,16,12,19};
148
149const byte   Difficult_1 [81 ]PROGMEM =                        // difficult
150{   18,17,13,5,4,1,16,19,12,
151     14,15,6,12,7,19,11,13,8,
152    12,9,11,16,13,8,15,17,14,   
153    5,6,18,14,2,13,19,1,17,
154     17,11,2,19,15,16,4,18,13,
155    13,14,19,11,18,7,12,16,15,
156    11,8,14,3,16,5,17,12,9,
157     19,12,17,18,1,14,13,15,6,
158    16,3,5,17,19,12,18,14,11};
159
160const byte   UR [81 ]PROGMEM =                        // Invokes Unique Rectangle 1
161{   16,18,15,1,13,12,14,7,19,
162     7,3,14,15,9,18,11,16,12,
163    2,11,19,17,6,4,15,3,18,   
164    19,12,6,18,17,1,13,4,15,
165     18,15,1,3,14,19,17,2,6,
166    14,17,13,2,15,16,8,19,11,
167    15,6,8,4,12,17,9,11,13,
168     3,14,12,9,11,15,16,18,17,
169    1,19,17,16,18,13,12,15,14};     
170
171const   byte UR2V [81 ]PROGMEM =                        // Invokes Unique Rectangle 2, 2nd   one
172{   11,7,9,13,14,12,15,18,6,                          // Vertical x.x
173    3,18,5,6,19,1,4,17,12,                             //          ...
174    6,14,12,18,15,17,13,11,19,                         // Box      x.x                 
175    5,6,4,17,13,8,19,2,11,
176     2,9,8,5,1,4,6,3,7,
177    7,1,3,2,16,19,8,5,4,
178    14,13,17,19,12,15,11,6,8,
179     8,5,11,4,17,16,2,19,3,
180    19,12,6,11,18,13,17,4,15};  
181
182
183const   byte UR2H [81 ]PROGMEM =                        // Invokes Unique Rectangle 2
184{    4,6,9,5,18,13,2,7,1,                              // Horizontal x.........x
185     1,8,5,7,6,2,4,3,9,                                // Box        x.........x
186     7,2,3,9,11,14,8,5,6,
187    6,4,7,8,5,9,3,1,2,
188    3,1,8,4,2,7,6,9,5,
189     9,5,2,11,13,6,7,8,4,
190    12,17,4,13,9,11,5,6,18,
191    18,13,1,6,14,5,9,12,17,
192     5,9,6,12,7,18,1,14,13};   
193
194
195const byte UR5  [81 ] PROGMEM =                         //   test case for UR type 5
196{   13,9,11,8,14,16,2,5,17,
197    8,17,15,2,19,13,16,1,14,
198    14,6,12,7,11,15,13,8,19,
199    9,8,4,5,2,1,7,6,3,
200    7,2,6,4,3,8,5,9,1,
201     5,1,3,19,16,7,4,2,8,
202    12,3,19,16,8,4,1,7,5,
203    1,5,8,3,7,12,19,4,16,
204     16,14,17,1,5,19,8,3,12};
205
206const byte Expert [81 ] PROGMEM =                        
207{    12,19,14,11,16,15,18,13,17,
208    16,11,7,8,3,14,9,15,12,
209    13,18,5,19,17,2,6,4,11,
210     15,13,2,6,18,11,14,7,19,
211    17,4,11,12,15,19,13,8,16,
212    18,6,19,17,14,3,2,11,15,
213     19,2,8,4,11,17,5,16,13,
214    14,17,13,15,9,6,1,12,18,
215    11,15,16,13,12,18,17,19,14};                                   
216
217const byte FC [81 ]PROGMEM =                        //   Requires a forcing chain
218{   4,11,15,2,7,13,6,19,18,
219    7,9,8,1,5,6,2,3,4,
220     16,2,13,8,4,19,15,11,7,
221    2,3,7,4,6,8,9,5,1,
222    8,4,9,5,3,1,7,2,6,
223     5,6,1,7,9,2,8,4,3,
224    13,8,2,16,1,5,4,7,9,
225    11,7,16,19,2,4,3,18,15,
226     19,15,4,13,8,7,11,16,2};
227
228const byte XWing [81 ] PROGMEM =                        //   Test x-wing  and xy-wing algorithms
229{   1,18,17,14,12,13,5,6,9,
230    4,9,2,17,5,6,1,13,8,
231     13,5,6,1,18,9,2,4,17,
232    15,13,9,6,4,17,8,12,1,
233    17,6,4,12,1,18,19,15,13,
234     2,1,8,19,3,5,6,17,4,
235    18,4,13,5,19,12,17,1,6,
236    9,17,5,13,6,1,4,18,2,
237     6,2,1,18,17,14,13,19,5};
238
239const byte Swordfish_1 [81 ] PROGMEM =                        //   Test Swordfish algorithm
240{   1,9,5,3,6,7,2,4,8,                                       
241     12,7,8,11,5,14,3,6,9,
242    3,14,6,12,9,8,1,5,7,
243    16,12,3,7,8,11,5,9,14,
244     7,11,9,14,12,5,18,13,6,
245    5,8,4,9,13,6,7,1,12,
246    8,3,2,5,4,9,6,7,1,
247     9,16,7,18,1,3,14,2,5,
248    14,5,1,16,7,2,9,18,13};
249
250const byte Jellyfish_1   [81 ] PROGMEM =                        //  Test Jellyfish algorithm
251{   14,6,17,3,11,9,12,8,15,                                        
252    11,15,3,17,18,12,6,14,19,
253    2,19,18,14,6,15,17,13,1,
254     16,8,12,1,15,3,14,9,17,
255    19,11,15,18,7,14,13,12,16,
256    13,7,14,2,19,6,11,5,18,
257     7,12,11,19,3,18,15,16,4,
258    15,14,9,16,12,17,8,11,13,
259    18,3,16,5,14,1,19,7,12};
260
261const   byte Diabolical_1 [81 ] PROGMEM =                        //  Uses many algorithms   incl. two forcing chains
262{  1,18,16,13,14,15,12,7,19,                                       
263     19,3,2,18,7,11,14,16,15,
264    5,4,7,16,2,9,18,13,1,
265    17,5,1,19,13,14,16,12,18,
266     3,16,19,2,18,7,15,11,4,
267    14,12,18,15,11,16,3,9,17,
268    2,11,13,4,9,18,7,5,6,
269     16,17,14,11,5,13,9,8,12,
270    18,9,15,17,16,12,11,14,3};
271
272const byte   Diabolical_2  [81 ] PROGMEM =                         // test case for UR type 5,   other goodies, including XYZ Wing
273{  3,14,18,15,11,17,19,6,12,
274   15,6,11,4,12,19,8,7,13,
275    19,17,12,16,3,8,4,15,1,
276   12,8,16,17,4,11,13,9,15,
277   14,5,19,2,8,3,17,1,16,
278    17,1,13,19,5,16,12,4,18,
279   1,12,4,3,7,15,16,18,19,
280    18,9,7,11,16,2,15,3,14,
281     16,3,15,18,19,14,11,12,7};
282
283
284const byte  Diabolical_3 [81 ] PROGMEM   =                        // Was recursive until chains got to it, does show XYZ   Wing too!
285{  18,17,11,5,16,12,14,3,9,                                       
286     16,3,9,18,4,1,2,5,7,
287    14,12,5,17,3,9,6,8,11,
288    15,9,14,3,2,17,11,6,18,
289     12,11,8,9,5,6,7,4,13,
290    17,16,13,14,1,8,9,2,15,
291    19,4,6,1,18,5,3,17,12,
292     13,8,7,12,9,14,5,1,16,
293    11,5,12,16,17,13,18,19,14};
294
295const byte   Diabolical_4  [81 ] PROGMEM =                         // was used to fix UR 5 error   
296{   4,13,8,15,9,16,11,2,17,
297    15,7,6,12,14,11,8,13,19,
298   2,19,11,7,18,3,14,16,15,
299    17,15,9,1,16,12,13,18,4,
300   16,1,14,19,3,18,17,5,12,
301   3,18,12,14,17,5,6,19,11,
302     18,14,15,3,11,9,12,17,6,
303   11,12,3,16,15,17,9,4,18,
304    19,6,17,18,2,14,5,11,3};    
305
306
307const byte Diabolical_5  [81] PROGMEM =                         //Does   have XYZ but still stumped and requires recursive search!
308{  11,5,16,13,14,8,17,19,2,
309     18,19,17,6,12,11,13,15,14,
310  13,4,2,5,9,17,1,18,16,
311  14,11,13,8,17,16,19,12,5,
312    16,17,9,12,1,15,8,14,13,
313  2,18,15,19,13,4,16,11,17,
314  17,13,1,14,5,9,2,6,18,
315   15,12,18,11,16,3,14,17,19,
316   9,16,14,7,18,12,15,3,11};   
317
318
319const   byte RP_1 [81 ] PROGMEM =                        //  Tests Remote_Pair
320{  1,7,8,6,14,9,13,5,12,                                        
321    9,3,4,1,5,12,6,18,7,
322    2,5,6,7,18,3,14,1,19,
323     7,9,3,5,6,18,12,4,1,
324    6,4,1,12,3,7,5,9,18,
325    8,2,5,9,1,4,7,3,6,
326     5,6,7,3,19,1,18,12,14,
327    4,1,12,18,7,5,19,6,13,
328    3,8,19,4,12,6,1,7,5};
329
330const   byte RP_2 [81 ] PROGMEM =                        //  Tests Remote_Pair
331{   7,9,8,4,5,2,3,1,6,                                        
332    6,14,3,7,8,1,15,9,2,
333    15,1,2,19,3,16,8,7,14,
334     3,7,11,2,6,5,19,4,8,
335    8,2,19,1,4,3,7,6,15,
336    14,6,15,8,9,7,11,2,3,
337     9,8,16,15,1,4,2,3,7,
338    1,13,7,16,2,8,14,5,19,
339    2,15,14,13,7,19,16,8,1};
340
341const   byte MD_1 [81 ] PROGMEM =                        //  Medusa 3-D tests 1
342{   17,9,3,8,2,4,5,6,11,                                        
343    14,8,5,6,13,11,19,17,2,
344    2,11,6,19,7,5,14,13,8,
345     3,2,1,7,6,9,8,4,5,
346    19,16,14,2,5,8,3,11,17,
347    5,7,8,11,4,13,2,9,6,
348     8,5,19,14,1,6,7,2,3,
349    11,14,7,13,8,2,6,5,19,
350    16,13,2,5,19,7,1,8,14};
351
352const   byte MD_1_B [81 ] PROGMEM =                        //  Medusa 3-D tests 1, Sudoku   coach
353{   3,12,5,6,4,9,7,11,8,                                     
354    7,4,11,8,2,15,13,9,16,
355     8,16,9,11,13,7,12,4,15,
356    1,3,4,5,7,2,6,8,9,
357    16,15,17,9,8,4,11,12,3,
358     9,8,2,13,6,11,5,7,4,
359    2,11,16,4,9,13,8,15,7,
360    15,9,8,7,1,16,4,3,2,
361     4,17,13,2,15,8,9,16,1};
362
363
364const byte MD_1_37 [81 ] PROGMEM =                        //   Medusa 3-D tests 1 with 37 eliminations!
365{   16,17,12,9,11,8,4,3,15,                                       
366     19,15,4,7,13,2,6,8,11,
367    13,8,1,16,5,4,19,17,2,
368    17,14,5,18,16,3,1,2,9,
369     11,19,16,5,2,17,3,14,8,
370    12,13,18,14,9,11,5,6,17,
371    15,16,13,12,7,9,8,1,14,
372     18,1,7,13,14,5,12,19,6,
373    4,12,19,1,18,6,17,5,13};
374    
375const byte   MD_2 [81 ] PROGMEM =                        //  Medusa 3-D Tests 2
376{   3,18,16,11,5,2,14,19,17,                                        
377    2,5,17,3,14,19,16,1,18,
378    19,11,4,6,18,7,5,2,3,
379     16,9,3,2,17,11,8,14,5,
380    5,7,11,18,16,14,12,3,19,
381    4,12,8,19,3,5,17,6,11,
382     11,16,5,4,19,8,3,17,12,
383    17,3,12,5,11,6,19,8,4,
384    8,4,19,17,2,3,11,5,6};
385
386const   byte MD_2_B [81 ] PROGMEM =                        //  Medusa 3-D Tests 2, Series   B
387{   6,4,13,7,19,15,8,12,11,                                      
388    12,7,11,18,6,4,15,13,19,
389     18,15,9,1,12,3,4,7,6,
390    5,11,7,4,13,18,19,6,2,
391    3,6,18,12,11,19,7,15,14,
392     14,9,2,15,7,6,1,18,13,
393    7,13,14,6,18,1,2,9,15,
394    9,2,15,13,4,7,6,1,18,
395     11,18,6,9,15,2,13,14,7};
396
397
398const byte MD_3 [81 ] PROGMEM =                        //   Medusa 3-D Tests Rule 3
399{   2,9,16,15,17,14,8,3,11,                                      
400     14,11,18,16,2,13,9,7,15,
401    15,13,17,1,18,9,4,16,2,
402    8,4,5,7,6,1,2,9,3,
403     6,12,11,13,19,18,5,4,7,
404    13,17,9,12,4,5,16,11,8,
405    9,18,3,4,15,7,11,12,16,
406     11,6,14,18,3,12,7,15,9,
407    17,5,12,19,11,16,3,8,4};
408
409const byte MD_3_B   [81 ] PROGMEM =                        //  Medusa 3-D Tests Rule 3, Series B
410{    9,17,1,18,3,12,16,5,4,                                    
411    8,5,12,16,14,11,17,3,19,
412     4,13,16,5,17,19,8,11,12,
413    15,11,7,14,12,6,13,9,8,
414    2,9,8,3,1,5,14,16,7,
415     6,4,13,7,19,18,1,2,15,
416    7,12,4,19,16,13,15,8,11,
417    11,6,15,12,18,14,19,7,13,
418     3,8,9,11,5,7,2,14,6};
419
420const byte MD_4 [81 ] PROGMEM =                        //   Medusa 3-D Tests Rule 4
421{   1,19,12,18,5,6,17,14,3,                                      
422     15,4,3,12,9,17,11,18,16,
423    8,17,16,11,4,3,15,19,2,
424    17,3,14,5,6,18,2,1,19,
425     9,5,18,4,2,1,16,3,7,
426    16,2,1,17,3,19,18,15,14,
427    3,1,7,9,8,12,14,16,5,
428     12,16,15,3,1,14,9,7,18,
429    14,18,19,6,7,15,3,12,1};
430
431const byte MD_4_B   [81 ] PROGMEM =                        //  Medusa 3-D Tests Rule 4, Series B
432{    2,19,5,18,1,16,14,17,13,                                      
433    11,4,18,13,9,7,16,5,12,
434     16,3,17,14,2,5,19,8,11,
435    8,17,4,16,5,11,13,12,19,
436    9,1,13,2,8,4,17,6,5,
437     5,16,12,9,7,13,8,11,4,
438    4,5,6,1,3,18,12,9,17,
439    13,12,11,7,6,19,5,4,18,
440     17,18,19,5,4,12,1,13,6};    
441
442const byte MD_5 [81 ] PROGMEM =                        //   Medusa 3-D Tests Rule 5
443{   9,2,3,4,18,7,16,1,5,                                      
444     8,7,6,11,5,13,9,2,4,
445    5,14,11,2,19,16,18,3,17,
446    7,6,9,13,2,15,1,4,18,
447     4,3,2,18,16,11,17,5,9,
448    1,8,5,19,17,4,2,6,13,
449    13,9,8,16,4,2,15,7,1,
450     2,11,7,15,3,19,4,8,6,
451    16,15,14,7,11,8,13,9,2};
452
453const byte MD_5_B   [81 ] PROGMEM =                        //  Medusa 3-D Tests Rule 5, Series B
454{    16,5,3,11,19,7,18,4,12,                                     
455    9,14,11,6,18,2,7,3,5,
456     12,18,7,3,5,14,16,11,19,
457    7,1,12,14,16,3,5,19,8,
458    14,6,5,19,12,18,11,7,13,
459     8,13,9,5,7,11,14,2,16,
460    11,9,8,7,3,16,2,5,14,
461    5,12,14,8,11,9,13,16,7,
462     13,7,16,2,14,5,9,8,11};    
463
464const byte MD_6 [81 ] PROGMEM =                        //   Medusa 3-D Tests Rule 6
465{   9,8,6,7,2,1,3,4,5,                                      
466     3,11,4,9,5,6,18,12,7,
467    15,12,7,18,3,14,9,6,11,
468    18,7,3,12,6,5,14,11,9,
469     6,9,12,14,1,7,15,18,3,
470    1,14,15,3,9,18,2,7,6,
471    14,15,18,6,7,9,11,3,12,
472     12,6,9,1,4,3,7,15,18,
473    7,3,1,5,8,2,6,9,4};
474
475const byte MD_6_B [81   ] PROGMEM =                        //  Medusa 3-D Tests Rule 6, Series B
476{   13,7,2,6,15,4,19,8,11,                                       
477    16,11,15,13,8,9,4,7,12,
478    4,8,9,1,17,12,13,6,5,
479     15,19,1,8,14,13,6,12,7,
480    8,16,14,12,11,17,15,19,3,
481    2,13,7,19,16,15,8,11,14,
482     7,12,16,15,13,8,1,14,19,
483    11,14,3,7,9,16,12,15,8,
484    19,5,8,4,12,1,7,13,16};     
485
486const byte MD_3456 [81 ] PROGMEM =                        //  Medusa   3-D Tests Rules 3,4,5,6
487{   9,15,8,13,2,11,14,7,6,                                     
488     6,12,14,19,15,7,1,18,13,
489   1,7,13,18,16,14,15,2,19,
490    17,18,5,4,13,16,12,9,1,
491     3,9,1,7,8,2,16,14,5,
492    4,6,12,11,19,5,8,3,17,
493   18,4,17,16,11,13,19,5,12,
494     5,13,6,12,14,19,17,1,18,
495    2,1,9,5,7,18,3,16,4};    
496
497const byte   Workout [81 ] PROGMEM =                        //  Uses many different solvers
498{    11,18,16,14,12,5,17,19,3,                                     
499    9,13,2,1,18,17,16,14,5,
500     7,4,15,16,13,19,11,8,12,
501    5,11,3,18,17,4,12,16,9,
502    16,9,18,13,15,12,14,17,1,
503     12,17,4,19,16,1,5,13,18,
504    8,16,11,5,14,13,9,2,17,
505    13,12,19,17,11,16,18,15,14,
506     14,15,17,2,9,18,3,11,16}; 
507
508const byte Recursive_1 [ 81] PROGMEM =                        //   Famous Arto Inkala puzzle 1 - one of the most difficult puzzles
509{  1,16,12,18,15,7,14,9,13,                            
510   15,3,14,11,2,19,16,17,8,
511    17,18,9,6,14,13,5,12,11,
512     14,17,5,3,11,12,9,18,16,
513    19,1,13,15,8,16,17,14,2,
514    6,12,18,17,19,4,11,13,15,
515     3,15,16,14,17,18,12,1,19,
516   12,4,11,19,13,15,18,16,7,
517    18,19,7,12,16,11,3,15,14};
518
519const   byte Recursive_2 [81 ] PROGMEM =                        //  2nd Famous Arto Inkala   puzzle - one of the most difficult puzzles
520{ 11,14,5,3,12,17,16,19,18,                           
521    8,13,19,16,15,14,11,2,17,
522   16,7,12,19,1,18,5,14,13,
523    4,19,16,11,18,5,3,17,12,
524    12,1,18,14,7,13,19,15,6,
525    17,15,3,2,19,16,14,8,11,
526   13,6,17,5,14,12,18,11,9,
527    19,18,4,17,16,11,12,3,15,
528    15,12,11,18,13,9,7,16,14};
529
530// Matching   pointers to each input grid and the name of the puzzle to display
531
532
533const   char Puzzle_Names_1[] PROGMEM = "Easy";
534const char Puzzle_Names_2[] PROGMEM   = "Medium";
535const char Puzzle_Names_3[] PROGMEM = "Difficult";
536const char   Puzzle_Names_4[] PROGMEM = "Expert";
537const char Puzzle_Names_5[] PROGMEM =   "Jellyfish";
538const char Puzzle_Names_6[] PROGMEM = "Unique Rectangle 1";
539const   char Puzzle_Names_7[] PROGMEM = "Unique Rectangle 2";
540const char Puzzle_Names_8[]   PROGMEM = "Unique Rectangle 3";
541const char Puzzle_Names_9[] PROGMEM = "Unique   Rectangle 4";
542const char Puzzle_Names_10[] PROGMEM = "Hidden Rectangle 1";
543const   char Puzzle_Names_11[] PROGMEM = "Hidden Rectangle 2";
544const char Puzzle_Names_12[]   PROGMEM = "Remote Pair 1";
545const char Puzzle_Names_13[] PROGMEM = "Remote   Pair 2";
546const char Puzzle_Names_14[] PROGMEM = "Diabolical 1";
547const char   Puzzle_Names_15[] PROGMEM = "Diabolical 2";
548const char Puzzle_Names_16[] PROGMEM   = "Diabolical 3";
549const char Puzzle_Names_17[] PROGMEM = "Medusa 1";
550const   char Puzzle_Names_18[] PROGMEM = "Medusa 2";
551const char Puzzle_Names_19[] PROGMEM   = "Medusa 3";
552const char Puzzle_Names_20[] PROGMEM = "Medusa 4";
553const   char Puzzle_Names_21[] PROGMEM = "Medusa 5";
554const char Puzzle_Names_22[] PROGMEM   = "Medusa 6";
555const char Puzzle_Names_22a[] PROGMEM = "Workout!";
556const   char Puzzle_Names_23[] PROGMEM = "Long Recursive 1";
557const char Puzzle_Names_24[]   PROGMEM = "Long Recursive 2";
558
559
560#ifdef Test_Only                                        //   used in conjuntion with Test configurations in puzzle solver to auto run one puzzle   on startup
561
562const byte* Puzzles_List  [] = {Easy};
563const char *const Puzzle_Names_Table[]   PROGMEM = {Puzzle_Names_1};
564#else 
565const char *const Puzzle_Names_Table[]   PROGMEM = {Puzzle_Names_1, Puzzle_Names_2, Puzzle_Names_3, Puzzle_Names_4, Puzzle_Names_5,
566                                                                 Puzzle_Names_6,Puzzle_Names_7,   Puzzle_Names_8, Puzzle_Names_9, Puzzle_Names_10,
567                                                                Puzzle_Names_11,Puzzle_Names_12,Puzzle_Names_13,Puzzle_Names_14,Puzzle_Names_15,
568                                                                 Puzzle_Names_16,   Puzzle_Names_17, Puzzle_Names_18, Puzzle_Names_19,Puzzle_Names_20,
569                                                                Puzzle_Names_21,Puzzle_Names_22,Puzzle_Names_22a,Puzzle_Names_23,Puzzle_Names_24
570                                                           };
571
572
573const byte*   Puzzles_List  [] = {               Easy,
574                                               Medium_1,
575                                               Difficult_1,
576                                              Expert,
577                                               Jellyfish_1,
578                                              UR,
579                                               UR2H,
580                                              UR_3a,
581                                               UR5,
582                                              HR_1,                                           
583                                              HR_2,
584                                               RP_1,
585                                              RP_2,
586                                               Diabolical_3,
587                                              Diabolical_4,
588                                               Diabolical_5,
589                                              MD_1   ,
590                                              MD_1_B,                                             
591                                               MD_2 ,
592                                              MD_3   ,
593                                              MD_5_B,
594                                              MD_6,
595                                               Workout,
596                                              Recursive_1,
597                                               Recursive_2};
598#endif
599// end
600/*
601   *  Solving Sudoku Puzzles
602Fill in all blank cells making sure that each row,   column
603and 3 by 3 box contains the numbers 1 to 9.
604The Basics:
605Firstly,   it's impossible to get very far without carefully
606maintaining a list of 'possible   values' or candidates for each
607blank cell. Doing this by hand is laborious and   prone to error,
608and often detracts from the fun of solving these puzzles.
609Fortunately,   programs like this one will do this for you,
610while leaving you with the fun of   applying logic to solve each
611puzzle.
612If you don't have a program to help -   systematically analyse at
613each blank cell. Start with the assumption it can have   any digit
614(or value) between 1 and 9, and then remove all values which
615have   already been assigned to other cells in its respective row,
616column and 3x3 box.   This leaves each blank cell with a list of
617candidates.
618Singles:
619Any cells   which have only one candidate
620can safely be assigned that value.
621It is very   important whenever a value is
622assigned to a cell, that this value is also
623excluded   as a candidate from all other
624blank cells sharing the same row,
625column and   box. (Programs like Simple
626Sudoku will do this laborious step
627automatically   for you too.)
628Hidden Singles:
629Very frequently, there is only one
630candidate   for a given row, column or box,
631but it is hidden among other candidates.
632In   the example on the right, the
633candidate 6 is only found in the middle
634right   cell of the 3x3 box. Since every box
635must have a 6, this cell must be that 6.
636Beyond   the Basics:
637While the two steps above are the only ones which will directly
638assign   a cell value, they will only solve the simplest puzzles.
639That's fortunate, otherwise   Sudoku wouldn't be as popular as it
640is today. The following steps (in increasing   complexity) will
641reduce the number of candidates in blank cells so, sooner or
642later,   a 'single' candidate or 'hidden single' candidate will
643appear.
644
645Beyond   the Basics
646
647Locked Candidates 1: (Pointing)
648Sometimes a candidate within   a box is restricted to one row or
649column. Since one of these cells must contain   that specific
650candidate, the candidate can safely be excluded from the
651remaining   cells in that row or column outside of the box.
652In the example below, the right   box only has candidate 2's in its
653bottom row. Since, one of those cells must   be a 2, no cells in
654that row outside that box can be a 2. Therefore 2 can be
655excluded   as a candidate from the highlighted cells.
656
657Locked Candidates 2: (Claiming)
658Sometimes   a candidate within a row or
659column is restricted to one box. Since
660one of   these cells must contain that
661specific candidate, the candidate can
662safely   be excluded from the remaining
663cells in the box.
664
665Naked Pairs:
666If two   cells in a group contain an identical pair of candidates and
667only those two candidates,   then no other cells in that group could be those values.
668These 2 candidates can   be excluded from other cells in the group.
669
670Advanced Steps:
671
672Naked Triples   & Naked Quads:
673The same principle that applies to Naked
674Pairs applies to Naked   Triples & Naked
675Quads.
676
677A Naked Triple occurs when three cells in
678a   group contain no candidates other that
679the same three candidates. The cells
680which   make up a Naked Triple don't have
681to contain every candidate of the triple. If
682these   candidates are found in other cells
683in the group they can be excluded.
684
685A   Naked Quad occurs when four cells in a
686group contain no candidates other that
687the   same four candidates.
688
689Hidden Pairs:
690If two cells in a group contain a   pair of
691candidates (hidden amongst other
692candidates) that are not found in   any
693other cells in that group, then other
694candidates in those two cells can   be
695excluded safely.
696
697Hidden Triples:
698If three candidates are restricted   to three cells in a given group,
699then all other candidates in those three cells   can be excluded.
700Hidden triples are generally extremely hard to spot but
701fortunately   they're rarely required to solve a puzzle.
702Hidden Quads:
703If four candidates   are restricted to four cells in a given group,
704then all other candidates in those   four cells can be excluded.
705Hidden Quads are very rare, which is fortunate since   they're
706almost impossible to spot even when you know they're there.
707For the   Addict:
708The following techniques are no more difficult than those above
709but   requires observation as to how specific candidates relate to
710each other (in particular   patterns) beyond any given row,
711column or box.
712
713X-Wing:
714For every Sudoku,   a value can exist only once in each row,
715column and box. If a value has only   2 possible locations in a
716given row (ie it has a candidate in only 2 cells in   that row), then
717it must be assigned to one of these 2 cells. Given a particular
718puzzle   that has two rows where a given candidate 'C' is
719restricted to exactly the same   two columns (and no more than 2
720columns), and since:
7211) candidate C must be   assigned once in each of these two
722rows, and
7232) no column can contain more   than one of candidate C
724then candidate C must be assigned exactly once in each   of
725these two columns within these two rows. Therefore, it's not
726possible for   any other cells in these two columns to contain
727candidate C. This same logic   applies when a puzzle that has two
728columns where candidate C is restricted to   exactly the same two
729rows.
730
731Swordfish:
732The Swordfish pattern is a variation   on the "X-Wing" pattern above.
733Formal definition:
734Given a particular puzzle   that has three rows where a given
735candidate 'C' is restricted to the same three   columns, and since
7361. candidate C must be assigned once in each of these three   rows
7372. no column can contain more than one of candidate C
738then candidate   C must be assigned exactly once in each of
739these three columns within these three   rows. Therefore, it's not
740possible for any other cells in these three columns   to contain
741candidate C.
742This same logic applies when a puzzle that has three   columns
743where candidate C is restricted to exactly the same three rows.
744The   X-Wing and Swordfish techniques can be further
745generalised to include rows containing   candidates restricted to
746four cells in the same four columns (called a Jellyfish).
747
748XY-Wing   (also called Y Wing):
749Not to be confused with X-Wing (see above).
750Formal definition:
751Given   3 cells where -
7521. all cells have exactly 2 candidates
7532. they share the same   3 candidates in the form - xy, yz, xz
7543. one cell (the Y 'stem' with canidates   xy) shares a group
755with the other 2 cells (Y 'branches' with candidates xz &   yz)
756then any other cell which shares a group with both 'branch' cells
757can   have excluded the 'z' candidate that is common to these 'branch' cells.
758Proof:   If a cell sharing a group with both branch cells is
759assigned the 'z' candidate,   then neither branch can be assigned
760the 'z' candidate. Consequently, one branch   would be the 'x' and
761the other the 'y' leaving the 'stem' without a candidate,   an
762invalid state.
763Note: If all 3 cells in a xy-wing pattern shared the same   unit/house,
764then they would be a 'naked triple'.
765
766XYZ-Wing:
767An XYZ-Wing   is like an XY-Wing in that it is a group of three cells, one sharing a unit with   the other two.
768E.g., base is {1,4,5} and second cell in same box is {1,4}, need   to find 3rd cell {1,5} outside box but still seen by base
769However, the first   cell in an XYZ-Wing has three candidates while the other two, called the wings,   have two.
770Each of the wings must share one candidate with the first cell, (that's   part of sharing a unit) but of different values.
771If the two second candidates   in the wings are both the same, and are also the same as the extra candidate in   the first cell,
772then if any fourth cell shares that candidate and a unit with   all three, that candidate can be eliminated.
773It will be in the base's box and   seen by base and both 'pincers'.
774
775WXYZ-Wing:
776A WXYZ-Wing is like an XY-Wing   and an XYZ-Wing, except it is a group of four cells, one sharing a unit with the   other three. 
777The first cell in a WXYZ-Wing has three or four candidates while   the other three, called the wings, have two each.
778Each of the wings must share   one candidate with the first cell, (that's part of sharing a unit) but each wing   must share a different value.
779If the second candidates in the wings are all the   same, and are also the same as the left-over candidate of the first cell if the   first cell
780has four candidates, then if any fifth cell shares that candidate   and a unit with all the others, that candidate can be eliminated.
781(E.g.) Cells   in one box, Base {5,8,9}, {1,9}, {1,5} and one cell outside box that 'sees' the   base {1,8}.  If any other cell in the box has '1' and sees the outside 
782of the   box cell too, eliminate the candidate 1 in that cell.
783
784Unique Rectangle Type   1:
785A "Unique Rectangle" (UR) consists of four cells that occupy exactly two   rows, two columns, and two boxes.
786All four cells have the same two candidates   left (in real sudokus not all cells have to hold all of the UR candidates).
787A   UR Type 1 exists, if one of the four cells of a possible UR has additional candidates.
788If   those candidates were eliminated, the UR would exist, causing two solutions.
789It   is therefore absolutely necessary, that one of the additional candidates has to   be true. 
790That means, that the UR candidates can be eliminated from the cell   with the additional candidates.
791
792Unique Rectangle Type 2:
793If in a possible   UR two non diagonal cells have only one extra candidate, and that candidate is the   same in both cells,
794all candidates seeing both extra candidates can be eliminated.   In other words, you have two corners as in Type 1, and
795two more that have those   same two candidates plus an third, matching in both.  That candidate can be eliminated   from any cell that is
796in the same house/unit as cell 3 and as cell 4 (the three-candidate   corners) even those those cells may not be in same house as each other
797
798Unique   Rectangle Type 3:
799This is a combination of UR with Naked/Locked Subsets. We look   for two non diagonal cells in a possible UR that have extra candidates.
800Since   one of those candidates has to be set to avoid the UR, we can treat both cells as   one virtual cell containing only
801the extra candidates and try to build a Naked   Subset (all additional cells have to see both UR cells with extra candidates).
802If   such a UR/Naked Subset is found, all subset candidates can be eliminated from all   cells outside the subset (but in the same house). 
803So, one extra candidate seen   in non-diagnal cells and one that is seen by both.
804
805Unique Rectangle Type   4:
806We look for additional candidates in two non diagonal cells again, but this   time
807we ignore those extra candidates and concentrate on the UR candidates themselves:   
808If one of the UR candidates is not possible anymore in any other cell of a house
809that   contains both cells with the extra candidates, the other UR candidate can be eliminated   from those UR cells.
810So search the house(s) that contain both non-diagonal cells   (from the Type 2) and can't do the elimination if UR candidate cell is found
811
812Unique   Rectangle Type 5:
813UR Type 5 is a variation of UR Type 2, but now the additional   candidate can be in diagonal cells as well.
814Suppose we have a possible UR with   one extra candidate in either two diagonal cells or in three cells.
815All occurences   of that candidate can be eliminated in all cells that see all UR cells containing   the additional candidate.
816The logic behind that move is the same as in a UR Type   2. In other words, in the corners we have one 2-candidate bivalue and at least two   others,
817and maybe three, have three candidates with the 3rd matching in all.   That candidate can be removed from any cell 'seen' by all three non-bivalue cells.
818
819Hidden   Rectangle:
820Hidden Rectangles are very versatile, because they can be used in   possible URs that contain up to 
821three cells with arbitrary additional candidates   (the UR is hidden under a clutter of additional 
822candidates - not to be confused   with Almost Unique Rectangles). 
823We need a possible UR with two or three cells   containing additional candidates (with only one cell the 
824UR Type 1 should be   used). Now take one UR cell without additional candidates and check the row and   
825the column containing the opposite corner of the UR. If one UR candidate is   nowhere outside the UR in 
826those two houses, the other UR candidate can be eliminated   from the opposite corner. 
827
828Links and Inferences for chains
829The basis of   all chains are two types of basic implications, normally called "links" or "inferences"
830
831Weak   Links
832If two entities are weakly linked, they cannot be true at the same time.   That means: If one of them is true, 
833then the other has to be false (but both   can be false as well, so if one is false, nothing can be concluded).
834In simple   chains the entities are normally simply candidates, that share a house or a cell.
835
836Strong   Links
837If two entities are strongly linked, they cannot be false at the same time.
838That   means: If one of them is false, then the other has to be true (both true is only   possible in very advanced types of links).
839If we use candidates, we would need   exactly two candidates sharing a cell, or exactly two instances of the same candidate   sharing a house (a conjugate pair in coloring terms).
840
841Those two link types   are the basis for every type of chains, so the difference between them has to be   understood completely. To sum it up:
842
843Weak Link: If a is true then b is false
844Strong   Link: If a is false then b is true
845
846XY-Chain:
847This method can be used when   a great number of cells contain only two possible candidates.
848in choosing one   of the candidates in a starting cell, one forms a chain of choices
849which results   in the suppression of a candidate in a given cell.
850If the other candidate is   chosen in the starting cell and one ends with the suppression
851of the same candidate,   it can be excluded safely.
852Pick your starting cell, and make a small u shape   (a little smiley curve) underneath the first pencilmark.
853From there, look around,   but instead of crossing out pencilmarks (otherwise it gets too messy!),
854when   you find a value that it forces somewhere else, put the same u shape underneath   the forced value.
855Ignore any that the first choice eliminated  you might need   them later!
856Carry on doing this until you cant make any more u forces.
857Now   choose the second value in your original cell  and this time put a little n symbol   (a downturned mouth) above the second pencilmark.
858Like before, look at the implications   and forces that this makes, continuing on until you cant find any more.
859If theres   a forcing chain, at some point youll find a pencilmark with both a u and n on the   same mark
860(in which case theyll almost join up!). This its a sure sign that whichever   candidate you picked for the first cell,
861youve found the right value for the   second cell. 
862
863X-Chain:
864X-Chains are chains that use one digit only. X-Chains   of length 4 are sometimes called Turbot Fishes.
865A X-Chain is a single-digit solving   technique which uses a chain consisting of links that alternate between strong links   and weak links,
866with the starting and ending link being strong. In other words,   the chain involves an even number of cells having the target digit as a candidate.
867The   target digit can be eliminated from any cell that is seen by both ends of the X-Chain.
868The   important thing with X-Chains is, that they have to start and end with a strong   link.  This ensures that one of the endpoints actually contains
869the chain digit.   That digit can be removed from any cell that sees both ends of the chain. (EG --   even number of nodes, elimination cell must 'see' both ends)
870
871Forbidding Chain   -- Really another version of X-Chain, but implemented some handling of group nodes   and that opens up more strong links for chains.  Begin and 
872end on weak link   using single digit chain and alternating links.  If you reach the head again, eliminate   that candidate.
873
874Remote Pair Chain:
875Remote Pair is the simplest chaining   technique. It considers only bivalue cells that contain the same two candidates.
876Since   the cells are bivalue, a strong link exists within every cell between the two candidates.   The links between the cells
877can therefore be weak (the cells have to see each   other). To eliminate something, the chain has to be at least four cells long.
878The   Remote Pair ensures, that any cell within the chain has the opposite value of the   cell before it. Any cell outside the Remote Pair
879that sees two cells with different   values cannot have one of the Remote Pair digits set.
880
881Medusa 3D:
8823D Medusa   extends single's chains into a third dimension. Medusa 3-D extends the search is   up through the bi-value cells which contain two different numbers.
883You can think   of the different candidate numbers as existing in a third dimension lifting up from   the page with 1 at the bottom and 9 at the top.
884In other words, its a chain that   can jump not only between cells on strong links but inside a bivalue cell as well.   Start the chain on a cell and one candidate in that cell and chain with alternating   'colors'.  Create all possible chains and then 
885analyze the chain using six rules.
886
887Rule   1 -  Twice in a Cell -  If two candidates in a cell have the same colour - all of   that colour can be removed - and the opposite colour are all solutions.  All that   color in the ENTIRE puzzle grid!
888Rule 2 -  Twice in a Unit - Similiar to 1, but   looking for two coloured occurrences of X in the same unit (row, column or box)   as opposed the two of the colour in the same cell.
889Rule 3 -  Two Different Colors   in a Cell with more than 2 candidates - We know that either ALL the blue candidates   will be true, or ALL the green ones. If there are any another candidates in any   cell with two colours, they cannot be solutions
890Rule 4 -  Two Colors "Elsewhere"   - where there are candidates that can see both colours they can be removed. By 'see'   we mean any candidates that are the same candidate as members of the blue/green   links. (e.g., a '6' sees both a green and blue '6').  It can be removed.
891Rule   5 -  Two Colors in Unit and Cell - If an uncoloured candidate can see a coloured   candidate elsewhere (it shares a unit) AND an opposite coloured candidate in its   own cell, it can be removed.
892Rule 6 -  Cell Emptied by Color - If all the candidates   in an uncolored cell can 'see' their counterparts all colored the same, ALL of that   color can be removed (e.g., same as 1, in the entire grid)
893
894*/ 
895