Empty while loop with linq/lamba expression

Question

Where I work we're still on .Net 2.0, but I'm somewhat familiar with the 3.0/3.5 stuff. I wanted to get some practice using linq/lambda expression in C# so I wrote a simple Sudoku solver using a lot of generic List<T> and lambda expressions with the aggregate methods it provides.

In my solver, I have this at the top of the solver algorithm:

private Puzzle RecursiveSolve(Puzzle p, int idx)
{
 // start with simple filter to narrow down recursive paths
 // puzzle is still solved without this line, but it takes at least 20x longer
 while( p.board.Any(cell => cell.FilterPossibles()) );  // while(); <- empty while loop is intentional

As you can probably tell, it's a simple recursive algorithm, but I did optimize it a bit to get the run time down to something reasonable (3.6s for the toughest puzzle I could find on google).

To understand the snippet, Puzzle.board is a List<Cell>, and Cell.FilterPossibles() checks each cell's possible values against the values of other Cells in the same row, column, and 3x3 box to see if it can eliminate any. If it gets down to one possible it sets the value for the cell and returns true. Otherwise it returns false. So that while loop will run as long as at least one cell on the board changed (was solved) with the previous iteration.

What concerns me is that the while loop is empty. It amounts to a code smell and tells me I'm probably missing something. Is there a way I could write this as a statement, rather than a loop?

I actually have a whole bunch of questions as the result of this project: (Have I unknowingly implemented some interfaces I could tell the compiler about? Are my function choices generally appropriate? I have a lot of boolean methods to simplify the expressions: how could that be better? How could I better architect this to possible use immutable Puzzle/Cell objects?) But this is the one that's nagging at me the most right now.

Answer 1

An empty while loop suggests either a bug or side-effects - in this case it sounds like it's side-effects, changing the board.

What would be "LINQ-like" (but not necessarily efficient - it really depends) is to make the puzzle yield an iterator of boards - performing another iteration would return a new board (side-effect-free).

I'm not really "up" with exactly what you're doing, so it may not be appropriate - but that would be my first line of enquiry.

Other than that, I'd probably think about rewriting it somehow to make it more obvious that you do have side-effects - but again, without knowing your code it's hard to say exactly how that would work.

Answer 2

I'm not really opposed to empty loops, I use them relatively often in C++ – albeit qualifying the body as { } which is much clearer IMHO.

However, I don't get your code which seems to indicate that there's indeed code smell or at least that it could be formulated in a clearer way.

What I don't get in particular is the fact that Any returns a single boolean value, once. How does this tie together with a loop? The side-effect here is really non-obvious (you modify the contents of p.board?) … seems too clever, somehow.

Answer 3

I think an Extract Method with an appropriate name might be useful here. It won't eliminate the smell but you can move it away from the very first line in your RecursiveSolver. (I could imagine reading it and hitting a brick wall right away).

It is OK to have terse one liners like this but it would look better with a well named method...

Renaming FilterPossibles() could do wonders...That method is doing more than its saying...