0Pricing
Coding Interview Prep · レッスン

順列と N-Queens の考え方

要素を配置し、衝突時にバックトラックします

「順列と N-Queens の考え方」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

部分集合から順列へ

順列とは、すべての要素を何らかの順序に並べたものです。順列の生成は、部分集合の次に学ぶバックトラッキングの技法です。🔀

順列はいくつあるか

n個の要素からなる順列はnの階乗個あります。最初の位置にはn通り、次の位置にはn−1通りというように選べるためです。個数は急速に増加します。

1つずつ要素を配置する

再帰処理では、左から右へ位置を埋めていきます。各段階で未使用の要素を1つ選んで配置し、残りの要素について再帰します。

使用済みの要素を管理する

ブール値の使用済み配列で配置済みの要素を記録するため、すべての順列で各要素がちょうど1回ずつ現れます。

コードで順列を生成する

このバックトラッキングでは、未使用の値を配置して再帰し、その後で次の分岐のために使用済み状態を解除します。

def perm(cur):
    if len(cur) == n:
        out.append(cur[:]); return
    for x in a:
        if x not in cur:
            perm(cur + [x])

許可されていればitertoolsを使う

短時間で解く競技プログラミングでは、Pythonのitertools.permutationsを使うと、再帰を自分で書かずにすべての順序を生成できます。

from itertools import permutations
for p in permutations(a):
    print(p)

N-Queens問題

N-Queensでは、互いに攻撃し合わないように、n×nの盤面にn個のクイーンを配置します。これは典型的なバックトラッキングのパズルです。👑

各行に1個のクイーンを置く

同じ行に2個のクイーンを置くことはないため、各行に1個のクイーンを置き、その列だけを選びます。これにより探索量を大幅に減らせます。

3種類の衝突を確認する

配置する前に、すでに使われている列や対角線を選ばないようにします。使用済みの列と、2方向の対角線を集合で管理します。

if c in cols or r-c in d1 or r+c in d2:
    continue

行き詰まったらバックトラックする

その行で使える列がなければ、その分岐は失敗です。バックトラックして最後のクイーンを取り除き、次の選択肢を試します。

共通するパターン

順列とN-Queensには、選ぶ、再帰する、元に戻すという共通の形があります。この形が分かれば、多くの配置問題を同じテンプレートで解けます。

クイックチェック

N-Queensで各行に1個だけクイーンを置くのはなぜですか？

まとめ：選ぶ、再帰する、元に戻す

未使用の要素を配置して順列を生成する方法を学びました。また、N-Queensでも、衝突を確認しながら同じ「選ぶ、再帰する、元に戻す」パターンを使うことを学びました。🎯

よくある質問

「順列と N-Queens の考え方」レッスンは無料ですか？

はい。「順列と N-Queens の考え方」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「順列と N-Queens の考え方」で何を学びますか？

要素を配置し、衝突時にバックトラックします ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「順列と N-Queens の考え方」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 再帰的に考える: Base と Recurse
  2. すべての部分集合を生成する
  3. 順列と N-Queens の考え方
  4. 制限時間を守るために枝刈りする
← Coding Interview Prepに戻る