|
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:
- all the i's that the i at xx can see are added to the 'false' array to give "ixy", "izx", etc.
- all the other numers at xx are added to the 'false' array to give "jxx", "kxx", etc.
- 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.
- 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:
- 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.
- 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.
- 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:
- 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.
|
|
|