UVA 11214 Guarding the Chessboard ( IDDFS )

UVa Online Judge
Store the information of a queen set by the row, column and both diagonals it occupies in order to accelerate the search. A little prune used is to skip decisions that will not occupy any line.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10 + 2;
const int MAXM = 10 + 2;

int n, m;
char G[MAXN][MAXM];
bool vis[4][MAXN + MAXM];

bool match(){
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if( G[i][j] == 'X' )
                if( !vis[0][i] && !vis[1][j] && !vis[2][i + j] && !vis[3][i - j + 10] )
                    return false;
    return true;
}

int maxd;
bool dfs(int cnt, int pos){
    if( cnt == maxd ) return match();
    for(int i = pos; i < n * m; ++i){
        int r = i / m, c = i % m;
        bool v0 = vis[0][r], v1 = vis[1][c], v2 = vis[2][r + c], v3 = vis[3][r - c + 10];
        if( v0 && v1 && v2 && v3 ) continue; // makes no help
        vis[0][r] = vis[1][c] = vis[2][r + c] = vis[3][r - c + 10] = true;
        if( dfs( cnt + 1, i ) ) return true;
        vis[0][r] = v0, vis[1][c] = v1, vis[2][r + c] = v2, vis[3][r - c + 10] = v3;
    }
    return false;
}

int main(){
    int kase = 0;
    while( scanf("%d %d", &n, &m) == 2 ){
        memset( vis, 0, sizeof(vis) );
        for(int i = 0; i < n; ++i)
            scanf("%s", G[i]);
        for(maxd = 0; !dfs( 0, 0 ) && maxd < 5; ++maxd) ;
        printf("Case %d: %d\n", ++kase, maxd);
    }
    return 0;
}