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;
    }
}

Rustで騎士の周遊(Closed knight's tour)

エイトクイーンやったら次はこれでしょ。出発地点に戻ってくるので騎士の巡回ではなく周遊というらしい。BOARD_SIZE=6なら解が求められるけど、8では返ってこない。ロジックを少し変えないとダメ。それでもBOARD_SIZE=6ならJava版の2倍の速さで全パターン見つけ出す。

use std::time::Instant;

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

// 次の配置場所計算用
const NEXT_X: [i32; 8] = [1, 2, 2, 1, -1, -2, -2, -1];
const NEXT_Y: [i32; 8] = [-2, -1, 1, 2, 2, 1, -1, -2];

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

fn main() {
    // チェス盤
    let mut board = [[0 as i32; BOARD_SIZE as usize]; BOARD_SIZE as usize];
    let st = Instant::now();
    board[0][0] = 1;
    tour(0, 0, 1, &mut board);

    let et = Instant::now();
    unsafe {
        println!("num of path={}, elapsed: {:?}", NUM_OF_ANSWER, (et - st));
    }
}

// ナイトを次に置く場所を探す
fn tour(y: i32, x: i32, step: i32, board: &mut [[i32; BOARD_SIZE as usize]; BOARD_SIZE as usize]) {
    let mut x2; //  let mut x2, y2; とは書けない
    let mut y2;
    // すべてのマス目を巡回した
    if step == BOARD_SIZE * BOARD_SIZE {
        // 次の移動先候補に1があればClosed knight's tour
        for i in 0..NEXT_X.len() {
            x2 = x + NEXT_X[i];
            y2 = y + NEXT_Y[i];
            // 盤面の中
            if (-1 < x2 && x2 < BOARD_SIZE) && (-1 < y2 && y2 < BOARD_SIZE) {
                // 開始位置か?
                if board[y2 as usize][x2 as usize] == 1 {
                    // 結果を出力
                    print_board(board);
                    return;
                }
            }
        }
        // Closed knight's tourではない
        return;
    }
    // 次に置く場所を探す
    for i in 0..NEXT_X.len() {
        x2 = x + NEXT_X[i];
        y2 = y + NEXT_Y[i];
        // 盤面の中
        if (-1 < x2 && x2 < BOARD_SIZE) && (-1 < y2 && y2 < BOARD_SIZE) {
            // まだナイトを置いていない
            if board[y2 as usize][x2 as usize] == 0 {
                // ナイトを置く
                board[y2 as usize][x2 as usize] = step + 1;
                // 次の場所を探す
                tour(y2, x2, step + 1, board);
                // ナイトを取る
                board[y2 as usize][x2 as usize] = 0;
            }
        }
    }
}

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

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

これも先にJava版を作ってRustに書き直した。元プログラムはこれ。

package com.example;

import java.util.Collections;
import java.util.Date;

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

    // 次の配置場所計算用
    private static final int[] nextX = { 1, 2, 2, 1, -1, -2, -2, -1 };
    private static final int[] nextY = { -2, -1, 1, 2, 2, 1, -1, -2 };

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

    public static void main(String[] args) {
        // チェス盤
        int[][] board = new int[BOARD_SIZE][BOARD_SIZE];

        long st = System.currentTimeMillis();

        board[0][0] = 1;
        tour(0, 0, 1, board);

        long et = System.currentTimeMillis();
        System.out.printf("num of path=%,d elapsed: %,d(ms)\n", numOfAnswer, (et - st));
    }

    /**
    * ナイトを次に置く場所を探す
    * @param x
    * @param y
    * @param step
    * @param board
    */
    private static void tour(int y, int x, int step, int[][] board) {
        int x2, y2;
        // すべてのマス目を巡回した
        if (step == BOARD_SIZE * BOARD_SIZE) {
            // 次の移動先候補に1があればClosed knight's tour
            for (int i = 0; i < nextX.length; i++) {
                x2 = x + nextX[i];
                y2 = y + nextY[i];
                // 盤面の中
                if ((-1 < x2 && x2 < BOARD_SIZE) && (-1 < y2 && y2 < BOARD_SIZE)) {
                    // 開始位置か?
                    if (board[y2][x2] == 1) {
                        // 結果を出力
                        printBoard(board);
                        //System.exit(0);
                        return;
                    }
                }
            }
            // Closed knight's tourではない
            return;
        }

        // 次に置く場所を探す
        for (int i = 0; i < nextX.length; i++) {
            x2 = x + nextX[i];
            y2 = y + nextY[i];
            // 盤面の中
            if ((-1 < x2 && x2 < BOARD_SIZE) && (-1 < y2 && y2 < BOARD_SIZE)) {
                // まだナイトを置いていない
                if (board[y2][x2] == 0) {
                    // ナイトを置く
                    board[y2][x2] = step + 1;
                    // 次の場所を探す
                    tour(y2, x2, step + 1, board);
                    // ナイトを取る
                    board[y2][x2] = 0;
                }
            }
        }
    }

    /**
    * 結果を整形して出力する
    * @param board
    */
    private static void printBoard(int[][] board) {
        ++numOfAnswer;
        System.out.printf("[%,d] %tT\n", numOfAnswer, new Date());
        StringBuffer sb = new StringBuffer();
        sb.append("+");
        sb.append(String.join("", Collections.nCopies(BOARD_SIZE, "---+")));

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

    }
}

Rustでエイト・クイーン

本業が一段落したので、またRustの勉強。本読むだけではつまらないし、経験値上がらないので、プログラム書いてみる。テーマは「エイト・クイーン」。いきなりRustで書き下ろす自信は無いので、Javaで書いてそれをRustへ書き直してみた。よって、Rustの良さを生かし切れていないのは十分承知。それでもいろいろ知見が得られた。

use std::time::Instant;

// Queenの数 = チェス盤の大きさ
const NUM_OF_QUEEN: i32 = 8;
// 見つけた解の数
static mut NUM_OF_ANSWER: i32 = 0;

fn main() {
    let mut buff = [0; NUM_OF_QUEEN as usize];
    let st = Instant::now();
    place(0, &mut buff);
    let et = Instant::now();
    println!("elapsed: {:?}", et - st);
}

/// 指定された列でQueenが置ける行を探す
fn place(col: i32, buff: &mut [i32]) {
    // N-Queen完成
    if col == NUM_OF_QUEEN {
        unsafe {
            NUM_OF_ANSWER += 1;
            println!("{}:{:?}", NUM_OF_ANSWER, buff);
        }
        return;
    }

    // Queenを置ける場所を探す
    for row in 0..NUM_OF_QUEEN {
        if check_can_place_queen(col, row, buff) {
            //  おける
            buff[col as usize] = row;
            //  次の列へ
            place(col + 1, buff)
        }
    }
}

/// col, rowで指定された盤面の場所にQueenが置けるかチェックする
fn check_can_place_queen(col: i32, row: i32, buff: &[i32]) -> bool {
    // 左端列は自由における
    if col == 0 {
        return true;
    }

    // この列の左側の配置状況から判断する
    for i in 0..col {
        // 同じ行に配置済
        if buff[i as usize] == row {
            return false;
        }
        // 左上斜め方向に配置済
        if buff[i as usize] == (row - col + i) {
            return false;
        }
        // 左下斜め方向に配置済
        if buff[i as usize] == (row + col - i) {
            return false;
        }
    }
    // ここに配置できる
    return true;
}
  • 外部変数(グローバル変数)が使いにくい。シングルスレッドで実行するから競合する恐れは無いんだけど、コンパイラはそれを知らないからunsafeを要求する。

  • 配列の添字はusize。i32ではダメ。as usizeが必要。

  • 再帰呼び出しでbuffをcloneして渡すのかと思ったけど、&mutでいけた。所有権とか、参照の規則から見て良いんだろうか。

ちなみに最初に作ったJavaプログラムはこんな感じ。

package com.example;

public class NQueen {
    // Queenの数 = チェス盤の大きさ
    private static final int NUM_OF_QUEEN = 8;
    // 見つけた解の数
    private static int numOfAnswer = 0;

    public static void main(String[] args) {
        int[] buff = new int[NUM_OF_QUEEN];
        long st = System.currentTimeMillis();
        place(0, buff);
        long et = System.currentTimeMillis();
        System.out.printf("time=%,d(ms)\n", et - st);
    }

    /**
    * 指定された列でQueenが置ける行を探す
    * @param col
    */
    private static void place(int col, int[] buff) {
        if (col == NUM_OF_QUEEN) {
            // N-Queen完成
            ++numOfAnswer;
            System.out.printf("%,d:[", numOfAnswer);
            for (int i = 0; i < NUM_OF_QUEEN; i++) {
                if (i > 0) {
                    System.out.print(", ");
                }
                System.out.print(buff[i]);
            }
            System.out.println("]");
            return;
        }
        // Queenを置ける場所を探す
        for (int row = 0; row < NUM_OF_QUEEN; row++) {
            if (checkCanPlaceQueen(col, row, buff)) {
                // 配置できる
                buff[col] = row;
                // 次の列へ
                place(col + 1, buff);
            }

        }
    }

    /**
    * col, rowで指定された盤面の場所にQueenが置けるかチェックする
    * @param col
    * @param row
    * @param buff
    * @return
    */
    private static boolean checkCanPlaceQueen(int col, int row, int[] buff) {
        // 左端列は自由における
        if (col == 0) {
            return true;
        }

        // この列の左側の配置状況から判断する
        for (int i = 0; i < col; i++) {
            // 同じ行に配置済
            if (buff[i] == row) {
                return false;
            }
            // 左上斜め方向に配置済
            if (buff[i] == (row - col + i)) {
                return false;
            }
            // 左下斜め方向に配置済
            if (buff[i] == (row + col - i)) {
                return false;
            }
        }
        // ここに配置できる
        return true;
    }

}

実践Rustプログラミング入門

さくっと読了。

実践Rust入門[言語仕様から開発手法まで](2回目)

2回目読了。本業が忙しいから大分時間がかかた。

  • プログラミング言語Rust 公式ガイドを熟読したから、この本に書いてあることがわかる、という感じ。1冊目がこれだとかなり厳しと思う。
  • 大きめのサンプル(ToyVecとか)を作りながら重要な概念を説明してるけど、「こういう場合、~を使います」あるいは「こうします」的な書き方で「なぜこれが必要なのか?」の説明が少なめ。
  • プログラミング言語Rust 公式ガイドよりもテクニカルなことが説明されているんだけど、それがサンプルコードの機能説明の中に埋まっていて、あとから探すときに少々不便。
  • あと日本語的に、、、な文章も散見される。編集さん、もうちょっと頑張って欲しかった。

さて次は↓これだ。

プログラミング言語Rust 公式ガイド(2回目)

写経しつつ2回目読了。

  • コードを打ち込んで試すだけでなく、ノートに手書きで書き写しながらやってみた。またサンプルコードをあれやこれやいじってみた。おかげでかなり理解が進んだ気がする。
  • 型変換のおかげでメソッド仮引数には&を書かなくて済むんだけど「このメソッドは所有権をとるの?それとも参照?」と悩む。まぁAPI Docを見れば解決するんですけどね。でもDerefを使って推移的にされる場合は、?となる。慣れと言われればそうだけど、はじめは理屈がわからなくて悩む。
  • String(文字列)とstr(スライス)が、まだしっくりこない。これも型変換で&str型の引数にStringを渡せるせいかも。
  • Result, Optionは便利。
  • 所有権、ライフタイムは、Java以上に堅牢なプログラムを作るのに役立ちそう。

ということで、再度↓にチャレンジする。