Judging the finish of mahjong by combinatorial optimization

Introduction

You can also use Combinatorial Optimization to determine whether you can play mahjong. For the sake of simplicity, I'll just consider whether it's a raised shape (one sparrow head, three facets). In addition, Makiko is also excluded.

the term

--Jantou: Two identical tiles --Mentions: Junko, Kiko, or Mako --Shunz: Three tiles of the same type arranged in order --Coats: Three identical tiles --Kants: 4 same tiles --Rise: 1 sparrow head and 4 faces

Ideas and formulation

--There is no objective function because we will consider whether the condition is satisfied. --Using the given tiles, enumerate the combinations that will be the sparrow head, Junko, or engraving, and make them candidates. ――Choose a candidate well so that all tiles appear exactly once. --Choose exactly one sparrow head.

Variable $ x_i \ in \ {0, 1 \} $ $ x_i $: $ i $ Whether to choose the third candidate
Constraints $ \ sum_i {a_ {ij} x_i} = 1 ~ ~ \ forall j \ le 13 $ $ a_ {ij} $: Whether the $ i $ th candidate contains tile $ j $
$ \ sum_ {i \ in H} {x_i} = 1 $ $ H $: Sparrow head candidate

This problem is a partition of a set problem.

Example of execution by Python

--Mahjong tiles Manz (0-8), Tsutsuko (Pins) (10-18), Swords (20-28), Kazehai (30,32,34, 36), I will represent it with the numbers of Sangenpai (38,40,42). By doing this, Junko is always continuous, and if it is continuous, it becomes Junko. --Define a function calc that takes 14 tiles (variable hai) as input and returns 5 sparrow heads or faces.

python3


def calc(hai):
    import pandas as pd
    from itertools import combinations, product
    from pulp import LpProblem, LpBinary, LpVariable, lpSum, value
    cand  = [] #Candidate
    a = pd.DataFrame(sorted(hai), columns=['v'])
    b = a.v.value_counts()
    for i in b[b >= 2].index: #Sparrow head candidate creation
        cand.extend(combinations(a[a.v == i].index, 2))
    n2 = len(cand)
    for i in b[b >= 3].index: #Create engraving candidates
        cand.extend(combinations(a[a.v == i].index, 3))
    c = a.v.unique()
    for i in range(len(c)-2): #Junko candidate creation
        if c[i+1] - c[i] == c[i+2] - c[i+1] == 1:
            cand.extend(product(a.index[a.v==c[i]],
                                a.index[a.v==c[i+1]],
                                a.index[a.v==c[i+2]]))
    m = LpProblem() #Mathematical model
    v = [LpVariable('v%d'%i, cat=LpBinary) for i in range(len(cand))] #variable
    m += lpSum(v[:n2]) == 1 #One sparrow head
    d = [[] for _ in range(14)] #List of candidate numbers by tile
    for i, ca in enumerate(cand):
        for j in ca:
            d[j].append(v[i])
    for i in d:
        m += lpSum(i) == 1 #All tiles are one in any candidate
    if m.solve() != 1: return None
    return [[a.v[j] for j in cand[i]] for i, vv in enumerate(v) if value(vv) > 0.5]

Let's actually calculate.

python3


def show(n):
    if n < 30:
        return chr(ord('１')+n%10)+'Mantsubo'[n//10]
    return 'From east, west, north, south, and white'[n//2-16]

hai = [0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8] #14 tiles
for i in calc(hai):
    for j in i: print(show(j))
    print()
>>>
1 man
1 man

9 Man
9 Man
9 Man

1 man
2 Man
3 Man

4 Man
5 Man
6 Man

7 Man
8 Man
9 Man

I was able to find the sparrow head and face properly.

that's all

Recommended Posts