【H30春AP午後】ナイトの巡歴問題をbashで解く

はじめに

昨日は半年に一度の情報処理技術者試験でした。
受験した方はお疲れ様でした☺️

私も応用情報技術者試験(以下、AP)を受験しました。やはり午前2時間半、午後2時間半の計5時間も頭を使うと疲れますね。

終わったあとにチョコ食いまくりました🍫

チョコ食べながら帰っていた人がいたらきっと私です。

ナイトの巡歴問題

APで午後のプログラミングの問題は、「ナイトの巡歴問題」というパズルを解くプログラムの実装でした。

ただ、問題にはプログラムの実装までしか記載されておらず、実行結果まではわかりませんでした。
めちゃくちゃ頑張って考えたアルゴリズムを実行できないのはもどかしいので、実際にシェルスクリプトで実装して出力してみました。

注意

この問題を解いていない方にはネタバレになってしまいますのでご注意ください。
公式の問題冊子 がすでに公表されているので、問題を読んでから本記事を読むことをおすすめします。
H30 春 AP 午後 p.16 問3

環境

• OS：macOS High Sierra 10.13.1

解法

変更前

変更前とは、問題で盤面を拡大する前のことです。

実装

できる限り変数名やアルゴリズムなどを問題のプログラムに近づけて実装しました。

knights_tour.sh

#!/bin/bash

# 問題で省略されている定数の定義
# 盤面のサイズは引数で渡せるようにする
readonly M=$1
readonly N=$2
# 添字を1から始めるよう、0番目の要素を空にする
readonly dv=("" -2 -1 1 2 2 1 -1 -2)
readonly dh=("" 1 2 2 1 -1 -2 -2 -1)

function search () {
  local i=$1
  local v=$2
  local h=$3
  if [ $v -ge 1 ] && [ $v -le $m ]; then
    if [ $h -ge 1 ] && [ $h -le $n ]; then
      local board=`eval echo \\$board${v}${h}`
      if [ $board == 0 ]; then
        eval board${v}${h}=$i
        if [ $i == $((m * n)) ]; then
          printBoard
          printFlag=1
        else
          local j
          for (( j=1; j<=8; j++ )); do
            search $((i + 1)) $((v + ${dv[j]})) $((h + ${dh[j]}))
          done
        fi
        eval board${v}${h}=0
      fi
    fi
  fi
}

# 解答を出力する
function printBoard () {
  local v
  for (( v=1; v<=$m; v++ )); do
    local h
    for (( h=1; h<=$n; h++ )); do
      # Macでは `/bin/echo` を使わないと改行しない `-n` オプションが使えない
      # 見やすさのため、数字間にスペースを設ける
      eval /bin/echo -n "\$board${v}${h}"; /bin/echo -n " "
    done
    echo "" # 改行
  done
  echo "" # 見やすさのため、解答の末尾でも改行
}

function main () {
  m=$M
  n=$N
  initBoard
  printFlag=0
  search 1 1 1
  if [ $printFlag == 0 ]; then
    echo "解答がありません。"
  fi
}

# boardを初期化する
# 問題で省略されている関数
function initBoard () {
  local v
  for (( v=1; v<=$m; v++ )); do
    local h
    for (( h=1; h<=$n; h++ )); do
      eval board${v}${h}=0
    done
  done
}

main


exit

bashには2次元配列がないので、board[v][h]はevalを使って無理やり実現しました。
board12のような変数をM×Nつ生成して2次元配列に見せかけています。
参考
http://www.kurobuti.com/blog/?p=4880

出力結果

# sh knights_tour.sh M N
$ sh knights_tour.sh 4 3
1 8 3
4 11 6
7 2 9
10 5 12

1 12 3
4 9 6
7 2 11
10 5 8

4×3の盤面では2通りの解がありました。

盤面のサイズを変えて実行してみます。

$ sh knights_tour.sh 3 4
1 4 7 10
12 9 2 5
3 6 11 8

1 4 7 10
8 11 2 5
3 6 9 12

$ sh knights_tour.sh 4 4
解答がありません。

当然ですが3×4は4×3と同じ2通りの解がありました。
4×4は解がないようです。

変更後

実装

knights_tour_after.sh

#!/bin/bash

readonly M=$1
readonly N=$2
readonly dv=("" -2 -1 1 2 2 1 -1 -2)
readonly dh=("" 1 2 2 1 -1 -2 -2 -1)

function search () {
  local i=$1
  local v=$2
  local h=$3
- if [ $v -ge 1 ] && [ $v -le $m ]; then
-   if [ $h -ge 1 ] && [ $h -le $n ]; then
      local board=`eval echo \\$board${v}${h}`
      if [ $board == 0 ]; then
        eval board${v}${h}=$i
        if [ $i == $((m * n)) ]; then
          printBoard
          printFlag=1
        else
          local j
          for (( j=1; j<=8; j++ )); do
            search $((i + 1)) $((v + ${dv[j]})) $((h + ${dh[j]}))
          done
        fi
        eval board${v}${h}=0
      fi
-   fi
- fi
}

function printBoard () {
  local v
- for (( v=1; v<=$m; v++ )); do
+ for (( v=3; v<=$((m + 2)); v++ )); do
    local h
-   for (( h=1; h<=$n; h++ )); do
+   for (( h=3; h<=$((n + 2)); h++ )); do
      eval /bin/echo -n "\$board${v}${h}"; /bin/echo -n " "
    done
    echo ""
  done
  echo ""
}

function main () {
  m=$M
  n=$N
  initBoard
  printFlag=0
- search 1 1 1
+ search 1 3 3
  if [ $printFlag == 0 ]; then
    echo "解答がありません。"
  fi
}

function initBoard () {
  local v
- for (( v=1; v<=$m; v++ )); do
+ for (( v=1; v<=$((m + 2 * 2)); v++ )); do
    local h
-   for (( h=1; h<=$n; h++ )); do
+   for (( h=1; h<=$((n + 2 * 2)); h++ )); do
+     if [ $v -le 2 ] || [ $v -gt $((m + 2)) ] || [ $h -le 2 ] || [ $h -gt $((n + 2)) ]; then
+       eval board${v}${h}=1
+     else
        eval board${v}${h}=0
+     fi
    done
  done
}

main


exit

出力結果

$ sh knights_tour_after.sh 4 3
1 8 3
4 11 6
7 2 9
10 5 12

1 12 3
4 9 6
7 2 11
10 5 8

変更前と同様の結果になっています。

変更前後の処理時間

何となく気になったので、 time コマンドを使って変更前後の処理時間を計測してみました。
user の時間を載せています。

盤面	変更前	変更後
4×3	0m0.169s	0m0.289s
4×4	0m4.776s	0m7.981s
5×4	1m25.523s	2m16.912s

圧倒的に変更前の方が早いです 。
search 再帰関数の簡略化より、盤面が大きくなったことによるオーバーヘッドの方が大きかったということでした。

変更前も処理が遅いと思うのは私だけでしょうか。
他の言語だと5×4でも一瞬で処理が終わる気がします。

おわりに

シェルスクリプトを初めてがっつり書いたので、おかしな構文も多々あると思います。
お気づきのことがありましたらご指摘いただければ幸いです。

そして実装して気づきましたが、 試験では設問③の(1)を間違えていました。
ループで1→を3にするだけで満足し、mとnに2を足し忘れていました。
時間が足りなくて見直しする時間がなかったんです。。

おまけ(リファクタリング)

リファクタリングしたい欲望に駆られるあたり、私もプログラマとして成長している証なのでしょうか。
せめて 早期リターンはしてほしい！
おそらくネストを深くして読みづらくするためにわざとやっているのでしょうが、将来性豊かな大学生の方などが勘違いして覚えてしまうのでやめた方がいいと思います。

ということで簡単にできる範囲でリファクタリングしてみました。

knights_tour_refactoring.sh

#!/bin/bash

# 定数定義
readonly BOARD_ROWS=$1
readonly BOARD_COLUMNS=$2
readonly SRC_V=1
readonly SRC_H=1
readonly dv=(-2 -1 1 2 2 1 -1 -2)
readonly dh=(1 2 2 1 -1 -2 -2 -1)

# ----------------------------------------
# ナイトを次のマスへ移動させる
# 引数：$1 移動順序
# 　　：$2 移動先の行番号
# 　　：$3 移動先の列番号
# 備考：再帰関数
# ----------------------------------------
function search () {
  local i=$1
  local v=$2
  local h=$3
  if [ $v -lt 1 ] || [ $v -gt $BOARD_ROWS ] ||
     [ $h -lt 1 ] || [ $h -gt $BOARD_COLUMNS ]; then
    return
  fi
  local board=`eval echo \\$board${v}${h}`
  if [ $board != 0 ]; then
    return
  fi
  eval board${v}${h}=$i
  if [ $i == $((BOARD_ROWS * BOARD_COLUMNS)) ]; then
    printSolution
    solutionExists=true
  else
    local j
    for (( j=0; j<=7; j++ )); do
      search $((i + 1)) $((v + ${dv[j]})) $((h + ${dh[j]}))
    done
  fi
  eval board${v}${h}=0
}

# 解答を出力する
function printSolution () {
  local v
  for (( v=1; v<=$BOARD_ROWS; v++ )); do
    local h
    for (( h=1; h<=$BOARD_COLUMNS; h++ )); do
      eval /bin/echo -n "\$board${v}${h}"; /bin/echo -n " "
    done
    echo ""
  done
  echo ""
}

# boardを初期化する
function initBoard () {
  local v
  for (( v=1; v<=$BOARD_ROWS; v++ )); do
    local h
    for (( h=1; h<=$BOARD_COLUMNS; h++ )); do
      eval board${v}${h}=0
    done
  done
}

function main () {
  initBoard
  solutionExists=false
  search 1 $SRC_V $SRC_H
  if [ $solutionExists == false ]; then
    echo "解答がありません。"
  fi
}


main


exit

やったこととしては主に以下の3つです。

• 早期リターン
• リネーム
• コメントの追加

…あまり変わっていないかもしれません。
むしろ変数名が長くなることで可読性が落ちている気すらします。

編集リクエストでプロシェルスクリプターさまが華麗なリファクタリングを見せてくれないかなぁ。。(チラッ

参考リンク

• ナイト・ツアー - Wikipedia