2. 騎士巡歴問題
著者:梅谷 武
騎士巡歴問題の解法を実装する。
作成:2024-06-01
更新:2024-10-29
更新:2024-10-29
騎士巡歴問題きしじゅんれきもんだい, knight's tour problem(knight's tour problem)とは8×8のチェス盤上をナイトを移動させてすべての枡目を一回ずつ通過させるという問題である。ナイトとは将棋の桂馬と同じ動きを前後左右の四方向にできるチェスの駒である。
チェス盤を8×8行列boardで表わし、-1で初期化しておく。ナイトの初期位置は(0,0)に固定する。ナイトが何回動いたかをcountで表わす。次の状態は可能な8個の枡目で有効なものの中からいずれかを選び、count = count + 1とし、その枡目にcountを書き込む。これを繰り返してcountが63になったとき解が求まっている。この最初の解が求まったら終了する。プログラムは探索空間を木と考えたときの深さ優先探索(バックトラック法)で書く。
ktour.cpp:
#include <print>
#include <vector>
const int N = 8;
const int moveX[8] = {2, 1, -1, -2, -2, -1, 1, 2};
const int moveY[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool isValidMove(int x, int y, const std::vector<std::vector<int>> &board) {
return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1);
}
bool KnightTour(int x, int y, int count, std::vector<std::vector<int>> &board) {
if (count == N * N)
return true;
for (int k = 0; k < N; ++k) {
int nextX = x + moveX[k];
int nextY = y + moveY[k];
if (isValidMove(nextX, nextY, board)) {
board[nextX][nextY] = count;
if (KnightTour(nextX, nextY, count + 1, board))
return true;
else
board[nextX][nextY] = -1;
}
}
return false;
}
void printBoard(const std::vector<std::vector<int>> &board) {
for (const auto &row : board) {
for (const auto &cell : row)
std::print("{}\t", cell);
std::print("\n");
}
}
int main() {
std::vector<std::vector<int>> board(N, std::vector<int>(N, -1));
board[0][0] = 0;
if (KnightTour(0, 0, 1, board))
printBoard(board);
else
std::println("No solution exists.");
return 0;
}
makefile:
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = ktour.cpp
EXES = ktour_g ktour_l
all: $(EXES)
ktour_g: $(SRC)
$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
ktour_l: $(SRC)
$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
clean:
rm -f $(EXES)
$ measure ./ktour_g
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
======================================
Process exited with status: 0
total time: 0.233499 [sec]
mem size: 3676 [KB]
code size: 118 [KB]
$ measure ./ktour_l
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
======================================
Process exited with status: 0
total time: 0.225330 [sec]
mem size: 3696 [KB]
code size: 92 [KB]
ktour.ml:
open Printf
let n = 8
let moveX = [|2; 1; -1; -2; -2; -1; 1; 2|]
let moveY = [|1; 2; 2; 1; -1; -2; -2; -1|]
let is_valid_move x y board =
x >= 0 && x < n && y >= 0 && y < n && board.(x).(y) = -1
let rec knight_tour x y count board =
if count = n * n then true
else
let rec try_moves k =
if k = n then false
else
let nextX = x + moveX.(k) in
let nextY = y + moveY.(k) in
if is_valid_move nextX nextY board then
begin
board.(nextX).(nextY) <- count;
if knight_tour nextX nextY (count + 1) board then true
else
begin
board.(nextX).(nextY) <- -1;
try_moves (k + 1)
end
end
else
try_moves (k + 1)
in
try_moves 0
let print_board board =
Array.iter (fun row ->
Array.iter (fun cell ->
printf "%d\t" cell
) row;
printf "\n"
) board
let () =
let board = Array.make_matrix n n (-1) in
board.(0).(0) <- 0;
if knight_tour 0 0 1 board then
print_board board
else
printf "No solution exists.\n"
$ ocamlopt -O2 -o ktour ktour.ml
$ measure ./ktour
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
======================================
Process exited with status: 0
total time: 0.514517 [sec]
mem size: 5496 [KB]
code size: 2343 [KB]
ktour.rkt:
#lang racket
(require iso-printf)
(define n 8)
(define moveX (vector 2 1 -1 -2 -2 -1 1 2))
(define moveY (vector 1 2 2 1 -1 -2 -2 -1))
(define (is-valid-move? x y board)
(and (>= x 0) (< x n) (>= y 0) (< y n) (= (vector-ref (vector-ref board x) y) -1)))
(define (try-moves k x y count board)
(if (= k n)
#f
(let* ([nextX (+ x (vector-ref moveX k))]
[nextY (+ y (vector-ref moveY k))])
(if (is-valid-move? nextX nextY board)
(begin
(vector-set! (vector-ref board nextX) nextY count)
(if (knight-tour nextX nextY (+ count 1) board)
#t
(begin
(vector-set! (vector-ref board nextX) nextY -1)
(try-moves (+ k 1) x y count board))))
(try-moves (+ k 1) x y count board)))))
(define (knight-tour x y count board)
(if (= count (* n n))
#t
(try-moves 0 x y count board)))
(define (print-board board)
(for ([i n])
(for ([j n])
(printf "%d\t" (vector-ref (vector-ref board i) j)))
(printf "\n")))
(define board (for/vector ([i n]) (make-vector n -1)))
(vector-set! (vector-ref board 0) 0 0)
(if (knight-tour 0 0 1 board)
(print-board board)
(printf "No solution exists.\n"))
$ raco exe ktour.rkt
$ measure ./ktour
0 59 38 33 30 17 8 63
37 34 31 60 9 62 29 16
58 1 36 39 32 27 18 7
35 48 41 26 61 10 15 28
42 57 2 49 40 23 6 19
47 50 45 54 25 20 11 14
56 43 52 3 22 13 24 5
51 46 55 44 53 4 21 12
======================================
Process exited with status: 0
total time: 1.425365 [sec]
mem size: 133788 [KB]
code size: 12446 [KB]
測定結果を表にまとめる。単位は秒[sec]。
| 測定項目 | GCC | Clang | OCaml | Racket |
|---|---|---|---|---|
| knight's tour | 0.233 | 0.225 | 0.515 | 1.425 |
[1] Wikipedia, Knight's tour, Wikimedia Foundation, Inc., 2024
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani