N-Queen(쇼기판)
N-Queen을 장기로 해본다
말은 적 아군 20개씩, 합계 40개 놓기로 한다. (더 둘 수 있을지도 모르지만)
조건은 어떤 말도 적 아군을 포함하여 이동할 수 있는 위치에 없는 것. 수리 최적화 에서 풀어 보자.
python3import numpy as np
from itertools import product
from more_itertools import pairwise
from pulp import *
koma = '歩90g,香21g,桂20ce,銀20fghln,金20fghikm,角21fhln,飛21gikm,王20fghiklmn'.split(',')
arr,pos,whc = [],[0],[]
for iko, ko in enumerate(koma):
for my in range(-1,2,2):
ar = []
lst = [(ord(c)%3-1,(ord(c)//3-35)*my) for c in ko[3:]]
for x,y in product(range(9),range(9)):
a = [0]*81
a[x+y*9] = 40
for p,q in lst:
for z in range(1,int(ko[2])*7+2):
i,j = x+z*p,y+z*q
if not (0<=i<9 and 0<=j<9):
break
a[i+j*9] = 1
ar.append(a)
arr.extend(ar)
pos.append(pos[-1]+len(ar))
whc.extend([iko*2+my//2+1]*len(ar))
if iko > 4:
break
A = np.array(arr)
pp = (A==40).dot(range(81))
m = LpProblem()
x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(A.shape[0])]
m += lpSum(x) == 40
for i, (p1, p2) in enumerate(pairwise(pos)):
m += lpSum(x[p1:p2]) <= int(koma[i//2 if i < 10 else i-5][1])
for i in range(81):
m += lpDot(x,A[:,i]) <= 40
%time m.solve(GUROBI_CMD())
print(LpStatus[m.status])
>>>
Wall time: 582 ms
Optimal
과연, GUROBI!
0.5초 정도로 풀렸다 1
보자.
python3from PIL import Image, ImageDraw, ImageFont
v = np.vectorize(value)(x)
n = 181
fnt = ImageFont.truetype(r'C:\Windows\Fonts\ipaexg.ttf', 18)
im = Image.new(mode='1', size=(n,n), color=1)
for h in range(2):
im = im.transpose(Image.ROTATE_180)
d = ImageDraw.Draw(im)
d.font = fnt
for i,j,k in zip(range(40),np.array(whc)[v==1],pp[v==1]):
x,y = (k%9,k//9) if h else (8-k%9,8-k//9)
if (j<=9 and j%2==h) or (j>9 and i%2==h):
d.text((x*20+2,y*20+2),koma[j//2][0])
for i in range(10):
d.line([(0,i*20),(n,i*20)])
d.line([(i*20,0),(i*20,n)])
im.show()
참고:
- 조합 최적화로 N 퀸 문제 해결 - Qiita
이상
「목적 함수가 dummy의 허용성 판정 문제가 되고 있습니다. 농공대의 미야시로 선생님의 코멘트보다 ↩
Reference
이 문제에 관하여(N-Queen(쇼기판)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://qiita.com/SaitoTsutomu/items/96731d86c9f38da0d717
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import numpy as np
from itertools import product
from more_itertools import pairwise
from pulp import *
koma = '歩90g,香21g,桂20ce,銀20fghln,金20fghikm,角21fhln,飛21gikm,王20fghiklmn'.split(',')
arr,pos,whc = [],[0],[]
for iko, ko in enumerate(koma):
for my in range(-1,2,2):
ar = []
lst = [(ord(c)%3-1,(ord(c)//3-35)*my) for c in ko[3:]]
for x,y in product(range(9),range(9)):
a = [0]*81
a[x+y*9] = 40
for p,q in lst:
for z in range(1,int(ko[2])*7+2):
i,j = x+z*p,y+z*q
if not (0<=i<9 and 0<=j<9):
break
a[i+j*9] = 1
ar.append(a)
arr.extend(ar)
pos.append(pos[-1]+len(ar))
whc.extend([iko*2+my//2+1]*len(ar))
if iko > 4:
break
A = np.array(arr)
pp = (A==40).dot(range(81))
m = LpProblem()
x = [LpVariable('x%.4d'%i, cat=LpBinary) for i in range(A.shape[0])]
m += lpSum(x) == 40
for i, (p1, p2) in enumerate(pairwise(pos)):
m += lpSum(x[p1:p2]) <= int(koma[i//2 if i < 10 else i-5][1])
for i in range(81):
m += lpDot(x,A[:,i]) <= 40
%time m.solve(GUROBI_CMD())
print(LpStatus[m.status])
>>>
Wall time: 582 ms
Optimal
from PIL import Image, ImageDraw, ImageFont
v = np.vectorize(value)(x)
n = 181
fnt = ImageFont.truetype(r'C:\Windows\Fonts\ipaexg.ttf', 18)
im = Image.new(mode='1', size=(n,n), color=1)
for h in range(2):
im = im.transpose(Image.ROTATE_180)
d = ImageDraw.Draw(im)
d.font = fnt
for i,j,k in zip(range(40),np.array(whc)[v==1],pp[v==1]):
x,y = (k%9,k//9) if h else (8-k%9,8-k//9)
if (j<=9 and j%2==h) or (j>9 and i%2==h):
d.text((x*20+2,y*20+2),koma[j//2][0])
for i in range(10):
d.line([(0,i*20),(n,i*20)])
d.line([(i*20,0),(i*20,n)])
im.show()
Reference
이 문제에 관하여(N-Queen(쇼기판)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/SaitoTsutomu/items/96731d86c9f38da0d717텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)