数独をプログラムで解いてみる。

とりあえず、一番単純な方法で、各マスに関して１〜９のうち一つだけしか入れない数値を入れていく方法。

template< int SIZE_ = 3 >
class Sudoku2DSolver
{
public:
	enum{ 
		SIZE = SIZE_,
		SIZE_2 = SIZE * SIZE,
	};

	Sudoku2DSolver();
	virtual ~Sudoku2DSolver(){}

	//初期データ挿入
	bool AddData( int x, int y, int value );

	//解く。
	enum SOLVE{ SUCCESS, NON, PLURAL, };
	SOLVE Solve();

	//結果。０は未定
	int Get( int x, int y ){ return m_Num[y][x]; }

protected:
	//座標変換
	int GetX( int block, int num ){ return (block%SIZE)*SIZE+num%SIZE; }
	int GetY( int block, int num ){ return (block/SIZE)*SIZE+num/SIZE; }
	int GetBlock( int x, int y )const{ return (x/SIZE) + (y/SIZE)*SIZE; }
	int GetBlockNum( int x, int y )const{ return (y%SIZE)*SIZE + x%SIZE; }

	//挿入
	void InputData( int x, int y, int value );

	//単純に１個埋める
	bool SolveInsert( int x, int y );

private:
	//数値データ。０は未決定
	int m_Num[SIZE_2][SIZE_2];
	//入れることが出来る数値。[y][x][value]
	bool m_check[SIZE_2][SIZE_2][SIZE_2+1];
	//現在埋まっている数
	int m_fillAll;
};


//----------------------------------------------------------------------------------------------------------------

template< int SIZE_ >
Sudoku2DSolver< SIZE_ >::Sudoku2DSolver()
{
	//データ初期化
	std::fill( m_Num[0], m_Num[0] + SIZE_2 * SIZE_2, 0 );
	std::fill( m_check[0][0], m_check[0][0] + SIZE_2 * SIZE_2 * (SIZE_2+1), true );
	m_fillAll = 0;
}

template< int SIZE_ >
bool Sudoku2DSolver< SIZE_ >::AddData( int x, int y, int value )
{
	if( m_check[y][x][value] ){
		InputData( x, y, value );
		return true;
	}else{
		return false;
	}
}

template< int SIZE_ >
void Sudoku2DSolver< SIZE_ >::InputData( int x, int y, int value )
{
	//入れる
	m_Num[y][x] = value;
	//チェックする。
	for( int x_sub = 0; x_sub < SIZE_2; ++x_sub ){
		m_check[y][x_sub][value] = false;
	}
	for( int y_sub = 0; y_sub < SIZE_2; ++y_sub ){
		m_check[y_sub][x][value] = false;
	}
	const int block = GetBlock( x, y );
	for( int num = 0; num < SIZE_2; ++num ){
		m_check[GetY(block,num)][GetX( block, num )][value] = false;
	}
	//カウントする
	++m_fillAll;
}

template< int SIZE_ >
typename Sudoku2DSolver< SIZE_ >::SOLVE Sudoku2DSolver< SIZE_ >::Solve()
{
	while( m_fillAll < SIZE_2 * SIZE_2 ){
		const int pre = m_fillAll;
		//縦横ブロックで１つしか入れない場所を埋める。
		for( int y = 0; y < SIZE_2; ++y ){
			for( int x = 0; x < SIZE_2; ++x ){
				if( m_Num[y][x] == 0 ){
					if( !SolveInsert( x, y ) ){
						//失敗
						return NON;
					}
				}
			}
		}
		if( pre == m_fillAll ){
			//変化なし
			return PLURAL;
		};
	}
	//完成。
	return SUCCESS;
}

template< int SIZE_ >
bool Sudoku2DSolver< SIZE_ >::SolveInsert( int x, int y )
{
	int insert = 0;
	for( int v = 1; v < SIZE_2+1; ++v ){
		if( m_check[y][x][v] ){
			if( insert == 0 ){
				insert = v;
			}else{
				//候補が２つ以上ある。
				return true;
			}
		}
	}
	if( insert == 0 ){
		//入れられるデータが存在しない
		return false;
	}
	InputData( x, y, insert );
	return true;
}

無駄にテンプレートを使って大きいのにも対応しています。
簡単な問題ならこれで大抵解けますが、ちょっと難しくなっていくとこれでは解けません。そういう場合はどうするか？試しに適当に一つマスを埋めてまた解いてみてダメなら別の数値を入れていきます。これを繰り返せば原理上、どんな問題も解けます。

#include "Sudoku2DSolver.h"


template< int SIZE_ = 3 >
class Sudoku2D
{
public:
	enum{ 
		SIZE = SIZE_,
		SIZE_2 = SIZE * SIZE,
	};

	Sudoku2D():m_Result(Sudoku2DSolver< SIZE_ >::SUCCESS){}
	virtual ~Sudoku2D(){}

	//初期データ挿入
	bool AddData( int x, int y, int value );

	//解く。解の数を返す。
	//０なら解なし。２以上なら複数解がある。
	int Solve();

	//結果
	int Get( int x, int y, int solve = 0 );

private:
	//数値データ。０は未決定
	//int m_Num[SIZE_2][SIZE_2];

	//単体実行
	Sudoku2DSolver< SIZE_ > m_Solver;
	typename Sudoku2DSolver< SIZE_ >::SOLVE m_Result;
	//複数解
	std::vector< std::shared_ptr< Sudoku2D< SIZE_ > > > m_apSolve;
};

template< int SIZE_ >
bool Sudoku2D< SIZE_ >::AddData( int x, int y, int value )
{
	return m_Solver.AddData( x, y, value );
}



template< int SIZE_ >
int Sudoku2D< SIZE_ >::Solve()
{
	//普通に処理する。
	m_Result = m_Solver.Solve();
	if( m_Result == Sudoku2DSolver< SIZE_ >::SUCCESS ){
		//成功
		return 1;
	}else if( m_Result == Sudoku2DSolver< SIZE_ >::NON ){
		//失敗
		return 0;
	}else if( m_Result == Sudoku2DSolver< SIZE_ >::PLURAL ){
		//不定解。解が複数ある(かもしれない)
		int x(0), y(0);
		//適当に１点を埋めて試す。
		std::vector< int > candidate = m_Solver.GetPluralData( x, y );
		for( std::vector< int >::iterator p = candidate.begin(); p != candidate.end(); ++p ){
			std::shared_ptr< Sudoku2D< SIZE_ > > solver( new Sudoku2D< SIZE_ >() );
			for( int iy = 0; iy < SIZE_2; ++iy ){
				for( int ix = 0; ix < SIZE_2; ++ix ){
					const int data = m_Solver.Get( ix, iy );
					if( data != 0 ){
						solver->AddData( ix, iy, data );
					}
				}
			}
			solver->AddData( x, y, *p );
			if( 0 < solver->Solve() ){
				//解が存在するので取っておく。
				m_apSolve.push_back( solver );
			}
		}
		return static_cast< int >( m_apSolve.size() );
	}
	return 0;
}


template< int SIZE_ >
int Sudoku2D< SIZE_ >::Get( int x, int y, int solve )
{
	if( m_Result == Sudoku2DSolver< SIZE_ >::SUCCESS ){
		//成功
		return m_Solver.Get( x, y );
	}else if( m_Result == Sudoku2DSolver< SIZE_ >::NON ){
		//失敗
		return 0;
	}else if( m_Result == Sudoku2DSolver< SIZE_ >::PLURAL ){
		//複数解
		return m_apSolve[solve]->Get( x, y );
	}
	return 0;
}

ちなみに、最初のSudoku2DSolverに以下のメソッドを付け足しています。

template< int SIZE_ >
std::vector< int > Sudoku2DSolver< SIZE_ >::GetPluralData( int& x, int& y )
{
	//最小の候補数を探す
	int minCount(SIZE_2+1);
	for( int iy = 0; iy < SIZE_2; ++iy ){
		for( int ix = 0; ix < SIZE_2; ++ix ){
			if( m_Num[iy][ix] == 0 ){
				int count = 0;
				for( int v = 1; v < SIZE_2+1; ++v ){
					if( m_check[iy][ix][v] ){
						++count;
					}
					if( minCount > count ){
						minCount = count;
						x = ix;
						y = iy;
					}
				}
			}
		}
	}
	std::vector< int > result;
	for( int v = 1; v < SIZE_2+1; ++v ){
		if( m_check[y][x][v] ){
			result.push_back( v );
		}
	}
	return result;
}

まあ事実上の総当りなので解けて当たり前なのですが。しかし普通に総当りしたら9^(9*9)で終わらないので途中で普通に解くアルゴリズムを挟むことによって実現しております。boostingですな(違)

ちなみにクラス名に2Dとかついていますが、まあ３次元とか作れたら面白いなと思って名前がそうなっています。本当に作るかは謎。