[伯俊]9663:N-Queen

ついせき

N-Queen

これはバックグラウンド追跡の代表的な問題です.
まず、私たちは他の皇后に食べられないように手配しなければなりません.
同じ列、行、対角線に他の皇后を置くことはできません.△問題はどうしてこのような説明がないのですか.

さかのぼってさかのぼる

の任意の集合(セット)から所定の基準(基準)で要素の順序(シーケンス)を選択する問題を解くのに適しています.

ツリー型データ構造の変化DFS(1回の深さ優先ナビゲーション)

では、すべての問題を解決することはできませんが、多くの場合、問題を解決することができます.
たとえば、n-queen、サブセットの和、0-1リュックサックの問題です.

例として迷宮問題を探しに来ました.
テスト]プログラマーのための質問3-迷路を探す:“厳俊一”と一緒に使用するソフトウェアプラットフォームについて述べる
プログラマーのための質問です...ほほほ
車の中の子犬がハチミツを探しに行くにはどうすればいいですか?
この問題には2つの解決策があります.
1.スタックを利用して進むことができれば、進めない場合はpopをジャンプします.
2.ツリーでDFSプリソート(前列順)を使用すればよい.
でもこれで完全に探索すると、時間が長すぎるでしょう.
したがって、バックグラウンドトラッキングでは、ステータススペースツリーとDFSが使用されます.
ここでbacktracking用のツリーをステータススペースツリーと呼ぶ.
≪ステータス・スペース｜Status Space｜ldap≫:解答をナビゲートするためのナビゲーション・スペース
≪ステータス空間ツリー｜Status Space Tree｜oraolap≫:ナビゲーション空間をツリー型構造として暗黙的に解釈します.
最適化により、すべてのステータスツリーがDFSを迂回することができます.

ついせき

1)状態空間DFS:brootfors(長い時間がかかる)
2)親ノードを返し、そのノードのサブツリーにアクセスしない(希望->トリム)

希望がある

いまの状態でこれ以上進めても始まらない

サブノードは、アクセス中のノードで答えを見つけることができます->希望がある

枝を切る

かかとは枝を切ることと関係がある.
遡及:ステータス空間ツリーDFS
希望があるかどうかを確認し、希望がない場合は枝を切って追跡します.
この時、希望のない次の木にアクセスしないことを枝切りと言います.
典型的な反追跡アルゴリズム首都コード

void checkNode(node v){	
	node u;
    	if promising(v)){
    		if (v 에 해답이 있다면){
        		해답출력
         	}
       		else:
       	    		for (v의 모든 자식 u에 대해){
            			checkNode(u);
             		}

アンチトラッキングの実装

状態空間ツリーを実装する必要はありません.

で現在調査中の値を追跡する必要があります.

状態空間ツリーは無名の存在である.

N-Queen

8-queen(n=8)一般化
1.n*n碁盤にn個の皇后を置く
2.他の皇后に食べられないように手配する
3.同じ列、行、対角線に他の皇后を置くことはできません.
「任意のセット(set)で所定の基準(criterion)で要素順序(sequence)を選択する問題を解くのに適しています.」
任意集合:チェス盤上のn^2個の可能な位置
基準:新しく設立された皇后は他の皇后を脅かすことはありませんか?
要素の順序:皇后のn個の位置を置くことができます
まず基本仮定で、同じ行に置くことはできません.
希望関数(profiled):同じ列または対角線にあるかどうかを確認します.
1.同一列検査:
col[i]:i 1行目においてqueenが存在する列の位置
col[k]:k行目でqueenが存在する列の位置
col[i]=col[k]:同じ列に置いても希望はありません.
2.対角線検査
abs(col[i] - col[k]) == abs(i-k)
タイムアウト

def n_queens(i, col):
	global cnt
	n = len(col) -1
	if (promising(i, col)):
		if (i == n):
			# print(col[1:n+1])
			cnt += 1
		else:
			for j in range(1, n+1):
				col[i+1] = j
				n_queens(i+1, col)
def promising(i, col):
	k = 1
	flag = True
	while (k < i and flag):
		if ((col[i] == col[k]) or (abs(col[i] - col[k]) == (i-k))):
			flag = False
		k += 1
	return flag
cnt = 0
n = int(input())
col = [0] * (n+1)
n_queens(0, col)
print(cnt)

国境を越える

import sys
def n_queens(i, col):
	global cnt
	n = len(col) -1
    	# 만족하는 조건에 다다르면 함수 return 
	if (promising(i, col)):
		if (i == n):
			# print(col[1:n+1])
			cnt += 1
			return  # 중요
		else:
			for j in range(1, n+1):
				col[i+1] = j
				n_queens(i+1, col)
def promising(i, col):
	k = 1
    	#얘도 마찬가지 
	while k < i :
		if ((col[i] == col[k]) or abs(col[i] - col[k]) == i-k):
			return False
		k += 1
	return True
cnt = 0
n = int(sys.stdin.readline().rstrip())
col = [0] * (n+1)
n_queens(0, col)
print(cnt)