棋盘覆盖问题（分治策略）

2023-07-19

完成时间：大二上

问题描述

棋盘覆盖问题：给定一个2k×2k的棋盘(具体图例见教材)，有一个特殊棋格，拥有一个特殊棋格的棋盘称为特殊棋盘。现要用四种L型骨牌(具体图例见教材)覆盖特殊棋盘上除特殊棋格外的全部棋格，不能重叠，找出覆盖方案。

可行性分析

当n = 1时（22棋盘），显然有解
假设当n = k时（2^k2^k棋盘），有解，那么当n = k+1时（2^k+12^k+1棋盘），
将其划分为4个2^k2^k子棋盘，特殊方格位于其中一个棋盘中，用一个L形的骨牌
覆盖在另外三个子棋盘的公共部分，则子棋盘也化为了特殊棋盘，以此递归，得出有解。

源码

def chess(tr,tc,pr,pc,size):#tr:棋盘初始行号 tc:棋盘初始列号  
                            #pr:特殊棋盘格行号 pc:特殊棋盘格列号
                            #size:棋盘格大小
    global mark         
    global table                  
    if size==1:
        return      #递归终止条件
    mark+=1             #表示直角骨牌号
    count=mark
    half=size//2         #当size不等于1时，棋盘格规模减半，变为4个
    #小棋盘格进行递归操作
    #左上角
    if (pr<tr+half) and (pc<tc+half):
        chess(tr,tc,pr,pc,half)
    else:
        table[tr+half-1][tc+half-1]=count
        chess(tr,tc,tr+half-1,tc+half-1,half)
        #将[tr+half-1,tc+half-1]作为小规模棋盘格的特殊点，进行递归
 
    #右上角
    if (pr<tr+half) and (pc>=tc+half):
        chess(tr,tc+half,pr,pc,half)
    else:
        table[tr+half-1][tc+half]=count
        chess(tr,tc+half,tr+half-1,tc+half,half)
    #将[tr+half-1,tc+half]作为小规模棋盘格的特殊点，进行递归
 
    #左下角
    if (pr>=tr+half) and (pc<tc+half):
        chess(tr+half,tc,pr,pc,half)
    else:
        table[tr+half][tc+half-1]=count
        chess(tr+half,tc,tr+half,tc+half-1,half)
    #将[tr+half,tc+half-1]作为小规模棋盘格的特殊点，进行递归
 
    #右下角
    if (pr>=tr+half) and (pc>=tc+half):
        chess(tr+half,tc+half,pr,pc,half)
    else:
        table[tr+half][tc+half]=count
        chess(tr+half,tc+half,tr+half,tc+half,half)
    #将[tr+half,tc+half]作为小规模棋盘格的特殊点，进行递归
 
        #输出矩阵
def show(table):
    n=len(table)
    for i in range(n):
        for j in range(n):
            print(table[i][j],end=' ')
        print('')
 
mark=0
n = int(input("请输入棋盘规模："))
pr = int(input("请输入特殊棋格行号："))
pc = int(input("请输入特殊棋格列号："))
# n=8   #输入8*8的棋盘规格
table=[[-1 for x in range(n)] for y in range(n)] #-1代表特殊格子
chess(0,0,pr,pc,n)   #特殊棋盘位置
show(table)

其中-1表示特殊棋格，行号列号均从0开始，相同数字表示一块L形的骨牌，数字大小说明其叠放次序。

运行结果

说明

本实验完成于大二上学期（2021下半年），所使用语言为Python