首页 > 搜索 > DFS搜索 > HDU 4210-Su-domino-ku-DFS-[解题报告]HOJ
2015
05-23

HDU 4210-Su-domino-ku-DFS-[解题报告]HOJ

Su-domino-ku

问题描述 :

As if there were not already enough sudoku-like puzzles, the July 2009 issue of Games Magazine describes the following variant that combines facets of both sudoku and dominos. The puzzle is a form of a standard sudoku, in which there is a nine-by-nine grid that must be filled in using only digits 1 through 9. In a successful solution:
Each row must contain each of the digits 1 through 9.
Each column must contain each of the digits 1 through 9.
Each of the indicated three-by-three squares must contain each of the digits 1 through 9.
For a su-domino-ku, nine arbitrary cells are initialized with the numbers 1 to 9. This leaves 72 remaining cells. Those must be filled by making use of the following set of 36 domino tiles. The tile set includes one domino for each possible pair of unique numbers from 1 to 9 (e.g., 1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, …). Note well that there are not separate 1+2 and 2+1 tiles in the set; the single such domino can be rotated to provide either orientation. Also, note that dominos may cross the boundary of the three-by-three squares (as does the 2+9 domino in our coming example).
To help you out, we will begin each puzzle by identifying the location of some of the dominos. For example, Figure 1 shows a sample puzzle in its initial state. Figure 2 shows the unique way to complete that puzzle.
Pizza PricingPizza Pricing

输入:

Each puzzle description begins with a line containing an integer N, for 10 ≤ N ≤ 35, representing the number of dominos that are initially placed in the starting configuration. Following that are N lines, each describing a single domino as U LU V LV. Value U is one of the numbers on the domino, and LU is a two-character string representing the location of value U on the board based on the grid system diagrammed in Figure 1. The variables V and LV representing the respective value and location of the other half of the domino. For example, our first sample input beings with a domino described as 6 B2 1 B3. This corresponds to the domino with values 6+1 being placed on the board such that value 6 is in row B, column 2 and value 1 in row B, column 3. The two locations for a given domino will always be neighboring.
After the specification of the N dominos will be a final line that describes the initial locations of the isolated numbers, ordered from 1 to 9, using the same row-column conventions for describing locations on the board. All initial numbers and dominos will be at unique locations.
The input file ends with a line containing 0.

输出:

Each puzzle description begins with a line containing an integer N, for 10 ≤ N ≤ 35, representing the number of dominos that are initially placed in the starting configuration. Following that are N lines, each describing a single domino as U LU V LV. Value U is one of the numbers on the domino, and LU is a two-character string representing the location of value U on the board based on the grid system diagrammed in Figure 1. The variables V and LV representing the respective value and location of the other half of the domino. For example, our first sample input beings with a domino described as 6 B2 1 B3. This corresponds to the domino with values 6+1 being placed on the board such that value 6 is in row B, column 2 and value 1 in row B, column 3. The two locations for a given domino will always be neighboring.
After the specification of the N dominos will be a final line that describes the initial locations of the isolated numbers, ordered from 1 to 9, using the same row-column conventions for describing locations on the board. All initial numbers and dominos will be at unique locations.
The input file ends with a line containing 0.

样例输入:

10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5 
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1
11
5 I9 2 H9
6 A5 7 A6
4 B8 6 C8
3 B5 8 B4
3 C3 2 D3
9 D2 8 E2
3 G2 5 H2
1 A2 8 A1
1 H8 3 I8
8 I3 7 I4
4 I6 9 I7
I5 E6 D1 F2 B3 G9 H7 C9 E5
0

样例输出:

Puzzle 1
872643195
361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578
Puzzle 2
814267593
965831247
273945168
392176854
586492371
741358629
137529486
459683712
628714935

题意:数独游戏,不过只能用给定的多米诺骨牌填数独,而且每一个牌只能用一次,有唯一解

分析:对一个未填的方格枚举三十六个牌,每一个牌有俩种摆放方式,……

关键在于有没有好一点的判断方法,判断当前的放置方法是否符合数独的要求

用三个数字st[3][9]表示st[0]数组表示九行的放置状态,比如,st[0][0]的每一个位表示第一行对应选了哪一个数字

以此类推,st[1]表示列,st[2]表示3*3的方格

代码有点冗长了,好挫…………

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N = 10;
struct Domino
{
    int x,y;
}d[40];//保存所有的牌
struct Uncover
{
    int x,y;
}u[N*N];//保存未填的方格
int map[N][N],st[3][9],t,num;
//st[0]行,st[1]列,st[2]方格
int dir[2][2]={{0,1},{1,0}};
bool vis[N][N],flag;
//vis用来标记选了哪些牌
void init()
{
    for(int i=1;i<=8;i++)
        for(int j=i+1;j<=9;j++)
        {
            d[t].x=i,d[t].y=j;
            t++;
        }
}
bool isfinish()//判断数独是否填完整
{
    for(int i=0;i<3;i++)
        for(int j=0;j<9;j++)
            if(st[i][j]!=((1<<9)-1))
                return false;
    return true;
}
bool check(int x,int y,int xx,int yy,int first,int second)//判断该放置是否符合要求,是则修改对应的行列等的状态
{
    int ss1=(x/3)*3+y/3,ss2=(xx/3)*3+yy/3;
    first--,second--;
    if((st[0][x]&(1<<first))||(st[0][xx]&(1<<second)))
        return false;
    if((st[1][y]&(1<<first))||(st[1][yy]&(1<<second)))
        return false;
    if((st[2][ss1]&(1<<first))||(st[2][ss2]&(1<<second)))
        return false;
    st[0][x]|=(1<<first),st[0][xx]|=(1<<second);
    st[1][y]|=(1<<first),st[1][yy]|=(1<<second);
    st[2][ss1]|=(1<<first),st[2][ss2]|=(1<<second);
    return true;
}
void restore(int x,int y,int xx,int yy,int first,int second)//还原行列等的状态
{
    int ss1=(x/3)*3+y/3,ss2=(xx/3)*3+yy/3;
    first--,second--;
    st[0][x]&=~(1<<first),st[0][xx]&=~(1<<second);
    st[1][y]&=~(1<<first),st[1][yy]&=~(1<<second);
    st[2][ss1]&=~(1<<first),st[2][ss2]&=~(1<<second);
}
void set(int x,int y,int a)
{
    int ss=(x/3)*3+y/3;
    a--;
    st[0][x]|=(1<<a);
    st[1][y]|=(1<<a);
    st[2][ss]|=(1<<a);
}
void dfs(int n)
{
    int x=u[n].x,y=u[n].y;
    if(isfinish())
    {
        flag=true;
        return ;
    }
    for(int i=0;i<t;i++)//枚举骨牌
    {    
        if(vis[d[i].x][d[i].y])
            continue;
        vis[d[i].x][d[i].y]=true;
        for(int f=0;f<2;f++)//骨牌正反放置
        {
            int first=d[i].x,second=d[i].y;
            if(f&1) swap(first,second);
            for(int k=0;k<2;k++)//放置的方向
            {    
                int temp=n;
                int xx=x+dir[k][0];
                int yy=y+dir[k][1];
                if(xx<0 || xx>=9 || yy<0 || yy>=9 || map[xx][yy]!=0)
                    continue;
                if(!check(x,y,xx,yy,first,second))
                    continue;
                map[x][y]=first,map[xx][yy]=second;
                if(map[u[temp+1].x][u[temp+1].y]==0)
                    dfs(temp+1);
                else {
                    while(temp<num && map[u[temp+1].x][u[temp+1].y]!=0)//已经填上的方格跳过
                        temp++;
                    dfs(temp+1);
                }
                if(flag) return;
                restore(x,y,xx,yy,first,second);
                map[x][y]=0,map[xx][yy]=0;
            }
        }
        vis[d[i].x][d[i].y]=false;
    }            
}
int main()
{
    t=0;
    init();
    int m,cas=0;
    char s1[5],s2[5];
    int a,b,c,d;
    while(scanf("%d",&m)==1 && m)
    {
        memset(vis,false,sizeof(vis));
        memset(map,0,sizeof(map));
        memset(st,0,sizeof(st));
        for(int i=0;i<m;i++)
        {
            scanf("%d %s %d %s",&a,s1,&b,s2);
            int x=s1[0]-'A',y=s1[1]-'0'-1;
            map[x][y]=a;
            set(x,y,a);
            x=s2[0]-'A',y=s2[1]-'0'-1;
            map[x][y]=b;
            set(x,y,b);
            vis[a][b]=vis[b][a]=true;
        }
        for(int i=1;i<=9;i++)
        {
            scanf("%s",s1);
            int x=s1[0]-'A',y=s1[1]-'0'-1;
            set(x,y,i);
            map[x][y]=i;
        }
        num=0;
        for(int i=0;i<9;i++)
            for(int j=0;j<9;j++)
                if(map[i][j]==0)
                {
                    u[num].x=i,u[num].y=j;
                    num++;
                }
        flag=false;
        dfs(0);
        printf("Puzzle %d\n",++cas);
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
                printf("%d",map[i][j]);
            puts("");
        }
    }
    return 0;
}

 

参考:http://www.cnblogs.com/nanke/archive/2012/04/10/2440645.html


,