Sort all the cells in the grid by their values and keep track of their original positions.

Try dynamic programming with the following states: the current cell that we might select and a bitmask representing all the rows from which we have already selected a cell so far.