n-Rooks / simplex algorithm / bipartite matching

[gusl]

Someone has proposed a better solution to my "constrained n-Rooks" problem that I don't understand.

"constrained n-Rooks": return every possible assignment of rooks to squares on an n x n chessboard, under the constraint that no two rooks threaten each other, and that there are some given squares in which rooks can't be placed.

<< Define a graph with edge weights of zero or one, depending on whether or
not there is an edge. Bipartite matching can be written as an LP.
You find some solution to the problem. Now you want to find the other
optimal solutions. These solutions form a connected set in the polytope,
so you can just to breadth first search with coloring from any starting solution,
only stepping through other optimal solutions. >>

If you understand how bipartite matching relates to my problem, how it can be solved as above, and can explain this to me by this weekend, I'll buy you dinner.

I do not understand the Simplex algorithm.

Comments

[jcreed.livejournal.com]

Well, I see how "constrained n-rooks" is exactly bipartite matching. Bipartite matching is: we've got n vertices on the left x1..xn, and n vertices on the right y1..yn and there are some edges Eij : xi → yj. The goal is to find a collection of edges that cover each vertex (on the left and right) exactly once.

In "constrained n-roocks" we've got x-coordinates x = 1..x = n, and y-coordinates y = 1..y = n, and some cells on the chessboard Eij at (x = i,y = j). The goal is to find a collection of positions such that each column and row is mentioned exactly once.

[jcreed.livejournal.com]

This seems to explain the relationship to LP, though I'm not sure:
http://math.mit.edu/~goemans/18433S07/matching-notes.pdf