水排序拼图 python soulver

water_sort_puzzle_solver.py

"""

version 1 穷举        

# 一个瓶子有4段水
# 瓶子初始化，每一段水可以为不同颜色
# 每次倒出一种颜色（多段水一次倒出）
# 倒入颜色必须与瓶子最上层颜色相同
#
# 数字表示水的颜色
"""


import copy



RED = 1 # 红
YEL = 2 # 黄
BLU = 3 # 蓝
PUR = 4 # 紫
GRE = 5 # 绿
DAG = 6 # 暗绿
PIN = 7 # 粉红
SKB = 8 # 天空蓝
BRY = 9 # 亮黄

SL = 1
Q = 2
DL = 3
TL = 4
R = 5
C = 6
F = 7
H = 8
Z = 9




def pour(sender, receiver):
    """
    sender 倒水 到 receiver
    """
    pour_color = sender[0]
    if len(receiver) != 0 and sender[0] != receiver[0]:
        # 颜色不同，无法倒水
        return False, sender, receiver
    
    pour_length = 1
    for water in sender[1:]:
        if water == pour_color:
            pour_length += 1
        else:
            break
    
    if pour_length + len(receiver) > 4:
        # 倒入过多
        return False, sender, receiver
    
    if pour_length == len(sender) and len(receiver) == 0:
        # 都倒入一个空瓶，没有任何意义
        return False, sender, receiver
    
    s = copy.copy(sender)
    r = copy.copy(receiver)
    
    for _ in range(pour_length):
        s.pop(0)
        r.insert(0, pour_color)
    return True, s, r
            
    
    
def is_same_color(bottle):
    """判断是否整瓶颜色一致， 空瓶也算
    """
    if len(bottle) <= 1: return True

    sample = bottle[0]
    for color in bottle:
        if sample != color:
            return False
    return True


fail_count = 0
is_solved = False
        

def solver(bottles, steps=None):
    global is_solved
    global fail_count 
    
    if is_solved:
        return 
        
    steps = steps or []
    # 判断问题是否解决
    if all([True if is_same_color(bottle) else False for bottle in bottles]):
        is_solved = True
        print('resolved! fail:{} total:{} steps:\n{}'.format(
            fail_count, 
            len(steps), 
            "\n".join(
                ["%s. put %s to %s"%(index, step[0], step[1]) for index, step in enumerate(steps, 1)]
            )
        ))
        return True
    
    
    # 所有可能的sender/receivers
    senders = []
    receivers = []
    for index, bottle in enumerate(bottles, 1):
        if len(bottle) != 0:
            senders.append((index, bottle))
        if len(bottle) != 4:
            receivers.append((index, bottle))

    for si, sender in senders:
        for ri, receiver in receivers:
            if si != ri:
                ret, s, r = pour(sender, receiver)
                if ret:    
                    _bottles = copy.deepcopy(bottles)
                    _bottles[si-1] = s
                    _bottles[ri-1] = r
                    _steps = copy.deepcopy(steps)
                    _steps.append([si, ri])
                    solver(copy.deepcopy(_bottles), _steps)
                else:
                    fail_count += 1
                    

def sort_bottles(bottles):
    # 判断题目是否正常。每种颜色是4的倍数
    from collections import defaultdict
    d = defaultdict(list)

    for bottle in  bottles:
        for color in bottle:
            d[color].append(color)

    for color, color_list in d.items():
        if len(color_list) % 4 != 0:
            print(f"{color} length is {len(color_list)}")
            return False
    solver(bottles)




bottles = [
    [SL, Q, Q, DL],
    [TL, H, SL, C],
    [SL, Q, F, DL],
    [TL, Q, R, H],
    [Z, DL, C, C],
    [H, Z, Z, TL],
    [DL, SL, R, R],
    [F, TL, Z, R],
    [F, H, F, C],
    [],
    [],
]

sort_bottles(bottles)