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