●ms1.c
/*
* 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("時間がかかるので1から始まる順列のみをチェックする\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
/*
* 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
/*
* 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;
}
戻る