理论上应该可以解决N较大的问题。不过回溯所有点。故效率不高。

#include <iostream>
#define N 10

using namespace std;

char map[N*N];
int visit[N*N];
int a[N*N];

bool can_visit(int i,int n)
{
	int x,j;
	x = i/n;
	if( visit[i] != 0 )	return false;
	for ( j = i-1 ; j >= n*x ; j--)
	{
		if( visit[j] == 2 )	break;
		if( visit[j] == 1 )	return false;
	}
	for ( j = i-n ; j >= 0 ; j=j-n)
	{
		if( visit[j] == 2 )	break;
		if( visit[j] == 1 )	return false;
	}
	return true;
}

int next(int i,int n)
{
	//从点i起，寻找下一个可走的点
	for(int j = i ; j < n*n ; j++)
	{
		if(can_visit(j,n))	return j;
	}
	return -1;
}

int back(int n)
{
	int i,j,count,max;
	memset(visit,0,sizeof(visit));
	memset(a,0,sizeof(a));
	for ( i = 0 ; i < n ; i++)
	{
		for ( j = 0 ; j < n ; j++)
		{
			cin>>map[i*n+j];
			if( map[i*n+j] == 'X' )	visit[i*n+j] = 2 ;
			//else	visit[i*n+j] = 2 ;
			//cout<<visit[i*n+j]<<" ";
		}
		//cout<<endl;
	}
	max = 0 ;
	count = 0 ;
	//回溯求解
	while (1)
	{
		if( count > 0 )
		{
			i = next(a[count-1]+1,n) ;
			if( i == -1 )
			{
				//之后的点都不满足，即该回溯了。
				if( count > max )	max = count;
				//回溯,先查看去掉count点后是否还有可用之点。
				visit[a[count-1]] = 0 ;	//标记
				i = next(a[count-1]+1,n) ;
				while( i == -1 )
				{
					if( count == 1 ) return max;
					count--;
					visit[a[count-1]] = 0 ;	//标记
					i = next(a[count-1]+1,n) ;
				}
				visit[i] = 1;
				a[count-1] = i ;
			}
			else
			{
				//之后还有点，故向前
				a[count++] = i ;
				visit[i] = 1 ;
			}
		}
		else
		{
			i = next(0,n);
			if( i == -1 )
				return 0;
			visit[i] = 1 ;
			a[count++] = i ;
		}
	}
}

int main()
{
	int n;//,res;
	cin>>n;
	while (n!=0)
	{
		//res = back(n);
		cout<<back(n)<<endl;
		cin>>n;
	}
	return 0;
}