I just updated my PADS library to include some quick code for computing minimum spanning trees, via Kruskal's algorithm. Very simple given the prior existence in the library of union-find.

The same update also adds another case to the Sudoku solver's rectangle rule, that I found while trying to solve a "diabolic" puzzle in the LA Times last week. It didn't help solve that puzzle, but I want my program to be able to do anything I know to do by hand...

ETA: The impetus for me to implement this was a query from Mauro Cherobini, who is using minimum spanning trees to cluster spatial messaging data. Apparently the data set size is small enough that it's not necessary to go to an \(O(n\log n)\) Delaunay triangulation based MST algorithm.