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

    }
}