いろいろな方法

• 解を探す方法について
  • こちらのコメントで教えていただいた
• いろいろな方法があるらしい
  • 焼き鈍し法
• まず大域的な分布をつくる
  • nクイーン問題なら
    • 1.Qの効きの領域を近くに限定しておいて
    • (1'.縦横ナナメに他のQがいるかどうかを探す領域を小さくしておいて)
    • 2.徐々に全領域まで延ばしていく

• この方針で修正してみた(あとswitch()を使うと見やすいかも)
  • N=10
  • Q 8コ
  • 縦横は全領域、ナナメはキョリrだけ気にする
  • rが１からスタート (龍王)
  • rが10になっていたら終了 (奔王)
• このときにどれくらい順調に解に近づいているかをみてみるためにrがどれくらいのびているかをプロットした
  • 横軸：サイクル数 t
  • 縦軸：r
• rが４〜６あたりで時間がかかるようだ

N<-10
k<-8    #クイーンの数
T<-2000
r<-1     #調べる近傍のrangeの初期値
R<-N     #rの最大値
A<-B<-matrix(0,N,N)
A[sample(1:N^2,k)]<-1   #k個のクイーンをおく
u<-c()
for ( t in 1:T){

for (i0 in N:1){
for (j0 in N:1){
	if(A[i0,j0]>0){
	for(k in 1:A[i0,j0]){
	
#   8  1  2
#   7  9  3
#   6  5  4
#周囲(1から8)と今いる場所(9の場所)にいくつのクイーンが"効いて"いるかを調べる

	for (d in 1:9){
	dir <- d	
	i <- i0
	j <- j0
	
	if(dir == 1 ){i <- i-1}
	if(dir == 2 ){i <- i-1; j <- j+1}
	if(dir == 3 ){j <- j+1}
	if(dir == 4 ){i <- i+1; j <- j+1}
	if(dir == 5 ){i <- i+1}
	if(dir == 6 ){i <- i+1; j <- j-1}
	if(dir == 7 ){j <- j-1}
	if(dir == 8 ){i <- i-1; j <- j-1}
	
	if(i == 0){i <- 1}      #境界条件
	if(i == N+1){i <- N}
	if(j == 0){j <- 1}
	if(j == N+1){j <- N}	

#他のクイーンがいないか調べる	
#縦横ナナメの成分のうち、キョリr内の範囲	
#	u0<-c(A[i,max(1,j-r):min(N,j+r)],A[max(1,i-r):min(N,i+r),j],diag(A[max(1,i-j+1,i-r):min(i+N-j,N,i+r),max(1,j-i+1,j-r):min(j+N-i,N,j+r)]),diag(A[min(i+j-1,N,i+r):max(1,i+j-N,i-r),max(1,j+i-N,j-r):min(i+j-1,N,j+r)]))

#縦と横ははじめから全領域調べる場合
#ナナメ方向はr近傍だけ
	u0<-c(A[i,],A[,j],diag(A[max(1,i-j+1,i-r):min(i+N-j,N,i+r),max(1,j-i+1,j-r):min(j+N-i,N,j+r)]),diag(A[min(i+j-1,N,i+r):max(1,i+j-N,i-r),max(1,j+i-N,j-r):min(i+j-1,N,j+r)]))

	u[d]<-sum(u0)  #これが効いている数(自分の効きも含まれる)
	
	}
	i <- i0
	j <- j0
#自分の今いる場所(9の場所)に他のクイーンの効きがあるときは効きの少ないところへ移動する
#他のクイーンが効いていないとき(u[9]==4のとき)は動かない
	if(u[9] !=4){
	dir<-sample(c(rep(which(u==min(u)),times=50),1:8),1)
	if(dir == 1 ){i <- i-1}
	if(dir == 2 ){i <- i-1; j <- j+1}
	if(dir == 3 ){j <- j+1}
	if(dir == 4 ){i <- i+1; j <- j+1}
	if(dir == 5 ){i <- i+1}
	if(dir == 6 ){i <- i+1; j <- j-1}
	if(dir == 7 ){j <- j-1}
	if(dir == 8 ){i <- i-1; j <- j-1}	
	}	

	if(i == 0){i <- 1}      #境界条件
	if(i == N+1){i <- N}
	if(j == 0){j <- 1}
	if(j == N+1){j <- N}
			
	B[i,j]<-B[i,j]+1

	
					
	}			
	}
}
}
	if(min(A-B)==0){        #定常状態になったらrをふやす
	A<-B
	B<-matrix(0,N,N)
	image(A,col=topo.colors(20))
	r <- r+1
	if(r==R+1){break}
	}else{
	A<-B              #次のステップへ
	B<-matrix(0,N,N)
	image(A,col=topo.colors(20))
	}	
}