梁剑的Blog

#include <iostream>
#include <cstdlib>
#include <cstdio>
 
using namespace std;
 
class CShuDu
{
	public:
		CShuDu()
		{
			_iLeft = 0;
			_GuestCount = 0;
			_Depth = 0;
			_CurrentX = _CurrentX = 0;
		};
		~CShuDu(){};
		void GetInput()
		{
			for( int i = 0; i < 9; i++ )
			{
				for( int j = 0; j < 9; j++ )
				{
					int n;
					cin >> n;
					switch(n)
					{
						case 1:
						case 2:
						case 3:
						case 4:
						case 5:
						case 6:
						case 7:
						case 8:
						case 9:
							_Board[i][j].iType 	= FIXED;
							_Board[i][j].iValue	= n;
							break;
						case 0:
							_Board[i][j].iType 	= BLANK;
							_Board[i][j].iValue	= n;
							_iLeft++;
							break;
						default:
							cout << "Input Error" << endl;	
							exit(-1);
					}
				}
			}
		}
 
		void OutputBoard(int x, int y)
		{
			cout << _GuestCount << "\t" << _Depth << "\t" << _iLeft << "(" << x << "," << y << ")" << endl;
			cout << "\t\t  ";
			for( unsigned int i = 0; i < 9; i++ )
				if( i == y )
					cout << " " << "x  ";
				else
					cout << " " << i << "  ";
 
			cout << endl;
 
			for(unsigned int i = 0; i < 9; i++)
			{
				if( i == x )
					cout << "\t\t" << "x ";
				else
					cout << "\t\t" << i << " ";
				for( unsigned int j = 0; j < 9; j++ )
				{
					if( _Board[i][j].iType == FIXED )
						cout << " " << _Board[i][j].iValue << "  ";
					else
						cout << "(" << _Board[i][j].iValue << ") ";
				}
				cout << endl;
			}
		}
 
		void Guest(int x, int y)
		{
			_Depth++;
			_CurrentX = x;
			_CurrentY = y;
			_GuestCount++;
 
			if( _iLeft == 0 )	
			{
				OutputBoard(-1, -1);
				return;
			}
 
			for( unsigned int i = 1; i <= 9; i++ )
			{
				_Board[x][y].iValue = i;	
				if( IsBoardValid(x, y) )
				{
					int _x = x;
					int _y = y;
					GetNextPosition(_x, _y);
					_iLeft--;
					Guest(_x, _y);
					_iLeft++;
				}
			}
			_Board[x][y].iValue = 0;	
			_Depth--;
		}
 
		void Run()
		{
			int x, y;
			x = y = -1;
			GetNextPosition(x, y);
			Guest(x, y);
		}
 
	private:
		int _iLeft;
		int _GuestCount;
		int _Depth;
		int _CurrentX;
		int _CurrentY;
 
		enum NodeType{ FIXED, BLANK };
		struct Node{
			int iValue;
			int iType;
			bool operator==(const Node &r)
			{
				return iValue == r.iValue;
			}
		};
 
		Node _Board[9][9];
 
		bool IsBoardValid(int x, int y)
		{
			int X = x / 3;
			int Y = y / 3;
			for( unsigned int i = 0; i < 9; i++ )
			{
				if( i == x )
					continue;
				if( _Board[i][y] == _Board[x][y] )
					return false;
			}
 
			for( unsigned int i = 0; i < 9; i++ )
			{
				if( i == y )
					continue;
				if( _Board[x][i] == _Board[x][y] )
					return false;
			}
 
			for( unsigned i = X * 3; i < (X+1)*3; i++ )
			{
				for( unsigned j = Y * 3; j < (Y+1)*3; j++ )
				{
					if( i == x && j == y )
						continue;
					if( _Board[x][y] == _Board[i][j] )
						return false;
				}
			}
		//	OutputBoard(x, y);
			return true;
		}
 
		void GetNextPosition(int &x, int &y)
		{
			if( x == -1 )
				x = 0;
			if( y == -1 )
				y = 0;
			else
			{
				if( y == 8 )
				{
					x++;
					y = 0;
				}
				else
				{
					y++;
				}
			}
 
			while( _Board[x][y].iType == FIXED )
			{
				if( y == 8 )
				{
					x++;
					y = 0;
				}
				else
				{
					y++;
				}
				CheckPosition(x, y);
			}
		}
 
		void CheckPosition(int x, int y)
		{
			if( x >= 9 || y >= 9 )
			{
				cerr << "Position Error" << endl;
				exit(-3);
			}
		}
};
 
int main()
{
	CShuDu cShudu;
	cShudu.GetInput();
	cShudu.Run();
	return 0;
}