第二章　練習2.42～2.43

練習2.42：Eight-queens 問題。
練習2.43：Eight-queens 問題の時間コスト。

import tango.util.container.LinkedList;
import tango.math.Math;
import tango.io.Stdout;
/**
* SICP練習2.42。
*/
LinkedList!(int[]) queens(int boardSize) {
auto ls = new LinkedList!(int[]);
void adjoinPosition(int[] pos, int col, int row) {
int[] newPos = new int[col];
if (pos !is null) {
for (int i = 0; i < pos.length; i++) {
newPos[i] = pos[i];
}
}
newPos[col - 1] = row;
// 先頭に追加
ls.add(newPos);
}
bool safe(int[] pos, int col, int row) {
if (col == 1) {
// first col, 常に safe
return true;
}
int colDiv, rowDiv;
int preRow;
for (int i = 0; i < pos.length; i++) {
preRow = pos[i];
if (preRow == row) {
return false;
}
colDiv = col - i - 1;
rowDiv = abs(row - preRow);
if (colDiv == rowDiv) {
return false;
}
}
return true;
}
LinkedList!(int[]) queenCols(int k) {
if (k > boardSize) {
return ls;
}
int prePos = ls.size();
// 初回
if (k == 1) {
for (int i = 1; i <= boardSize; i++) {
adjoinPosition(null, k, i);
}
}
if (k > 1) {
foreach (int[] pos ; ls) {
for (int i = 1; i <= boardSize; i++) {
if (safe(pos, k, i)) {
adjoinPosition(pos, k, i);
}
}
}
}
// 前回の位置情報を削除
if (prePos > 0) {
ls.removeRange(ls.size() - prePos, ls.size() - 1);
}
return queenCols(k + 1);
}
return queenCols(1);
}
void main() {
int boardSize = 8;
LinkedList!(int[]) qs = queens(boardSize);
int count;
foreach (int[] pos ; qs) {
foreach (int r ; pos) {
Stdout.format("{}\t", r);
}
count++;
Stdout.newline();
}
Stdout.formatln("全ての解の数: {}", count);
}

import tango.util.container.LinkedList; import tango.math.Math; import tango.io.Stdout; /** * SICP練習2.42。 */ LinkedList!(int[]) queens(int boardSize) { auto ls = new LinkedList!(int[]); void adjoinPosition(int[] pos, int col, int row) { int[] newPos = new int[col]; if (pos !is null) { for (int i = 0; i < pos.length; i++) { newPos[i] = pos[i]; } } newPos[col - 1] = row; // 先頭に追加 ls.add(newPos); } bool safe(int[] pos, int col, int row) { if (col == 1) { // first col, 常に safe return true; } int colDiv, rowDiv; int preRow; for (int i = 0; i < pos.length; i++) { preRow = pos[i]; if (preRow == row) { return false; } colDiv = col - i - 1; rowDiv = abs(row - preRow); if (colDiv == rowDiv) { return false; } } return true; } LinkedList!(int[]) queenCols(int k) { if (k > boardSize) { return ls; } int prePos = ls.size(); // 初回 if (k == 1) { for (int i = 1; i <= boardSize; i++) { adjoinPosition(null, k, i); } } if (k > 1) { foreach (int[] pos ; ls) { for (int i = 1; i <= boardSize; i++) { if (safe(pos, k, i)) { adjoinPosition(pos, k, i); } } } } // 前回の位置情報を削除 if (prePos > 0) { ls.removeRange(ls.size() - prePos, ls.size() - 1); } return queenCols(k + 1); } return queenCols(1); } void main() { int boardSize = 8; LinkedList!(int[]) qs = queens(boardSize); int count; foreach (int[] pos ; qs) { foreach (int r ; pos) { Stdout.format("{}\t", r); } count++; Stdout.newline(); } Stdout.formatln("全ての解の数: {}", count); }

練習2.43の解答

Louisの実装は、上記ソースの６０と６１行を入れ替えることです。そうすると、既に処理済みの位置を繰り返しチェックしてしまいます。queen-cols(8)は１（8^0）回、queen-cols(7)は８（8^1）回・・・queen-cols(k)は8^(8-k)回呼び出されます。従って、Louisの実装では、queen-cols は合計で（8^0 + 8^1 + ... + 8^7 = 8^8 - 1）回呼び出されます。その一方、元々の実装は 8^2 回です。結局、Louis の実装は約 (8^6) * T の時間が要します。