Quartoの引き分け図を数理最適ソルバで作成

はじめに

Quartoは4x4マスのボードゲームです。プレイヤーは4つの異なる高さ、形状、色、材質の形状の中から1つを選び、相手に配置することになります。相手はその形状を使って、自分のターンに使用します。

目的は、自分のターンに4つの形状が同じ特徴を持つ行または列を作ることです。例えば、全ての高さが同じ行を作ることができれば勝ちとなります。

もし、相手に渡した形状を使って、相手が勝利することができないようにすることができれば、あなたが勝者となります。

ゲームは先手と後手が交互に形状を選んで配置することで進行します。形状がなくなった時点でゲームは終了し、どちらかが4つの形状が同じ特徴を持つ行または列を作れば勝者となります。もしどちらも作れない場合は引き分けとなります。
(chatgpt)

Quartoで引き分けになったときは、すべての駒が盤上に乗っています。
三目並べで引き分けになったような感じです。
そのようなパターンはどこまで制約を加えて残るか気になったため調べてみました。
結果として、縦・横・斜め・2x2ブロックまでは引き分け図が存在しました。

実装

import re, pandas as pd
from itertools import product
from pulp import LpProblem, lpSum, value
from ortoolpy import addbinvars
import itertools
pd.set_option('display.max_rows', None)


binary_list = [0, 1]
combs = list(itertools.product(binary_list, repeat=4))
# print(combs)

r = range(4)
a = pd.DataFrame([(i, j, k+1, combs[k]) for i,j in product(r,r) for k in range(len(r)**2)], columns=['行','列','数', 'combs'])
a['Var'] = addbinvars(len(a))


# 問題作成
m = LpProblem()


#　一意に定まる条件
for _, _df in a.groupby(['行', '列']):
    m += sum(_df.Var) == 1

for _, _df in a.groupby(['数']):
    m += sum(_df.Var) == 1


dfs = pd.DataFrame()
for _, _df in a.groupby(['行', '列']):
    _df['0'] = _df.combs.map(lambda x: x[0]) * _df.Var
    _df['1'] = _df.combs.map(lambda x: x[1]) * _df.Var
    _df['2'] = _df.combs.map(lambda x: x[2]) * _df.Var
    _df['3'] = _df.combs.map(lambda x: x[3]) * _df.Var
    dfs = pd.concat([dfs, _df])

    
# 行と列のそれぞれで0~4
for _, _df in dfs.groupby('行'):
    for col in ['0', '1', '2', '3']:
        m += sum(_df[col]) >= 0.1
        m += sum(_df[col]) <= 3.9

for _, _df in dfs.groupby('列'):
    for col in ['0', '1', '2', '3']:
        m += sum(_df[col]) >= 0.1
        m += sum(_df[col]) <= 3.9


# 斜めも0~4
_df = pd.concat([dfs[(dfs['行']==i) & (dfs['列']==i)] for i in r])
for col in ['0', '1', '2', '3']:
    m += sum(_df[col]) >= 0.1
    m += sum(_df[col]) <= 3.9

_df = pd.concat([dfs[(dfs['行']==i) & (dfs['列']==3-i)] for i in r])
for col in ['0', '1', '2', '3']:
    m += sum(_df[col]) >= 0.1
    m += sum(_df[col]) <= 3.9

for i in range(3):
    for j in range(3):
        _df = dfs[((dfs['行']==i) & (dfs['列']==j)) | ((dfs['行']==i+1) & (dfs['列']==j)) | ((dfs['行']==i) & (dfs['列']==j+1)) | ((dfs['行']==i+1) & (dfs['列']==j+1))]
        for col in ['0', '1', '2', '3']:
            m += sum(_df[col]) >= 0.1
            m += sum(_df[col]) <= 3.9


m.solve()

# 繰り返し解を求める (以前求めた解は除外していく)
# for i in range(1000):
#     a['Val'] = a.Var.apply(value)
#     tmp = sum(a[a.Val==1].Var)
#     m += tmp <= 15
#     m.solve()

def map_func(comb):
    d1 = {0:'うすい', 1:'濃い'}
    d2 = {0:'高い', 1:'低い'}
    d3 = {0:'丸い', 1:'四角い'}
    d4 = {0:'穴あり', 1:'穴なし'}
    return d1[comb[0]], d2[comb[1]], d3[comb[2]], d4[comb[3]]


a['Val'] = a.Var.apply(value)
items = a[a.Val>0.5].combs.map(map_func).values

for i, item in enumerate(items):
    if i % 4 == 0:
        print()
    print(item)

# ('濃い', '低い', '四角い', '穴なし')
# ('うすい', '高い', '四角い', '穴なし')
# ('濃い', '高い', '四角い', '穴あり')
# ('濃い', '高い', '丸い', '穴あり')

# ('濃い', '低い', '丸い', '穴あり')
# ('うすい', '高い', '丸い', '穴あり')
# ('うすい', '低い', '四角い', '穴あり')
# ('濃い', '高い', '丸い', '穴なし')

# ('うすい', '低い', '丸い', '穴なし')
# ('濃い', '高い', '四角い', '穴なし')
# ('うすい', '低い', '四角い', '穴なし')
# ('うすい', '高い', '四角い', '穴あり')

# ('うすい', '高い', '丸い', '穴なし')
# ('濃い', '低い', '四角い', '穴あり')
# ('濃い', '低い', '丸い', '穴なし')
# ('うすい', '低い', '丸い', '穴あり')