Forcing Net
 

Forcing Nets

When dealing with very hard puzzles, a number of people have put forward methods involving branching of chains as a means of increasing the chance of finding eliminations. Some of these are listed and discussed at Sudopedia. If what I've come up with here is similar to any of these, it is by coincidence only. The challenge as I see it is to extend and multiply the chains in order to identify as many "true" and "false" numbers as possible.

A. Consequences of a number being tested as 'true'

Whereas a strong link can only go from a false candidate to a true candidate, a weak link can go from a true candidate to many false candidates. All the false candidates can then be used to look for strong links, and so on. The approach used here utilises this branching of chains to maximise the chance of discovering a contradiction. I will describe how the program generates as wide a net as possible.

I used two arrays, each holding 3 digit strings, each representing the number and the two digit address. For example, a 1 in the top left corner would be "100". When starting with a candidate i at xx being true, the first member of the 'true' array would be "ixx".

1. the array of false number/addresses resulting from i at [xx] being true is started:

  1. all the i's that the i at xx can see are added to the 'false' array to give "ixy", "izx", etc.
  2. all the other numers at xx are added to the 'false' array to give "jxx", "kxx", etc.
  3. If there are 2 or 3 numbers in the same row/col occurring in a box, then these are false. If there are 2 same numbers in the same box either in a row or column (ie empty rectangle setup) then one of these two numbers must be true, and other numbers in the same row/col will be false.
  4. all ALSs of length 2, 3, and 4 containing i are generated, and if there is one where the i at xx can see the i(s) in the ASL, then the ALS reduces to a naked set whose numbers can be used to render other numbers false that are in the same unit.

2. each false number is tested to see if a true number can be found:

  1. If i at xx is false, and all but one of the other numbers in the cell are false, then the remaining number j at xx is true and is added to the 'true' array.
  2. Alternatively, other numbers in the cell are checked to see if they can 'see' a same number which is true, and if there is only one that can't, then it can be added to the 'true' array as above.
  3. If there is another same number, eg i at yy, in the unit which is the only one that is not false, then a strong link is present, and the "iyy" can be added to the 'true' array.

3. each false number is tested to see if further false numbers can be found:

  1. If all the other same numbers in the row (or column) are in the same box, then one of them has to be true. Therefore, others of this number in the box must be false.

These processes are run inside a 'do while' loop, terminating when no further members can be found and added to the 'false' and 'true' arrays. The two arrays are checked for duplicates, and any found removed. The two arrays can then be tested for the presence of contradictions. How this works can be seen by placing the starting true number/address in the appropriate textbox and clicking the 'Show True/False' button. The step-by-step development of the net is shown in the textarea at the bottom.

B. Consequences of a number being tested as 'false'

This is similar to the above, except the 'false' array is seeded with the starting false number/address, and that in the loop, processes 2 & 3 are run before 1.