棋盘覆盖问题

  • Tags: 算法 棋盘覆盖问题

【问题描述】

在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘.

下图中的特殊棋盘是当k=364个特殊棋盘中的一个:

k = 3,棋盘大小8 x 8

棋盘覆盖问题中,要用下图中 4 中不同形态的** L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖**。易知,在任何一个 2^k × 2^k 的棋盘中,用到的 L 型骨牌个数恰为 (4^k-1)/3

4 中不同形态的 L 型骨牌

分治策略,可以设计解棋盘问题的一个简捷的算法。

k>0 时,将 2^k * 2^k 棋盘分割为 42^(k-1) * 2^(k-1) 子棋盘,如下图所示:

四个子棋盘

特殊方格必位于 4 个较小子棋盘之一中,其余 3 个子棋盘中无特殊方格。

为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘,我们可以用一个 L 型骨牌覆盖这 3 个较小的棋盘的汇合处,如下图所示,这 3 个子棋盘上被 L 型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将原问题化为 4 个较小规模的棋盘覆盖问题。

四个子问题

递归的使用这种分割,直至棋盘简化为 1x1 棋盘。

【算法实现】

下面讨论棋盘覆盖问题中数据结构的设计:

(1)棋盘:可以用一个二维数组board[size][size]表示一个棋盘,其中,size=2^k。为了在递归处理的过程中使用同一个棋盘,将数组board设为全局变量; (2)子棋盘:整个棋盘用二维数组board[size][size]表示,其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示; (3)特殊方格:用board[dr][dc]表示特殊方格,dr和dc是该特殊方格在二维数组board中的下标; (4) L型骨牌:一个2k×2k的棋盘中有一个特殊方格,所以,用到L型骨牌的个数为(4^k-1)/3,将所有L型骨牌从1开始连续编号,用一个全局变量t表示。

【算法分析】

设T(k)是算法ChessBoard覆盖一个2k×2k棋盘所需时间,从算法的划分策略可知,T(k)满足如下递推式:

T(k) = 1             当k=0时
T(k) = 4 * T(k-1)    当k>0时

解此递推式可得 T(k) = O(4^k)

【C语言代码】

#include <stdio.h>

#define BOARD_SIZE 4
int board[BOARD_SIZE][BOARD_SIZE];

// c1, r1: 棋盘左上角的行号和列号
// c2, r2: 特殊方格的行号和列号
// size = 2 ^ k
void chessboard(int r1, int c1, int r2, int c2, int size)
{
    if(1 == size) return;
    int half_size;
    static int domino_num = 1;
    int d = domino_num++;
    half_size = size / 2;   
   
    if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角子棋盘
    {
       chessboard(r1, c1, r2, c2, half_size); 
    }
    else   // 不在此棋盘,将此棋盘右下角设为相应的骨牌号
    {
       board[r1 + half_size - 1][c1 + half_size - 1] = d;
       chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size);
    }
   
    if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角子棋盘
    {
       chessboard(r1, c1 + half_size, r2, c2, half_size);
    }
    else  // 不在此棋盘,将此棋盘左下角设为相应的骨牌号
    {
       board[r1 + half_size - 1][c1 + half_size] = d;
       chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size);
    }
   
    if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角子棋盘
    {
       chessboard(r1 + half_size, c1, r2, c2, half_size);
    }
    else  // 不在此棋盘,将此棋盘右上角设为相应的骨牌号
    {
       board[r1 + half_size][c1 + half_size - 1] = d;
       chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);
    }
   
    if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在左上角子棋盘
    {
       chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size);
    }
    else   // 不在此棋盘,将此棋盘左上角设为相应的骨牌号
    {
       board[r1 + half_size][c1 + half_size] = d;
       chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size);
    }   
}

int main()
{
    int i, j;
    board[2][2] = 0;
    chessboard(0, 0, 2, 2, BOARD_SIZE);
    for(i = 0; i < BOARD_SIZE; i++)
    {
        for(j = 0; j < BOARD_SIZE; j++)
        {
           printf("%-4d", board[i][j]);
        }
        printf("\n");
    }
}

【C++代码1】

#include<iostream>  
using namespace std;  
int tile=1;                   //L型骨牌的编号(递增)  
int board[100][100];  //棋盘  
/***************************************************** 
* 递归方式实现棋盘覆盖算法 
* 输入参数: 
* tr--当前棋盘左上角的行号 
* tc--当前棋盘左上角的列号 
* dr--当前特殊方格所在的行号 
* dc--当前特殊方格所在的列号 
* size:当前棋盘的:2^k 
*****************************************************/  
void chessBoard ( int tr, int tc, int dr, int dc, int size )  
{  
    if ( size==1 )    //棋盘方格大小为1,说明递归到最里层  
        return;  
    int t=tile++;     //每次递增1  
    int s=size/2;    //棋盘中间的行、列号(相等的)  
    //检查特殊方块是否在左上角子棋盘中  
    if ( dr<tr+s && dc<tc+s )              //在  
        chessBoard ( tr, tc, dr, dc, s );  
    else         //不在,将该子棋盘右下角的方块视为特殊方块  
    {  
        board[tr+s-1][tc+s-1]=t;  
        chessBoard ( tr, tc, tr+s-1, tc+s-1, s );  
    }  
    //检查特殊方块是否在右上角子棋盘中  
    if ( dr<tr+s && dc>=tc+s )               //在  
        chessBoard ( tr, tc+s, dr, dc, s );  
    else          //不在,将该子棋盘左下角的方块视为特殊方块  
    {  
        board[tr+s-1][tc+s]=t;  
        chessBoard ( tr, tc+s, tr+s-1, tc+s, s );  
    }  
    //检查特殊方块是否在左下角子棋盘中  
    if ( dr>=tr+s && dc<tc+s )              //在  
        chessBoard ( tr+s, tc, dr, dc, s );  
    else            //不在,将该子棋盘右上角的方块视为特殊方块  
    {  
        board[tr+s][tc+s-1]=t;  
        chessBoard ( tr+s, tc, tr+s, tc+s-1, s );  
    }  
    //检查特殊方块是否在右下角子棋盘中  
    if ( dr>=tr+s && dc>=tc+s )                //在  
        chessBoard ( tr+s, tc+s, dr, dc, s );  
    else         //不在,将该子棋盘左上角的方块视为特殊方块  
    {  
        board[tr+s][tc+s]=t;  
        chessBoard ( tr+s, tc+s, tr+s, tc+s, s );  
    }  
}  
  
void main()  
{  
    int size;  
    cout<<"输入棋盘的size(大小必须是2的n次幂): ";  
    cin>>size;  
    int index_x,index_y;  
    cout<<"输入特殊方格位置的坐标: ";  
    cin>>index_x>>index_y;  
    chessBoard ( 0,0,index_x,index_y,size );  
    for ( int i=0; i<size; i++ )  
    {  
        for ( int j=0; j<size; j++ )  
            cout<<board[i][j]<<"/t";  
        cout<<endl;  
    }  
}  

【C++代码2】

#include<iostream>  
#include<vector>  
#include<stack>  
   
using namespace std;  
   
vector<vector<int> > board(4);//棋盘数组,也可以作为参数传递进chessBoard中去,作为全局变量可以减少参数传递  
stack<int> stI;   //记录当前所使用的骨牌号码,使用栈顶元素填充棋盘数组  
int sL = 0;     //L型骨牌序号  
   
//所有下标皆为0开始的C C++下标  
void chessBoard(int uRow, int lCol, int specPosR, int specPosC, int rowSize)  
{  
    if(rowSize ==1) return;  
    //static int sL = 0;棋牌和骨牌都可以用static代替,如果不喜欢用全局变量的话。  
    sL++;     
    stI.push(sL); //每递归深入一层,就把一个骨牌序号入栈  
    int halfSize = rowSize/2;//拆分  
   
    //注意:下面四个if else,肯定是只有一个if成立,然后执行if句,而肯定有三个else语句要执行的,因为肯定有一个是特殊位置,而其他三个是空白位置,需要填充骨牌。  
   
    //1如果特殊位置在左上角区域,则继续递归,直到剩下一个格子,并且该格子已经填充,遇到函数头一句if(rowSize == 1) return;就跳出一层递归。  
    //注意是一个区域或子棋盘,有一个或者多个格子,并不是就指一个格子。  
    if(specPosR<uRow+halfSize && specPosC<lCol+halfSize)  
        chessBoard(uRow, lCol, specPosR, specPosC, halfSize);  
    //如果其他情况  
    else 
    {  
        board[uRow+halfSize-1][lCol+halfSize-1] = stI.top();  
        //因为特殊位置不在,所以可以选择任意一个空格填充,但是本算法只填充左上角(也许不止一个格,也许有很多个格子)区域的右下角。大家仔细查一下,就知道下标[uRow+halfSize-1][lCol+halfSize-1]是本区域中最右下角的一个格子的下标号。  
        chessBoard(uRow, lCol, uRow+halfSize-1, lCol+halfSize-1, halfSize);  
        //然后是递归填充这个区域的其他空白格子。因为上一句已经填充了[uRow+halfSize-1][lCol+halfSize-1]这个格子,所以,这个下标作为特殊位置参数传递进chessBoard中。  
    }     
   
    //2右上角区域,解析类上  
    if(specPosR<uRow+halfSize && specPosC>=lCol+halfSize)  
        chessBoard(uRow, lCol+halfSize, specPosR, specPosC, halfSize);  
    else 
    {  
        board[uRow+halfSize-1][lCol+halfSize] = stI.top();  
        chessBoard(uRow, lCol+halfSize, uRow+halfSize-1, lCol+halfSize, halfSize);  
    }         
   
    //3左下角区域,类上  
    if(specPosR>=uRow+halfSize && specPosC<lCol+halfSize)  
        chessBoard(uRow+halfSize, lCol, specPosR, specPosC, halfSize);  
    else 
    {  
        board[uRow+halfSize][lCol+halfSize-1] = stI.top();  
        chessBoard(uRow+halfSize, lCol, uRow+halfSize, lCol+halfSize-1, halfSize);  
    }     
   
    //4右下角区域,类上  
    if(specPosR>=uRow+halfSize && specPosC>=lCol+halfSize)  
        chessBoard(uRow+halfSize, lCol+halfSize, specPosR, specPosC, halfSize);  
    else 
    {  
        board[uRow+halfSize][lCol+halfSize] = stI.top();  
        chessBoard(uRow+halfSize, lCol+halfSize, uRow+halfSize, lCol+halfSize, halfSize);  
    }     
   
    stI.pop();//本次骨牌号填充了三个格,填充完就出栈  
}  
   
void test()  
{  
    //初始化数组  
    for(int i=0; i<4; i++)  
    {  
        board[i].resize(4);  
    }  
   
    chessBoard(0, 0, 3, 3, 4);  
   
    //特殊位置填充0  
    board[3][3] = 0;  
   
    //序列输出  
    for(int j=0; j<4; j++)  
    {  
        for(int i=0; i<4; i++)  
            cout<<board[j][i]<<"\t";  
        cout<<endl;  
    }  
    cout<<endl;  
}  
   
   
int main()  
{  
    test();  
    return 0;  
}  

【JAVA】

1、Element类,它有两个属性,一个是JPanel,它主要用来显示一个小格的颜色;另一个属性是flag,它用来标记此方格有没有被填充过。另外Element之所以要继承Jcomponent,是因为我们要把Element加入到JFrame当中去。因此具体代码如下:

package com.qipan.test;
 
import javax.swing.JComponent;
import javax.swing.JPanel;
 
public class Element extends JComponent {
 
    private static final long serialVersionUID = 1L;
    private JPanel j;
    boolean flag = false;
 
    public Element() {
       this.j = new JPanel();
    }
 
    public JPanel getJ() {
       return j;
    }
 
    public void setJ(JPanel j) {
       this.j = j;
    }
 
    public boolean isFlag() {
       return flag;
    }
 
    public void setFlag(boolean flag) {
       this.flag = flag;
    }
}

2、Application主类的设计:首先在它里面有一个JFrame,然后对它进行网格布局,对每个小的布局区域里我们加入一个Element元素,注意覆盖的时候都是按三格L型来操作的。具体算法如下: (1)把全部方格分成4个区域,若其中一个区域中有被覆盖过的,则从其他域中各选一个构成三格L型进行着色。 (2)对上面分完后的每个区域,我们再同上一样进行那样的一次着色过程。 (3)到一定程度时,我们要退出着色过程,也就是递归的出口。 此类的源代码如下:

package com.qipan.test;
 
import java.awt.Color;
import java.awt.GridLayout;
import java.util.Random;
 
import javax.swing.JFrame;
 
public class Application extends JFrame {
 
         private static final long serialVersionUID = 1L;
         int size = 16;
         private Element[][] elements = new Element[size][size];
         Color[] colors = new Color[220];
         JFrame jf = new JFrame();
 
         public void makeColor() {
                   int num = 0;
                   for (int i = 0; i < 255; i += 50)
                            for (int j = 0; j < 255; j += 50)
                                     for (int k = 0; k < 255; k += 50) {
                                               Color c = new Color(i, j, k);
                                               colors[num++] = c;
                                     }
         }
 
        
         public Application() {
                   for (int i = 0; i < size; i++)
                            for (int j = 0; j < size; j++) {
                                     elements[i][j] = new Element();
                            }
         }
 
         public void create() {
                   for (int i = 0; i < size; i++)
                            for (int j = 0; j < size; j++) {
                                     jf.add(elements[i][j].getJ());
                            }
                   jf.setVisible(true);
                   jf.setSize(512, 512);
                   jf.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
         }
 
        
 
         public void paintFrame() {
                   makeColor();
                   elements[6][10].setFlag(true);
                   jf.setLayout(new GridLayout(size, size));
                   search(0, 0, size);
         }
 
         public void search(int m, int n, int length) {
                   if (length == 1)
                            return;
                   int subLength = length / 2;
                   int n1 = 0, n2 = 0, n3 = 0, n4 = 0;
                   for (int i = 0; i < subLength; i++)
                            for (int j = 0; j < subLength; j++) {
                                     if (elements[m + i][n + j].isFlag())
                                               n1++;
                                     if (elements[m + i][n + subLength + j].isFlag())
                                               n2++;
                                     if (elements[m + subLength + i][n + j].isFlag())
                                               n3++;
                                     if (elements[m + subLength + i][n + subLength + j].isFlag())
                                               n4++;
                            }
                   Random r = new Random();
                   int color_num = r.nextInt(216);
                   Color c = colors[color_num];
                   if (n1 == 1) {
                            elements[m + subLength - 1][n + subLength].getJ().setBackground(c);
                            elements[m + subLength][n + subLength - 1].getJ().setBackground(c);
                            elements[m + subLength][n + subLength].getJ().setBackground(c);
                            elements[m + subLength - 1][n + subLength].setFlag(true);
                            elements[m + subLength][n + subLength - 1].setFlag(true);
                            elements[m + subLength][n + subLength].setFlag(true);
                   }
                   if (n2 == 1) {
                            elements[m + subLength - 1][n + subLength - 1].getJ()
                                               .setBackground(c);
                            elements[m + subLength][n + subLength - 1].getJ().setBackground(c);
                            elements[m + subLength][n + subLength].getJ().setBackground(c);
                            elements[m + subLength - 1][n + subLength - 1].setFlag(true);
                            elements[m + subLength][n + subLength - 1].setFlag(true);
                            elements[m + subLength][n + subLength].setFlag(true);
                   }
                   if (n3 == 1) {
                            elements[m + subLength - 1][n + subLength - 1].getJ()
                                               .setBackground(c);
                            elements[m + subLength - 1][n + subLength].getJ().setBackground(c);
                            elements[m + subLength][n + subLength].getJ().setBackground(c);
                            elements[m + subLength - 1][n + subLength - 1].setFlag(true);
                            elements[m + subLength - 1][n + subLength].setFlag(true);
                            elements[m + subLength][n + subLength].setFlag(true);
                   }
                   if (n4 == 1) {
                            elements[m + subLength - 1][n + subLength - 1].getJ()
                                               .setBackground(c);
                            elements[m + subLength - 1][n + subLength].getJ().setBackground(c);
                            elements[m + subLength][n + subLength - 1].getJ().setBackground(c);
                            elements[m + subLength - 1][n + subLength - 1].setFlag(true);
                            elements[m + subLength - 1][n + subLength].setFlag(true);
                            elements[m + subLength][n + subLength - 1].setFlag(true);
                   }
                   try {
                            Thread.sleep(200);
                   } catch (InterruptedException e) {
                            System.out.println(e);
                   }
                   create();
                   search(m, n, subLength);
                   search(m, n + subLength, subLength);
                   search(m + subLength, n, subLength);
                   search(m + subLength, n + subLength, subLength);
         }
 
         public static void main(String[] args) {
                   Application app = new Application();
                   app.paintFrame();
         }
}

程序的最终效果:


Reference:

[1] http://blog.csdn.net/akof1314/article/details/5423608 [2] http://www.cnblogs.com/kahreman/archive/2011/08/08/2130613.html [3] http://www.iamyoso.com/?p=393 [4] http://blog.sina.com.cn/s/blog_7476a4db0100wpk1.html [5] http://www.cnblogs.com/nokiaguy/archive/2008/05/11/1192579.html [6] http://blog.chinaunix.net/uid-26548237-id-3505163.html [7] http://www.2cto.com/kf/201310/252188.html [8] http://baike.baidu.com/link?url=7fqQcXwuMNpTL-oASXVdI6PH11tg1vpkbIQBWKgOOeFW7SMypkyXbSm3huRwt0-JNQ6UDnB858AFDmmFnSMTka [9] http://blog.sina.com.cn/s/blog_67cf65ab0100qt4z.html


(注:感谢您的阅读,希望本文对您有所帮助。如果觉得不错欢迎分享转载,但请先点击 这里 获取授权。本文由 版权印 提供保护,禁止任何形式的未授权违规转载,谢谢!)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

iOS开发-OpenGLES进阶教程2

教程 OpenGLES入门教程1-Tutorial01-GLKit OpenGLES入门教程2-Tutorial02-shader入门 OpenGLES入门教程...

31370
来自专栏数据结构与算法

洛谷P3209 [HNOI2010]PLANAR(2-SAT)

题目描述 若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要...

34860
来自专栏书山有路勤为径

Keras tutorialThe Happy House

Why are we using Keras? Keras was developed to enable deep learning engineers to...

10510
来自专栏逍遥剑客的游戏开发

边缘高亮效果

23590
来自专栏大数据文摘

动图,用Python追踪NBA球员的运动轨迹

71540
来自专栏BestSDK

10行代码告诉你,为什么说Python数据可视化是一件艺术品

1. 画散点图 画散点图用plt.scatter(x,y)。画连续曲线在下一个例子中可以看到,用到了plt.plot(x,y)。 plt.xticks(loc,...

43960
来自专栏数说工作室

【SAS Says】基础篇:基本统计、相关分析与回归分析

特别说明:本节【SAS Says】基础篇:SAS宏初步,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择 S...

46750
来自专栏木子昭的博客

机器学习三剑客之PandasPandas的两大核心数据结构Panda数据读取(以csv为例)数据处理Pandas的分组和聚合(重要)

Pandas是基于Numpy开发出的,专门用于数据分析的开源Python库 Pandas的两大核心数据结构 Series(一维数据) 允许索引重复...

33860
来自专栏量子位

谷歌云TPU上可以用Julia啦!0.23秒跑100张图片,Jeff Dean点赞推荐

不久前,Julia Computing官方放出了一篇论文,展示将Julia代码和机器学习模型编译到谷歌云TPU的方法,可以实现在0.23秒内完成100张图片VG...

13130
来自专栏MelonTeam专栏

OpenGL ES (iOS) 学习笔记 — 基础篇(一)

最近一直在做视频相关的工作,结合最近很火的AR技术,所以准备好好学习一下3D渲染的相关知识。因为一直在iOS移动端开发,所以学习一下OpenGL ES 技术。 ...

713100

扫码关注云+社区

领取腾讯云代金券