首页 > 搜索 > DFS搜索 > HDU 3111-Sudoku-DFS-[解题报告]HOJ
2014
03-02

HDU 3111-Sudoku-DFS-[解题报告]HOJ

Sudoku

问题描述 :

A Sudoku puzzle, once solved, is a 9×9 grid of digits organized as a 3×3 grid of smaller 3×3 units. Each of the nine rows must contain every positive digits exactly once, as do each column and also each 3×3 unit. The puzzle is to start from a partially filled 9×9 grid and to fill in the remaining cells using only logic. The puzzle maker usually makes sure that the solution will be unique and that it can be reached using deduction only, without guessing.
Crystal Ball Factory

This number placing game is gaining popularity in the west, and every second newspaper publishes weekly instances of the puzzle. Somewhere at the head of one such newspaper, someone decided that buying individual instances from a puzzle maker would be too expansive, and instead decided to steal puzzles from other newspapers and also to print randomly generated Sudoku-like grids.

One week later, his assistant gets stuck with the job of printing the solution to the Sudoku puzzles his boss previously published. Unfortunately, his boss doesn’t have those solutions, the randomly generated problems don’t have any solution, and he doesn’t even remember which is which. In despair, the assistant calls for your help.

输入:

The first line of the input will contain the number of test cases. Each test case will consist of a 9 by 9 grid of characters, where each character will either be ‘?’ or a digit between 1 and 9 inclusively.

输出:

The first line of the input will contain the number of test cases. Each test case will consist of a 9 by 9 grid of characters, where each character will either be ‘?’ or a digit between 1 and 9 inclusively.

样例输入:

3
??4??9??8
?3??5??1?
7??4??2??
3??8??1??
?5?????9?
??6??1??2
??8??3??1
?2??4??5?
6??1??7??
---
??4??9??8
?3??5??1?
7??4??2??
3??8??1??
?5?????9?
??6??1??2
??8??3??1
62??4??5?
6??1??7??
---
3?1????76
7??9?????
2?5?3????
?????64?1
???2?1???
1?25?????
????8?9?3
?????9??4
51????7?8

样例输出:

264319578
839257416
715486239
372894165
451632897
986571342
548763921
127948653
693125784
---
impossible
---
391452876
764918532
285637149
953876421
678241395
142593687
426785913
837169254
519324768

10天没写代码了啊。,一个这样的搜索写了两小时。。我擦。。

搜索部分没什么好说的。。主要就是visited标记位。。申明类型为int。以后每次visited就+1,回溯就-1。。这样就可以避免交叉的问题出现(感谢春哥的方法。)

#include<iostream>
using namespace std;

int map[10][10];
int visited[10][10][10];
void init()
{
    memset(visited,0,sizeof(visited));
}
bool dfs(int num)
{
    int i,j;
    int k;
    i=num/9;
    j=num%9;
    while(num<=80&&map[i][j]!=-1)
    {
        num++;
        i=num/9;
        j=num%9;
    }
    i=num/9;
    j=num%9;
    if(num>=81)
    {
        return 1;
    }
    for(k=1;k<=9;k++)
    {
        if(!visited[i][j][k])
        {
            visited[i][j][k]=1;
            map[i][j]=k;
            int l;
            for(l=0;l<=8;l++)
            {
                visited[i][l][map[i][j]]++;
                visited[l][j][map[i][j]]++;
                visited[(i/3)*3+l/3][(j/3)*3+l%3][map[i][j]]++;
                //cout<<(i/3)*3+l/3<<"|"<<(j/3)*3+l%3<<endl;
            }
            if((dfs(num+1)))
            {
                return 1;
            }else
            {
                int l;
                for(l=0;l<=8;l++)
                {
                    visited[i][l][map[i][j]]--;
                    visited[l][j][map[i][j]]--;
                    visited[(i/3)*3+l/3][(j/3)*3+l%3][map[i][j]]--;
                }
                visited[i][j][k]=0;
                map[i][j]=-1;
            }
        }
    }
    return 0;
}
int main()
{
    int t;
    cin>>t;
    bool tag=0;
    bool tag2=0;
    while(t--)
    {
        if(tag2)
        {
            char fuck[44];
            cin>>fuck;
        }
        tag2=1;
        int i,j;
        int done=0;
        init();
        for(i=0;i<=8;i++)
        {
            for(j=0;j<=8;j++)
            {
                char c;
                cin>>c;
                if(c=='?')
                {
                    map[i][j]=-1;
                }else
                {
                    map[i][j]=c-'0';
                    done++;
                    int k;
                    for(k=0;k<=8;k++)
                    {
                        visited[i][k][map[i][j]]++;
                        visited[k][j][map[i][j]]++;
                        visited[(i/3)*3+k/3][(j/3)*3+k%3][map[i][j]]++;
                        //cout<<(i/3)*3+k/3<<"|"<<(j/3)*3+k%3<<endl;
                    }
                }
            }
        }
        if(dfs(0))
        {
            if(tag)
            {
                cout<<"---"<<endl;
            }
            for(i=0;i<=8;i++)
            {
                for(j=0;j<=8;j++)
                {
                    cout<<map[i][j];
                }
                cout<<endl;
            }  
            tag=1;
            
        }else
        {
            if(tag)
            {
                cout<<"---"<<endl;
            }
            cout<<"impossible"<<endl;
            tag=1;
        }
    }
    return 0;
}

  

参考:http://www.cnblogs.com/cj695/archive/2012/08/17/2644745.html


,
  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。