順列で 3x3 魔方陣を

こんな記事をみかけた。

- http://d.hatena.ne.jp/n9d/20071213/1197521285
> すごいぞprolog！魔方陣がワンライナーでかける！（swi-prologで魔方陣を計算その２） - 計算機と戯れる日々

ふーん、すごいな。
MacBook でやってみた。

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.61)

?- time((permutation([1, 2, 3, 4, 5, 6, 7, 8, 9], [A, B, C, D, E, F, G, H, I]),X is A+B+C,X is D+E+F,X is G+H+I,X is A+D+G,X is B+E+H,X is C+F+I,X is A+E+I,X is C+E+G,print([A,B,C,D,E,F,G,H,I,X]),nl,fail)).
[6, 1, 8, 7, 5, 3, 2, 9, 4, 15]
[8, 1, 6, 3, 5, 7, 4, 9, 2, 15]
[8, 3, 4, 1, 5, 9, 6, 7, 2, 15]
[4, 3, 8, 9, 5, 1, 2, 7, 6, 15]
[6, 7, 2, 1, 5, 9, 8, 3, 4, 15]
[2, 7, 6, 9, 5, 1, 4, 3, 8, 15]
[2, 9, 4, 7, 5, 3, 6, 1, 8, 15]
[4, 9, 2, 3, 5, 7, 8, 1, 6, 15]
% 1,154,595 inferences, 0.63 CPU in 0.64 seconds (99% CPU, 1832690 Lips)
false.

ruby でもやってみた
$ cat magicsqure3.rb
#  0 1 2
#  3 4 5
#  6 7 8

[1,2,3,4,5,6,7,8,9].permutation do |a|
  p a if a[0]+a[1]+a[2] == 15 and a[3]+a[4]+a[5] == 15 and a[6]+a[7]+a[8] == 15 and a[0]+a[3]+a[6] == 15 and a[1]+a[4]+a[7] == 15 and a[2]+a[5]+a[8] == 15 and a[0] + a[4] + a[8] == 15 and a[2] + a[4] + a[6] == 15
end

$ ruby -v
ruby 1.8.7 (2008-08-11 patchlevel 72) [i686-darwin9]

$ time ruby magicsquare3.rb
[2, 7, 6, 9, 5, 1, 4, 3, 8]
[2, 9, 4, 7, 5, 3, 6, 1, 8]
[4, 3, 8, 9, 5, 1, 2, 7, 6]
[4, 9, 2, 3, 5, 7, 8, 1, 6]
[6, 1, 8, 7, 5, 3, 2, 9, 4]
[6, 7, 2, 1, 5, 9, 8, 3, 4]
[8, 1, 6, 3, 5, 7, 4, 9, 2]
[8, 3, 4, 1, 5, 9, 6, 7, 2]

real    0m2.435s
user    0m1.797s
sys    0m0.623s

jruby も試そうと思ったが、jruby （1.1.4) には permutaion メソッドが無いとのエラーになった。

java での 順列生成の例をネットで探してみた。

- http://sakura.bb-west.ne.jp/spr/damayan/algo/PermEnum.java
> 順列を生成する Enumeration
これをつかって、プログラムを作り、実行させてみた。

$ cat MagicSquare3.java
// See http://sakura.bb-west.ne.jp/spr/damayan/algo/PermEnum.java

import java.util.Enumeration;

/**
* 順列を生成する Enumeration
* N 個の要素から順列を生成する個数は N!
* （参考）Ｃ言語によるアルゴリズム入門
*/
class PermEnum implements Enumeration {

    private int N;
    private int c[], k;
    private Object[] objs;

    public PermEnum(Object[] items) {
    N = items.length;
    c = new int[N + 1];
    for(int i=0; i<=N; i++) c[i] = i;
    objs = items;
    k = 1;
    }

    public boolean hasMoreElements() {
    return (k < N);
    }

    public Object nextElement() {
    int i = 0;
    if((k & 1) != 0) i = c[k];

    Object tmp = objs[k];
    objs[k] = objs[i];
    objs[i] = tmp;

    k = 1;
    while(c[k] == 0) c[k] = k++;

    c[k]--;
    return objs;
    }
}

public class MagicSquare3 {

    // テスト
    public static void main(String[] args) {
    Integer[] data = {1,2,3,4,5,6,7,8,9};
    System.out.println("N="+data.length);
    Enumeration e = new PermEnum(data);
    int count = 0;
    while(e.hasMoreElements()) {
        Integer[] a = (Integer[])e.nextElement();

        if (a[0]+a[1]+a[2] == 15 & a[3]+a[4]+a[5] == 15 & a[6]+a[7]+a[8] == 15 & a[0]+a[3]+a[6] == 15 & a[1]+a[4]+a[7] == 15 & a[2]+a[5]+a[8] == 15 & a[0] + a[4] + a[8] == 15 & a[2] + a[4] + a[6] == 15) {
        System.out.print("{" + a[0]);
        for(int i=1; i<a.length; i++)
            System.out.print(", "+a[i]);
        System.out.println("}");
        count++;
        }
    }
    System.out.println("count="+count);
    }
}

$ java -version
java version "1.5.0_16"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_16-b06-284)
Java HotSpot(TM) Client VM (build 1.5.0_16-133, mixed mode, sharing)

$ time java -cp . MagicSquare3
N=9
{2, 9, 4, 7, 5, 3, 6, 1, 8}
{2, 7, 6, 9, 5, 1, 4, 3, 8}
{8, 3, 4, 1, 5, 9, 6, 7, 2}
{8, 1, 6, 3, 5, 7, 4, 9, 2}
{6, 7, 2, 1, 5, 9, 8, 3, 4}
{6, 1, 8, 7, 5, 3, 2, 9, 4}
{4, 9, 2, 3, 5, 7, 8, 1, 6}
{4, 3, 8, 9, 5, 1, 2, 7, 6}
count=8

real    0m0.277s
user    0m0.169s
sys    0m0.046s