Hi Alejandra! Did you know we also solved this as an example for WFR`DepthFirstSearch? The code is under "Neat Examples", and I reproduce it here for purpose of a timing test:
The time for System is only
$3$ to
$4\times$ faster than WFR, when the compile advantage could very well be
$10\times$ or more. Time can depend on a lot of things, including optimization mistakes made by the programmer. Instead, we can just trace the computation and ask how many nodes did the search tree have? Answers to this question are typically order-dependent, and search trees can be minimized through heuristics. There's a sizeable literature on this. For example, I'm sure that Donald Knuth has written about it in connection with exact cover problems.
Unfortunately, we don't know much what's going on under the hood of FindIndependentVertexSet, so it's not possible presently to compare the search trees directly. Maybe you can ask Charles or Yan if they know how to trace search trees or at least output statistics about vertex count per level.
If you want to be more "independent", you can also try to write your own search code starting from the queen graph and iterating through successive placements by deleting vertices. This could be done depth-first using DepthFirstSearch, or breadth-first using NestWhileGraph. Right away there is an issue, should the first choice have a branching ratio
$8$ or
$8^2$ or something else?
If you can figure out how to compare search trees, and potentially minimize them, that would make an interesting chapter in our upcoming book about game theory.
