Hi experts,
Tom wrote:I'd guess that solvers that incorporate lots of human patterns like rjami's RJSolBit.c will also do well with pencilmark, since these puzzles favor forward inference vs. backtracking.
Please note that, my solver is slower than as what you have tested other solvers in two ways as follows:
1) I used step by step recursion for forward searching, in case solution found, program returns from same number of recursion it forwarded; and
2) I used step by step backtracking instead of directly jumping back to last guess.
If I will convert my program from recursive to iterative; and, instead of forwarding and backtracking step by step, just jump forward after/backtrack before guessing (as JCZSolve do) then, maybe, my program becomes faster many folds.
Similarly, I will definitely think to upgrade my program in order to input batch puzzles from given/clues to pencil mark separately as RJSudoku and RJSukaku respectively. I am adding this to my todo list but with less priority.
However, my program IS faster in a sense that it will search patterns with zero (or minimal in case I missed any) duplicate searching criteria. Let me elaborate this as how it works:
Consider following WXYZ-Wing patterns:
- Code: Select all
WXYZ-Wing Type 4a (2 exemplars, up to 4 exclusions):
--------------+-------------+----------- --------------+-------------+-----------
01) . wz . | -Z -Z -Z | . . . 02) . xyz . | -Z -Z -Z | . . .
-Z wxy wxy | . xyz . | . . . -Z wxy wxy | . wz . | . . .
. . . | . . . | . . . . . . | . . . | . . .
72--------------+-------------+-----------72--------------+-------------+-----------
WXYZ-Wing Type 4b (4 exemplars, 1 exclusion):
--------------+-------------+----------- --------------+-------------+-----------
01) . wz . | . . . | . . . 02) . xyz . | . . . | . . .
-Z wxyz wxy | . xyz . | . . . -Z wxyz wxy | . wz . | . . .
. . . | . . . | . . . . . . | . . . | . . .
72--------------+-------------+-----------72--------------+-------------+-----------
--------------+-------------+----------- --------------+-------------+-----------
03) . wz . | . . . | . . . 04) . xyz . | . . . | . . .
-Z wxyz wxyz | . xyz . | . . . -Z wxyz wxyz | . wz . | . . .
. . . | . . . | . . . . . . | . . . | . . .
72--------------+-------------+-----------72--------------+-------------+-----------
Please note that, I use single dimensional arrays of 81 elements; holding bitwise cell values and clue/solved separately.
I don't know how many times other solver search the above mentioned patterns (I guess, at least double) but, my program search as follows:
1) For each 1st apex in unsolved cells; (maximum 64 occurrences for proper vanilla puzzle)
2) If 1st apex contain more than 4 values then go to step 1;
3) for each 1st wing in 1st apex row but not box; (maximum 6 occurrences)
4) If either 1st wing is not unsolved or 1st apex and 1st wing contain more than 4 values in total then go to step 3;
5) For each 2nd wing in 1st apex box but not 1st wing row; (maximum 6 occurrences)
6) If either 2nd wing is not unsolved or 1st apex, 1st wing and 2nd wing contain more than 4 values in total then go to step 5;
7) For each 2nd apex in 1st apex mini-row; (duplicate occurrences found here)
8) If either 1st apex position is greater than 2nd apex position; or 2nd apex is not unsolved then go to step 7;
9) Now check if one of the above mentioned pattern found then perform eliminations accordingly.
(
Row can be replaced by column)
Added as on 20191009: a good example to check duplicate occurences is
August 26, 2019 puzzle.
Where as, Hodoku searches all occurrences, then sort and delete duplicate one by one, in find all steps processing. In case of batch puzzle processing, imagine if no above mentioned WXYZ-Wing pattern found then how many unnecessary duplicate occurrences searched!!
I think, duplicate searching happened in programming but not in manual solving.
Hope, I present my point of view clearly as why I prefer to code my solver as pattern based.
R. Jamil
