Finding the largest square submatrix with identical rows

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
//#include "sequence_lister.h"

using namespace std;

int n, m;       // n = number of rows, m = number of cols
vector<vector<int> > x;     // x[i][j] = number at row i+1, col j+1
int biggest = 0;
unsigned long long nSearchNodes = 0;
unsigned long long nDominancePrunings = 0;
unsigned long long nFathomed = 0;
unsigned long long nFathomedByRowCount = 0;

// The partial solution so far is the set of rows in rows.
// Every column in cols is identical across these rows.
// The first row to consider adding next is nextRow.
// We can reorder rows freely in x[][] from nextRow on down.
// E.g. we can pick any row at or below nextRow and swap it with
// the row at nextRow.
void solve(vector<int>& rows, int nextRow, vector<int>& cols) {
    //cerr << "solve(rows=" << list_sequence(rows) << ", nextRow=" << nextRow << ", cols=" << list_sequence(cols) << ") called.\n";     //DEBUG
    ++nSearchNodes;
    //if (cols.empty()) {
    //if (cols.size() < biggest) {
    if (cols.size() <= biggest) {
        // We've run out of options.
        if (!cols.empty()) {
            ++nFathomed;
        }

        return;
    }

    if (nextRow == n) {
        // No more rows to try adding.
        return;
    }

    // First look for the best row to branch on.  A good approximation is
    // to pick the one that results in the fewest remaining columns.
    // But we override this with a (probably very strong) domination rule:
    // Whenever we can add a row without shrinking cols at all, we can
    // immediately do it, and we never have to consider not adding it.
    //HACK: This will wind up just picking the 1st row on the very first call,
    // but that's not so bad.
    int iBestRow;
    bool canForceIn = false;
    int nBestSameCols = INT_MAX;
    int nPotentialRows = 0;
    for (int i = nextRow; i < n; ++i) {
        int nSameCols = 0;
        for (int ic = 0; ic < cols.size(); ++ic) {
            if (rows.empty() || x[i][cols[ic]] == x[rows.front()][cols[ic]]) {
                ++nSameCols;
            }
        }

        if (!rows.empty() && nSameCols == cols.size()) {
            // We can stop right here, we have a winner ;)
            iBestRow = i;
            canForceIn = true;
            break;
        }

        if (nSameCols < nBestSameCols) {
            iBestRow = i;
            nBestSameCols = nSameCols;
        }

        if (nSameCols >= biggest) {
            ++nPotentialRows;
        }
    }

    if (!canForceIn && rows.size() + nPotentialRows <= biggest) {
        // Even if all the rows that match at least biggest columns were to be compatible
        // (i.e. match on the same columns), there still wouldn't be enough rows to
        // make a difference.
        ++nFathomedByRowCount;
        return;
    }

    // Rearrange x[][] so the chosen row comes next.
    swap(x[nextRow], x[iBestRow]);

    // Try forcing this row in.
    vector<int> newCols;

    if (canForceIn || !rows.empty()) {
        // Form the reduced set of columns.
        for (int i = 0; i < cols.size(); ++i) {
            if (x[nextRow][cols[i]] == x[rows.front()][cols[i]]) {
                newCols.push_back(i);
            }
        }
    } else {
        // Otherwise just leave the set of columns at the complete set.
        //TODO: Could maybe speed up by avoiding the copy somehow.
        newCols = cols;
    }

    rows.push_back(nextRow);
    //if (rows.size() > biggest && newCols.size() > biggest)
    if (rows.size() > biggest && newCols.size() >= biggest) {       // Let's also report when we get a taller solution of the same width
        //biggest = newCols.size();
        biggest = min(newCols.size(), rows.size());
        cerr << "New solution of size " << biggest << " found with width " << newCols.size() << ", height " << rows.size() << "!\n";
    }

    solve(rows, nextRow + 1, newCols);

    // Try forcing this row out -- but only if we have to!
    rows.pop_back();
    if (!canForceIn) {
        solve(rows, nextRow + 1, cols);
    } else {
        ++nDominancePrunings;
    }
}

int main(int argc, char **argv) {
    cin >> n >> m;

    cerr << "About to read in a " << n << '*' << m << " matrix...\n";

    x.resize(n, vector<int>(m, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> x[i][j];
        }
    }

    cerr << "Read in a " << n << '*' << m << " matrix.\n";

    vector<int> rows;
    vector<int> cols;
    for (int i = 0; i < m; ++i) {
        cols.push_back(i);
    }

    solve(rows, 0, cols);

    cerr << "Finished.  Biggest solution has width " << biggest << " (and at least the same height).\n";
    cerr << nSearchNodes << " search nodes evaluated; " << nDominancePrunings << " nodes could be pruned due to dominance; " << nFathomed << " fathomed via B&B columns; " << nFathomedByRowCount << " fathomed via B&B rows.\n";
    return 0;
}