If a "step" is changing out a row or column, then your goal is to do the change-outs that will affect the most Xes before you do those that cover fewer.
The way to figure that out is to traverse the entire array once and keep track of the number of Xes in each row and column. For a minor variant on your example, the end result of that calculation would look like this:
C C C
1 2 3
R1 X X X -- 3 Total
R2 0 X 0 -- 1 Total
R3 0 X 0 -- 1 Total
| | |
1 3 1 Totals
Break that information out into a list (read each item as "3 Xes in Row 1", "1 X in Row 2", etc.):
3/R1 1/R2 1/R3 1/C1 3/C2 1/C3
A descending sort of the counts makes it pretty obvious which one to change out first:
3/R1 3/C2 1/R2 1/R3 1/C1 1/C3
Change out R1, make note of that as your first step and remove it from the list. When you change out a row with Xes, the columns that contained those Xes (all of them in this case) now contain one less. This means you have to reduce the count in each column where you found an X:
0/C1 1/R2 1/R3 2/C2 0/C3
That change blows the sort order right out of the water, because now the item that's going to wipe out the most Xes is no longer up front. A re-sort fixes that and reveals column 2 as the next step:
2/C2 1/R2 1/R3 0/C1 0/C3
After a change-out, decrement and re-sort, you're down to this:
0/R2 0/R3 0/C1 0/C3
A zero first element means you've reached the end because anything following it will also be zero, meaning no more Xes in the array. Anything else means you repeat the process.
Not only will you get the number of steps out of this, you'll also get a list of what those steps are.
You also don't necessarily have to do a sort, either. You can simply traverse the list each time, and hold onto the element with the largest count. If you're using a language that has a sorted collection available, writing this would be a piece of cake.