色塗り問題の件、お願いします。前回は僕の説明不足でした。。。

質問

すいません、よろしくお願いします。三色色塗り問題を解きたいのですが、よくわかりません。
条件はこのようになっています。
ノード数　６　V={X1、X2、X3、X4、X5、X6}
色数　3
接続｛(X1,X2)、(X2,X3)、(X3,X4)、(X4,X5)、(X5,X6)、(X6,X1)、(X2,X5)}
接続がつながっているノード同士は同じになってはいけないという設定なんですが、初心者なものでどうすればよいのか。。。
じぶんで本を読んだりしてみはしましたがさっぱりわからず困っています。
簡単なソースコードを教えてください。よろしくお願いします。
moritan2さん、trick--o--さん、回答ありがとうございました！
実は、この問題のノード数、色数、制約を可変的にしたいのです。よろしければ、ソースコードと、その簡単な説明をお願いします。たびたびすみません。。。

回答No.1

moritan2 · ベストアンサー

いろんなやり方があるけど、初心者向きにわかりやすさを重視するなら再帰をつかうのがいいでしょう。

int a[MAX_NODE]; // ノードの色が入る配列

bool check_link(int n)
{
// n個目までのノードの色がa[]に入っている時、そこまでリンクのあるノードに同じものがないかをチェックする関数
// 違反がなければ true、あれば false、n < 2 の時は常に true
// この関数ぐらいは自分で書けるでしょ
}

bool aaa(int n)
{
int i;

if(check_link(n) == false) {
// チェックがfalseなら失敗なので、戻る
return false;
}
// ここまで n個目までは違反がないことがわかった
if(n >= MAX_NODE) {
// n >= MAX_NODE なら答えは a[] に完成している
return true;
}

for(i = 0; i < 3; i++) {
// n+1個目の色を順番に試す
a[n] = i;
if(aaa(n + 1) == true) {
// 正解が見つかった
return true;
}
}
return false;
}

これで
aaa(0);

を呼び出して true が返ってきたら答えは a[] に完成しているし、false なら解は存在しない。

ただし、上の方法はあくまでも原理を記述したもので、ノード数が多くてリンクもたくさんなら
解を得るまでの時間を短縮するためにいろいろ工夫が必要になるでしょう。
たとえば check_link(n)は、一つ前(n-1)までは真であることが確認済みと仮定するとか。

補足

moritan2さん、
//n個目までのノードの色がa[]に入っている時、そこまでリンクのあるノードに同じものがないかをチェックする関数
// 違反がなければ true、あれば false、n < 2 の時は常に true
// この関数ぐらいは自分で書けるでしょ
のところも教えていただけないでしょうか？
できもしないのに手を出してしまって、困っています。提出しなければいけない状況なんで、もし差し支えなければよろしくお願いします。