Puzzle DE Programming

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

戻る