Python解决数桥问题的面试项目算法

本项目基于一个流行的日本谜题–"Hashiwokakero"、"Hashi "或 "Bridges"。你需要编写一个程序来解决这个谜题，并简要说明你所使用的算法和数据结构。

程序的输入将是一个由数字和点组成的矩形数组，例如：

每个数字代表一个 "岛屿"，而点代表岛屿之间的空隙（水域）。大于 9 的数字用 "a"（10）、"b"（11）或 "c"（12）表示。游戏的目的是用一个桥梁网络连接所有岛屿，同时满足以下规则：

1.所有桥梁必须水平或垂直延伸
2.桥梁不能相互交叉，也不能与其他岛屿交叉
3.连接任何一对岛屿的桥梁不能超过三座
4.连接每个岛屿的桥梁总数必须等于岛上的桥梁数
5.例如，读取上述 10 行输入后，您的程序可能会产生以下输出：

请注意，单座桥梁用字符"-"或"|"表示，成对桥梁用"="或"""表示，三座桥梁用 "E "或"#"表示，

这取决于它们是横向还是纵向。桥梁和岛屿之间的水域用空格符" '"表示。
在某些情况下，谜题可能有很多解，在这种情况下，您的程序应该只打印一个解。有关谜题的更多详情，请参见维基百科页面。不过请注意，我们的版本允许最多连接 3 个桥，而不是 2 个桥；而且我们并不坚持要求整个图形都是连通的。

import sys
import random
direction = [(0, -1), (-1, 0), (0, 1), (1, 0)]
max_bridge_num = 3
ch_to_int = [{0: 0, '-': 1, '=': 2, 'E': 3, '|': 0, '"': 0, '#': 0},
             {0: 0, '|': 1, '"': 2, '#': 3, '-': 0, '=': 0, 'E': 0}]
int_to_ch = [{0: 0, 1: '-', 2: '=', 3: 'E'},
             {0: 0, 1: '|', 2: '"', 3: '#'}]



def scan_map():
    text = []
    for line in sys.stdin:
        row = []
        for ch in line:
            n = ord(ch)
            if n >= 48 and n <= 57:  # between '0' and '9'
                row.append(n - 48)
            elif n >= 97 and n <= 122:  # between 'a' and 'z'
                row.append(n - 87)
            elif ch == '.':
                row.append(0)
        text.append(row)

    return text



def get_bridge_code(dir, ch):
    if isinstance(ch, int) and 0 < ch:
        return 0
    return ch_to_int[dir % 2][ch]


def format(ele):
    if isinstance(ele, int):
        if ele >= 10:
            return chr(ord('a') + ele - 10)
        elif ele == 0:
            return ' '
    return ele



def print_map(data):
    for row in data:
        # print(' '.join(str(format(cell)) for cell in row))
        print(''.join(str(format(cell)) for cell in row))

def map_2_tuple(data):
    return tuple(tuple(row) for row in data)

def is_valid(data, i, j):
    n = len(data)
    m = len(data[0])
    if i >= 0 and i < n and j >= 0 and j < m:
        return True
    return False

def get_bridge_num(data, i, j, dir):
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    if not is_valid(data, ni, nj):
        return 0
    return get_bridge_code(dir % 2, data[ni][nj])



def search_direction(data, i, j, dir):
    bnum = get_bridge_num(data, i, j, dir)
    if bnum >= max_bridge_num:
        return [0, (-1,-1)]
    bnch = int_to_ch[dir % 2][bnum]
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    while is_valid(data, ni, nj) and data[ni][nj] == bnch:
        ni = ni + direction[dir][0]
        nj = nj + direction[dir][1]
    if not is_valid(data, ni, nj):
        return [0, (-1,-1)]
    if isinstance(data[ni][nj], int) and 0 < data[ni][nj]:
        exsit_bn = 0
        for nd in range(0, 4):
            exsit_bn += get_bridge_num(data, ni, nj, nd)
        return [min(max_bridge_num - bnum, data[ni][nj] - exsit_bn), (ni,nj)]
    return [0, (-1,-1)]

def potential_bridge_num(data, i, j, dir):
    return search_direction(data, i, j, dir)[0]

def add_bridge(data, i, j, dir, num):
    if num == 0:
        return
    #print("bridge",i,j,dir,num)
    bnum = get_bridge_num(data, i, j, dir)
    bnch = int_to_ch[dir % 2][bnum]
    nbnch = int_to_ch[dir % 2][bnum + num]
    ni = i + direction[dir][0]
    nj = j + direction[dir][1]
    while is_valid(data, ni, nj) and data[ni][nj] == bnch:
        data[ni][nj] = nbnch
        ni = ni + direction[dir][0]
        nj = nj + direction[dir][1]

def get_min_comfirmed_bridges(potential, remain_bn):
    sump = sum(potential)
    min_bridge_list = []
    for p in potential:
        min_bridge_list.append(max(0, remain_bn - sump + p))
    return min_bridge_list 

def add_comfirmed_and_check(data, ris):
    n = len(data)
    m = len(data[0])
    correct = True 
    valid = True
    no_comfirmed_bridge = True
    for (i, j) in ris:
        exsit = []
        potential = []
        for d in range(0, 4):
            exsit.append(get_bridge_num(data, i, j, d))
            potential.append(potential_bridge_num(data, i, j, d))
        if sum(potential) + sum(exsit) >= data[i][j]:
            min_bridge = get_min_comfirmed_bridges(potential, data[i][j] - sum(exsit))
            for d in range(0, 4):
                if min_bridge[d] > 0:
                    no_comfirmed_bridge = False
                    add_bridge(data, i, j, d, min_bridge[d])
                    exsit[d] += min_bridge[d] 
                    potential[d] -= min_bridge[d] 
        else:
            valid = False
        if sum(exsit) > data[i][j]:
            valid = False
        elif sum(exsit) < data[i][j]:
            correct = False
        elif sum(exsit) == data[i][j]:
            if (i,j) in ris:
                ris.remove((i,j))
    return [correct, valid, no_comfirmed_bridge] 

def dfs_map(data, i, j, vis2):
    if (i,j) in vis2.keys():
        return 0
    vis2[(i,j)] = True

    ret = data[i][j]
    for d in range(0, 4):
        ret -= get_bridge_num(data, i, j, d)
        [potential, (ni,nj)] = search_direction(data,i,j,d)
        if potential > 0:
            ret += dfs_map(data, ni, nj, vis2)
    if ret < 0:
        print("error")
    return ret


def check_map_right(data, ris):
    dfs_vis = {}
    for (i, j) in ris:
        numsum = dfs_map(data,i, j,dfs_vis)
        if numsum % 2 == 1:
            return False
    return True

def cost_estimation(num, po):
    if (num,po[0],po[1],po[2],po[3]) in est_mp.keys():
        return est_mp[(num,po[0],po[1],po[2],po[3])]
    if num == 0:
        return 0
    count = 0
    for i in range(0,4):
        for k in range(1, po[i]+1):
            if num - k >= 0:
                copied_po = po[:]
                copied_po[i] -= k
                count += cost_estimation(num-k, copied_po) + 1
    est_mp[(num,po[0],po[1],po[2],po[3])] = count
    return count

def heuristic(data, ris):
    res = []
    for (i, j) in ris:
        exsit = []
        potential = []
        for d in range(0, 4):
            exsit.append(get_bridge_num(data, i, j, d))
            potential.append(potential_bridge_num(data, i, j, d))
        if sum(exsit) == data[i][j]:
            continue
        remain = data[i][j]-sum(exsit)
        cost = cost_estimation(remain, potential)
        res.append((i,j,cost))
    #random.shuffle(res)
    #res_xy = [(x[0], x[1]) for x in res]
    #return res_xy
    sorted_res = sorted(res, key=lambda x: x[2])
    sorted_res_xy = [(x[0], x[1]) for x in sorted_res]
    return sorted_res_xy

def backtrack(data, vis, ris):
    if map_2_tuple(data) in vis.keys():
        return False
    vis[map_2_tuple(data)] = True
    while True:
        [correct, valid, no_comfirmed] = add_comfirmed_and_check(data, ris)
        if not valid:
            return False
        if correct:
            print_map(data)
            return True
        if no_comfirmed:
            break
    if not check_map_right(data, ris):
        return False
    #print_map(data)
    #print("--------"+str(len(vis))+"----------")
    ris = heuristic(data, ris)
    for (i, j) in ris:
        dir_list = [0, 1, 2, 3]
        random.shuffle(dir_list)
        for d in dir_list:
            if potential_bridge_num(data, i, j, d) > 0:
                data_tmp = [row[:] for row in data]
                ris_tmp = ris[:]
                add_bridge(data_tmp, i, j, d, 1)
                if backtrack(data_tmp, vis, ris_tmp):
                    return True
    return False


if __name__ == '__main__':
    map = scan_map()
    #print_map(map)
    #print("------------------------")
    vis = {}
    islands = []
    est_mp = {}
    n = len(map)
    m = len(map[0])
    for i in range(0, n):
        for j in range(0, m):
            if isinstance(map[i][j], int) and 0 < map[i][j]:
                islands.append((i,j))
    backtrack(map,vis,islands)