bashで8 queensを並列処理

並列処理で8 queensを解きます。bashで竹内関数( https://qiita.com/nihongi/items/21a4a215920150ef7eb8 )では、サブシェルをdisった気がしますが、ここではサブシェルが活躍します。

並列化しない場合

8queens1.sh

#!/bin/sh

board="0000000000000000000000000000000000000000000000000000000000000000"

put() {
  # ${1}の${2}列目にクイーンを置く
  # 0列目は無条件に置ける
  if [ ${2} -eq 0 ]; then
    for i in {0..7}
    do
      tmp=${1:0:$(( ${2} + 8 * ${i} ))}"1"${1:$(( ${2} + 8 * ${i} + 1 ))}
      put ${tmp} 1
    done
  else
  # 1列目以降
    # もしi行目にクイーンを置いたら(${2}-1)列目までに衝突があるかを調べる
    # 衝突がなければクイーンを置いて次の列に行く
    for i in {0..7}
    do
      for j in `seq 0 $(( ${2} - 1 ))`  # j列目
      do
        # 横方向
        if [ "${1:$(( ${j} + 8 * ${i} )):1}" = "1" ]; then
          continue 2
        fi
        # 斜め上方向
        if [ $(( ${i} + ${j} - ${2} )) -ge 0 ]; then
          if [ "${1:$(( ${j} + 8 * ( ${i} + ${j} - ${2} ) )):1}" = "1" ]; then
            continue 2
          fi
        fi
        # 斜め下方向
        if [ $(( ${i} + ${2} - ${j} )) -le 7 ]; then
          if [ "${1:$(( ${j} + 8 * ( ${i} + ${2} - ${j} ) )):1}" = "1" ]; then
            continue 2
          fi
        fi
      done
      # 衝突なし
      tmp=${1:0:$(( ${2} + 8 * ${i} ))}"1"${1:$(( ${2} + 8 * ${i} + 1 ))}
      if [ ${2} = 7 ]; then
        echo ${tmp}
      else
        put ${tmp} $(( ${2} + 1 ))
      fi
    done
  fi
}

put ${board} 0

実行結果

$ time sh 8queens1.sh
1000000000000010000010000000000101000000000100000000010000100000
1000000000000010000100000000010000000001010000000000100000100000
(途中省略)
0010000000001000010000000000000100000100000100000000001010000000
0010000000000100000100000100000000000001000010000000001010000000

real    0m19.155s
user    0m11.444s
sys     0m7.939s

長いので途中省略してますが、92個の解が表示されます。時間は19秒程度です。

並列処理化

putの再帰呼び出しの部分をサブシェルでバックグラウンドでの実行に変えます。差分だけ載せます。

diff

$ diff 8queens1.sh 8queens2.sh
12c12
<       put ${tmp} 1
---
>       (put ${tmp} 1)&
44c44
<         put ${tmp} $(( ${2} + 1 ))
---
>         (put ${tmp} $(( ${2} + 1 )))&

実行結果

$ time sh 8queens2.sh

real    0m0.003s
user    0m0.001s
sys     0m0.002s
$ 0001000001000000000000100010000000000100000000010000100010000000
0000100001000000000100000000001000100000000000010000010010000000
0010000000001000010000000000000100000100000100000000001010000000
0010000000000010010000000000000100000100000100001000000000001000
0000010000010000010000000000000100001000000000101000000000100000
0010000000000100000000010100000000010000100000000000001000001000
(以下省略)

timeコマンドが先に終わって、その後にわらわらと答えが返ってきます。実体がバックグラウンドで動いているのでこうなります。最後の答えが返るまで約5秒くらいです。CPUのコア数が4なので、時間が4分の1に減ったのだと思います。よくわかりませんが。

結論

並列処理にしたら本当に速くなりました。めでたしめでたし。