wikioi-天梯-提高一等-啟發式搜尋-1074：靶形數獨

題目描述 Description

小城和小華都是熱愛數學的好學生，最近，他們不約而同地迷上了數獨遊戲，好勝的他

們想用數獨來一比高低。但普通的數獨對他們來說都過于簡單了，于是他們向Z 博士請教，

Z 博士拿出了他最近發明的“靶形數獨”，作為這兩個孩子比試的題目。

靶形數獨的方格同普通數獨一樣，在 9 格寬×9 格高的大九宮格中有9 個3 格寬×3 格

高的小九宮格（用粗黑色線隔開的）。在這個大九宮格中，有一些數字是已知的，根據這些

數字，利用邏輯推理，在其他的空格上填入1 到9 的數字。每個數字在每個小九宮格内不能

重複出現，每個數字在每行、每列也不能重複出現。但靶形數獨有一點和普通數獨不同，即

每一個方格都有一個分值，而且如同一個靶子一樣，離中心越近則分值越高。

上圖具體的分值分布是：最裡面一格（黃色區域）為 10 分，黃色區域外面的一圈（紅

色區域）每個格子為9 分，再外面一圈（藍色區域）每個格子為8 分，藍色區域外面一圈（棕

色區域）每個格子為7 分，最外面一圈（白色區域）每個格子為6 分，如上圖所示。比賽的

要求是：每個人必須完成一個給定的數獨（每個給定數獨可能有不同的填法），而且要争取

更高的總分數。而這個總分數即每個方格上的分值和完成這個數獨時填在相應格上的數字

的乘積的總和。如圖，在以下的這個已經填完數字的靶形數獨遊戲中，總分數為2829。遊

戲規定，将以總分數的高低決出勝負。

由于求勝心切，小城找到了善于程式設計的你，讓你幫他求出，對于給定的靶形數獨，能

夠得到的最高分數。

輸入描述 Input Description

一共 9 行。每行9 個整數（每個數都在0—9 的範圍内），表示一個尚未填滿的數獨方

格，未填的空格用“0”表示。每兩個數字之間用一個空格隔開。

輸出描述 Output Description

輸出可以得到的靶形數獨的最高分數。如果這個數獨無解，則輸出整數-1。

樣例輸入 Sample Input

【輸入輸出樣例 1】

7 0 0 9 0 0 0 0 1

1 0 0 0 0 5 9 0 0

0 0 0 2 0 0 0 8 0

0 0 5 0 2 0 0 0 3

0 0 0 0 0 0 6 4 8

4 1 3 0 0 0 0 0 0

0 0 7 0 0 2 0 9 0

2 0 1 0 6 0 8 0 4

0 8 0 5 0 4 0 1 2

【輸入輸出樣例 2】

0 0 0 7 0 2 4 5 3

9 0 0 0 0 8 0 0 0

7 4 0 0 0 5 0 1 0

1 9 5 0 8 0 0 0 0

0 7 0 0 0 0 0 2 5

0 3 0 5 7 9 1 0 8

0 0 0 6 0 1 0 0 0

0 6 0 9 0 0 0 0 1

0 0 0 0 0 0 0 0 6

樣例輸出 Sample Output

【輸入輸出樣例 1】

2829

【輸入輸出樣例 1】

2852

資料範圍及提示 Data Size & Hint

【資料範圍】

40%的資料，數獨中非0 數的個數不少于30。

80%的資料，數獨中非0 數的個數不少于26。

100%的資料，數獨中非0 數的個數不少于24。

類型：圖論  難度：2.5

題意：給出一個數獨（每行每列，每一個3*3區域都不出現重複的數字），每個格子給出一個分值，由内向外遞增，整個數獨的分值是每個格子的分值乘以填入格子的數，再求和。求分值最高的合法數獨。

分析：整體思想還是枚舉每個空白格子的可能的取值，然後用dfs搜尋，但是這種盲目搜尋可能會造成很大的搜尋空間，是以利用啟發式搜尋的思想，可以看出，由于要求每行每列，每一個3*3區域都不出現重複的數字，那麼如果這一行/列給出的數字越多，那麼空白格子枚舉的次數就越少，那麼從這種格子開始搜尋，搜尋空間就小。

是以在進行dfs之前，先按每行/列給出的數字的個數對行/列排序，給出的數字越多，該行/列優先級越高，然後按照這個優先級計算所有空白格子的周遊順序，按照先行後列的優先級排序，然後按照這個順序進行dfs，找到一個合法數獨後，記錄最大值。

代碼：

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;

int m[9][9];
int s[9][9] = {
    {6,6,6,6,6,6,6,6,6},
    {6,7,7,7,7,7,7,7,6},
    {6,7,8,8,8,8,8,7,6},
    {6,7,8,9,9,9,8,7,6},
    {6,7,8,9,10,9,8,7,6},
    {6,7,8,9,9,9,8,7,6},
    {6,7,8,8,8,8,8,7,6},
    {6,7,7,7,7,7,7,7,6},
    {6,6,6,6,6,6,6,6,6},
    };
int que[90][2],qlen;

int cmp(const void*a, const void*b)
{
    if(((int*)b)[1]==((int*)a)[1])
        return ((int*)a)[0]-((int*)b)[0];
    return ((int*)b)[1]-((int*)a)[1];
}

int fun(int pos)
{
    if(pos>=qlen)
        return 0;
    
    int i = que[pos][0];
    int j = que[pos][1];
        
    bool inv[10];
    memset(inv,0,sizeof(inv));
    for(int k=0; k<9; k++)
    {
        inv[m[i][k]] = 1;
        inv[m[k][j]] = 1;
    }
    for(int x=i/3*3; x<i/3*3+3; x++)
        for(int y=j/3*3; y<j/3*3+3; y++)
            inv[m[x][y]] = 1;

    int maxn = -1;
    for(int k=1; k<=9; k++)
    {
        if(inv[k]==0)
        {
            m[i][j] = k;
                
            int tmp = fun(pos+1);
            if(tmp>=0)
                if(tmp+k*s[i][j]>maxn) 
                    maxn = tmp+k*s[i][j];
            
            m[i][j] = 0;
        }
    }
    return maxn;
}

int main()
{
    int row[9][2],col[9][2];
    for(int i=0; i<9; i++)
    {
        row[i][0] = i;
        row[i][1] = 0;
        col[i][0] = i;
        col[i][1] = 0;
    }
        
    int ans = 0;
    for(int i=0; i<9; i++)
    {
        for(int j=0; j<9; j++)
        {
            cin>>m[i][j];
            if(m[i][j]>0)
            {
                row[i][1]++;
                col[j][1]++;
                ans += m[i][j]*s[i][j];
            }
        }
    }
    
    qsort(row,9,sizeof(int)*2,cmp);
    qsort(col,9,sizeof(int)*2,cmp);
    
    qlen=0;
    for(int i=0; i<9; i++)
    {
        for(int j=0; j<9; j++)
        {
            if(m[row[i][0]][col[j][0]]==0)
            {
                que[qlen][0] = row[i][0];
                que[qlen++][1] = col[j][0];
            }
        }
    }
    int tmp = fun(0);
    if(tmp<0) ans = -1;
    else ans += tmp;
    cout<<ans<<endl;
}