パズルの説明
五芒星（左図）を使ったパズルはいろいろな種類がありますが、今回は数字を配置するパズルを取り上げます。五芒星には頂点と交点が 10 ヵ所ありますが、ここに 1 から 10 までの数字を配置します。すると、直線上に 4 つの数字が並びますが、その和が n 本の直線で等しくなるような配置を求める、というものです。
3 本の直線で等しくなる配置は、ある本で見かけたことがあります。それでは、4 本の直線が等しくなる配置は何通りあるのでしょうか。プログラムを作って調べてみましょう。使用するプログラミング言語はＣ言語です。
●データ構造の定義
五芒星の 10 ヵ所の点は配列 stars で表します。そして、五芒星の点は左図のように stars の添字と対応づけると、5 本の直線は次に示すデータで表すことができます。
リスト：直線の定義
const int lines[LINE][4] ={
0, 2, 5, 8,
0, 3, 6, 9,
1, 2, 3, 4,
1, 5, 7, 9,
4, 6, 7, 8,
};
1 行で 1 本の直線を表していることは、図を見ればすぐにわかるでしょう。あとは生成検定法の出番です。1 から 10 までの順列を生成して、それが条件を満たしているかチェックすればいいわけです。
●プログラムの作成
最初に、順列を生成して五芒星をチェックするプログラムを作ります。
リスト：探索
void search_star( int pos )
{
if( pos == SIZE ){
check_stars();
} else {
int n;
for( n = 1; n <= SIZE; n++ ){
if( !use_number[n] && !check_symmetry( pos, n ) ){
use_number[n] = TRUE;
stars[pos] = n;
search_star( pos + 1 );
use_number[n] = FALSE;
}
}
}
}
重複解をチェックする関数 check_symmetry を除くと、いままで説明したバックトラックによる探索とほぼ同じなので、とくに難しいところはないはずです。check_symmetry はあとで詳しく説明します。
次に、条件をチェックする関数 check_stars を作ります。
リスト：条件のチェック
void check_stars( void )
{
int i, j;
for( i = 0; i < LINE; i++ ){
total[i] = 0;
for( j = 0; j < 4; j++ ){
total[i] += stars[ lines[i][j] ];
}
}
for( i = 0; i < 2; i++ ){
int c = 0;
for( j = i; j < LINE; j++ ){
if( total[i] == total[j] ) c++;
}
if( c >= 4 ){
print_answer( total[i] ); break;
}
}
}
各直線の合計値を配列 total に格納します。次に、4 本以上同じ値の直線があるかチェックします。5 本のうち 4 本が同じ値になっているか調べるわけですから、直線 0 と同じ値の本数と、直線 1 と同じ値の本数を調べるだけです。また、直線 1 の場合は、1 から 4 までの直線を調べるだけで OK です。同じ値を 4 つ以上見つけたら print_answer で解を出力します。
●対称解のチェック
パズルの解法では 対称解 のチェックが必要になる場合があります。対称解とは、盤面を回転させたり裏返しにすると同じになる解のことで、重複解 と呼ぶこともあります。盤面に対称性がある場合は必ず発生します。五芒星の場合、72 度ずつ回転させると同じ形になりますね。つまり、回転すると同じになる解（回転解）が 5 つあるわけです。また、五芒星を裏返しにすると、次の図のような配置になります。
このような解を 鏡像解 といいます。当然ですが、この鏡像解にも回転解が存在します。したがって、重複解のチェックを行わないと、同じ解を 10 通り出力することになります。
五芒星の場合、重複解のチェックは難しい処理ではありません。まず、回転解のチェックですが、0 番で選んだ数字に注目してください。選択した数字が 1 だとすると、五芒星を 72 度ずつ回転していくと、1 は 1 番、8 番、9 番、4 番へと移動していきます。これらは同じ解なのですから、0 番でほかの数字を選んだ場合でも、これらの位置では数字 1 を選ぶ必要はありませんね。ようするに、0 番に配置したことがある数字は、1, 4, 8, 9 番に配置しないことで回転解を取り除くことができるわけです。
次は鏡像解のチェックです。上図の 2 番と 3 番に注目してください。左右の図で 2 つの位置が入れ替わっていますね。ある解の 2 番と 3 番の数字が 2, 10 だったとすると、鏡像解では逆の 10, 2 になるわけです。この数字の大小関係を限定することで、鏡像解をチェックすることができます。
対称解をチェックする関数 check_symmetry は次のようになります。
リスト：条件のチェック
int check_symmetry( int pos, int num )
{
static const char flag[SIZE] = {
0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
};
if((flag[pos] && stars[0] > num) || (pos == 3 && stars[2] > num))
return TRUE;
return FALSE;
}
引数 pos は位置で、num はそこに入れる数字です。配列 flag は位置 1, 4, 8, 9 を判定するために使います。flag[pos] が 1 で num が star[0] より小さい場合は、すでに 0 番に配置したことがある数字です。0 番は 1 から順番に数字がセットされるので、数字の大きさを比較するだけでチェックすることができます。鏡像解のチェックは簡単ですね。
●実行結果
それでは、実行結果を示します。
| 直線の値 | 個数 |
|---|---|
| 20 (30) | 24 |
| 21 (26) | 60 |
| 23 (18) | 60 |
| 24 (14) | 24 |
| 総数 | 168 |
解の総数は 168 通りになりました。カッコの中は残り 1 本の値を表しています。解答例は、直線の値が 24 の場合です。ところで、直線の値が 20, 21, 23, 24 の 4 通りもあるとは驚きました。M.Hiroi は、六芒星で 6 本全部の直線が 26 になる場合を調べたことがあります。この場合、解は 80 通りありますが、もしかすると六芒星でも別の値で解があるかもしれませんね（追記参照）。
●追記１(2000/10/06)
M.Kamada さんに 168 通りで正しいことを確認していただきました。また、六芒星の場合、M.Kamada さんが 26 以外では解が存在しないことを確認されました。M.Kamada さん、ありがとうございました。
●追記２(2000/10/08)
一般の n 芒星で n 本の和が等しくなる場合について、次の関係が成り立つことを deepgreen さんがゲストブック(No.61)で指摘されました。
直線上の 4 点の和を m とし、n 本の直線の総和を考える。n 本の直線によって、すべての点は丁度 2 回数えられます。従って、
ｍ＊ｎ ＝ ２＊｛１＋２＋．．．＋２ｎ｝ ＝ ２＊｛２ｎ＊（２ｎ＋１）／２｝即ち
ｍ ＝ ２（２ｎ＋１）という関係が成り立つことが必要です。
いやー、まいりました。このような関係が成立するとは、M.Hiroi はちっとも気がつきませんでした。この関係から、直線の和がすべて等しくなる場合、その値は 1 通りしかないこともわかりますね。deepgreen さん、ありがとうございました。
●プログラムリスト１
/*
* five_star.c : 五芒星のパズル
*
*/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
#define LINE 5
#define TRUE 1
#define FALSE 0
const int lines[LINE][4] ={
0,2,5,8,
0,3,6,9,
1,2,3,4,
1,5,7,9,
4,6,7,8,
};
int stars[SIZE];
int use_number[SIZE + 1];
int total[LINE];
int count = 0;
void print_answer( int num )
{
int i;
count++;
printf("%d [", num );
for( i = 0; i < SIZE; i++ ){
printf("%2d ", stars[i] );
}
printf("][");
for( i = 0; i < LINE; i++ ){
printf("%2d ", total[i] );
}
printf("]\n");
}
void check_stars( void )
{
int i, j;
for( i = 0; i < LINE; i++ ){
total[i] = 0;
for( j = 0; j < 4; j++ ){
total[i] += stars[ lines[i][j] ];
}
}
for( i = 0; i < 2; i++ ){
int c = 0;
for( j = i; j < LINE; j++ ){
if( total[i] == total[j] ) c++;
}
if( c >= 4 ){
print_answer( total[i] ); break;
}
}
}
/* 対称解のチェック */
int check_symmetry( int pos, int num )
{
static const char flag[SIZE] = {
0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
};
if((flag[pos] && stars[0] > num) || (pos == 3 && stars[2] > num))
return TRUE;
return FALSE;
}
/* 探索 */
void search_star( int pos )
{
if( pos == SIZE ){
check_stars();
} else {
int n;
for( n = 1; n <= SIZE; n++ ){
if( !use_number[n] && !check_symmetry( pos, n ) ){
use_number[n] = TRUE;
stars[pos] = n;
search_star( pos + 1 );
use_number[n] = FALSE;
}
}
}
}
int main()
{
int i;
for( i = 0; i <= SIZE; i++ ){
use_number[i] = 0;
}
search_star( 0 );
printf("総数 %d\n", count );
return 0;
}
5 本の直線の和が等しくなる場合
ところで、書店で立ち読みした本に変形魔方陣の話があり、五芒星の魔方陣も掲載されていました。五芒星や六芒星のような星型は 魔星陣 と呼ばれていて、3 と 7 を除いた 1 から 12 までの数字を配置すると 5 本の直線の和が 24 になるそうです。もしかすると、別の数字の組み合わせがあるかもしれません。さっそくプログラムを作って確かめてみました。
●実行結果
実行結果ですが、直線の和が 24 になる配置が 12 通り、28 になる配置が 12 通りありました。実行時間は M.Hiroi のオンボロマシン (Pentium 166 MHz) で約 72 秒かかりました。プログラムは対称解のチェックを行っているだけで、ほかの枝刈りはいっさい行っておりません。興味のある方は枝刈りを追加してプログラムの高速化に挑戦してみてください。配置の一例を図に示します。
●プログラムリスト２
/*
* five_star.c : 五芒星のパズル(1 - 12 までの数字を 10 個選ぶ)
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
#define NUMBER 12
#define LINE 5
#define TRUE 1
#define FALSE 0
const int lines[LINE][4] ={
0,2,5,8,
0,3,6,9,
1,2,3,4,
1,5,7,9,
4,6,7,8,
};
int stars[SIZE];
int use_number[NUMBER + 1];
int total[LINE];
int count = 0;
void print_answer( int num )
{
int i;
count++;
printf("%d [", num );
for( i = 0; i < SIZE; i++ ){
printf("%2d ", stars[i] );
}
printf("][ ");
for( i = 0; i < LINE; i++ ){
printf("%2d ", total[i] );
}
printf("]\n");
}
void check_stars( void )
{
int i, j;
for( i = 0; i < LINE; i++ ){
total[i] = 0;
for( j = 0; j < 4; j++ ){
total[i] += stars[ lines[i][j] ];
}
}
for( i = 0; i < 2; i++ ){
int c = 0;
for( j = i; j < LINE; j++ ){
if( total[i] == total[j] ) c++;
}
if( c >= 5 ){
print_answer( total[i] ); break;
}
}
}
/* 対称解のチェック */
int check_symmetry( int pos, int num )
{
static const char flag[SIZE] = {
0, 1, 0, 0, 1, 0, 0, 0, 1, 1,
};
if((flag[pos] && stars[0] > num) || (pos == 3 && stars[2] > num))
return TRUE;
return FALSE;
}
/* 探索 */
void search_star( int pos )
{
if( pos == SIZE ){
check_stars();
} else {
int n;
for( n = 1; n <= NUMBER; n++ ){
if( !use_number[n] && !check_symmetry( pos, n ) ){
use_number[n] = TRUE;
stars[pos] = n;
search_star( pos + 1 );
use_number[n] = FALSE;
}
}
}
}
int main()
{
int i, start, end;
for( i = 0; i <= NUMBER; i++ ){
use_number[i] = 0;
}
start = clock();
search_star( 0 );
end = clock();
printf("総数 %d, 時間 %d\n", count, end - start );
return 0;
}