N-Queen(쇼기판)

N-Queen을 장기로 해본다



말은 적 아군 20개씩, 합계 40개 놓기로 한다. (더 둘 수 있을지도 모르지만)
조건은 어떤 말도 적 아군을 포함하여 이동할 수 있는 위치에 없는 것. 수리 최적화 에서 풀어 보자.

python3
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

과연, GUROBI!
0.5초 정도로 풀렸다 1

보자.

python3
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()



참고:
- 조합 최적화로 N 퀸 문제 해결 - Qiita

이상



「목적 함수가 dummy의 허용성 판정 문제가 되고 있습니다. 농공대의 미야시로 선생님의 코멘트보다

좋은 웹페이지 즐겨찾기