lp_solveを用いたNクイーン問題の解の探索

Nクイーン問題のような問題は自分で探索プログラムを書くと探索空間が広くなりがちでなかなか解が見つけられなかったりします．そうでなくても書くのが面倒です．そういう時には線形計画法ソルバー(lp_solve)やSATソルバー(Sugar)などが便利です．今回は簡単にインストールできるlp_solveを用いてNクイーン問題を解きましょう．

解決法

まずlp_solveをインストールしてください．MacならMacPortsで，Ubuntuならaptで入ると思います．そして下記PHPプログラムをn-queen.phpで保存します．

<?php
$n = 8;
$conditions = array('x4y5'); // すでに置いているところを指定 (盤面は1-origin)

$constraints = array();
$variables = array();
for ($y = 1; $y <= $n; $y++) {
    for ($x = 1; $x <= $n; $x++) {
        $v = sprintf('x%dy%d', $x, $y);
        $variables[] = $v;
        $constraints["row$y"][] = $v; // 横方向の制約
        $constraints["col$x"][] = $v; // 縦方向の制約
        $constraints['~add' . ($x + $y)][] = $v; // 斜め方向(／)の制約
        $constraints['~sub' . ($x - $y)][] = $v; // 斜め方向(＼)の制約
    }
}
ksort($constraints);
echo 'max: ' . implode('+', $variables) . ";\n";
foreach ($conditions as $condition)
    echo "$condition=1;\n";
foreach ($constraints as $constrain)
    echo implode('+', $constrain) . "<=1;\n";
echo 'int ' . implode(',', $variables) . ";\n";

実行方法

$ php n-queen.php | lp_solve | grep '1$'
x2y1                            1
x6y2                            1
x1y3                            1
x7y4                            1
x4y5                            1
x8y6                            1
x3y7                            1
x5y8                            1

これで7つの配置がわかりました．

別解の探索

もし別の解が知りたければ，

x2y1+x6y2+x1y3+x7y4+x4y5+x8y6+x3y7+x5y8<8;

という行でもn-queen.phpの出力に加えておくと良いでしょう．