Nクイーン問題(3)第一章 バックトラック準備編


【参考リンク】Nクイーン問題 過去記事一覧はこちらから

前回までのあらすじ

前回の記事では、エイトクイーンの3つのルール
1.縦に一つだけのクイーン
2.横に一つだけのクイーン
3.斜めに一つだけのクイーン

の「1.縦に一つだけのクイーン」を実現する方法を紹介しました。

N5の時の実行結果ですが、

:
:
:
3117:4 4 4 3 1 
3118:4 4 4 3 2 
3119:4 4 4 3 3 
3120:4 4 4 3 4 
3121:4 4 4 4 0 
3122:4 4 4 4 1 
3123:4 4 4 4 2 
3124:4 4 4 4 3 
3125:4 4 4 4 4 

N5の場合、3125ステップかかりました。
このステップは計算で算出することが可能です。

5*5*5*5*5=3125
N^N=3125

ということになります。
こうした、可能性のあるすべての解を体系的に「ちからまかせ」に数え上げる方法を、ブルートフォースといいます。

今回は、抑制ルールを1つ加えます。

今回は、前回のルールに加え、「2.横に一つだけのクイーン」を追加します。
要するに、縦にも横にもクイーンの効きが当たらないように配置するということになります。

そういう意味で、前回は「ブルートフォース」、今回は少し手を入れている分、「バックトラック準備編」という位置づけでご説明します。
次回は、エイトクイーンの解決方法の金字塔「バックトラック」の完成です。

考え方

これまでのクイーンの並びは、以下のような並びであってもカウントしていました。
(できたということにしていました)

        column(列)
   _4___3___2___1___0_
  |-Q-|-Q-|-Q-|-Q-|-Q-|0
  +-------------------+
  |---|---|---|---|---|1
  +-------------------+ 
  |---|---|---|---|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

今回からは、縦列に一つのクイーンというルールに加えてさらに、「横行にも一つのクイーンしかおけないからね」というルールが追加されるわけです。

まず、スタート段階はクイーンは0列目に一つ(0,0)クイーンを配置します。

        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|---|---|1
  +-------------------+ 
  |---|---|---|---|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

次に1列目にクイーンを配置します。
(1,0)は(0,0)のクイーンの効きとなります。
よって1列目のクイーンは(1,1)に配置されます。
以下のようになります。

        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|---|---|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

次は2列目ですが、(2,0)も置けません。
同様に(2,1)も置けません。
結果、(2,2)に配置することになります。

        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

こうして続けていくと、以下のような形で5列全てにクイーンが配置されることになります。

4,3,2,1,0

        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|---|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

縦(各列)に一つだけのクイーン、というルールに加えて、横(各行)に一つだけのクイーン、というルールが加わり、今回の配置によって「一つの解を見つけた」ということになりました。

列と行に一つだけのクイーンという縛りについての検討は、この画面から考えてみるのが良いのです。

問題は、ここからなのです。
そのまえにソースを以下に示します。

ソース

#!/usr/bin/bash

declare -i COUNT=0;   # カウンター
: '
 縦と横に1つだけのクイーン
';
function N-Queens03(){
  local -i min="$1";
  local -i size="$2";
  local -i col=0;       # 再帰に必要
  local -i row=0;       # 再帰に必要
  local sEcho="";       # 出力用変数
  for(( col=0;col<size;col++ )){
    if (( down[col] == 0 ));then
      pos[$min]="$col";
      if (( min==(size-1) ));then
        # echo -n "$((COUNT++)): ";
        # 画面出力はせず変数に格納
        ((COUNT++));
        for(( row=0;row<size;row++ )){
          #echo -n " ${pos[row]} "
          # 画面出力はせず変数に格納
          #sEcho="${sEcho}${pos[row]} ";
          sEcho="${pos[row]} ${sEcho}";
        }
        # echo "";  # 改行
        # ここでまとめて画面に出力
        # -n オプションは付けずに改行付きで出力します。
        echo "$COUNT: $sEcho"     # flush出力
      else
        down[$col]=1; # trueを代入
        N-Queens03 "$((min+1))" "$size" ;
        down[$col]=0; # falseを代入
      fi
    fi
  }
}
#
echo "<>3.バックトラック準備編 N-Queens03()";
N-Queens03 0 5;

実行結果

実行結果は以下のとおりです。

$ bash N-Queens03.sh
<>3.バックトラック準備編 N-Queens03()
1: 4 3 2 1 0 
2: 3 4 2 1 0 
3: 4 2 3 1 0 
4: 2 4 3 1 0 
5: 3 2 4 1 0 
6: 2 3 4 1 0 
7: 4 3 1 2 0 
8: 3 4 1 2 0 
9: 4 1 3 2 0 
10: 1 4 3 2 0 
11: 3 1 4 2 0 
12: 1 3 4 2 0 
13: 4 2 1 3 0 
14: 2 4 1 3 0 
15: 4 1 2 3 0 
16: 1 4 2 3 0 
17: 2 1 4 3 0 
18: 1 2 4 3 0 
19: 3 2 1 4 0 
20: 2 3 1 4 0 
21: 3 1 2 4 0 
22: 1 3 2 4 0 
23: 2 1 3 4 0 
24: 1 2 3 4 0 
25: 4 3 2 0 1 
26: 3 4 2 0 1 
27: 4 2 3 0 1 
28: 2 4 3 0 1 
29: 3 2 4 0 1 
30: 2 3 4 0 1 
31: 4 3 0 2 1 
32: 3 4 0 2 1 
33: 4 0 3 2 1 
34: 0 4 3 2 1 
35: 3 0 4 2 1 
36: 0 3 4 2 1 
37: 4 2 0 3 1 
38: 2 4 0 3 1 
39: 4 0 2 3 1 
40: 0 4 2 3 1 
41: 2 0 4 3 1 
42: 0 2 4 3 1 
43: 3 2 0 4 1 
44: 2 3 0 4 1 
45: 3 0 2 4 1 
46: 0 3 2 4 1 
47: 2 0 3 4 1 
48: 0 2 3 4 1 
49: 4 3 1 0 2 
50: 3 4 1 0 2 
51: 4 1 3 0 2 
52: 1 4 3 0 2 
53: 3 1 4 0 2 
54: 1 3 4 0 2 
55: 4 3 0 1 2 
56: 3 4 0 1 2 
57: 4 0 3 1 2 
58: 0 4 3 1 2 
59: 3 0 4 1 2 
60: 0 3 4 1 2 
61: 4 1 0 3 2 
62: 1 4 0 3 2 
63: 4 0 1 3 2 
64: 0 4 1 3 2 
65: 1 0 4 3 2 
66: 0 1 4 3 2 
67: 3 1 0 4 2 
68: 1 3 0 4 2 
69: 3 0 1 4 2 
70: 0 3 1 4 2 
71: 1 0 3 4 2 
72: 0 1 3 4 2 
73: 4 2 1 0 3 
74: 2 4 1 0 3 
75: 4 1 2 0 3 
76: 1 4 2 0 3 
77: 2 1 4 0 3 
78: 1 2 4 0 3 
79: 4 2 0 1 3 
80: 2 4 0 1 3 
81: 4 0 2 1 3 
82: 0 4 2 1 3 
83: 2 0 4 1 3 
84: 0 2 4 1 3 
85: 4 1 0 2 3 
86: 1 4 0 2 3 
87: 4 0 1 2 3 
88: 0 4 1 2 3 
89: 1 0 4 2 3 
90: 0 1 4 2 3 
91: 2 1 0 4 3 
92: 1 2 0 4 3 
93: 2 0 1 4 3 
94: 0 2 1 4 3 
95: 1 0 2 4 3 
96: 0 1 2 4 3 
97: 3 2 1 0 4 
98: 2 3 1 0 4 
99: 3 1 2 0 4 
100: 1 3 2 0 4 
101: 2 1 3 0 4 
102: 1 2 3 0 4 
103: 3 2 0 1 4 
104: 2 3 0 1 4 
105: 3 0 2 1 4 
106: 0 3 2 1 4 
107: 2 0 3 1 4 
108: 0 2 3 1 4 
109: 3 1 0 2 4 
110: 1 3 0 2 4 
111: 3 0 1 2 4 
112: 0 3 1 2 4 
113: 1 0 3 2 4 
114: 0 1 3 2 4 
115: 2 1 0 3 4 
116: 1 2 0 3 4 
117: 2 0 1 3 4 
118: 0 2 1 3 4 
119: 1 0 2 3 4 
120: 0 1 2 3 4 

順を追って見ていきます。

実行結果を順を追ってみていきましょう。

この作業はとても重要です。
この作業をやることなく次に進んでもまったくといってよいほど意味がありません。
理解していなくてもステップを進むことはできますが、理解していないから身につかないのです。
バカバカしいと思わずに、実行結果を順番にボード上のクイーンを配置しつつ、動きを確認してください。

では、実行結果の解を上から順を追ってみていきます。

1つ目の実行結果は

1: 4 3 2 1 0 

でした。
この盤面情報を図に置き換えるとどうなりますか?

1: 4 3 2 1 0 

        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|---|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

さてここで、どのクイーンが動くのかというところが重要です。
動くのは盤面の左側である「先っぽ」となります。
とはいえ、(4,4)のクイーンはもう最下部まで到達しています。
再帰では最下部へ到達しているその条件を「基底条件」というのでしたね。

「4列のクイーンはこれ以上手がない状態」といえます。

ここで操作している4列に「↓」マークを付けておきます。
いずれこの矢印が役に立ちます。

   ↓
        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|---|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

さて4列にこれ以上「手がない」ということになり初めて、一つ手前3列のクイーンに軸が移動します。

ここでは「↓」が右に一つずれます。

       ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-x-|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|---|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

軸(↓)にある(3,3)のクイーン可能性のある移動箇所を探します。
(3,0),(3,1),(3,2)はアタリでおけません。
(3,3)は現在の場所となりますし、
(3,4)に移動できそうですね。
盤面は以下のとおりです。

       ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-x-|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|-x-|---|---|---|3
  +-------------------+
  |-Q-|-Q-|---|---|---|4
  +-------------------+

col3列のクイーンは(3,4)へ移動しました。
となると、ここからcol4列のクイーンの移動が始まります。
(4,0),(4,1),(4,2)まではアタリですね。(4,3)….
(4.3)におけますね。

これで、2つ目の解ができあがります。
盤面は以下のとおりです。

2: 3 4 2 1 0 
       ↓
        column(列)
   _4___3___2___1___0_
  |-x-|---|---|---|-Q-|0
  +-------------------+
  |-x-|---|---|-Q-|---|1
  +-------------------+ 
  |-x-|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |-Q-|-x-|---|---|---|3
  +-------------------+
  |---|-Q-|---|---|---|4
  +-------------------+

(4,4)は(3,4)のクイーンのアタリなので移動できません。

これでcol4列のクイーンはすべての可能性を探し終わった」といえます。

ですので3列のクイーンを桁上りしたいところなのですが、残念ながらcol3のクイーンはすでに最下部へ到達しており、
「3列のクイーンはこれ以上手がない状態」と、なりました。

ここで軸「↓」を col3からcol2へずらします。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-Q-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

先程と同様、手がない状態となると「一つ手前の」列である2列のクイーンが「ひとつずれてみようか」と下(2,3)に移動し桁上りします。

元の場所にはわかりやすく「x」マークを付けておきました。
盤面は以下のようになります。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|-Q-|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

ここからいつもの処理が始まります。

col3 列のクイーンは移動できる可能性を最上部から順にたどります。

(3,0),(3,1)はアタリとなり置けません、(3,2)に置けそうですね。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-Q-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|-Q-|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

ここで4列目の移動候補を最上部から順番にたどります。
(4,0),(4,1),(4,2),(4,3),(4,4)
(4,4)におけますね!

これで3つ目の解が見つかったことになります。
盤面は以下の通りとなります。

3: 4 2 3 1 0 
           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-x-|-Q-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |-x-|---|-Q-|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

さて、現在の矢印↓の場所は col2 です。
また、(3,2)のクイーンの位置で展開した col4列で移動できる可能性は上から順にすべて潰しました。

そこで、3列はひとつ下(3,3)にずれます。
アタリですね。

さらにひとつ下の(3,4)にずれます。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|-x-|-Q-|---|---|3
  +-------------------+
  |---|-Q-|---|---|---|4
  +-------------------+

さて col4列目の移動候補を気を取り直して上から順番にたどりましょう。
(4,0),(4,1),(4,2)

まず(4,2)へ移動できそうですね。
盤面は以下のとおりです。
ここで4つ目の解ができました。
盤面は以下のとおりです。

4: 2 4 3 1 0 
           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-Q-|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|-x-|-Q-|---|---|3
  +-------------------+
  |---|-Q-|---|---|---|4
  +-------------------+

4列目の続きも見てみましょう。
(4,3),(4,4)はアタリですので置けませんね。

           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-Q-|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |-x-|-x-|-Q-|---|---|3
  +-------------------+
  |-x-|-Q-|---|---|---|4
  +-------------------+

col4列目の可能性はすべて潰しました。
さらに3列目(3,4)のクイーンは最下部となりました。
col4 col3 でもう動かせる可能性はありません。

col2列(2,3)のクイーンはこれ以上手がない」状態なので、

col2列(2,3)のクイーンは(2,4)へ移動します。
盤面は以下のとおりです。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-Q-|---|1
  +-------------------+ 
  |---|---|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

ではいつものとおり col3列目の一番上から可能性をたどっていきます。
(3,0),(3,1),(3,2)
(3,2)に置けそうです。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-Q-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|---|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

では4列目の移動できる可能性を上から順番にたどっていきます。
(4,0),(4,1),(4,2),(4,3)
(4,3)が置けそうです。

解が一つ見つかりました。

5: 3 2 4 1 0 
           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-x-|-Q-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |-Q-|---|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

さらに(4,4)への可能性も探索しますが、あたりなので移動できません。

           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-x-|-Q-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |-x-|---|-x-|---|---|3
  +-------------------+
  |-x-|---|-Q-|---|---|4
  +-------------------+

4列のクイーンは一番下まで到達しましたので、(3,2)のクイーンは(3,3)へ移動します。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

ではあらためて col4列目のクイーンの移動の可能性を上から順番にたどります。
(4,0),(4,1),(4,2)
(4,2)が置けそうです。

これで一つ解が発見できました。

6: 2 3 4 1 0 
           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-Q-|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

続けて4列目のクイーンを下に移動してたどってみます。
(4,3),(4,4)もあたり
4列の移動候補はすべて潰しました。

           ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|---|---|-Q-|0
  +-------------------+
  |-x-|-x-|---|-Q-|---|1
  +-------------------+ 
  |-x-|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |-x-|-Q-|-x-|---|---|3
  +-------------------+
  |-x-|---|-Q-|---|---|4
  +-------------------+

ここで3列目(3,3)のクイーンをひとつ下にずらします。
(3,4)はあたりで移動できませんね。

           ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|---|---|-Q-|0
  +-------------------+
  |---|-x-|---|-Q-|---|1
  +-------------------+ 
  |---|-x-|-x-|---|---|2 row(行) 
  +-------------------+ 
  |---|-x-|-x-|---|---|3
  +-------------------+
  |---|-x-|-Q-|---|---|4
  +-------------------+

3列目のクイーンの移動できる可能性はすべて潰しました。
さらに、矢印↓である col2 列目のクイーンの移動できる可能性はすべて潰しました。

ここで軸「↓」が一つ左にずれて col1 列が軸となり、(1,1)のクイーンをひとつ下に移動させます。
こうした動きが「バックトラック」と言われる理由です。

盤面は以下のとおりです。

               ↓
        column(列)
   _4___3___2___1___0_
  |---|---|---|---|-Q-|0
  +-------------------+
  |---|---|---|-x-|---|1
  +-------------------+ 
  |---|---|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

そこで、2列(2,4)のクイーンが移動できる可能性をしらみつぶしに(ブルートフォース)たどっていきます。
(2,1)におけますね。

               ↓
        column(列)
   _4___3___2___1___0_
  |---|---|-x-|---|-Q-|0
  +-------------------+
  |---|---|-Q-|-x-|---|1
  +-------------------+ 
  |---|---|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |---|---|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

では、3列目の可能性をたどります。
(3,3)に置けそうです。

               ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|-x-|---|-Q-|0
  +-------------------+
  |---|-x-|-Q-|-x-|---|1
  +-------------------+ 
  |---|-x-|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |---|-Q-|---|---|---|3
  +-------------------+
  |---|---|---|---|---|4
  +-------------------+

では4列目の可能性をたどります。
(4,4)に置けました。
7つ目の解が発見できました。

7: 4 3 1 2 0 
               ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|-x-|---|-Q-|0
  +-------------------+
  |-x-|-x-|-Q-|-x-|---|1
  +-------------------+ 
  |-x-|-x-|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |-x-|-Q-|---|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+

では3列目の(3,3)を下に一つずらします。

               ↓
        column(列)
   _4___3___2___1___0_
  |---|-x-|-x-|---|-Q-|0
  +-------------------+
  |---|-x-|-Q-|-x-|---|1
  +-------------------+ 
  |---|-x-|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |---|-x-|---|---|---|3
  +-------------------+
  |---|-Q-|---|---|---|4
  +-------------------+

4列目の移動候補を上から順番にたどります。
(4,0),(4,1),(4,2),(4,3),
(4,3)に置けそうです。

ここで新たな解が発見できました。

8: 3 4 1 2 0 
               ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|-x-|---|-Q-|0
  +-------------------+
  |-x-|-x-|-Q-|-x-|---|1
  +-------------------+ 
  |-x-|-x-|---|-Q-|---|2 row(行) 
  +-------------------+ 
  |-Q-|-x-|---|---|---|3
  +-------------------+
  |-x-|-Q-|---|---|---|4
  +-------------------+

ここからは解となる盤面情報表示しておきます。

9: 4 1 3 2 0 
               ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|-x-|---|-Q-|0
  +-------------------+
  |-x-|-Q-|-x-|-x-|---|1
  +-------------------+ 
  |-x-|---|-x-|-Q-|---|2 row(行) 
  +-------------------+ 
  |-x-|---|-Q-|---|---|3
  +-------------------+
  |-Q-|---|---|---|---|4
  +-------------------+
10: 1 4 3 2 0 
               ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|-x-|---|-Q-|0
  +-------------------+
  |-Q-|-x-|-x-|-x-|---|1
  +-------------------+ 
  |---|-x-|-x-|-Q-|---|2 row(行) 
  +-------------------+ 
  |---|-x-|-Q-|---|---|3
  +-------------------+
  |---|-Q-|---|---|---|4
  +-------------------+
11: 3 1 4 2 0 
               ↓
        column(列)
   _4___3___2___1___0_
  |-x-|-x-|-x-|---|-Q-|0
  +-------------------+
  |-x-|-Q-|-x-|-x-|---|1
  +-------------------+ 
  |-x-|---|-x-|-Q-|---|2 row(行) 
  +-------------------+ 
  |-Q-|---|-x-|---|---|3
  +-------------------+
  |---|---|-Q-|---|---|4
  +-------------------+

どうでしょうか?
ボード右側のクイーンよりも左側のクイーンが一生懸命に動いていることが判ります。
軸「↓」は右へ右へとずれていきますね。
この動きが「バックトラック」です。
次の章で本格的なバックトラックの完成となります。

左側のクイーンの移動候補がなくなったら右側のクイーンを一つおろして、左側のクイーンを候補の一番最初に戻し、可能性のある移動を探していましたね。

この処理は以下の部分が大きく影響しています。

        down[$col]=1; # trueを代入
        N-Queens03 "$((min+1))" "$size" ;
        down[$col]=0; # falseを代入

さらに言えば、クイーンの横列の当たり判定部分は以下のとおりです。

    if (( down[col] == 0 ));then

ソースの内容を深く理解する必要はありません。
どういう動きになるのかを知ることが重要です。
盤面の移動を何度も確認しておくのが良いです。
これからさらにどんどん複雑な動きとなります。
しっかりとクイーンの動きを理解してください。

Nが5のときの計算方法

前回は、縦に一つのクイーン、いわゆる縦の効きだけを考慮しました。

そのN5の計算方法は

5*5*5*5*5=3125
N^5=3125 となります。

一般的にこうしたブルートフォースの動きは
N^N
と書きます。

今回は、横の効きも取り入れたことでステップ数は120となりました。
計算で出すと以下の通りとなります。

5*4*3*2*1=120
5!=120

一般的にこうしたバックトラックの動きは
N!
と書きます。

実行結果

ちなみに、8x8の実行結果は以下の通りです。

<>3.バックトラック準備編 N-Queens03()
1: 7 6 5 4 3 2 1 0 
2: 6 7 5 4 3 2 1 0 
3: 7 5 6 4 3 2 1 0 
4: 5 7 6 4 3 2 1 0 
5: 6 5 7 4 3 2 1 0 
6: 5 6 7 4 3 2 1 0 
7: 7 6 4 5 3 2 1 0 
8: 6 7 4 5 3 2 1 0 
9: 7 4 6 5 3 2 1 0 
10: 4 7 6 5 3 2 1 0 
11: 6 4 7 5 3 2 1 0 
12: 4 6 7 5 3 2 1 0 
13: 7 5 4 6 3 2 1 0 
14: 5 7 4 6 3 2 1 0 
15: 7 4 5 6 3 2 1 0 
16: 4 7 5 6 3 2 1 0 
17: 5 4 7 6 3 2 1 0 
18: 4 5 7 6 3 2 1 0 
19: 6 5 4 7 3 2 1 0 
20: 5 6 4 7 3 2 1 0 
21: 6 4 5 7 3 2 1 0 
22: 4 6 5 7 3 2 1 0 
23: 5 4 6 7 3 2 1 0 
24: 4 5 6 7 3 2 1 0 
25: 7 6 5 3 4 2 1 0 
26: 6 7 5 3 4 2 1 0 
27: 7 5 6 3 4 2 1 0 
28: 5 7 6 3 4 2 1 0 
29: 6 5 7 3 4 2 1 0 
30: 5 6 7 3 4 2 1 0 

:
:
40306: 7 6 5 4 1 2 3 0
40307: 7 6 5 4 1 3 0 2
40308: 7 6 5 4 1 3 2 0
40309: 7 6 5 4 2 0 1 3
40310: 7 6 5 4 2 0 3 1
40311: 7 6 5 4 2 1 0 3
40312: 7 6 5 4 2 1 3 0
40313: 7 6 5 4 2 3 0 1
40314: 7 6 5 4 2 3 1 0
40315: 7 6 5 4 3 0 1 2
40316: 7 6 5 4 3 0 2 1
40317: 7 6 5 4 3 1 0 2
40318: 7 6 5 4 3 1 2 0
40319: 7 6 5 4 3 2 0 1
40320: 7 6 5 4 3 2 1 0

real	0m18.519s
user	0m18.304s
sys	0m0.154s
bash-3.2$

前回の記事では43分かかりましたが、今回のルールを一つ追加するだけで18秒に短縮できました。
バックトラックの準備編といえども、大きな効果がありました。

Nが8のときの計算方法

今回の縦の効きに加え、横の効きも取り入れたことでステップ数は120となりました。
N8を計算で出すと以下の通りとなります。

8*7*6*5*4*3*2*1=40,320
8!=40,320

次回は、斜めの効きにも対応することとします。
やっとそれが出来上がると、ブルートフォース(手当たりしだいの力まかせ探索)というロジックでエイトクイーンを解決したといえます。

参考リンク

以下の詳細説明を参考にしてください。
【参考リンク】Nクイーン問題 過去記事一覧
【Github】エイト・クイーンのソース置き場 BashもJavaもPythonも!

Nクイーン問題(50)第七章 マルチプロセス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-04-n-queens-suzuki/
Nクイーン問題(49)第七章 マルチスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-03-n-queens-suzuki/
Nクイーン問題(48)第七章 シングルスレッド Python編
https://suzukiiichiro.github.io/posts/2023-06-21-02-n-queens-suzuki/
Nクイーン問題(47)第七章 クラス Python編
https://suzukiiichiro.github.io/posts/2023-06-21-01-n-queens-suzuki/
Nクイーン問題(46)第七章 ステップNの実装 Python編
https://suzukiiichiro.github.io/posts/2023-06-16-02-n-queens-suzuki/
Nクイーン問題(45)第七章 キャリーチェーン Python編
https://suzukiiichiro.github.io/posts/2023-06-16-01-n-queens-suzuki/
Nクイーン問題(44)第七章 対象解除法 Python編
https://suzukiiichiro.github.io/posts/2023-06-14-02-n-queens-suzuki/
Nクイーン問題(43)第七章 ミラー Python編
https://suzukiiichiro.github.io/posts/2023-06-14-01-n-queens-suzuki/
Nクイーン問題(42)第七章 ビットマップ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-05-n-queens-suzuki/
Nクイーン問題(41)第七章 配置フラグ Python編
https://suzukiiichiro.github.io/posts/2023-06-13-04-n-queens-suzuki/
Nクイーン問題(40)第七章 バックトラック Python編
https://suzukiiichiro.github.io/posts/2023-06-13-03-n-queens-suzuki/
Nクイーン問題(39)第七章 バックトラック準備編 Python編
https://suzukiiichiro.github.io/posts/2023-06-13-02-n-queens-suzuki/
Nクイーン問題(38)第七章 ブルートフォース Python編
https://suzukiiichiro.github.io/posts/2023-06-13-01-n-queens-suzuki/
Nクイーン問題(37)第六章 C言語移植 その17 pthread並列処理完成
https://suzukiiichiro.github.io/posts/2023-05-30-17-n-queens-suzuki/
Nクイーン問題(36)第六章 C言語移植 その16 pthreadの実装
https://suzukiiichiro.github.io/posts/2023-05-30-16-n-queens-suzuki/
Nクイーン問題(35)第六章 C言語移植 その15 pthread実装直前版完成
https://suzukiiichiro.github.io/posts/2023-05-30-15-n-queens-suzuki/
Nクイーン問題(34)第六章 C言語移植 その14
https://suzukiiichiro.github.io/posts/2023-05-30-14-n-queens-suzuki/
Nクイーン問題(33)第六章 C言語移植 その13
https://suzukiiichiro.github.io/posts/2023-05-30-13-n-queens-suzuki/
Nクイーン問題(32)第六章 C言語移植 その12
https://suzukiiichiro.github.io/posts/2023-05-30-12-n-queens-suzuki/
Nクイーン問題(31)第六章 C言語移植 その11
https://suzukiiichiro.github.io/posts/2023-05-30-11-n-queens-suzuki/
Nクイーン問題(30)第六章 C言語移植 その10
https://suzukiiichiro.github.io/posts/2023-05-30-10-n-queens-suzuki/
Nクイーン問題(29)第六章 C言語移植 その9
https://suzukiiichiro.github.io/posts/2023-05-30-09-n-queens-suzuki/
Nクイーン問題(28)第六章 C言語移植 その8
https://suzukiiichiro.github.io/posts/2023-05-30-08-n-queens-suzuki/
Nクイーン問題(27)第六章 C言語移植 その7
https://suzukiiichiro.github.io/posts/2023-05-30-07-n-queens-suzuki/
Nクイーン問題(26)第六章 C言語移植 その6
https://suzukiiichiro.github.io/posts/2023-05-30-06-n-queens-suzuki/
Nクイーン問題(25)第六章 C言語移植 その5
https://suzukiiichiro.github.io/posts/2023-05-30-05-n-queens-suzuki/
Nクイーン問題(24)第六章 C言語移植 その4
https://suzukiiichiro.github.io/posts/2023-05-30-04-n-queens-suzuki/
Nクイーン問題(23)第六章 C言語移植 その3
https://suzukiiichiro.github.io/posts/2023-05-30-03-n-queens-suzuki/
Nクイーン問題(22)第六章 C言語移植 その2
https://suzukiiichiro.github.io/posts/2023-05-30-02-n-queens-suzuki/
Nクイーン問題(21)第六章 C言語移植 その1
N-Queens問://suzukiiichiro.github.io/posts/2023-05-30-01-n-queens-suzuki/
Nクイーン問題(20)第五章 並列処理
https://suzukiiichiro.github.io/posts/2023-05-23-02-n-queens-suzuki/
Nクイーン問題(19)第五章 キャリーチェーン
https://suzukiiichiro.github.io/posts/2023-05-23-01-n-queens-suzuki/
Nクイーン問題(18)第四章 エイト・クイーンノスタルジー
https://suzukiiichiro.github.io/posts/2023-04-25-01-n-queens-suzuki/
Nクイーン問題(17)第四章 偉人のソースを読む「N24を発見 Jeff Somers」
https://suzukiiichiro.github.io/posts/2023-04-21-01-n-queens-suzuki/
Nクイーン問題(16)第三章 対象解除法 ソース解説
https://suzukiiichiro.github.io/posts/2023-04-18-01-n-queens-suzuki/
Nクイーン問題(15)第三章 対象解除法 ロジック解説
https://suzukiiichiro.github.io/posts/2023-04-13-02-nqueens-suzuki/
Nクイーン問題(14)第三章 ミラー
https://suzukiiichiro.github.io/posts/2023-04-13-01-nqueens-suzuki/
Nクイーン問題(13)第三章 ビットマップ
https://suzukiiichiro.github.io/posts/2023-04-05-01-nqueens-suzuki/
Nクイーン問題(12)第二章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-17-02-n-queens-suzuki/
Nクイーン問題(11)第二章 配置フラグの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-17-01-n-queens-suzuki/
Nクイーン問題(10)第二章 バックトラックの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-16-01-n-queens-suzuki/
Nクイーン問題(9)第二章 ブルートフォースの再帰・非再帰
https://suzukiiichiro.github.io/posts/2023-03-14-01-n-queens-suzuki/
Nクイーン問題(8)第一章 まとめ
https://suzukiiichiro.github.io/posts/2023-03-09-01-n-queens-suzuki/
Nクイーン問題(7)第一章 ブルートフォース再び
https://suzukiiichiro.github.io/posts/2023-03-08-01-n-queens-suzuki/
Nクイーン問題(6)第一章 配置フラグ
https://suzukiiichiro.github.io/posts/2023-03-07-01-n-queens-suzuki/
Nクイーン問題(5)第一章 進捗表示テーブルの作成
https://suzukiiichiro.github.io/posts/2023-03-06-01-n-queens-suzuki/
Nクイーン問題(4)第一章 バックトラック
https://suzukiiichiro.github.io/posts/2023-02-21-01-n-queens-suzuki/
Nクイーン問題(3)第一章 バックトラック準備編
https://suzukiiichiro.github.io/posts/2023-02-14-03-n-queens-suzuki/
Nクイーン問題(2)第一章 ブルートフォース
https://suzukiiichiro.github.io/posts/2023-02-14-02-n-queens-suzuki/
Nクイーン問題(1)第一章 エイトクイーンについて
https://suzukiiichiro.github.io/posts/2023-02-14-01-n-queens-suzuki/

書籍の紹介

Nクイーン問題(4)第一章 バックトラック

Nクイーン問題(4)第一章 バックトラック

Nクイーン問題(2)第一章 ブルートフォース

Nクイーン問題(2)第一章 ブルートフォース