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;
    // ８方向に対して
    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;
    // ８方向チェックする
    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;
}