覚えたら書く

IT関係のデベロッパとして日々覚えたことを書き残したいです。twitter: @yyoshikaw

OSSの頒布

「OSSライセンスの教科書」という本を読んでいます。

OSSライセンスの教科書

OSSライセンスの教科書

普段の業務上でもお世話にならないことが無い、OSS(オープンソースソフトウェア)な訳ですが、 そのOSSのライセンスについて理解を深めるのにとても良い本だと思います。


以下は「OSSライセンスの教科書」の中の頒布に関する内容の一部メモです。


頒布

OSSのライセンスについて調べたりしていると頒布(はんぷ)という言葉が付きまといます。

頒布をネットで調べると以下のような感じの定義が出てきます

不特定多数の相手に広く配る行為のこと、有償無償は問わない。

OSSを適切に扱う(OSSのライセンスの内容に適合させる)ためには、頒布が大事なタイミングとなります。
OSSライセンスでは、OSSを頒布する側に条件を課していることが良くあるためです。
(ライセンスによっては、利用許諾されたソフトウェアを頒布する際に、頒布する人がソースコードを開示する ことなどを求めています)

「頒布する人」とは、OSSの開発者だけを指すわけではなく、そのOSSを入手し、誰か他の人に渡す人(法人含む)は全て頒布する人になります。
頒布する形態も色々とあり、ソースコードを誰かに渡すこと、バイナリコードを渡すこと、OSSを製品に組み込んで渡すのも頒布になります。


頒布の事例

「OSSライセンスの教科書」では、各種事例を取り上げ、それが頒布にあたるのかどうかを紹介してくれています。
以下はその内容の簡単なメモになります。


■ソフトウェアの内製

あなたは消費者用機器の開発メーカーでソフトウェア開発を行なっている。
あなたの開発したソフトウェアにOSSが含まれている。
そのソフトウェアを組み込んだ製品が発売された。この場合、あなたの会社はOSSを頒布すると言えるか?


頒布していると言える

機器に組み込まれているからといって、バイナリ形式になっているからといって頒布では無いと主張するのは無理がある。


■開発製造受託会社に開発を委託

あなたは消費者用機器の開発メーカーに在籍している。
開発製造受託業者に委託して製品を開発してもらい受給した。
製品が発売されたが、この製品にはソフトウェアが組み込まれていて、開発元のベンダーによるとその中にはOSSが入っているとのこと。
あなたの会社はOSSを頒布していると言えるか?


頒布していると言える

開発元のベンダーがあなたの会社にOSSを頒布したが、製品とともにユーザにOSSを頒布しているのはあなたの会社です。
そのため、頒布に伴う条件を履行する必要があります。


■マーケティング部門がモバイルアプリを作成

あなたはインターネット通販企業のマーケティング部門に属しています。
外部のソフトウェアハウスに頼んで、スマートフォンアプリを開発し、拡販を開始しました。
ソフトウェアハウスの担当者は「そのアプリには実はOSSを使っているんです」と話していました。
あなたの会社がOSSを頒布したと言えるか?


頒布していると言える

あなたの会社はスマートフォンアプリに組み込まれているOSSを頒布しています。
頒布する人(法人)としてOSSライセンスが求めていることを確実に実施する必要があります。


■Webサーバ構築

あなたは Linux と Apache を使ってWebサーバを構築しました。
そのサーバ上であるWebアプリケーションを構築して運用しています。
あなたはOSSを頒布したているでしょうか?

Webブラウザなどで、このシステムにアクセスするユーザは、このサーバに対してデータを受け渡して、
サーバで処理された結果を受け取ります。
その際に、LinuxやApacheといったOSSプログラムそのものをユーザに渡されることはありません。
この観点では、

頒布していると言えない

ということになります。
しかし、Webサイトからユーザ側(ユーザの端末)で実行されるプログラムがサーバからユーザに渡されることもあります。
例えば、JavaScriptがそれに該当します。
もしも、そのJavaScriptのプログラムがOSSであった場合、

頒布していると言える

となります。


一筋縄ではいかない例となります。


■知らぬ間にOSSが製品に入っていた

あなたはソフトェアが含まれる製品を出荷しています。
ある時、全く面識のない人から連絡を受け、あなたの製品の中にOSSが含まれているのではないか
という問い合わせを受けました。
改めて調べてみると、その製品の中にOSSが含まれていることがわかりました。
あなたはOSSを頒布したと言えるか?


頒布していると言える

たとえ、あなたがOSSを頒布した意識がなくてもOSSライセンスが求めることを履行する必要があります。


まとめ

「OSSライセンスの教科書」の内容を元に、OSSの頒布につい簡単にまとめました。
OSSを扱う上で、頒布について一定の理解をしておく必要があります。

「OSSライセンスの教科書」は、OSSライセンスを理解する上で読んだ方が良いです。

JavaのString#trim

JavaのString#trimメソッドは、文字列の先頭と末尾のスペース(半角スペース)を除外した文字列を返してくれます。


例えば " sample1 " という先頭にも末尾にも半角スペースが入った文字列にtrimを実行すると、
半角スペースが削られた "sample1" という文字列が返されます。


サンプルコード

import java.util.stream.Collectors;

public class TrimSample1 {

    public static void main(String[] args) {
        String sample1 = " sample1 ";
        printStrAndTrimedStr(sample1);
    }

    private static void printStrAndTrimedStr(String str) {
        System.out.printf("[%s](%s) -> trim -> [%s](%s)\n\n", str, asciiHexDump(str),
                str.trim(), asciiHexDump(str.trim()));
    }

    private static String asciiHexDump(String ascii) {
        return ascii.chars()
                .mapToObj(b -> String.format("0x%02X", b))
                .collect(Collectors.joining(" "));
    }
}

printStrAndTrimedStr で、trim実行前後の文字列を出力して、かつ16進表記の出力もしています。
(以降のサンプルでもprintStrAndTrimedStrasciiHexDump は使いまわします)


実行結果

[ sample1 ](0x20 0x73 0x61 0x6D 0x70 0x6C 0x65 0x31 0x20) -> trim -> [sample1](0x73 0x61 0x6D 0x70 0x6C 0x65 0x31)

先頭と末尾の半角スペース(0x20)が削られています。


まぁ、ここまでは予定通りの動きな訳ですが、 Javaの String#trim って、0x20以下の文字コードを先頭・末尾から削るようです。


改行コードを含む文字列で実行してみます。

サンプルコード

public class TrimSample2 {

    public static void main(String[] args) {
        String sample2 = " sample2\r\n";
        printStrAndTrimedStr(sample2);
    }

   // さっきのサンプルと同じメソッドは省略
}


実行結果

[ sample2
](0x20 0x73 0x61 0x6D 0x70 0x6C 0x65 0x32 0x0D 0x0A) -> trim -> [sample2](0x73 0x61 0x6D 0x70 0x6C 0x65 0x32)

半角スペース(0x20)だけではなく、改行コードのCR (0x0D) と LF (0x0A) も削られています。


今度は、末尾にNUL (NULL文字)を含む文字列で実行してみます。

サンプルコード

public class TrimSample3 {

    public static void main(String[] args) {
        byte[] bytes = "sample3 _".getBytes();
        bytes[bytes.length - 1] = 0x00;
        String sample3 = new String(bytes);
        printStrAndTrimedStr(sample3);
    }

   // さっきのサンプルと同じメソッドは省略
}


実行結果

[sample3 ](0x73 0x61 0x6D 0x70 0x6C 0x65 0x33 0x20 0x00) -> trim -> [sample3](0x73 0x61 0x6D 0x70 0x6C 0x65 0x33)

この結果から、NULL文字 (0x00) も削られることが分かります。


まとめ

String#trimは、先頭と末尾の 半角スペースだけではなく 改行コードなどの 0x20以下の文字を削ります。

ASCII文字列の16進数表記を取得する

JavaでASCII文字列の16進数表記の値(Hex Dump)を取得するサンプルです。

以下のようなメソッドを用意します。

import java.util.stream.Collectors;

static String asciiHexDump(String ascii, String delimiter) {
    return ascii.chars()
            .mapToObj(b -> String.format("0x%02X", b))
            .collect(Collectors.joining(delimiter));
}


実行サンプルは以下の通りです

サンプルコード

import java.util.stream.Collectors;

public class TrimSample {

    public static void main(String[] args) {
        String sample1 = "sample1";
        System.out.printf("%s -> [%s]\n", sample1, asciiHexDump(sample1, ","));

        System.out.println();

        String sample2 = " sample2\r\n";
        System.out.printf("%s -> [%s]\n", sample2, asciiHexDump(sample2, " "));
    }

    private static String asciiHexDump(String ascii, String delimiter) {
        return ascii.chars()
                .mapToObj(b -> String.format("0x%02X", b))
                .collect(Collectors.joining(delimiter));
    }
}


実行結果

sample1 -> [0x73,0x61,0x6D,0x70,0x6C,0x65,0x31]

 sample2
 -> [0x20 0x73 0x61 0x6D 0x70 0x6C 0x65 0x32 0x0D 0x0A]

Nクイーン問題を扱ってみる

8クイーンと呼ばれるパズルが存在しています。

チェスのクイーン(上下左右斜めに何マスでも進める)を、チェスボードの8×8マスに、8つのクイーンを互いに利きに入らないように配置するパズルです。
8×8マスの盤面の中に、縦・横・斜めにクイーンが重複しないよう配置していくパズルということになります。

この8という値を変数Nに置き換えたものをNクイーン問題と呼びます。
Nの値によって、答えの総数は異なっています。

ちなみに、Nが3以下の場合は解が無いことがわかっています。

今回はこのNクイーン問題をJavaで扱ってみます。
ちなみにクイーンの配置可能なパターンを1つだけ見つけ出すサンプルになっています。


いきなりですがサンプルコードになります。

正直言って以下サイトを参考にさせてもらっています


サンプルコード

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.IntStream;

public class NQueenSearch {

    /** 盤面上のクイーンの配置(index=row, 値=column) */
    private final int[] board;

    /** クイーンのColumn(値=column)位置の候補群 */
    private final int[] candidateColumnPositions;

    /** 探索回数のLimit */
    private final int searchLimit;

    /** 配置するクイーンの数 */
    private final int queenCount;

    /** 現在の探索回数 */
    private int searchCnt = 0;

    NQueenSearch(int searchLimit, int boardSize) {
        this.searchLimit = searchLimit;
        this.queenCount = boardSize;

        this.board = new int[queenCount];
        this.candidateColumnPositions = new int[queenCount];

        for (int i = 0; i < queenCount; i++) {
            candidateColumnPositions[i] = i;
        }
    }

    public boolean searchQueenPositions() {
        return put(0);
    }

    /**
     * 対象の深さ(行)でクイーンが配置可能かチェックします
     *
     * @param depth 探索時の深さ(=行)
     * @return 配置可能ならtrue, それ以外の場合はfalse
     */
    boolean put(int depth) {

        // limit回探索しても見つからなければ一旦あきらめる
        if (searchCnt > searchLimit) {
            return false;
        }
        searchCnt++;

        if (depth == queenCount) {
            return true;
        }

        // 配置可能なColumnかどうか(配置可能=true)
        boolean enabledPut[] = new boolean[queenCount];
        Arrays.fill(enabledPut, true);

        // これまで探索した結果から対象の深さ(行)で配置可能な空きのColumnを設定する(配置不可能な場所を除外する)
        IntStream.range(0, depth)
                .forEach(i -> {
                    // 既に配置済みColumnは利用不可 としてマーク
                    enabledPut[board[i]] = false;

                    // 左下斜め方向(/)は配置できないようにマーク
                    if (board[i] - (depth - i) >= 0) {
                        enabledPut[board[i] - (depth - i)] = false;
                    }

                    // 右下斜め方向(\)は配置できないようにマーク
                    if (board[i] + (depth - i) < queenCount) {
                        enabledPut[board[i] + (depth - i)] = false;
                    }
                });

        // 対象行で配置してみて配置可能かチェックする
        for (int i = 0; i < queenCount; i++) {
            if (enabledPut[candidateColumnPositions[i]]) {
                board[depth] = candidateColumnPositions[i];
                if (put(depth + 1)) {
                    // 対象の深さ(行)での配置場所が見つかった
                    return true;
                }
            }
        }

        // 対象の深さ(行)での配置場所が見つからなかった
        return false;
    }

    void reset() {
        randomShuffleArray(candidateColumnPositions);
        this.searchCnt = 0;
        // System.out.printf("Execute reset. %s\n", Arrays.toString(candidateColumnPositions));
    }

    // Fisher–Yates shuffle
    void randomShuffleArray(int[] array) {
        Random rnd = ThreadLocalRandom.current();
        for (int i = array.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // 要素入れ替え(swap)
            int tmp = array[index];
            array[index] = array[i];
            array[i] = tmp;
        }
    }

    public void printQueensBoard() {
        int n = board.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i] == j) {
                    System.out.printf("Q ");
                } else {
                    System.out.printf("* ");
                }
            }
            System.out.println();
        }
        System.out.printf("%s\n\n", "-------------------------------------------------");
    }

    @Override
    public String toString() {
        int[] cols = Arrays.stream(board)
                .map(val -> val + 1)
                .toArray();
        return Arrays.toString(cols);
    }

    public static void main(String[] args) {
        int boardSize = 128;

        long time = searchAndPrint(boardSize);

        System.out.printf("time: %d(ms)", time);
    }

    private static long searchAndPrint(int boardSize) {
        if (boardSize <= 3) {
            throw new RuntimeException("Not Found Solution.");
        }

        int limit = boardSize + 1000;
        NQueenSearch nQueenSearch = new NQueenSearch(limit, boardSize);

        long start = System.currentTimeMillis();

        do {
            // 置く順番をランダムに定める
            nQueenSearch.reset();
        } while(!nQueenSearch.searchQueenPositions());

        long end = System.currentTimeMillis();

        System.out.println(nQueenSearch.toString());

        System.out.println("-------------------------------------------------");

        nQueenSearch.printQueensBoard();

        return end - start;

    }
}

基本的にバックトラッキングを使っているわけですが、素直に綺麗に順番通りやっていると、
Nが大きくなった際に解にたどり着く時間が極端に大きくなるため、
乱択アルゴリズムも組み合わさっています。


N=8の場合の実行例

上記のmainメソッド内のローカル変数boardSizeがNの値に対応しています。
(上記のコードは8×8の盤面に8つクイーンを配置する8クイーン問題となります)

実行結果例は以下になります

[7, 3, 1, 6, 8, 5, 2, 4]
-------------------------------------------------
* * * * * * Q * 
* * Q * * * * * 
Q * * * * * * * 
* * * * * Q * * 
* * * * * * * Q 
* * * * Q * * * 
* Q * * * * * * 
* * * Q * * * * 
-------------------------------------------------

time: 60(ms)

1行目の内容が、各行の何番目の列にクイーンを配置しているかを表現している列番号(1〜N列目)の配列の内容です。
(上の例では1行目は7列目に、2行目は3列目に配置、3行目は1列目に配置・・・ということを表しています)

その下には盤面上のクイーンの配置状況を2次元で表現しています。

さらに、解を見つけるまでにかかった時間(ミリ秒)も出力しています。


N=20の場合の実行例

実行結果例は以下になります

[10, 7, 2, 8, 20, 18, 1, 6, 19, 13, 4, 14, 9, 15, 5, 11, 17, 3, 16, 12]
-------------------------------------------------
* * * * * * * * * Q * * * * * * * * * * 
* * * * * * Q * * * * * * * * * * * * * 
* Q * * * * * * * * * * * * * * * * * * 
* * * * * * * Q * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * Q 
* * * * * * * * * * * * * * * * * Q * * 
Q * * * * * * * * * * * * * * * * * * * 
* * * * * Q * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * Q * 
* * * * * * * * * * * * Q * * * * * * * 
* * * Q * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * Q * * * * * * 
* * * * * * * * Q * * * * * * * * * * * 
* * * * * * * * * * * * * * Q * * * * * 
* * * * Q * * * * * * * * * * * * * * * 
* * * * * * * * * * Q * * * * * * * * * 
* * * * * * * * * * * * * * * * Q * * * 
* * Q * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * Q * * * * 
* * * * * * * * * * * Q * * * * * * * * 
-------------------------------------------------

time: 61(ms)


N=128の場合の実行例

実行結果例は以下になります

[83, 38, 111, 128, 61, 40, 113, 62, 81, 32, 84, 60, 54, 79, 102, 8, 45, 58, 31, 115, 18, 74, 25, 70, 87, 116, 36, 125, 118, 26, 76, 57, 86, 23, 101, 120, 72, 33, 65, 78, 41, 69, 15, 93, 29, 75, 21, 27, 117, 14, 28, 1, 112, 109, 88, 24, 2, 68, 10, 53, 4, 35, 94, 42, 123, 56, 49, 110, 89, 7, 121, 43, 5, 55, 6, 11, 47, 97, 13, 104, 19, 119, 16, 105, 124, 85, 100, 17, 51, 59, 50, 9, 46, 99, 96, 126, 64, 48, 39, 44, 22, 108, 66, 91, 71, 67, 63, 20, 107, 95, 37, 106, 12, 90, 30, 52, 77, 122, 127, 103, 34, 80, 98, 3, 82, 73, 92, 114]
-------------------------------------------------
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * 
* * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * 
* * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Q * * * * * * * * * * * * * * 
-------------------------------------------------

time: 182(ms)


まとめ

今回はサンプル的にNクイーン問題をJavaで扱ってみました。
もうちょっと改良すべきポイントある気がしますが、今回はこの辺で・・・。



関連リンク

Java - 配列をシャッフルする

Javaで配列をシャッフルするサンプルです。


Listをシャッフルする

Javaで、List内部の要素をシャッフル(ランダムに入れ替え)するには、
Java標準で用意されている Collections.shuffle のAPIを利用すればよいです。


コードサンプル

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ShuffleListSample {

    public static void main(String[] args) {
        List<Integer> targetList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9));

        // シャッフルする前
        printArray(targetList, "No Shuffle");

        // シャッフル1回目
        Collections.shuffle(targetList);
        printArray(targetList, "Shuffle 1 ");

        // シャッフル2回目
        Collections.shuffle(targetList);
        printArray(targetList, "Shuffle 2 ");

        // シャッフル3回目
        Collections.shuffle(targetList);
        printArray(targetList, "Shuffle 3 ");
    }

    private static void printArray(List<Integer> list, String headerComment) {
        System.out.printf("%s -> %s\n\n", headerComment, list);
    }
}


実行結果

No Shuffle -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

Shuffle 1  -> [6, 7, 1, 5, 8, 3, 2, 4, 9]

Shuffle 2  -> [5, 2, 9, 3, 1, 7, 4, 6, 8]

Shuffle 3  -> [4, 1, 7, 2, 8, 6, 5, 3, 9]


配列をシャッフルする場合

Listの場合は、標準でシャッフルするAPIが用意されていますが、配列の場合そのようなAPIが用意されていません。
以下のようなメソッドを用意しましょう。(以下はint配列用です)

public static void shuffle(int[] array) {
    // 配列が空か1要素ならシャッフルしようがないので、そのままreturn
    if (array.length <= 1) {
        return;
    }

    // Fisher–Yates shuffle
    Random rnd = ThreadLocalRandom.current();
    for (int i = array.length - 1; i > 0; i--) {
        int index = rnd.nextInt(i + 1);
        // 要素入れ替え(swap)
        int tmp = array[index];
        array[index] = array[i];
        array[i] = tmp;
    }
}

上記は、Fisher–Yates shuffle(フィッシャー - イェーツのシャッフル)というアルゴリズムでシャッフルしています。


実行のためのサンプルコードは以下の通りです。

import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

public class FisherYatesShuffleSample {

    public static void main(String[] args) {
        int[] targetArray = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};

        // シャッフルする前
        printArray(targetArray, "No Shuffle");

        // シャッフル1回目
        shuffle(targetArray);
        printArray(targetArray, "Shuffle 1 ");

        // シャッフル2回目
        shuffle(targetArray);
        printArray(targetArray, "Shuffle 2 ");

        // シャッフル3回目
        shuffle(targetArray);
        printArray(targetArray, "Shuffle 3 ");
    }

    public static void shuffle(int[] array) {
        // 配列が空か1要素ならシャッフルしようがないのので、そのままreturn
        if (array.length <= 1) {
            return;
        }

        // Fisher–Yates shuffle
        Random rnd = ThreadLocalRandom.current();
        for (int i = array.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            // 要素入れ替え(swap)
            int tmp = array[index];
            array[index] = array[i];
            array[i] = tmp;
        }
    }

    private static void printArray(int[] array, String headerComment) {
        System.out.printf("%s -> %s\n\n", headerComment, Arrays.toString(array));
    }
}


実行結果

No Shuffle -> [1, 2, 3, 4, 5, 6, 7, 8, 9]

Shuffle 1  -> [2, 3, 8, 4, 9, 5, 6, 1, 7]

Shuffle 2  -> [9, 7, 5, 2, 6, 3, 4, 1, 8]

Shuffle 3  -> [2, 8, 5, 4, 1, 6, 7, 3, 9]


まとめ

Fisher–Yates shuffle で配列をシャッフルすることができるようになりました。