Namaran

Code daily. Without assist.

2026-11-01

queens.rs

fn count(queens: &mut Vec<usize>, n: usize) -> usize {
    let row = queens.len();
    if row == n {
        return 1;
    }
    let mut total = 0;
    for col in 0..n {
        let attacked = queens.iter().enumerate().any(|(r, &c)| c == col || row - r == c - col);
        if !attacked {
            queens.push(col);
            total += count(queens, n);
            queens.pop();
        }
    }
    total
}

fn main() {
    println!("{}", count(&mut Vec::new(), 6));
}

6×6の盤の各行に1個ずつクイーンを置き、どの2個も同じ列や同じ斜めの線に並ばない置き方の数を数えるつもりのプログラムです。queens[r] は r 行目のクイーンの列で、すでに置いたクイーンと同じ列や斜めに並ぶ列は候補から外します。本来は 4 を出力するはずが、いまは何も出力せずに attempt to subtract with overflow でパニックします。

Answer

Wrong

let attacked = queens.iter().enumerate().any(|(r, &c)| c == col || row - r == c - col);

2個のクイーンが斜めに並ぶのは、行の差と列の差の大きさが等しいときです。row - r は、いま置こうとしている行 row が置き済みの行 r より必ず大きいので負になりません。列のほうは、置き済みの列 c が新しい列 col より小さいこともあります。usize は負の値を表せないので、デバッグビルドでは c - col が負になる時点でパニックします。1行目に列0のクイーンを置いたあと、2行目で列1を調べると 0 - 1 を計算することになり、ここで止まります。

Right

let attacked =
    queens.iter().enumerate().any(|(r, &c)| c == col || row - r == c.abs_diff(col));

abs_diff は2つの値の差の大きさを、引く順序に関係なく返します。c と col のどちらが大きくても負の値を経由しないので、右上と左上のどちらの斜めも同じ式で判定でき、6×6の盤の置き方 4 を数えられます。1

  1. リリースビルドでは引き算の溢れを検査しないので、c - col は巨大な値に回り込み、パニックせずに左上の斜めを見逃します。その場合は取り合う置き方まで数えてしまい、6×6の盤では 4 ではなく 83 を黙って出力します。