CodeIQ：n-Queenで反転

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「n-Queenで反転」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
アルゴリズムの勉強でよく登場する8-Queen問題。
縦、横、斜めのいずれにも重複しないように8個のコマを配置する問題です。
エイト・クイーン(Wikipedia)

n × n マスの盤で n 個のコマの配置を考える場合、n-Queen問題と呼ばれます。
今回はこの配置を活用してみます。

オセロのように白と黒の両面がある石が、 n × n マスの盤上で1マスに1つずつ置かれています。
最初、すべての石は白の面が上を向いています。
n-Queenを満たすコマの配置を使って、コマがある位置に該当する石を反転することを繰り返して、すべてのマスの石を反転させる（つまり、すべての石が黒の面になる）ことを考えます。

標準入力から n が与えられたとき、最小回数ですべての石を反転させるまでの回数を求め、その回数を標準出力に出力してください。
ただし、何度繰り返してもすべての石を反転できない場合は 0 を出力してください。
（ n は最大で 7 とします。）

私のプログラム

Rubyで解答しています。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#!/usr/bin/ruby
 
# N-Queen
$QPattern = []
 
# 参考：http://www.cc.kyoto-su.ac.jp/~yamada/ap/backtrack.html
def changeBoard(board, i, j, d)
 
    for k in 0...$N
        board[i][k] += d
        board[k][j] += d
    end
 
    if i>j then
        for k in 0...($N-(i-j))
            board[k+(i-j)][k] += d
        end
    else
        for k in 0...($N-(j-i))
            board[k][k+(j-i)] += d
        end
    end
 
    if i+j < $N then
        for k in 0..(i+j)
            board[i+j-k][k] += d
        end
    else
        for k in (i+j-$N+1)...$N
            board[i+j-k][k] += d
        end
    end
end
 
def setQueen(queen, board, i)
    if i == $N then
#       p queen
        $QPattern << queen.dup
        return
    end
 
    for j in 0...$N
        if board[i][j] == 0 then
            queen[i] = j
            changeBoard(board, i, j, +1)
            setQueen(queen, board, i+1)
            changeBoard(board, i, j, -1)
        end
    end
end
 
def nQueen()
    queen = Array.new($N, 0)
    board = Array.new($N){Array.new($N, 0)}
 
    setQueen(queen, board, 0)
end
# N-Queen ここまで
 
def getResult()
    # Queenの配置パターンが$Nより少ない場合、配置されないマスがある
    # つまり、絶対に全部黒にはできない
    if $QPattern.size < $N then return 0
    # それ以外の場合、少なくとも$N<=7では全パターンの内$Nパターンの組み合わせで全部黒にできる
    else return $N
    end
end
 
# main
while line = gets
    line.strip!
    if line.empty? then next end
 
    $N = line.to_i
end
 
nQueen()
p getResult()

解説

★★★★の問題ですがそれほど難しくありません。ただ、私はマスの石を反転させる部分を真面目に探索しないでやっているので、その部分をきちんとすると難しいかもしれません。
問題の解説の前に問題を少し補足しておきます（私がイマイチ問題文から読み取れなかった部分があるので）。
問題文にある『最小回数ですべての石を反転させるまでの回数』ですが、これはN-Queenの配置全てを使う必要はなく、使っていない配置があっても全ての石を反転できた時点までの回数を出力すればOKです。
引用は省略しましたが問題の図にある通り、反転されるのはQueenの位置にある石だけで、オセロのように間に挟まれた石は反転しません。

基本的な考え方

この問題は2段階の探索が必要です。
最初にN-Queen問題を解いて配置可能なパターンを求めます。
次にその配置を組み合わせて全ての石を反転できる配置の組み合わせを調べます。

N-Queen問題

コードのコメントにある通り、N-Queen問題を解く処理は調べてそのコードをそのまま実装しました（元はC言語だったのでRubyで書き直しただけです）。なので簡単に処理の流れだけを説明します。

N-Queen問題を解く関数はnQueen()ですが、これはボードのサイズ（board[][]）と答えとなるQueenの配置を保持する領域(queen[])を確保してsetQueen()を呼ぶだけです。
queen[]はn行目のQueenはm列目に置かれると言う値が入ります。

setQueen()が処理の本体です。
参考サイトにある通り、バックトラック法で問題を解きます。
手順としてはQueenをボードに配置し、ボードの縦横斜め方向にQueenを置けないことを示すフラグを立てます。このフラグを立てます。これを行うのがchangeBoard()です（45行目）。Queenを置けるかどうかは43行目のif文でチェックします。
Queenを置いたら再帰的にsetQueen()を呼び出し（46行目）、次の行を処理します。これをQueenが置けなくなるまで繰り返します。setQueenの引数i=Nの場合、つまり全ての行を処理した場合は結果を$QPatternに保持して再帰を終了します。またi=NにならなくてもどこにもQueenを置けなかった場合はsetQueen()は何もせず関数を抜けるので再帰を終了します。
再帰が戻ってきたらボードを1手順戻します（47行目）。
これを全パターン繰り返せばN-Queenを解くことができます。

changeBoard()はボードの縦横斜め方向にQueenを置けないことを示すフラグを立てる関数で、第三引数dの値をボードに加えます。初期値は0なので1以上ならQueenを置けないことを表します。
Queenの場所（引数i,j）を変えずに第三引数dに-1を与えればQueenを取り除くことになり1手順戻すことになります。
9〜12行目が縦横、14〜32行目が斜めにフラグを立てます。board[][]は初期値0になっているので1だとその場所にはQueenを置けないことを表します。

反転回数

前述のN-Queenの解はボードを回転させると同じ配置になるものも解に含まれるのでこの中の全てを試してみれば結果が求まります。が、私は探索をプログラムで書いていません。

まず、Queenの配置パターンがNよりも少ない場合は問題の条件を満たすことができません。
何故なら$QPatternの1要素は「各行の何列目にQueenが配置できるか」を記録したものなので$QPatternの要素数がNより少ない場合Queenが絶対に置けない場所＝石を反転できない場所が存在することを意味します。

Queenの配置パターンがN以上の場合ですが、今回問題の条件からN≦7であることがわかっています。N≦7でN-Queen問題が解を持つのはN=1,4,5,6,7でパターンがN以上になるのはN=1,5,7の3通りだけです。N=1の場合1か所しか置けないので調べる必要もありません。つまり、探索する必要があるのはN=5,7の場合だけなのです。
そして、Queenの配置パターンは各行に列の重複なく1個ずつQueenが置かれているということから、最低でもN個のパターンを組み合わせないとボードの全てのマスの石をひっくり返せないことは明らかです。
で、N-Queen問題は解いていて配置は印字すれば確認できるのでN=5,7の場合についてそれぞれ5パターン、7パターンの組み合わせで盤面をQueenで埋めることのできる組み合わせが1つでもあるかを調べました（手動ですが大した手間ではありません）。結果、それぞれ1パターンは発見できたので、N-Queenの解のパターン数がN以上になる場合、N回が答えになります（N≦7の場合）。
これを実装したのがgetResult()です。

雑感

N-Queen問題は自分で考えず、石の反転は手動で解く（それもN≦7に限って）というちょっとどうかというプログラムになってしまいました。石の反転に関しては最初、N-Queenの結果を1次元のビット列にして、その論理和がすべて1に成る組み合わせを求めればよいかな、と思っていましたがパターン数が少なかったので手で解いてしまいました。
でも、直感的にはN-Queenの解がN以上ある場合、反転に必要な手数はNのような気がします（証明できませんが）。