ExcelでCASL2シミュレータ

需要があるかどうかなんて、どうでもいい。ただ作りたいから作った(笑

ダウンロード ➡ Releases https://github.com/kktworks/CASL2-EXCEL/releases

f:id:kktworks:20220123115842p:plain

  • CASL2のコードをセルに入力(だってExcelですから...)→[ASM]ボタン押下でアセンブル実行


f:id:kktworks:20220123115904p:plain

  • 水色の行 ... 次に実行する行
  • [>>]ボタン ... ブレークポイント or 終了まで実行
  • [>]ボタン ... 1行実行
  • [⇒]ボタン ... Step over
  • [Trace ON]ボタン ... トレース表示する。トグルボタンになっていてTrace OFF(トレースしない)と交互に切り替わる
  • [MEM]ボタン ... メモリマップ表示(別ウィンドウ)
  • [STACK]ボタン ... スタックエリアの内容表示(別ウィンドウ)
  • [再]ボタン ... プログラムを再実行するとき押下する
  • 16進表示/算術10進/論理10進 ... GR値の表示方法
  • GR4下の空白列 ... ダブルクリックすると*が表示される→ブレークポイント。もう一度ダブルクリックでクリア。


f:id:kktworks:20220123115914p:plain

  • 緑色のセル ... 直前に実行した命令で読まれた(READ)エリア
  • オレンジ色のセル ... 直前に実行した命令で書き込まれた(WRITE)エリア
  • 斜体+太字 ... 直前に実行した命令で実効アドレス算出に使われたアドレス


動いている様子が見たい方は、こちらをDownloadしてご覧ください
https://github.com/kktworks/CASL2-EXCEL/blob/main/CASL2-Excel.mp4

RustでCASL2シミュレーター^3

さらにデバッガーも作ってみた。機能としては,,,

などができるようにした。このくらいないと、情報処理試験問題の動きを追うのが大変。といっても、受験するわけではないが。

ソースは全部で3.1KS。exeファイルは1.3MB。ここまで作ってやっと、借用やらスライスの意味が分かってきたような、わからないような。小さいプログラムをたくさん書くのもいいけど、それだけでは見えないこともたくさんあるね。

RustでCASL2シミュレーター

少しシステムぽいものを作りたくなって、RustでCASL2シュミレータにチャレンジ。空いた時間にコツコツ作ってたら1ヶ月かかった。規模は2.4KS(exeファイルは1.3MB)。構成は以下のような感じ。

  • lexer(字句解析)
  • プリプロセッサ(マクロの処理)
  • parser(構文解析、エラーチェック)
  • assembler(バイナリコードへ変換)
  • comet(バイナリコードの実行)

基本的に、行単位に処理すれば良いから、他の言語処理系に比べればメチャメチャ楽。と思ったけど、さすがはRust。そう簡単には行かない。特に文字列の扱いで悩むこと多かった。加えてデータ構造をどうするかで悩む。やはり最後はデータ構造をどうするかだよね...。

とりあえずコマンドラインで動くようになってきたから、しばらくCASL2プログラムを実行しまくってバグだし。安定したら次の展開を考える。

Rustで騎士の周遊(Closed knight's tour) BOARD_SIZE=8の場合(その2)

ワーンスドロフの規則(with Warnsdorf's Heuristic)で移動可能マス目が少ない順にするところがベタな配列の並び替えだったので、Vec + クロージャで書き換えてみた。JavaでもComparator使えばCollections.sort()でソートできるけどね。

use std::time::Instant;

// チェス盤の大きさ
const BOARD_SIZE: i32 = 8;

//  チェス盤のデータ型
type Board = [[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize];

// 開始位置
static Y_START_POS: i32 = 0;
static X_START_POS: i32 = 0;

// 次の配置場所候補との差分
const DELTA_X: [i32; 8] = [1, 2, -1, -2, 1, 2, -1, -2];
const DELTA_Y: [i32; 8] = [2, 1, 2, 1, -2, -1, -2, -1];

//  次に配置する場所候補
struct EvalInfo {
    direction: usize,
    grids: i32,
}
fn sort_asc(candidates: &mut Vec<EvalInfo>) {
    candidates.sort_by_key(|candidate| candidate.grids);
}

// 見つけた解の数
static mut NUM_OF_ANSWER: i32 = 0;
// 開始時間
static mut ST: Vec<Instant> = Vec::new();
// ナイトを置いた回数
static mut STEPS: i32 = 0;

//  メイン処理
fn main() {
    // チェス盤作成
    let mut board: Board = [[0 as i32; BOARD_SIZE as usize]; BOARD_SIZE as usize];
    unsafe {
        ST.push(Instant::now());
    }
    // 開始位置に 1 を置いて探索開始
    tour(&mut board, Y_START_POS, X_START_POS, 1);
}

///    ナイトを配置して、次に置く場所を探す
fn tour(board: &mut Board, y: i32, x: i32, step: i32) {
    board[y as usize][x as usize] = step;
    unsafe {
        STEPS += 1;
    }
    // すべてのマス目を巡回した
    if step == BOARD_SIZE * BOARD_SIZE {
        // 1 へ戻れる(=次の移動先候補に1がある)ならClosed knight's tour
        if can_move_to(board, y, x, 1) {
            print_board(board);
            std::process::exit(0);
        } else {
            // Closed knight's tourではない
            return;
        }
    }

    // 次に置く場所を探す(ワーンスドロフの規則:with Warnsdorf's Heuristic)
    let mut next_candidates: Vec<EvalInfo> = Vec::new();
    let mut x2;
    let mut y2;
    let mut xc;
    let mut yc;
    let mut n;
    // 次に移動可能なマスを探す
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        if can_put_to(board, y2, x2) {
            // そこから移動可能なマスをカウント
            n = 0;
            for j in 0..DELTA_X.len() {
                xc = x2 + DELTA_X[j];
                yc = y2 + DELTA_Y[j];
                if can_put_to(board, yc, xc) {
                    n += 1;
                }
            }

            // 移動方向, 移動可能マス数
            next_candidates.push(EvalInfo {
                direction: i,
                grids: n,
            });
        }
    }

    // 移動できるマスがなければバックトラック
    if next_candidates.is_empty() {
        return;
    }

    // 移動可能マス数を昇順にする
    sort_asc(&mut next_candidates);

    // 移動可能マス数が少ない順に試す
    //for i in 0..count.len() {
    for c in &next_candidates {
        // ナイトを置いてみる
        x2 = x + DELTA_X[c.direction];
        y2 = y + DELTA_Y[c.direction];
        board[y2 as usize][x2 as usize] = step + 1;

        // 開始位置(=1)から移動できるマスがなくなるならやめる
        if board[y2 as usize][x2 as usize] != BOARD_SIZE * BOARD_SIZE {
            if number_of_places(board, Y_START_POS, X_START_POS) < 1 {
                board[y2 as usize][x2 as usize] = 0;
                continue;
            }
        }

        // 次の場所を探す
        tour(board, y2, x2, step + 1);
        // ナイトを取る
        board[y2 as usize][x2 as usize] = 0;
    }
}

///    結果を整形して出力する
fn print_board(board: &Board) {
    let et = Instant::now();
    unsafe {
        NUM_OF_ANSWER += 1;
        //    println!("[{}] {}", NUM_OF_ANSWER, Local::now().format("%H:%M:%S"));
        println!("[{}] elapsed:{:?}", NUM_OF_ANSWER, (et - ST[0]));
        println!("steps={}", STEPS);
    }
    let mut line: String = "    +".to_string();
    line.push_str(&"---+".repeat(BOARD_SIZE as usize));

    print!("     ");
    for x in 0..BOARD_SIZE {
        print!("{:3} ", x);
    }
    println!();
    println!("{}", line);
    for y in 0..BOARD_SIZE as usize {
        print!(" {:>2} |", y);
        for x in 0..BOARD_SIZE as usize {
            print!("{:>3}|", board[y][x]);
        }
        println!("");
        println!("{}", line);
    }
}

/// board[y][x]にナイトが置けるかチェック
fn can_put_to(board: &mut Board, y: i32, x: i32) -> bool {
    return (-1 < x && x < BOARD_SIZE)
        && (-1 < y && y < BOARD_SIZE)
        && (board[y as usize][x as usize] == 0);
}

///board[y][x]から移動可能なマス数を返す
fn number_of_places(board: &mut Board, y: i32, x: i32) -> i32 {
    let mut x2;
    let mut y2;
    let mut count = 0;
    // 8方向に対して
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        // 未通過
        if can_put_to(board, y2, x2) {
            count += 1;
        }
    }
    return count;
}

/// board[y][x]からstepのマスへ移動できるかチェックする
fn can_move_to(board: &Board, y: i32, x: i32, step: i32) -> bool {
    let mut x2: i32;
    let mut y2: i32;
    // 8方向チェックする
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        // 移動可能な箇所に指定されたstepがある
        if (-1 < x2 && x2 < BOARD_SIZE)
            && (-1 < y2 && y2 < BOARD_SIZE)
            && (board[y2 as usize][x2 as usize] == step)
        {
            return true;
        }
    }
    return false;
}

Software Design 9月号 Rustでわかるメモリ管理

「Rust」という言葉に惹かれて買ったけど、なんか中途半端な感じ。正直「誰得なの?」と思うような特集。でも第2特集の「BigQueryが分析基盤に選ばれる理由」が面白かったのが救い。

Rustで騎士の周遊(Closed knight's tour) BOARD_SIZE=8の場合

BOARD_SIZE=6までなら周遊も一瞬だが、BOARD_SIZE=8ではそうはいかない。前回のプログラムでは一晩実行してもダメ。そこで「ワーンスドロフの規則」を適用してみる。

ワーンスドロフの規則(秋山 仁・中村義作 共著, 『POD版 ゲームに潜む数理』, 森北出版, 2019)

あるマスに飛び移ったとき, そのマスからさらに飛び移ることのできるすべてのマスを拾い上げる. そして, それぞれのマスからさらに何個のマスに飛び移れるかを数え, 最小の飛び方しかできないマスに飛び移る. ただし, 対象となるマスが 2 個以上あれば, そのなかの任意のマスを選ぶ.

これは証明された方法ではないが、やってみるとBOARD_SIZE=8,10,12,14,16,18はどこから初めても一瞬で解けるような感じ。以下はBOARD_SIZE=16で左上(0,0)開始の場合。処理時間は自分のノートPCのHyper-V上で100μ秒位)。そこから先は開始場所による。BOARD_SIZE=20の場合、(0,0), (10,0)はダメっぽいけど(9,9)からなら一瞬。

       0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15 
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  0 |  1|252| 31|244|205|196| 29|194|203|106| 27|104|187|108| 25|102|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  1 | 32|207|256|253| 30|243|204|197| 28|193|202|107| 26|103|180|109|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  2 |255|  2|251|206|245|216|195|234|201|198|105|186|181|188|101| 24|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  3 |208| 33|254|247|250|235|242|217|192|221|190|199|112|179|110|177|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  4 |  3|248|209|240|215|246|233|222|231|200|185|182|189|176| 23|100|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  5 | 34|211|214|249|236|241|230|167|218|191|220|113|184|111|178| 67|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  6 |213|  4|239|210|227|166|237|232|223|160|183|172|175| 68| 99| 22|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  7 |128| 35|212|165|238|229|226|161|168|219|170|149|114|173| 66| 69|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  8 |  5|164|129|228|143|162|157|224|159|148|115|174|171| 98| 21| 64|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
  9 | 36|127|136|163|156|225|144|141|152|169|150| 93|116| 65| 70| 55|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 10 |133|  6|155|130|137|142|153|158|147| 92|117| 80| 97| 56| 63| 20|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 11 |126| 37|132|135|154|145|140| 87|118|151| 94| 73| 62| 71| 54| 57|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 12 |  7|134|125|138|131| 86|119|146| 91| 74| 81| 96| 79| 58| 19| 50|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 13 | 38|123| 40| 85|120|139| 88| 45| 82| 95| 76| 61| 72| 51| 16| 53|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 14 | 41|  8|121|124| 43| 10| 83| 90| 75| 12| 47| 78| 59| 14| 49| 18|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
 15 |122| 39| 42|  9| 84| 89| 44| 11| 46| 77| 60| 13| 48| 17| 52| 15|
    +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

以下はRust版。

use std::time::Instant;

// チェス盤の大きさ
const BOARD_SIZE: i32 = 8;

// 開始位置
static Y_START_POS: i32 = 0;
static X_START_POS: i32 = 1;

// 次の配置場所候補との差分
const DELTA_X: [i32; 8] = [1,  2, -1, -2, 1, 2, -1, -2];
const DELTA_Y: [i32; 8] = [2, 1, 2, 1,  -2,  -1, -2, -1 ];

// 見つけた解の数
static mut NUM_OF_ANSWER: i32 = 0;

static mut ST: Vec<Instant> = Vec::new();
static mut STEPS: i32 = 0;
static NO_MOVE_POS: i32 = 9;

fn main() {
    // チェス盤作成
    let mut board = [[0 as i32; BOARD_SIZE as usize]; BOARD_SIZE as usize];
    unsafe {
        ST.push(Instant::now());
    }
    // 開始位置に 1 を置いて探索開始
    tour(&mut board, Y_START_POS, X_START_POS, 1);
}

///    ナイトを配置して、次に置く場所を探す
fn tour(board: &mut [[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize], y: i32, x: i32, step: i32) {
    board[y as usize][x as usize] = step;
    unsafe {
        STEPS += 1;
    }
    // すべてのマス目を巡回した
    if step == BOARD_SIZE * BOARD_SIZE {
        // 1 へ戻れる(=次の移動先候補に1がある)ならClosed knight's tour
        if can_move_to(board, y, x, 1) {
            print_board(board);
            std::process::exit(0);
        } else {
            // Closed knight's tourではない
            return;
        }
    }

    // 次に置く場所を探す(ワーンスドロフの規則:with Warnsdorf's Heuristic)
    let mut x2;
    let mut y2;
    let mut xc;
    let mut yc;
    let mut n;
    // 次に移動できるマスからさらに移動できるマス数
    let mut count = [NO_MOVE_POS as i32; BOARD_SIZE as usize];
    // 移動可能マス数に対応する方向
    let mut direction = [0 as usize; BOARD_SIZE as usize];

    // 次に移動可能なマスを探す
    let mut is_found = false;
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        if can_put_to(board, y2, x2) {
            is_found = true;
            // そこから移動可能なマスをカウント
            n = 0;
            for j in 0..DELTA_X.len() {
                xc = x2 + DELTA_X[j];
                yc = y2 + DELTA_Y[j];
                if can_put_to(board, yc, xc) {
                    n += 1;
                }
            }
            // 移動可能マス数
            count[i] = n;
            // その方向
            direction[i] = i;
        }
    }

    // 移動できるマスがなければバックトラック
    if !is_found {
        return;
    }

    // 移動可能マス数を昇順にする(方向も同期させる)
    let mut temp: i32;
    let mut temp2: usize;
    for i in 0..count.len() - 1 {
        for j in i+1..count.len() {
            if count[i] > count[j] {
                temp = count[i];
                count[i] = count[j];
                count[j] = temp;

                temp2 = direction[i];
                direction[i] = direction[j];
                direction[j] = temp2;
            }
        }
    }

    // 移動可能マス数が少ない順に試す
    for i in 0..count.len() {
        // なくなったらバックトラック
        if count[i] == NO_MOVE_POS {
            break;
        }

        // ナイトを置いてみる
        x2 = x + DELTA_X[direction[i]];
        y2 = y + DELTA_Y[direction[i]];
        board[y2 as usize][x2 as usize] = step + 1;
        //print_board(board);

        // 開始位置(=1)から移動できるマスがなくなるならやめる
        if board[y2 as usize][x2 as usize] != BOARD_SIZE * BOARD_SIZE {
            if number_of_places(board, Y_START_POS, X_START_POS) < 1 {
                board[y2 as usize][x2 as usize] = 0;
                continue;
            }
        }

        // 次の場所を探す
        tour(board, y2, x2, step + 1);
        // ナイトを取る
        board[y2 as usize][x2 as usize] = 0;
    }
}

///    結果を整形して出力する
fn print_board(board: &[[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize]) {
    let et = Instant::now();
    unsafe {
        NUM_OF_ANSWER += 1;
        //    println!("[{}] {}", NUM_OF_ANSWER, Local::now().format("%H:%M:%S"));
        println!("[{}] elapsed:{:?}", NUM_OF_ANSWER, (et - ST[0]));
        println!("steps={}", STEPS);
    }
    let mut line: String = "    +".to_string();
    line.push_str(&"---+".repeat(BOARD_SIZE as usize));

    print!("     ");
    for x in 0..BOARD_SIZE {
        print!("{:3} ", x);
    }
    println!();
    println!("{}", line);
    for y in 0..BOARD_SIZE as usize {
        print!(" {:>2} |", y);
        for x in 0..BOARD_SIZE as usize {
            print!("{:>3}|", board[y][x]);
        }
        println!("");
        println!("{}", line);
    }
}

/// board[y][x]にナイトが置けるかチェック
fn can_put_to(board: &mut [[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize], y: i32, x: i32) -> bool {
    return (-1 < x && x < BOARD_SIZE)
        && (-1 < y && y < BOARD_SIZE)
        && (board[y as usize][x as usize] == 0);
}

///board[y][x]から移動可能なマス数を返す
fn number_of_places(
    board: &mut [[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize],
    y: i32,
    x: i32,
) -> i32 {
    let mut x2;
    let mut y2;
    let mut count = 0;
    // 8方向に対して
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        // 未通過
        if can_put_to(board, y2, x2) {
            count += 1;
        }
    }
    return count;
}

/// board[y][x]からstepのマスへ移動できるかチェックする
fn can_move_to(
    board: &[[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize],
    y: i32,
    x: i32,
    step: i32,
) -> bool {
    let mut x2: i32;
    let mut y2: i32;
    // 8方向チェックする
    for i in 0..DELTA_X.len() {
        x2 = x + DELTA_X[i];
        y2 = y + DELTA_Y[i];
        // 盤面の中で 1 が配置されている
        if (-1 < x2 && x2 < BOARD_SIZE)
            && (-1 < y2 && y2 < BOARD_SIZE)
            && (board[y2 as usize][x2 as usize] == step)
        {
            return true;
        }
    }
    return false;
}

これも先にJava版を作ってからRustに書き換えた。

package com.example;

import java.util.Collections;

public class KnightsTourW2 {
    // チェス盤の大きさ
    private static final int BOARD_SIZE = 8;

    // 開始位置
    private static final int Y_START_POS = 0;
    private static final int X_START_POS = 1;

    // 次の配置場所候補との差分
    private static final int[] DELTA_X = { 1, 2, -1, -2, 1, 2, -1, -2 };
    private static final int[] DELTA_Y = { 2, 1, 2, 1, -2, -1, -2, -1 };

    // 見つけた解の数
    private static int numOfAnswer = 0;

    private static long st = 0;
    private static long steps = 0;
    private static int NO_MOVE_POS = 9;

    public static void main(String[] args) {
        // チェス盤作成
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
        st = System.currentTimeMillis();
        // 開始位置に 1 を置いて探索開始
        tour(board, Y_START_POS, X_START_POS, 1);
    }

    /**
    * ナイトを配置して、次に置く場所を探す
    * @param board
    * @param x
    * @param y
    * @param step
    */
    private static void tour(int[][] board, int y, int x, int step) {
        board[y][x] = step;
        steps++;

        // すべてのマス目を巡回した
        if (step == BOARD_SIZE * BOARD_SIZE) {
            // 1 へ戻れる(=次の移動先候補に1がある)ならClosed knight's tour
            if (canMoveTo(board, y, x, 1)) {
                printBoard(board);
                System.exit(0);
            } else {
                // Closed knight's tourではない
                return;
            }
        }

        // 次に置く場所を探す(ワーンスドロフの規則:with Warnsdorf's Heuristic)
        int x2, y2, xc, yc;
        int n = 0;
        // 次に移動できるマスからさらに移動できるマス数
        int[] count = new int[BOARD_SIZE];
        // 移動可能マス数に対応する方向
        int[] direction = new int[BOARD_SIZE];
        // 移動可能マス数
        for (int i = 0; i < count.length; ++i) {
            count[i] = NO_MOVE_POS;
        }
        // 次に移動可能なマスを探す
        boolean isFound = false;
        for (int i = 0; i < DELTA_X.length; i++) {
            x2 = x + DELTA_X[i];
            y2 = y + DELTA_Y[i];
            if (canPutTo(board, y2, x2)) {
                isFound = true;
                // そこから移動可能なマスをカウント
                n = 0;
                for (int j = 0; j < DELTA_X.length; j++) {
                    xc = x2 + DELTA_X[j];
                    yc = y2 + DELTA_Y[j];
                    if (canPutTo(board, yc, xc)) {
                        ++n;
                    }
                }
                // 移動可能マス数
                count[i] = n;
                // その方向
                direction[i] = i;
            }
        }

        // 移動できるマスがなければバックトラック
        if (!isFound) {
            return;
        }

        // 移動可能マス数を昇順にする(方向も同期させる)
        int temp;
        for (int i = 0; i < count.length - 1; i++) {
            for (int j = i + 1; j < count.length; j++) {
                if (count[i] > count[j]) {
                    temp = count[i];
                    count[i] = count[j];
                    count[j] = temp;

                    temp = direction[i];
                    direction[i] = direction[j];
                    direction[j] = temp;
                }
            }
        }

        // 移動可能マス数が少ない順に試す
        for (int i = 0; i < count.length; i++) {
            // なくなったらバックトラック
            if (count[i] == NO_MOVE_POS) {
                break;
            }

            // ナイトを置いてみる
            x2 = x + DELTA_X[direction[i]];
            y2 = y + DELTA_Y[direction[i]];
            board[y2][x2] = step + 1;

            // 開始位置(=1)から移動できるマスがなくなるならやめる
            if (board[y2][x2] != BOARD_SIZE * BOARD_SIZE) {
                if (numberOfPlaces(board, Y_START_POS, X_START_POS) < 1) {
                    board[y2][x2] = 0;
                    continue;
                }
            }

            // 次の場所を探す
            tour(board, y2, x2, step + 1);
            // ナイトを取る
            board[y2][x2] = 0;
        }
    }

    /**
    * 結果を整形して出力する
    * @param board
    */
    private static void printBoard(int[][] board) {
        long et = System.currentTimeMillis();

        ++numOfAnswer;
        System.out.printf("[%,d] elapsed:%,dms\n", numOfAnswer, (et - st));
        System.out.printf("steps=%,d\n", steps);
        StringBuffer line = new StringBuffer();
        line.append("    +");
        line.append(String.join("", Collections.nCopies(BOARD_SIZE, "---+")));

        System.out.print("     ");
        for (int x = 0; x < BOARD_SIZE; x++) {
            System.out.printf("%3d ", x);
        }
        System.out.println();
        System.out.println(line.toString());
        for (int y = 0; y < BOARD_SIZE; y++) {
            System.out.printf(" %2d |", y);
            for (int x = 0; x < BOARD_SIZE; x++) {
                System.out.printf("%3d|", board[y][x]);
            }
            System.out.println();
            System.out.println(line.toString());
        }
    }

    /**
    * board[y][x]にナイトが置けるかチェック
    * @param board
    * @param y
    * @param x
    * @return
    */
    private static boolean canPutTo(int[][] board, int y, int x) {
        return (-1 < x && x < BOARD_SIZE) && (-1 < y && y < BOARD_SIZE) && (board[y][x] == 0);
    }

    /**
    * board[y][x]から移動可能なマス数を返す
    * @param board
    * @param y
    * @param x
    * @return
    */
    private static int numberOfPlaces(int[][] board, int y, int x) {
        int x2, y2;
        int count = 0;
        // 8方向に対して
        for (int i = 0; i < DELTA_X.length; i++) {
            x2 = x + DELTA_X[i];
            y2 = y + DELTA_Y[i];
            // 未通過
            if (canPutTo(board, y2, x2)) {
                count++;
            }
        }
        return count;
    }

    /**
    * board[y][x]からstepのマスへ移動できるかチェックする
    * @param board
    * @param y
    * @param x
    * @param step
    * @return
    */
    private static boolean canMoveTo(int[][] board, int y, int x, int step) {
        int x2, y2;
        // 8方向チェックする
        for (int i = 0; i < DELTA_X.length; i++) {
            x2 = x + DELTA_X[i];
            y2 = y + DELTA_Y[i];
            // 盤面の中で step が配置されている
            if ((-1 < x2 && x2 < BOARD_SIZE) && (-1 < y2 && y2 < BOARD_SIZE) && (board[y2][x2] == step)) {
                return true;
            }
        }
        return false;
    }
}