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

}