1. nクイーン問題
著者:梅谷 武
nクイーン問題の解法を実装する。
作成:2024-06-01
更新:2024-10-29
更新:2024-10-29
nクイーン問題nくいーんもんだい, n-queen problem(n-queen problem)とはn×nのチェス盤上にn個のクイーンを置いて互いに相手の利きが当たらないようにする問題である。クイーンは将棋の飛車と角を合わせた動きをする駒であり、盤上の上下、左右、斜め方向のすべての枡目に利きがある。
n×nのチェス盤はn×n行列と考えることができる。
#lang racket
(require iso-printf)
(define (print-matrix mat)
(for ([i n])
(for ([j n])
(printf "(%d,%d)" i j))
(printf "\n"))
(printf "\n"))
(define n 8)
(define board (for/vector ([i n]) (make-vector n 0)))
(print-matrix board)
(0,0)(0,1)(0,2)(0,3)(0,4)(0,5)(0,6)(0,7)
(1,0)(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)(1,7)
(2,0)(2,1)(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)
(3,0)(3,1)(3,2)(3,3)(3,4)(3,5)(3,6)(3,7)
(4,0)(4,1)(4,2)(4,3)(4,4)(4,5)(4,6)(4,7)
(5,0)(5,1)(5,2)(5,3)(5,4)(5,5)(5,6)(5,7)
(6,0)(6,1)(6,2)(6,3)(6,4)(6,5)(6,6)(6,7)
(7,0)(7,1)(7,2)(7,3)(7,4)(7,5)(7,6)(7,7)
nクイーン問題の制約により、このn×n行列の各行、各列には一つのクイーンしか置くことができない。このような置き方は各行について何列目にクイーンがあるかというリストによって表現することができる。
(define n 8)
(define (print-board n pos)
(for ([i n])
(for ([j n])
(if (= (list-ref pos i) j)
(printf "Q ")
(printf ". ")))
(printf "\n"))
(printf "\n"))
(print-board n '(0 4 7 5 2 6 1 3))
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
二つのクイーンが(x,y)と(z,w)の位置に置かれているとき、これが斜めの利きで当たることは直線の方程式から
と表現することができる。
| |x － z| = |y － w| |
クイーンの置き方をリストposで表わし、'()で初期化しておく。これに一列ずつappendし、置いてみたクイーンが制約条件を満たすなら再帰的に繰り返し、リストの長さがnに達したら解が求まったことになる。これは探索空間を木と考えると深さ優先探索(バックトラック法と呼ばれる)になっている。
(define count 0)
(define (hit? pos row col)
(for/or ([i row])
(define j (list-ref pos i))
(= (abs (- row i)) (abs (- col j)))))
(define (nqueen n pos)
(define row (length pos))
(displayln pos)
(cond
[(>= count 1) (void)]
[(= n row)
(print-board n pos)
(set! count (+ count 1))]
[else
(for ([i n])
(unless (or (member i pos) (hit? pos row i))
(nqueen n (append pos (list i)))))]))
(define n 4)
(nqueen n '())
()
(0)
(0 2)
(0 3)
(0 3 1)
(1)
(1 3)
(1 3 0)
(1 3 0 2)
. Q . .
. . . Q
Q . . .
. . Q .
(2)
(3)
nクイーン問題のすべての解を求め、解の総数を表示する。
nqueen.cpp:
#include <algorithm>
#include <cmath>
#include <print>
#include <vector>
int count = 0;
void printBoard(int n, const std::vector<int> &pos) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (pos[i] == j) {
std::print("Q ");
} else {
std::print(". ");
}
}
std::print("\n");
}
std::print("\n");
}
bool hit(const std::vector<int> &pos, int row, int col) {
for (int i = 0; i < row; ++i) {
int j = pos[i];
if (std::abs(row - i) == std::abs(col - j)) {
return true;
}
}
return false;
}
void nQueen(int n, std::vector<int> pos) {
int row = pos.size();
if (row == n) {
count++;
return;
}
for (int i = 0; i < n; ++i) {
if (std::find(pos.begin(), pos.end(), i) == pos.end() && !hit(pos, row, i)) {
pos.push_back(i);
nQueen(n, pos);
pos.pop_back();
}
}
}
int main() {
int n = 12;
nQueen(n, {});
std::print("n = {}, count = {}\n", n, count);
return 0;
}
makefile:
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
SRC = nqueen.cpp
EXES = nqueen_g nqueen_l
all: $(EXES)
nqueen_g: $(SRC)
$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
nqueen_l: $(SRC)
$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
clean:
rm -f $(EXES)
$ measure ./nqueen_g
n = 12, count = 14200
======================================
Process exited with status: 0
total time: 0.212389 [sec]
mem size: 3720 [KB]
code size: 118 [KB]
$ measure ./nqueen_l
n = 12, count = 14200
======================================
Process exited with status: 0
total time: 0.218726 [sec]
mem size: 3760 [KB]
code size: 91 [KB]
nqueen.ml
open Printf
let count = ref 0
let print_board n pos =
for i = 0 to n - 1 do
for j = 0 to n - 1 do
if List.nth pos i = j then
printf "Q "
else
printf ". "
done;
printf "\n"
done;
printf "\n"
let hit pos row col =
let rec check i =
if i >= row then false
else
let j = List.nth pos i in
if abs (row - i) = abs (col - j) then true
else check (i + 1)
in
check 0
let rec nqueen n pos =
let row = List.length pos in
if row = n then
count := !count + 1
else
for i = 0 to n - 1 do
if not (List.mem i pos) && not (hit pos row i) then
nqueen n (pos @ [i])
done
let () =
let n = 12 in
nqueen n [];
printf "n = %d, count = %d\n" n !count
$ ocamlopt -O2 -o nqueen nqueen.ml
$ measure ./nqueen
n = 12, count = 14200
======================================
Process exited with status: 0
total time: 1.130500 [sec]
mem size: 5152 [KB]
code size: 2363 [KB]
nqueen.rkt:
#lang racket
(require iso-printf)
(define count 0)
(define (print-board n pos)
(for ([i n])
(for ([j n])
(if (= (list-ref pos i) j)
(printf "Q ")
(printf ". ")))
(printf "\n"))
(printf "\n"))
(define (hit? pos row col)
(for/or ([i row])
(define j (list-ref pos i))
(= (abs (- row i)) (abs (- col j)))))
(define (nqueen n pos)
(define row (length pos))
;(displayln pos)
(cond
;[(>= count 1) (void)]
[(= n row)
;(print-board n pos)
(set! count (+ count 1))]
[else
(for ([i n])
(unless (or (member i pos) (hit? pos row i))
(nqueen n (append pos (list i)))))]))
(define n 12)
(nqueen n '())
(printf "n = %d, count = %d\n" n count)
(printf "Total number of solutions: ~a\n" count)
$ raco exe nqueen.rkt
$ measure ./nqueen
n = 12, count = 14200
======================================
Process exited with status: 0
total time: 3.260200 [sec]
mem size: 134392 [KB]
code size: 12444 [KB]
測定結果を表にまとめる。単位は秒[sec]。
| 測定項目 | GCC | Clang | OCaml | Racket |
|---|---|---|---|---|
| 12-queen | 0.212 | 0.219 | 1.131 | 3.260 |
[1] Wikipedia, Eight queens puzzle, Wikimedia Foundation, Inc., 2024
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani