お待たせしました。それでは、実際にパズルを解いてみましょう。コンピュータで解くパズルのなかで、特に有名なのが「８クイーン」です。このパズルはプログラミングの例題に最適なので、教科書や雑誌などで見たことがある人は多いと思います。筆者も月刊・電脳倶楽部に連載されたプログラミング入門講座で取り上げたことがありました。同じパズルを解くのは面白くないので、今回はパズル雑誌でときどき見かける「マジックスター (magic stars) 」を解くことにします。
○ １
／ ＼ ／ ＼
○───○───○───○ ２───４───12───８
＼ ／ ＼ ／ ＼ ／ ＼ ／
○ ○ 10 ６
／ ＼ ／ ＼ ／ ＼ ／ ＼
○───○───○───○ 11───５───３───７
＼ ／ ＼ ／
○ ９
正解例
図 6 : マジックスター
マジックスター (図 6) は、12 個ある○に 1 から 12 までの数字をひとつずつ入れていき、直線上に並んだ 4 個の数字の合計が、どの直線も 26 になるような配置を求めるのが目的です。パズル雑誌で出題される場合、ヒントとなる数字がいくつか表示されていて、空いている場所の数字を考えるのですが、今回はコンピュータで解くパズルらしく、すべての解を求めることにします。
マジックスターは 12 個の数字から構成されるので、配列を使って表すことにします。数字は 1 から 12 までなので、配列は char 型でいいでしょう。
/* マジックスター */ #define N 12 char star[N];
配列名は star としました。マジックスターと配列 star の関係ですが、図 7 に示すように、○に 0 から 11 までの番号をつけ、それを配列の添字に対応させます。
０
／ ＼
１───２───３───４
＼ ／ ＼ ／
５ ６
／ ＼ ／ ＼
７───８───９───10
＼ ／
11
図 7 : 位置を表す番号
つまり、マジックスターの 0 番の位置に配置された数字は、star[0] の数字と考えるのです。そうすると、6 本の直線は配列 line のように表すことができます。
/* 直線を表すデータ */
#define LINE 6
const char line[LINE][4] = {
0, 2, 5, 7,
0, 3, 6, 10,
7, 8, 9, 10,
1, 2, 3, 4,
1, 5, 8, 11,
4, 6, 9, 11
};
このデータを使って、直線上に並んだ数字の合計を求めることができます。
数字の選択ですが、これは次のように行えばいいでしょう。0 番に 1 を選んだならば、1 番にはそれ以外の 2 から 12 までの数字から選びます。1 番に 2 を選んだならば、2 番には 3 から 12 までの数字から選びます。これを 11 番まで繰り返します。結局、数字の配置は 1 から 12 までの順列を求めることと同じになります。要するに、順列を求めて直線上にある 4 個の数字の合計が 26 になっているかチェックすればいいわけです。正解の可能性があるデータを生成してチェックする、という方法を「生成検定法 (generate and test) 」といいます。可能性のあるデータをもれなく作るのにバックトラックは最適です。もちろん、順列を求めるにもバックトラックを使えば簡単です。
それでは、順列を求めるプログラムから作りましょう。まずはウオーミングアップとして、1, 2, 3 の順列を求めてみます。再帰呼び出しを使わないのであれば、次のようなプログラムになるでしょう。
リスト : 順列の生成（その１）
#define N 3
#define TRUE 1
#define FALSE 0
char use_number[N + 1];
char perm[N];
void make_perm( void )
{
int i, j, k;
/* 初期化 */
for( i = 0; i <= N; i++ ){
use_number[i] = FALSE;
};
/* 順列の生成 */
for( i = 1; i <= N; i++ ){
use_number[i] = TRUE;
perm[0] = i;
for( j = 1; j <= N; j++ ){
if( use_number[j] == FALSE ){
use_number[j] = TRUE;
perm[1] = j;
for( k = 1; k <= N; k++ ){
if( use_number[k] == FALSE ){
perm[2] = k;
print_perm(); /* 順列の完成 */
}
}
use_number[j] = FALSE;
}
}
use_number[i] = FALSE;
}
}
選んだ数字は配列 perm に格納します。順列は同じ数字を複数回使うことはできません。これをチェックするために memchr で perm を検索してもいいのですが、数字の種類が増えると、検索に時間がかかるようになります。そこで配列 use_number を使います。たとえば、1 を選んだならば use_number[1] に TRUE をセットします。あとは、use_number が FALSE の数字を選んでいくだけです。この方法は経路の探索にも利用できます。
順列が完成したら print_perm で出力します。次の順列を求めるため、使った数字を未使用の状態に戻すことに注意してください。たとえば、順列 1, 2, 3 が完成して次の順列を求める場合、2 番目のループで数字 2 を未使用に戻しておかないと、1, 3 と数字を選んだ時に 3 番目のループで 2 を選ぶことができず、すべての順列を求めることができなくなります。配列 perm は上書きされるため、元の状態に戻す必要はありません。
このプログラムは 3 重のループですが、けっこう大変ですね。1 から 12 までの順列を発生させるとなると、12 重のループになってしまいます。ところが、再帰呼び出しを使うと簡単にプログラムできるのです。
リスト : 順列を求める
void make_perm( int n )
{
int i;
if( n == N ){
print_perm(); /* 順列の完成 */
} else {
for( i = 1; i <= N; i++ ){
if( use_number[i] == FALSE ){
use_number[i] = TRUE;
perm[n] = i;
make_perm( n + 1 ); /* 再帰呼び出し */
use_number[i] = FALSE;
}
}
}
}
関数 make_perm は 1 から N までの順列を生成します。N はマクロで定義します。考え方は経路の探索と同じです。最初の呼び出しでひとつの数字を選び、次の再帰呼び出しで 2 つ目の数字を選ぶ、というように、N 重のループが N 回の再帰呼び出しに対応します。再帰呼び出しから戻ってきたら、新しい順列を求めるために、選んだ数字を未使用状態に戻すことを忘れないでください。変数 i は局所変数なので、引数 n と同様に関数が実行されている間だけ有効です。たとえば、i の値が 1 で再帰呼び出しが行われたとすると、再帰呼び出しから戻ってきても i の値は 1 のままです。このことにより、1 から N までの数字を順番に選ぶことができるのです。
プログラムの骨格は、経路の探索とよく似ていることがわかります。バックトラックによるプログラムは、どのプログラムでもだいたい同じようなかたちになります。基本をしっかりと理解しておけば、バックトラックを自由自在に使いこなすことができるようになります。
あとは、生成した順列がマジックスターの条件を満たしていることを確かめるだけです。これは 6 本の直線について数値を足し算して、合計が 26 になるかチェックするだけです。プログラムは次のようになります。
リスト : マジックスターの検査
int check_star( void )
{
int i;
for( i = 0; i < LINE; i++ ){
int j, n;
for( j = n = 0; j < 4; j++ ){
n += star[ line[i][j] ];
}
if( n != 26 ) return FALSE;
}
return TRUE;
}
6 本の直線のうち 1 本でも 26 でないものが見つかれば FALSE を返します。1 から 12 までの順列を生成したら、check_star を呼び出してマジックスターの条件を満たしているかチェックします。プログラムは次のようになります。
リスト : マジックスターを求める
void search_star( int n )
{
int i;
if( n == N && check_stars() ){
print_star();
} else {
for( i = 1; i <= N; i++ ){
if( use_number[i] == FALSE ){
use_number[i] = TRUE;
star[n] = i;
search_star( n + 1 ); /* 再帰呼び出し */
use_number[i] = FALSE;
}
}
}
}
順列を生成するプログラム make_perm とほとんど同じですが、順列を生成したら check_star を呼び出していることに注意してください。条件を満たしていたら print_star() でマジックスターを表示します。今回は単純に star の内容を表示するだけの味気ないものなので、面白くない方はスターの形になるように表示を工夫してください。あとは、main 関数で大域変数 use_number の初期化を行い、search_star を呼び出すだけです。
これでプログラム (ソースファイル ms1.c) は完成です。ところが、このプログラムをコンパイルして実行してみると、すべての解を出力するのにとても時間がかかるのです。そこで、ms1.c では 1 から始まる順列だけに限定したのですが、それでも、実行時間は 172 秒 (Pentium 166 MHz) もかかってしまいます。このとき 80 とおりの解が出力されたので、解の総数は 960 とおりあることがわかります。すべての解を出力させるとなると、実行時間は単純計算で約 35 分もかかることになります。生成する順列の総数は 12! = 479,001,600 とおりもあるのです。これでは時間がかかるのも当然ですね。
パズルを生成検定法で解く場合、チェックするデータをできるだけ絞り込むことが重要です。単純に考えると、膨大なデータをチェックしなければならないようなパズルでも、そのパズル固有の性質をうまく使うことでデータ数を減らすことができます。
マジックスターの場合、1 から 12 までの順列を生成していますが、明らかに無駄なデータを生成しています。たとえば、1, 2, 3, 4, 5 まで数字を選んだときの配置は図 8 のようになります。
１
／ ＼
２───３───４───５ => 合計値 14
＼ ／ ＼ ／
○ ○
／ ＼ ／ ＼
○───○───○───○
＼ ／
○
図 8 : 可能性の無いデータ
1 本の直線上に 4 つの数字が並びましたが、その合計値は 14 にしかなりません。これではマジックスターの条件を満たしませんね。つまり、1, 2, 3, 4, 5 で始まる順列は、すべて条件を満たさないことがわかるのですが、順列を生成してからチェックする方法では、このような無駄を省くことができません。そこで、数字を配置するときに、直線上に数字が 4 つ並んだ時点で合計値をチェックすることにします。
このように、できるだけ早い段階でチェックを入れることで、無駄なデータをカットすることを「枝刈り」と呼びます。バックトラックでパズルを解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。ところが、枝刈りの方法はパズルによって違います。パズル固有の性質をよく調べて、適切な枝刈りを考えることが必要なのです。パズル自体はコンピュータに解かせるのですが、枝刈りの条件は私達が考えるのです。これも「パズルの解法」の面白いところでしょう。解を求めるだけでなく、いかに効率の良い条件を見つけて実行時間を短縮するか、ということでも楽しむことができるわけです。
ひとつの直線に数字が 4 つ並んだことを確かめる簡単な方法は、配列 star の内容を確認することです。数字が置かれていない状態を 0 と定義すれば、0 より大きい値の個数を数えることで実現できます。ですが、数字を選択するたびに配列 star を検索するのでは時間がかかりそうです。そこで、直線ごとに置かれた数字を数えるカウンタを用意することにします。
/* 数字を置いた個数 */ int number_count[LINE]; /* 数字の合計 */ int total[LINE];
直線は配列 line に定義された順番で区別することができます。たとえば、0 番に 1 を選んだとします。ここは直線の 0 番と 1 番に属しているので、number_count の 0 番と 1 番の要素をインクリメントし、total の 0 番と 1 番の要素に 1 を加算します。ここで、4 個の数字が並んで合計値が 26 になったか簡単にチェックすることができます。バックトラックするときは、元の値に戻すことを忘れてはいけません。また、位置から直線を求めるのに配列 line を検索すると時間がかかるので、次に示す配列を用意します。
/* 位置から直線を求める */
const char position_line[N][2] = {
0, 1, /* 0 */
3, 4, /* 1 */
0, 3, /* 2 */
1, 3, /* 3 */
3, 5, /* 4 */
0, 4, /* 5 */
1, 5, /* 6 */
0, 2, /* 7 */
2, 4, /* 8 */
2, 5, /* 9 */
1, 2, /* 10 */
4, 5, /* 11 */
};
配列 position_line を使えば、位置から該当する直線を簡単に求めることができます。
それでは、プログラムを改造しましょう。数字を選択するときに、直線上にある数字の個数と合計値をチェックします。この処理を関数 set_number で行います。プログラムは次のようになります。
リスト : 数値のセット
int set_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
if( number_count[line] == 3 && total[line] + num != 26 ){
return FALSE;
}
}
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] += num;
number_count[line]++;
}
use_number[num] = TRUE;
star[pos] = num;
return TRUE;
}
位置 pos に数字 num を置いたときに、直線上に数字が 4 つ並んで、その合計値が 26 にならなければ FALSE を返します。number_count と total の値を更新する前に、チェックを行っていることに注意してください。
次は、数字を取り消す関数 remove_number を作ります。プログラムは次のようになります。
リスト : 数字の削除
void remove_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] -= num;
number_count[line]─;
}
use_number[num] = FALSE;
}
数字を取り消すときは、total と number_count の値も元に戻します。これは簡単なので説明は不要でしょう。最後に search_star() を改造します。
リスト : 探索
void search_star( int n )
{
if( n == N ){
print_star();
} else {
int i;
for( i = 1; i <= N; i++ ){
if( !use_number[i] && set_number( n, i ) ){
search_star( n + 1 );
remove_number( n, i );
}
}
}
}
数字を選ぶときに set_number を呼び出し、元に戻すときは remove_number を呼び出します。マジックスターの条件チェックは、順列を生成している途中の set_number で行っているため、順列が完成してから行う必要はありません。
これでプログラム (ソースファイル ms2.c) は完成です。実行してみると解の総数は 960 個で、実行時間は結果をファイルへリダイレクトした場合で約 5.5 秒 (Pentium 166 MHz) となりました。
ところで、パズルの解法では対称解のチェックが必要になる場合があります。対称解とは、盤面を回転させたり裏返しにすると同じになる解のことで、重複解と呼ぶこともあります。盤面に対称性がある場合は必ず発生します。マジックスターの場合、60 度ずつ回転させると同じ形になりますね。つまり、回転すると同じになる解 (回転解) を 6 重に数えていることになります。また、マジックスターを裏返しにすると、図 9 のような配置になります。
０ ０
／ ＼ ／ ＼
１───２───３───４ ４───３───２───１
＼ ／ ＼ ／ ＼ ／ ＼ ／
５ ６ ６ ５
／ ＼ ／ ＼ ／ ＼ ／ ＼
７───８───９───10 10───９───８───７
＼ ／ ＼ ／
11 11
図 9 : 鏡像解
このような解を鏡像解といいます。この鏡像解にも回転解が存在するので、全部で 12 重に数えていることになります。よって、重複しない解は 960 / 12 = 80 とおりになるはずです。
それでは対称解をチェックするようにプログラムを改造してみましょう。まず、回転解のチェックですが、0 番で選んだ数字に注目してください。選択した数字が 1 だとすると、マジックスターを 60 度ずつ回転していくと、1 は 1 番、7 番、11 番、10 番、4 番へと移動していきます。これらは同じ解なのですから、0 番でほかの数字を選んだ場合でも、これらの位置では数字 1 を選ぶ必要はありませんね。要するに、0 番に配置したことがある数字は、1, 4, 7, 10, 11 番に配置しないことで、回転解を取り除くことができるわけです。
次は鏡像解のチェックです。図 9 の 2 番と 3 番に注目してください。左右の図で 2 つの位置が入れ替わっていますね。ある解の 2 番と 3 番の数字が 4, 12 だったとすると、鏡像解では逆の 12, 4 になるわけです。この数字の大小関係を限定することで、鏡像解をチェックすることができます。つまり、次の条件 star[2] < star[3] を満たす解を求めればいいのです。ほかの位置関係でチェックしてもいいのですが、早い段階でチェックした方が、枝刈りとしての効果も高くなるので、この位置を選びました。このように、数字を使ったパズルでは、数字の大小関係を限定することで対称解を排除することができます。
対称解をチェックする関数 check_symmetry は次のようになります。
リスト : 対称解のチェック
int check_symmetry( int pos, int num )
{
static const char flag[SIZE] = {
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1,
};
if((flag[pos] && star[0] > num) || (pos == 3 && star[2] > num))
return TRUE;
return FALSE;
}
引数 pos は位置で、num はそこに入れる数字です。配列 flag は位置 1, 4, 7, 10, 11 を判定するために使います。flag[pos] が 1 で num が star[0] より小さい場合は、すでに 0 番に配置したことがある数字です。0 番は 1 から順番に数字がセットされるので、数字の大きさを比較するだけでチェックすることができます。これで回転解を判定することができます。pos が 3 のときは、star[2] との大小関係をチェックします。これで鏡像解をチェックできます。回転解か鏡像解であれば TRUE を返します。
あとは search_star で check_summetry を呼び出すだけです。
リスト : 探索
void search_star( int n )
{
if( n == N ){
print_star();
} else {
int i;
for( i = 1; i <= N; i++ ){
if( !use_number[i] &&
!check_symmetry( n, i ) && set_number( n, i ) ){
search_star( n + 1 );
remove_number( n, i );
}
}
}
}
これでプログラムの修正（ソースファイル ms3.c）は終わりです。実際に実行すると、80 とおりの解が出力されます。また、対称解のチェックは枝刈りの効果もあるため、実行時間もファイルへリダイレクトした場合で約 1.4 秒と短縮されます。
このプログラムは単純な枝刈りだけでなので、高速化する余地はまだまだ残っていると思われます。たとえば、数字を選択する順番を工夫すると、もう少し速くなるかもしれません。このプログラムでは、数字を 5 つ選んだところで 1 本の直線が完成しますが、数字を 4 つ選んだ段階で直線が完成するように配置を工夫した方がいいはずです。また、数字を 3 つ選んだら残りの数字は自動的に決まります。この数字が 12 より大きくなったり使用済みの数字であれば、その段階で枝刈りすることがでるはずです。どのくらい速くなるか、興味のある方は改造してみてください。
今回説明したバックトラックによる探索は、深さ優先探索とか縦形探索と呼ばれますが、これと対になるのが「幅優先探索」です。この 2 つがパズルの解法だけではなく、経路の探索のような問題を解くのに使用される基本的なアルゴリズムです。次回は幅優先探索を使って、完成するまでの最短手数を求めるパズルを解いてみましょう。それでは次回をお楽しみに。
/*
* ms1.c : マジックスター全解探索
*
* Copyright (C) 2001,2002 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define N 12
#define LINE 6
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
char star[N];
char use_number[N + 1];
int count = 0;
/* 出力 */
void print_star( void )
{
int i;
for( i = 0; i < N; i++ ){
printf("%2d ", star[i] );
}
printf("\n");
}
/* 星の検査 */
int check_star( void )
{
int i;
for( i = 0; i < LINE; i++ ){
int j, n;
for( j = n = 0; j < 4; j++ ){
n += star[ line[i][j] ];
}
if( n != 26 ) return FALSE;
}
return TRUE;
}
/* 単純な生成検定法 */
void search_star( int n )
{
int i;
if( n == N && check_star() ){
count++;
print_star();
} else {
for( i = 1; i <= N; i++ ){
if( !use_number[i] ){
use_number[i] = TRUE;
star[n] = i;
search_star( n + 1 );
use_number[i] = FALSE;
}
}
}
}
int main()
{
int start, end;
memset( use_number, 0, N + 1 ); /* 初期化 */
printf("時間がかかるので１から始まる順列のみをチェックする\n");
use_number[1] = TRUE;
star[0] = 1;
start = clock();
search_star( 1 );
end = clock();
printf("総数 %d 個, 時間 %d\n", count, end - start );
return 0;
}
/*
* ms2.c : マジックスター全解探索
*
* Copyright (C) 2001,2002 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define N 12
#define LINE 6
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
const char position_line[N][2] = {
0, 1, /* 0 */
3, 4, /* 1 */
0, 3, /* 2 */
1, 3, /* 3 */
3, 5, /* 4 */
0, 4, /* 5 */
1, 5, /* 6 */
0, 2, /* 7 */
2, 4, /* 8 */
2, 5, /* 9 */
1, 2, /* 10 */
4, 5, /* 11 */
};
int total[LINE]; /* 合計 */
int number_count[LINE]; /* 数字を置いた個数 */
char star[N];
char use_number[N + 1];
int count = 0;
/* 出力 */
void print_star( void )
{
int i;
for( i = 0; i < N; i++ ){
printf("%2d ", star[i] );
}
printf("\n");
}
/* 数値のセット */
int set_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
if( number_count[line] == 3 && total[line] + num != 26 ){
return FALSE;
}
}
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] += num;
number_count[line]++;
}
use_number[num] = TRUE;
star[pos] = num;
return TRUE;
}
/* 数字の削除 */
void remove_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] -= num;
number_count[line]--;
}
use_number[num] = FALSE;
star[pos] = FALSE;
}
/* 探索 */
void search_star( int pos )
{
if( pos == N ){
count++;
print_star();
} else {
int n;
for( n = 1; n <= N; n++ ){
if( !use_number[n] && set_number( pos, n ) ){
search_star( pos + 1 );
remove_number( pos, n );
}
}
}
}
/* 初期化 */
void init_global( void )
{
int i;
memset( use_number, 0, N + 1 ); /* 初期化 */
for( i = 0; i < LINE; i++ ){
total[i] = 0;
number_count[i] = 0;
}
}
int main()
{
int start, end;
init_global();
start = clock();
search_star( 0 );
end = clock();
printf("総数 %d 個, 時間 %d\n", count, end - start );
return 0;
}
/*
* ms3.c : マジックスター全解探索
*
* Copyright (C) 2001, 2002 Makoto Hiroi
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TRUE 1
#define FALSE 0
#define N 12
#define LINE 6
const char line[LINE][4] = {
0, 2, 5, 7, 0, 3, 6, 10, 7, 8, 9, 10,
1, 2, 3, 4, 1, 5, 8, 11, 4, 6, 9, 11
};
const char position_line[N][2] = {
0, 1, /* 0 */
3, 4, /* 1 */
0, 3, /* 2 */
1, 3, /* 3 */
3, 5, /* 4 */
0, 4, /* 5 */
1, 5, /* 6 */
0, 2, /* 7 */
2, 4, /* 8 */
2, 5, /* 9 */
1, 2, /* 10 */
4, 5, /* 11 */
};
int total[LINE]; /* 合計 */
int number_count[LINE]; /* 数字を置いた個数 */
char star[N];
char use_number[N + 1];
int count = 0;
/* 出力 */
void print_star( void )
{
int i;
for( i = 0; i < N; i++ ){
printf("%2d ", star[i] );
}
printf("\n");
}
/* 対称解のチェック */
int check_symmetry( int pos, int num )
{
static const char flag[N] = {
0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1,
};
if((flag[pos] && star[0] > num) || (pos == 3 && star[2] > num))
return TRUE;
return FALSE;
}
/* 数値のセット */
int set_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
if( number_count[line] == 3 && total[line] + num != 26 ){
return FALSE;
}
}
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] += num;
number_count[line]++;
}
use_number[num] = TRUE;
star[pos] = num;
return TRUE;
}
/* 数字の削除 */
void remove_number( int pos, int num )
{
int i;
for( i = 0; i < 2; i++ ){
int line = position_line[pos][i];
total[line] -= num;
number_count[line]--;
}
use_number[num] = FALSE;
star[pos] = FALSE;
}
/* 探索 */
void search_star( int pos )
{
if( pos == N ){
count++;
print_star();
} else {
int n;
for( n = 1; n <= N; n++ ){
if( !use_number[n] && !check_symmetry( pos, n ) && set_number( pos, n ) ){
search_star( pos + 1 );
remove_number( pos, n );
}
}
}
}
/* 初期化 */
void init_global( void )
{
int i;
memset( use_number, 0, N + 1 );
for( i = 0; i < LINE; i++ ){
total[i] = 0;
number_count[i] = 0;
}
}
int main()
{
int start, end;
init_global();
start = clock();
search_star( 0 );
end = clock();
printf("総数 %d 個, 時間 %d\n", count, end - start );
return 0;
}