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 公式ガイドを読んだ自分は大丈夫だったけど、Stringとstr、借用、などは文章だけでなく、図が無いとイメージしづらいのでは。
- 後半はWebアプリ、WebAssembly、GUIアプリ、組み込みシステムなどへの適用について。
- 読むならプログラミング言語Rust 公式ガイドのあと、実践Rust入門[言語仕様から開発手法まで]の前かな。
実践Rust入門[言語仕様から開発手法まで](2回目)
2回目読了。本業が忙しいから大分時間がかかた。
![実践Rust入門[言語仕様から開発手法まで]](https://m.media-amazon.com/images/I/51e5B1Zx+yL._SL500_.jpg "実践Rust入門[言語仕様から開発手法まで]")
- プログラミング言語Rust 公式ガイドを熟読したから、この本に書いてあることがわかる、という感じ。1冊目がこれだとかなり厳しと思う。
- 大きめのサンプル(ToyVecとか)を作りながら重要な概念を説明してるけど、「こういう場合、～を使います」あるいは「こうします」的な書き方で「なぜこれが必要なのか？」の説明が少なめ。
- プログラミング言語Rust 公式ガイドよりもテクニカルなことが説明されているんだけど、それがサンプルコードの機能説明の中に埋まっていて、あとから探すときに少々不便。
- あと日本語的に、、、な文章も散見される。編集さん、もうちょっと頑張って欲しかった。
さて次は↓これだ。
プログラミング言語Rust 公式ガイド(2回目)
写経しつつ2回目読了。
- コードを打ち込んで試すだけでなく、ノートに手書きで書き写しながらやってみた。またサンプルコードをあれやこれやいじってみた。おかげでかなり理解が進んだ気がする。
- 型変換のおかげでメソッド仮引数には&を書かなくて済むんだけど「このメソッドは所有権をとるの?それとも参照?」と悩む。まぁAPI Docを見れば解決するんですけどね。でもDerefを使って推移的にされる場合は、？となる。慣れと言われればそうだけど、はじめは理屈がわからなくて悩む。
- String(文字列)とstr(スライス)が、まだしっくりこない。これも型変換で&str型の引数にStringを渡せるせいかも。
- Result
, Option は便利。 - 所有権、ライフタイムは、Java以上に堅牢なプログラムを作るのに役立ちそう。
ということで、再度↓にチャレンジする。
Wikipediaへの寄付
最近アクセスするたびにバナーが表示されるので「そろそろ来るか？」と思ってたら、創設者からのメールが届いた。1,560円でいいらしかったけど、Wikipediaにはほぼ毎日お世話になっているので3,000円寄付した。これで今年も2%の特別な読者になったわけだ。
Git本
これから急いでGitを学びたいなら、この本(以下「わかばちゃん」)がお薦め。
漫画と図解でほんとわかりやすい。何よりもたとえが秀逸。例えばステージングすることを「撮影台に載せる」とかね。そしてgitコマンドではなく、SourceTreeでgit操作を説明しているのがイイ。
Git入門書には「いちばんやさしい」を標榜しているいちばんやさしいGit&GitHubの教本 人気講師が教えるバージョン管理&共有入門 (「いちばんやさしい教本」シリーズ)もあるけど、この本は基本gitコマンドで各種操作を説明している。いまどきコマンドでやるの？SourceTreeとかGUI操作が主流じゃね？gitコマンドを学びたい人にはいいけど、ソース管理するためのgitなんだから、本末転倒な気もする。 そう考えるとお薦めできない。
SourceTree前提ならGitが、おもしろいほどわかる基本の使い方33 改訂新版もあるけど、わかばちゃんに比べ説明が難しい。同じことを説明しているんだけど、わかばちゃんの方がずっとわかりやすい。読むならわかばちゃんの次にした方がいいと思う。
もっとも現場ではSourceTreeじゃなくてEclipseのEGitとか、Visual Studio Codeのgitプラグインを使う場合も多いので、もうちょっと勉強が必要になることも多いけど、「forkしてcloneしてbranch切ってpullしてcommitしてpushしてpull requestしてmergeしてもらう」という一連の流れが理解でき、現場でもみんなの会話について行けるようになると思う。とりあえずこれを読めばGitは大丈夫じゃね？と思う内容になってます。
