The New Sudoku Players' Forum

[ronk]

we need to revisit SE (sudoku explainer) at some point
I'd like to see a C rewrite from the ground up, for efficiency, portability, and extensibility
the java code is fairly modular, so it would be possible to divide and conquer
given the right perspective we should be able to find the places where it trips up on automorphic permutations
I also believe we can squeeze a lot of cycles out of rating the harder puzzles in the process

If you really mean "C", as opposed to "C++", count me in as a volunteer. I know sudoku and C, but not Java or C++. Reasonably sure I could handle one learning curve, but most likely not two. Hmm, wonder if Nicolas Juillerat is planning another release.

Should this be happening on the Programmers' Forum?

[Red Ed]

Despite myself (not a fan of SE), I'd be interested in pitching-in as well.

[gsf]

If you really mean "C", as opposed to "C++", count me in as a volunteer.

yes, C -- I don't trust C++ for high performance applications because it too hard to
control where time is being spent, especially in the face of constructors/destructors/garbage-collection

Should this be happening on the Programmers' Forum?

possibly, except now I trust the admins on this forum more that the prog forum

initial thoughts are to start with a stripped down version of my solver
retaining the input/output parts, and keeping the framework where each solving technique is a separate function
internally the rating number would be integers (se rating * 10) to avoid floating point anomalies
we would probably start with the functions for the lower ratings and work up
those functions would be the divisions of labor

we could collect puzzles that exercise each function and use them for regression testing
making sure the regression tests keep pace with the rating function additions

I believe the general flow of control over the rating functions would be simply based on the rating for each function
at each stage apply the rating functions from lowest to highest rating until one provides a placement/elimination

[dobrichev]

yes, C -- I don't trust C++ for high performance applications because it too hard to
control where time is being spent, especially in the face of constructors/destructors/garbage-collection

C++ itself is not dangerous for high performance applications.
Default create constructor and default destructor are compiled to nothing.
Copy constructor is compiled to optimized version of memcpy() - such with known constant size and alignment.
There is no garbage collection different than this in the standard C runtime (heap for malloc() and free()).

C++ code sometimes provides compiler with more optimization hints, especially in the pointers to deeply indexed read-only data.

On the other hand C++ allows java-style coding which by definition is not applicable for high performance applications. This could cause problems in a heterogeneous team.

[ronk]

we could collect puzzles that exercise each function and use them for regression testing
making sure the regression tests keep pace with the rating function additions

I believe the general flow of control over the rating functions would be simply based on the rating for each function
at each stage apply the rating functions from lowest to highest rating until one provides a placement/elimination

I agree with all of this, and the rest of your post as well. The Interactive games forum should be a great resource from which to collect test puzzles.

In the end, duplicating the solution path of Sudoku Explainer will, I believe, be the most difficult challenge. If that doesn't happen, ratings would assuredly change. However, if the compiled Explainer is really fast, we might not mind recalculating some ratings.

[Red Ed]

if the compiled Explainer is really fast, we might not mind recalculating some ratings.

If SE's dynamic forcing chains are anything like as bad as nrczt chains, complexity-wise, then I would not be optimistic of the compiled version being "really fast".

[daj95376]

if the compiled Explainer is really fast, we might not mind recalculating some ratings.

If SE's dynamic forcing chains are anything like as bad as nrczt chains, complexity-wise, then I would not be optimistic of the compiled version being "really fast".

I was under the impression that there was already a compiled Java version of SE. If so, then I suspect that any radical speed increase from a compiled C version of SE will only occur from:

we need to revisit SE (sudoku explainer) at some point
I'd like to see a C rewrite from the ground up, for efficiency, portability, and extensibility
the java code is fairly modular, so it would be possible to divide and conquer
given the right perspective we should be able to find the places where it trips up on automorphic permutations
I also believe we can squeeze a lot of cycles out of rating the harder puzzles in the process

The part in green may or may not be significant, but the part in blue implies more than a migration from Java to C.

Maybe now would be a good time to review how SE determines its ratings ... and see if it's worth the conversion effort.

[ronk]

if the compiled Explainer is really fast, we might not mind recalculating some ratings.

If SE's dynamic forcing chains are anything like as bad as nrczt chains, complexity-wise, then I would not be optimistic of the compiled version being "really fast".

I was under the impression that there was already a compiled Java version of SE. If so, then ...

I guess "compiled Explainer" was careless of me. Both the C-language and the Java-language are compiled; C into machine code and Java into "bytecode." A Java virtual machine (JVM) layer sits between the bytecode and the machine.

We are assuming this extra layer introduces inefficiencies of sufficient magnitude to warrant rewriting to a language compiled directly into machine code. I have no idea how much speed improvement to expect from this, but would very disappointed if not better than 2:1, and very happy with better than 5:1. I fear 5:1 is a pipe dream.

[daj95376]

I guess "compiled Explainer" was careless of me. Both the C-language and the Java-language are compiled; C into machine code and Java into "bytecode." A Java virtual machine (JVM) layer sits between the bytecode and the machine.

We are assuming this extra layer introduces inefficiencies of sufficient magnitude to warrant rewriting to a language compiled directly into machine code. I have no idea how much speed improvement to expect from this, but would very disappointed if not better than 2:1, and very happy with better than 5:1. I fear 5:1 is a pipe dream.

I'm ignorant of the Java environment. It was some time ago that I'd read that a compiled version of the Java SE was faster than some other form of the Java SE. Thanks for the information that a JVM layer still exists on top of the machine level for the compiled version. I can see why you're expecting a speed increase by converting to a language that'd compile all the way to machine code. Good luck!!!

It seems to me that gsf's suggestion for portability is a nice concept, but I've learned that my Borland C compiler uses header files that are (sometimes) incompatible with Microsoft C. My compiler also lacks an inline assemble mode, so I can't take advantage of specialized bit-operations on my Pentium 4 hardware. _ _

Regards, Danny

[Red Ed]

we need to revisit SE (sudoku explainer) at some point
I'd like to see a C rewrite from the ground up, for efficiency, portability, and extensibility
the java code is fairly modular, so it would be possible to divide and conquer
...

Seems most of the interest expressed so far is in efficiency. So perhaps we should look at the Dynamic Forcing Chains code first.

[JasonLion]

I have been reading through some of the SE code today. It is fairly elegant in some ways, but makes no effort at being fast that I could detect. If the code I looked at was at all representative, it shouldn't be at all difficult to speed things up dramatically.

For example, each cell on the board is an object and every time you place a digit it recalculates the list of neighbors so it can tell each of them to clear their "can contain that digit" flags. Similar inefficiencies are visible in the fish detection code, where just about every intermediate value is an object that needs to be allocated and then garbage collected latter. The loop iterator in the fish code is a set of permutations, each an object, that is recreated each time the routine is called.

Some of the first round projects include:

• Make a database of puzzles with known SE ratings in a convient format
• Make a list of solving techniques used in SE and their ratings
• Read the code to build a complete description of the overall rating process (leaving out details of the techniques)
• Define the core routines (grid representation, hint lists, and supporting routines)
• Define and setup a team coordination framework
• Agree on which open source license to use

[ronk]

JasonLion, thanks for reporting on your study of Sudoku Explainer source code, and glad to hear that you think it possible to "speed things up dramatically."

Some of the first round projects include:

• Make a database of puzzles with known SE ratings in a convenient format
• Make a list of solving techniques used in SE and their ratings
• Read the code to build a complete description of the overall rating process (leaving out details of the techniques)
• Define the core routines (grid representation, hint lists, and supporting routines)
• Define and setup a team coordination framework
• Agree on which open source license to use

This looks good to me, but note my background is electronic hardware, not software. Therefore, I probably won't be able to contribute as much to the coding effort as you, or gsf, or Red Ed. However, I've started to assemble a "database of puzzles" which have a given ER rating, but with EP and ED ratings as low as possible. IOW the ideal benchmark would be a singles step of the rated ER with other steps being singles. Working this from the low ERs going up. As to a list of techniques and their ratings, Mike Barker's Mar 2008 list here should be a good starting point.

But let's back up one step and first agree on the goal here. I don't think it's to write a C++ or C-language equivalent to Sudoku Explainer, but rather to produce an equivalent SE puzzle rater invoked by command line. IOW the solver and solver hint functions would be dropped, and the GUI would be dropped too. Perhaps gsf will chime in soon.

[gsf]

But let's back up one step and first agree on the goal here. I don't think it's to write a C++ or C-language equivalent to Sudoku Explainer, but rather to produce an equivalent SE puzzle rater invoked by command line. IOW the solver and solver hint functions would be dropped, and the GUI would be dropped too. Perhaps gsf will chime in soon.

yes, I would like to see a fast command line SE rating program, no GUI, no hints
but I think we will at least have a embedded backtracking solver to weed out invalid puzzles
and we also might be able to use to use the solution to speed up some of the methods

[ronk]

Test Puzzles

This is putting the cart in front of the horse, but here are (usually) 10 puzzles for each of Sudoku Explainer ratings 1.2 through 4.4. I intend to add the higher ratings, chunk by chunk, as time permits or as needed. All the ratings are ED=X.X/1.2/1.2, so a minimal number of additional techniques are required. If the format needs improvement, please advise.

All the puzzles were taken from the Patterns Game Results, with the attribution omitted. The list includes the default output of gsf's solver, which includes the techniques it requires to reach a solution.

Hidden Text: Show

Code: Select all

# ED=1.2/1.2/1.2 Hidden Single in box
1..2..3...2..1..4...3..5..67..6..5...5..8..7...8..4..18..7..4...3..6..2...9..2..7 #     6 N C27.m/S4.da
..1...2.....3.4...5...6...1.5.1.2.7...8...4...2.9.7.8.9...7...8...5.9.....3...7.. #    12 N C24.m/S8.f
1...2...3.4.....1...5.4.6.....2.1...7.8...1.5...4.8.....7.6.8...8.....2.4...3...7 #    10 N C24.m/S8.f
1...2...3.4.....5....6.7.....5...8..7...8...2..6...9.....8.2....1.....6.2...7...1 #    10 N C21.m/S8.f
1..2..3......4..5...6..7..82.....7...5..1..4...7.....98..1..2...6..2......4..6..7 #    10 N C23.m/S4.da
...........12.34...235.617..35...74.....3.....76...82..143.825...87.23........... #    14 N C29.m/S8.f
...1.......2..3..4.5..2..6.6..4..7....7..1..8.8..5..2....5.......4..8..3.3..6..8. #     8 N C23.m/S2.d
12.....87..6...2..7...8...65..9.6..1..7...3..6..5.1..83...1...2..5...6..27.....93 #    12 N C28.m/S4.hv
..1..23...2.....1.4..5....2..64....3.........2....78..1....3..6.7.....4...56..9.. #    12 N C22.m/S4.da
...........12.34...2.1.5.6..14...35...........37...81..5.6.1.2...68.41........... #    14 N C24.m/S8.f

# ED=1.5/1.2/1.2 Hidden Single in line
7.......9.6.....2....9.8.....91.28......3......24.51.....8.3....7.....6.8.......1 #    16 N C21.m/S8.f
.1.....2...2...3.....4.5.....6.4.2...7.....1...5.6.8.....9.1.....4...6...9.....7. #    16 N C20.m/S4.hv
9..2..6...7..9..5...6..1..91..3..8...3..4..9...5..2..46..9..5...2..6..7...9..3..2 #    14 N C27.m/S4.da
..3...5.....7.1...8...2...6.8.4.6.1...7...9...3.1.8.2.4...6...9...2.9.....1...3.. #    12 N C24.m/S8.f
8...3...7.6.....8...2.6.5.....3.8...2.1...8.9...9.7.....4.5.1...5.....3.6...7...4 #    16 N C24.m/S8.f
1...2...3.8.....5....4.1.....5...6..7...8...1..4...2.....8.2....6.....4.2...3...6 #    12 N C21.m/S8.f
1..8..4......1..5...7..3..98.....2...5..6..8...2.....32..6..3...7..8......1..7..2 #    14 N C23.m/S4.da
...........12.34...235.418..35...74.....3.....76...82..143.825...87.23........... #    14 N C29.m/S8.f
...5.......8..7..4.3..2..8.8..4..6....6..5..3.9..3..2....2.......4..9..5.7..6..9. #    20 N C23.m/S2.d
12.....89..6...2..7...2...55..9.6..1..7...5..6..5.1..83...1...2..5...4..27.....93 #    12 N C28.m/S4.hv

# ED=1.7/1.2/1.2 Direct Pointing
.8.....5...5...9.....9.2.....9.6.2...3.....4...7.2.3.....8.4.....6...7...1.....8. #    26 NB C20.m/S4.hv
9..2..8...3..9..4...5..8..28..5..1...9..7..8...7..9..36..7..9...2..4..5...9..6..4 #    24 NB C27.m/S4.da
1...2...3.4.....5....6.7.....5...4..7...4...1..6...2.....4.1....8.....6.2...3...8 #    16 NB C21.m/S8.f
1..8..4......1..2...7..5..36.....2...9..3..6...2.....12..6..9...3..8......1..2..7 #    22 NB C23.m/S4.da
...........64.73...375.146..68...74.....4.....14...93..436.851...21.38........... #    16 NB C29.m/S8.f
...1.......2..3..4.5..6..2.5..4..7....3..1..8.2..5..3....6.......4..9..1.3..7..9. #    20 NB C23.m/S2.d
1..2.3..4...........2.5.6..3.......7..5.7.8..4.......3..8.6.9...........7..5.4..2 #    24 NB C21.m/S8.f
..1..23...2.....1.4..5....6..76....3.........8....14..6....3..5.9.....7...87..1.. #    18 NB C22.m/S4.da
...........12.34...2.1.5.6..16...52...........73...68..6.5.1.7...54.63........... #    28 NB C24.m/S8.f
.12.....33.4......56.1.......3.57......6.3......81.9.......4.57......4.26.....89. #    22 NB C24.m/S4.da

# ED=2.0/1.2/1.2 Direct Hidden Pair
.1.....2...2...3.....4.8.....8.5.6...7.....1...5.6.4.....1.9.....6...2...9.....7. #   220 NH C20.m/S4.hv
1..5..2...9..8..1...3..2..55..3..8...3..1..5...6..5..24..8..9...5..7..2...8..1..7 #    78 NH C27.m/S4.da
3..1..9......2..5...4..9..69.....4...5..9..8...2.....34..6..7...2..8......9..3..5 #   270 NH C23.m/S4.da
...........69.48...375.146..71...93.....9.....94...57..481.679...97.36........... #    78 NH C29.m/S8.f
1..2.3..4...........5.4.6..7.......2..6.1.5..2.......1..8.3.7...........9..4.1..3 #    86 NH C21.m/S8.f
.86.....45.7......23.1.......4.32......7.5......64.8.......1.32......7.58.....16. #    78 NH C24.m/S4.da
.......1......1.23..4.5.......2...4...5.3.6...3...7.......4.8..17.6......9....... #   144 NH C19.m/S4.da
1....2..3.9..8..6...75.......8.....1.7..6..9.2.....4.......51...4..2..3.9..7....6 #    80 NH C23.m/S4.da
..86......4...73..3......9.7..1...8.....2.....6...3..4.3......2..97...1......67.. #   334 NH C21.m/S4.da
..97......8...92..7......1.6..3...7...........9...2..5.2......9..61...3......48.. #   210 NH C20.m/S4.da

# ED=2.3/1.2/1.2 Naked Single
.1.....8...8...3.....6.2.....6.4.5...7.....1...5.2.8.....1.9.....2...4...9.....7. #    24 FN C20.m/S4.hv
4..5..3...8..7..5...9..4..78..1..7...6..4..8...5..7..11..6..2...9..5..3...6..8..9 #    14 FN C27.m/S4.da
1..9..3......7..8...4..1..24.....9...2..3..7...6.....36..7..5...7..2......2..5..6 #    17 FN C23.m/S4.da
...........12.34...234.567..32...86.....3.....85...91..673.924...46.13........... #    14 FN C29.m/S8.f
...6.......8..7..4.3..4..9.8..9..6....7..5..3.9..3..2....2.......4..9..5.6..1..4. #    23 FN C23.m/S2.d
.1..2.3..24.........5.....6...1..7..1...3..8......5..45..8...7.....9.1....4..6... #    13 FN C21.m/S2.d
.......1......2.34..5.6.......3...5...6.7.8...7...9.......5.9..39.8......1....... #    23 FN C19.m/S4.da
6....1..9.2..7..3...73.......3.....4.8..4..2.9.....3.......46...7..8..4.5..9....2 #    20 FN C23.m/S4.da
..79......4...73..6......9.5..1...8.....2.....6...3..2.3......6..97...1......49.. #    24 FN C21.m/S4.da
.....435.3...9....8..2.....6.....9...1..5..2...7.....1.....3..7....4...6.728..... #    18 FN C21.m/S4.r

# ED=2.5/1.2/1.2 Direct Hidden Triplet
1...2...3.8.....4....7.1.....5...6..7...4...1..4...9.....8.5....6.....7.2...3...6 #    42 FNBT C21.m/S8.f
1..2.3..4...........5.6.7..6.......2..7.1.5..2.......3..8.9.4...........3..6.1..9 #    29 FNBT C21.m/S8.f
.....123.4...5....6..7.....5.....8...9.....1...6.....4.....9..7....4...6.173..... #    26 FNBT C20.m/S4.r
.....1.2..3...4.....43..5..6......1...7.2.8...4......3..8..27.....7...6..1.4..... #    54 FNBT C21.m/S2.p
.....1..2.3.....4...156......7..31....5.8....6..4........7..5...4.....3.8.......6 #    49 FNBT C20.m/S2.d
.9.....8.7.6...5.4.3.2.1.6...1.6.4.....9.5.....5.1.6...4.7.8.5.3.7...8.2.5.....4. #    39 FNBT C28.m/S8.f
......1.2.3...4.5...6.1.......6...2...1.7.6...8...5.......2.7...5.3...9.7.8...... #    51 FNBT C21.m/S2.p
.9......23....4.......5.6.......5.3...7.8.4...8.2.......5.2.......9....16......9. #    50 FNBT C19.m/S4.da

# ED=2.6/1.2/1.2 Pointing
.1.....2...2...7.....3.8.....8.3.2...7.....9...3.6.4.....9.1.....4...6...9.....5. #    21 FNB C20.m/S4.hv
...........59.73...835.679..16...97.....9.....72...83..271.965...98.51........... #    17 FNB C29.m/S8.f
..6..82...1.....3.4..2....7..94....6.........7....51..2....1..5.8.....9...39..4.. #    23 FNB C22.m/S4.da
...........43.16...3.5.4.1..21...34...........49...27..1.8.5.3...26.98........... #    23 FNB C24.m/S8.f
.......5......6.12..8.4.......5...9...1.2.3...4...8.......1.4..95.3......2....... #    20 FNB C19.m/S4.da
5....37297...8....6..2.....8..9.76...6.....9...43.6..5.....2..1....3...81834....7 #    15 FNB C28.m/S4.r
.1......27.3.......4..6.9.....2....8..9.7..6......45....6..51......9..3.8..6....4 #    17 FNB C22.m/S2.d
1....2..3.7..8..9...85.......3.....4.5..1..8.2.....9.......37...9..6..2.6..4....5 #    17 FNB C23.m/S4.da
..26......4...75..9......8.6..3...1.....4.....5...6..9.1......7..42...3......54.. #    28 FNB C21.m/S4.da
4....1.2...73..9...8..6...1.2.....8...1.8...39.....7...1...95..6..2....8..3.7..1. #    17 FNB C25.m/S2.d

# ED=2.8/1.2/1.2 Claiming
9..3..1...5..7..9...7..8..31..7..9...4..3..8...9..4..18..5..4...6..8..7...4..3..2 #    23 FNB C27.m/S4.da
..8..52...3.....7.9..1....5..97....1.........7....68..5....1..7.4.....6...79..4.. #    28 FNB C22.m/S4.da
.1..6.9..23.........4.....8...2..1..1...5..7......4..35..7...1.....8.5....3..6... #    38 FNB C21.m/S2.d
3....82691...3....4..2.....7..9.35...1.....9...98.1..7.....7..6....8...58375....4 #    32 FNB C28.m/S4.r
.....12...4..8..6.1..5.....6...9.7...3.2.8.9...4.6...5.....3..9.8..5..3...58..... #    27 FNB C24.m/S4.r
58.............94.7...31...8..4..2...4.2.5.1...5..3..7...64...2.52.............36 #    30 FNB C24.m/S2.p
..18......5...76..2......3.8..2...9.....4.....6...1..5.8......4..23...8......57.. #    25 FNB C21.m/S4.da
..12......3...45..2......6.7..1...2...........4...3..8.5......4..46...1......83.. #    31 FNB C20.m/S4.da
..37......9...45..8......3.3..1...8.....2.....4......9.2......4..63...1......69.. #    25 FNB C20.m/S2.d
..12......3...41..5......6.1..6...5.....3.....7...8..6.8......2..61..........78.. #    22 FNB C20.m/S2.d

# ED=3.0/1.2/1.2 Naked Pair
.4.....6...5...3.....9.2.....1.8.5...6.....9...3.7.8.....3.1.....8...7...9.....2. #    44 FNBT C20.m/S4.hv
7..6..4......2..7...2..4..81.....9...8..7..1...5.....32..3..6...5..8......8..9..2 #    36 FNBT C23.m/S4.da
...........64.92...375.146..65...94.....4.....94...17..436.879...97.36........... #    50 FNBT C29.m/S8.f
.1..2.3..45.........6.....1...2..7..8...7..9......1..83..9...7.....8.2....8..6... #    44 FNBT C21.m/S2.d
..18......4...79..8......3.9..1...8.....2.....6...9..3.9......4..37...1......57.. #    30 FNBT C21.m/S4.da
..12......3...49..6......7.8..9...1.....2.....4......5.8......4..71...5......23.1 #    52 FNBT C21.m/S2.d
......72....25......9...38..5......4.2..6...9.....8...3.8...9..5.6.........41.... #    64 FNBT C20.m/S2.d
..17......9...45..8......3.3..1...7.....5.....4......6.2......9..53...1......94.. #    41 FNBT C20.m/S2.d
.....123.4...5....6..7.....2.....4...8.....1...7.....5.....3..9....7...6.318..... #    54 FNBT C20.m/S4.r
..1..23...4..5..1.6.......4...6.......2.1.7.......3...8.......3.6..7..9...74..2.. #    49 FNBT C21.m/S2.p

# ED=3.2/1.2/1.2 X-Wing
1..2..3...2..1..4...3..5..66..1..5...4..9..7...8..4..22..8..9...3..6..2...9..2..7 #  1046 FNBW C27.m/S4.da
6...7...3.4.....8....9.1.....6...7..5...3...6..4...2.....4.3....8.....1.1...6...5 #   789 FNBW C21.m/S8.f
...........87.62...798.241..32...75.....2.....94...62..256.719...71.95........... #  1809 FNBW C29.m/S8.f
...436.....9...3...8.....1.8....7..11.......34..3....2.3.....6...7...4.....281... #  1040 FNBW C22.m/S4.da
.1..2.3..45.........6.....1...2..7..8...7..9......1..83..4...7.....8.2....8..6... #   800 FNBW C21.m/S2.d
.......6......1.23..7.5.......6...8...5.8.7...4...2.......1.8..92.7......3....... #  3867 FNBW C19.m/S4.da
1....23453...1....6..7.....2..5.16...6.....5...42.6..8.....7..6....2...97293....1 #  1814 FNBW C28.m/S4.r
..57......8...92..3......1.6..3...7...........4...8..5.2......4..71...3......38.. #  2840 FNBW C20.m/S4.da
......12....23......4...56..2......7.3..8...4.....1...6.1...9..5.8.........84.... #   796 FNBW C20.m/S2.d
..67......9...45..3......6.2..1...7.....2.....4......9.2......4..53...1......69.. #  1818 FNBW C20.m/S2.d

# ED=3.4/1.2/1.2 Hidden Pair
..8...5...65...97.17.....32...3.2......718......9.6...52.....14.86...72...4...6.. #   149 FNBH C27.m/S4.hv
2..8..6...4..9..7...1..7..91..4..8...6..7..5...3..5..45..9..7...8..5..3...4..2..8 #    89 FNBH C27.m/S4.da
.41.....58.7......39.8.......6.35......1.6......29.7.......1.43......8.62.....91. #   153 FNBH C24.m/S4.da
.1..8.5..23.........4.....8...6..2..6...1..9......4..35..7...1.....2.6....3..8... #   218 FNBH C21.m/S2.d
.......1......1.23..4.5.......3...4...5.6.7...8...9.......4.8..32.6......9....... #    92 FNBH C19.m/S4.da
51.............53.7...81...2..4..6...4.2.5.1...6..3..5...14...3.92.............86 #   151 FNBH C24.m/S2.p
..26......4...75..3......2.6..3...1.....8.....5...4..6.8......5..12...3......94.. #   212 FNBH C21.m/S4.da
..37......6...45..7......2.4..1...7.....2.....8......2.5......6..23...1......68.. #    85 FNBH C20.m/S2.d
.....123.4...5....6..7.....5.....3...3.....8...6.....4.....2..9....4...6.198..... #   229 FNBH C20.m/S4.r
.3......68......9...1..42......154.....3.2.....586......29..5...6......43......7. #    89 FNBH C22.m/S4.da

# ED=3.6/1.2/1.2 Naked Triplet
.....9..8.1.....5...724......4..27....6.5....2..3........7..2...8.....6.1.......3 #    57 FNT C20.m/S2.d
.....85...1..2..3....6....9..95......7...2...6...3..4.9.....6...3...7.1...5.....8 #    93 FNT C21.m/S2.d
.1.....8...8...2.....7.4.....2.9.3...8.....7...6.5.9.....6.2.....9...5...7.....4. #    60 FNBT C20.m/S4.hv
1...2...3.7.....4....8.6.....2...9..3...4...5..6...1.....5.7....6.....8.5...3...9 #    88 FNBT C21.m/S8.f
...........84.79...375.146..65...34.....3.....24...17..436.879...27.36........... #    50 FNBT C29.m/S8.f
...1.......2..3..4.5..4..2.9..4..3....7..1..2.8..5..6....3.......9..8..1.3..7..8. #    91 FNBT C23.m/S2.d
52.............54.7...84...8..4..1...7.2.5.6...6..3..7...67...3.92.............86 #    97 FNBT C24.m/S2.p
..64......8...92..7......4.1..3...6...........9...1..8.1......9..76...3......58.. #    66 FNBT C20.m/S4.da
.....123.4...5....6..7.....5.....7...3.....8...4.....6.....3..8....6...4.892..... #    60 FNBT C20.m/S4.r
..1..23...2..8..5.6.......7...5.......4.6.9.......7...3.......8.7..5..2...96..1.. #    91 FNBT C21.m/S2.p

# ED=3.8/1.2/1.2 Swordfish
..1...2.....1.3...3...2...4.1.5.6.2...7...6...8.9.4.1.6...5...8...3.8.....5...7.. #  1561 FNBW C24.m/S8.f
..12......3...45..6......7.2..8...6.....5.....4...9..3.7......4..61..........53.. #  1566 FNBW C20.m/S2.d
..1..23...4..5..6.6.......7...4.......3.8.1.......9...4.......6.7..2..4...23..9.. #  1566 FNBW C21.m/S2.p
...1.2......3.4.....4.5.2...6.....7...32.89..7.......11.......3..8.9.4...7.....6. #  1561 FNBW C22.m/S2.v
1....2..3..4.5.....2.6.......5..7..8.6.....2.4.....6...8...3.9...6.4.5.....9....2 #  1555 FNBW C22.m/S2.a
.1.....2...3...4.....5.1.....6.4.5...7.....8...4.5.9.....6.9.....5...6...8.....1. #  2581 FNBW C20.m/S4.hv
...........91.57...539.241..61...59.....3.....94...37..162.394...58.12........... #  1549 FNBW C29.m/S8.f
1....23455...4....6..7.....3..8.71...6.....8...12.6..3.....8..4....2...12581....6 #  2577 FNBW C28.m/S4.r
..12......3...45..6......7.2..6...1...........4...5..3.5......4..21...6......83.. #  2585 FNBW C20.m/S4.da
..1.2..3.34...5.6...5...1.4.7..8....1..6.7..8....1..9.8.7...9...1.9...23.3..5.6.. #  1557 FNBW C28.m/S4.r

# ED=4.0/1.2/1.2 Hidden Triplet
...........93.78...125.963..68...57.....3.....35...12..817.639...61.37........... #   605 FNBH C29.m/S8.f
..8..52...3.....7.9..3....5..97....2.........7....61..5....1..3.4.....6...79..8.. #   538 FNBH C22.m/S4.da
.1..2.3..45.........6.....7...5..6..8...1..7......3..47..4...1.....5.2....8..9... #   540 FNBH C21.m/S2.d
..12......8...92..5......3.2..3...1...........9...7..8.7......9..41...5......38.. #   537 FNBH C20.m/S4.da
...1.2.3.1.....4...23..45..4.67.3..8.........3..8.16.4..89..14...9.....6.1.2.7... #   534 FNBH C28.m/S4.r
...8...4...2...6...1..2...34..7...9...1.3.5.......6....2..1..8.8..6..9....4...... #   598 FNBH C21.m/S2.d
..1..2..3.4..7.5..8..6...9...2.....1.1..8..2.3.....7...9...6..7..5.1..4.2..9..3.. #   537 FNBH C25.m/S4.da
..8...7...3...4.5.2.......6...7...3.....1.4...5...2...7...6...1.6.5...2...2...8.. #   540 FNBH C21.m/S2.d

# ED=4.2/1.2/1.2 XY-Wing
.7.....8...6...3.....9.8.....4.2.5...8.....1...9.3.2.....7.1.....2...6...3.....7. #   275 FNBY C20.m/S4.hv
1..2..3...2..1..4...3..5..67..6..8...5..8..7...8..4..18..7..4...4..6..2...9..2..7 #   271 FNBY C27.m/S4.da
1..9..3......7..8...3..1..24.....9...2..3..7...6.....36..8..1...7..2......2..5..6 #   270 FNBY C23.m/S4.da
...........37.68...461.325..95...13.....1.....18...92..312.564...24.85........... #   268 FNBY C29.m/S8.f
.......1......1.23..4.5.......2...4...5.1.6...7...8.......4.7..82.9......6....... #   279 FNBY C19.m/S4.da
..14......4...96..2......5.1..3...2.....7.....8...4..1.9......8..52...3......19.. #   525 FNBY C21.m/S4.da
..12......3...45..6......7.7..6...1...........4...5..6.5......8..27...6......83.. #   271 FNY C20.m/S4.da
..12......3...49..9......7.7..9...8.....7.....4......3.2......4..61...5......83.1 #   275 FNBY C21.m/S2.d
..1..9..3.4.....5.6...7.1.....8.3..7..9...5..2..6.7.....6.3...1.5.....8.4..1..9.. #   270 FNBY C24.m/S4.da
4....2.6...71..5...3..6...7.7.....8...8.2...53.....6...4...63..9..5....2..5.7..9. #   269 FNBY C25.m/S2.d

# ED=4.4/1.2/1.2 XYZ-Wing
.3.....8...7...6.....4.5.....6.1.5...8.....4...9.6.1.....3.2.....1...7...4.....3. #   274 FNBY C20.m/S4.hv
1..2..3...4..5..6...7..6..87..3..6...2..8..1...3..1..44..6..8...8..4..3...2..5..7 #   269 FNBY C27.m/S4.da
1..8..4......6..9...7..5..36.....5...7..3..2...4.....12..6..1...9..8......5..7..4 #   527 FNBY C23.m/S4.da
...........75.14...123.456..48...23.....3.....76...18..842.365...31.87........... #   530 FNBY C29.m/S8.f
.......6......3.54..9.1.......8...9...1.2.3...5...6.......9.8..46.5......7....... #   289 FNBY C19.m/S4.da
51.............53.7...81...2..4..6...4.2.5.1...6..3..5...64...7.32.............29 #   275 FNBY C24.m/S2.p
..93......4...23..8......9.6..1...8.....2.....7...3..1.3......2..79...1......14.. #   278 FNBY C21.m/S4.da
..12......3...45..6......7.8..1...6...........4...5..3.9......5..76...2......34.. #   283 FNBY C20.m/S4.da
..1..2..3.4.....5.2...5.6.....4.6..7..8...3..9..5.8.....3.7...5.9.....6.4..2..8.. #   275 FNBY C24.m/S4.da
.....12...2..3..4.5.67..1..4.....8...3.....1...7.....3..9..36.7.5..8..9...16..... #   270 FNBY C24.m/S4.r


Puzzles with an Aligned Triplet Exclusion as the most difficult move. One has a BUG type 1, several have turbot fish, but otherwise nothing more difficult than an xyz-wing is required to solve.

Code: Select all

...123....4..5..6..........2.......736..4..524.......1..........8..6..4....712... # ED=7.5/1.2/1.2
.63.....25.2......89.4.......1.73......1.4......58.7.......7.34......8.79.....56. # ED=7.5/2.0/2.0
1....82652...3....7..1.....6..3.95...1.....9...58.1..7.....3..6....8...43645....9 # ED=7.5/7.5/2.6
.....12...1..3..4.3..5.....4...6.7...8.3.5.9...5.4...6.....2..7.4..9..8...76..... # ED=7.5/7.5/7.5
87.............29.4...35...9..6..5...5.2.1.4...1..7..6...17...8.83.............69 # ED=7.5/7.5/2.6
1.......2.2..3..4...52.67....43.89......6......69.12....14.36...5..9..3.4.......8 # ED=7.5/7.5/7.5
..7..5..9.2..6.1..4..9...7...6.....5.4..8..2.7.....8...1...9..6..3.5..9.6..8..3.. # ED=7.5/7.5/7.5
1.2...3.......9.4.9...7...8...7...5...6.9.1...2...3...7...8...6.5.9.......3...5.4 # ED=7.5/7.5/7.5
..........12..3..4.56..1..3....1..7....3..8...68..7..9....2.4.....5...1..97..6..5 # ED=7.5/7.5/7.5
..6.4.1...4...8.2.5.....3.4...4...9.7...6.2...5...2...4.7.5...1.9.8...7...5...6.. # ED=7.5/7.5/7.5

[edit: added aligned triplet puzzles]

[PIsaacson]

It is possible to compile Java code into native machine code using the GNU gcj compiler. Instead of a virtual java machine interpreter, it literally uses several libraries (libgcj/libgcjgc...) to provide standard Java service functions. I used this technique several years ago on some Java code to "cheaply" halve the process time. I don't have gcj on my current mingw installation and I don't see where there is one easily available other than on cygwin and/or linux, so I'll try building a mingw gcj using the latest gcc 4.5.1 source code. If I'm successful, it might help with the decisions of whether or not to convert/rewrite various SE algorithms into C/C++.

As for "blind porting" Java to C or C++, using C++ and STL in lieu of the Java classes is probably much easier than converting to standard C. Again, this is from some heavy lifting of Java code to C++ when we were looking for more than a doubling of speed. Essentially, we finally redesigned internal structures and algorithms using C++/STL/Boost to simplify the code and vastly reduce the processing time.

If we take the time to define a relatively complete set of techniques (including things such as sk-loops, exocets, ribbons, nrc whips/braids ...) and design a framework that easily allows for additional techniques and scoring algorithm changes, then the project should prove to be very interesting. SInce I use mingw/gnu C++/STL/Boost, that would be my choice for platform development, especially since using the C++ compiler doesn't prohibit writing functions in standard ansi C code.

Cheers,
Paul