「おねえさんのコンピュータ」をArduinoで

日本科学未来館が公開した「フカシギの数えかた」という動画は「同じところを2度通らない道順の数」を数えるという一見簡単だが、組み合わせ爆発の恐ろしさを教えるものだ。結末がとても狂気じみていて反響が大きかった。
8×8のマトリックスならArduinoでも表示はできるなと思って作ってみた。ただし、組み合わせの数がとても大きいので、現実的な時間では終わらないので、ループはなくても事実上無限ループみたいなものである。
おねえさんのやっている方法はアルゴリズムの教科書などを見れば必ず出てくる深さ優先探索(depth first search)というもので
、再帰的な関数を使って簡単に実装できる。本来は天文学的な時間のかかる場合でもZDDというアルゴリズムを使うと短時間で解けるという背景があるのだが、私の手には負えないのでここではおねえさん止まりである。

8×8のドットマトリックスLEDを使うとして、各LEDの座標x[i],y[i](i=0,..,63)と、i番目のサイトを通ったかどうかという情報v[i]、各サイトから進める隣接サイトの番号dir[i][]、通った道筋の履歴site[]を準備する。
0番目から出発して、次に進めるサイトへどんどん進み、目的地i=63に到達したら、道筋を表示し、進んだ後は引き返して別の道を探すという繰返しである。
arms22さんによるドットマトリクスを表示するためのDotsduinoをたまたま持っていたので、そのためのDotsライブラリを使うことで表示部分は簡単に実装できた。

myDots.write(x,y,HIGH);

のように座標を指定してHIGH,LOWを指定するだけである。
回路図も公開されているので、ドットマトリクスLED部分の接続だけ同じにするとふつうのArduinoでも同じことができる。
いつまでも終わらないちょっと複雑なLチカということで。

動画はこちら

#include <Dots.h>

#define L 8
#define N (L*L)

int x[N], y[N];
uint8_t v[N];
uint8_t dir[N][5];
uint8_t site[N];
uint8_t length = 0;
unsigned long count = 0;

Dots myDots = Dots(9,4,10,6,17,11,16,13, 5,15,14,8,12,7,3,2);

int dist(int i, int j) {
  return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}

void setup()
{
  int i, j, k, n, cnt;
  
  myDots.begin();
  Serial.begin(9600);
  
  n = 0;
  // setup coordinate
  for (i=0; i<L; i++) {
    for (j=0; j<L; j++) {
      x[n] = i;
      y[n] = j;
      n++;
    }
  }
  // setup available directions
  for (i=0; i<N; i++) {
    cnt = 0;
    for (j=0; j<N; j++) {
      if (dist(i, j)==1) {
        dir[i][cnt] = j;
        cnt++;
      }
    }
    dir[i][4] = cnt; // number of available directions
  } 
}

void show()
{
  int i, j;
  // display path
  myDots.clear();
  for (j=0; j<=length; j++) {
	i = site[j];
	myDots.write(x[i],y[i],HIGH);
	myDots.updateWithDelay(10);
  }
  myDots.updateWithDelay(10);
}

void visit(int i)
{
  int j, d;
  v[i] = 1;
  if (i==N-1) {
	// reached the goal and show the path
    show();                                                                   
    count++;
  } else {
    site[length] = i;
    for (j=0; j<dir[i][4]; j++) {
      d = dir[i][j];
      if (v[d] == 0) {
        length++;
        site[length] = d;
		visit(d);
		// traceback to enumerate all the traces
        v[d] = 0;
        length--;
      }
    }
  }
}

void loop()
{
  int i;
  for (i=0; i<N; i++) {
    v[i] = 0;
    site[i] = 0;
  }
  visit(0);
  Serial.println(count); 
}
広告
カテゴリー: Arduino

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

カテゴリー
2012年10月
« 7月   11月 »
1234567
891011121314
15161718192021
22232425262728
293031  
%d人のブロガーが「いいね」をつけました。