欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数独 约束求解 C++ and Python

程序员文章站 2022-03-31 10:33:33
利用每一个空格的域空间进行约束求解,注释应该够了,直接贴代码 C++: #include #include #include #include #inclu...

利用每一个空格的域空间进行约束求解,注释应该够了,直接贴代码

C++:

#include 
#include 
#include 
#include 
#include 
using namespace std;

vector CurDom[81];
int map[9][9];
vector< vector > answer;
int num_of_blank;
int able_num[9];
int Assigned[81];
int counts = 0 ;
void init_CurDom(int map[9][9], int index )//index表示0~81某一位置索引,将该索引位置的行,列,方块进行检查,把可走的数字的域放入CurDom[index]的容器中
{
    for ( int k = 0 ; k < 9 ; k ++ )    able_num[k] = k + 1;//先初始为1~9,将行,列,方块中出现的数字的索引置为0,不为零的即为可走域
    int i = index/9;
    int j = index%9;
    for ( int row = 0 ; row < 9 ; row ++ )
        if ( map[row][j] != 0 ) able_num[ map[row][j] - 1 ] = 0;
    for ( int col = 0 ; col < 9 ; col ++ )
        if ( map[i][col] != 0 ) able_num[ map[i][col] - 1 ] = 0;
    for ( int r = i/3*3 ; r < i/3*3 + 3 ; r ++ )
        for ( int c = j/3*3 ; c < j/3*3 + 3 ; c ++ )
            if ( map[r][c] != 0 ) able_num[ map[r][c] - 1 ] = 0;

    for ( int k = 0 ; k < 9 ; k ++ )
        if( able_num[k] != 0 ) CurDom[index].push_back( able_num[k] );
}
void init(int map[9][9],int & num)//初始化操作,num表示空格数目
{
    for (int i = 0 ; i < 9 ; i ++ )
        for ( int j = 0 ; j < 9 ; j ++ )
        {
            int index = i*9+j;
            if( map[i][j] == 0 )
            {
                num ++;
                init_CurDom( map, index );
            }
            else
            Assigned[i*9+j]=1;//已经有值的位置置为1
        }
}
int PickAnUnassignedVariable()//找出可走的index,即为访问过的具有最少域空间的index值
{
    int min_value = 10;
    int min_index = 82;
    for ( int i = 0 ; i < 81 ; i ++ )
    {
        if(Assigned[i] == 0 && CurDom[i].size() < min_value ) 
        {
            min_value = CurDom[i].size();
            min_index = i;
        }
    }
    return min_index;
}

bool have_d(int index , int d)//判断CurDom[index]域空间中是否有d
{
    for(int i = 0 ;i temp;
    for(int j = 0 ;j temp_Assigned(int index,int d)//索引位置index中的d被选择后,行,列,方块中其他索引位置的域中有d值时将d删除掉
{
    int row = index/9;
    int col = index%9;
    vector temp;
    for(int i=0;i<9;i++)
    {
        int row_index = row*9+i;
        if(Assigned[row_index] == 0)
        {
            if(have_d(row_index,d))
            {
                temp.push_back(row_index);
                remove_d(row_index,d);
            }
        }

    }
    for(int i=0;i<9;i++)
    {
        int col_index = i*9+col;
        if(Assigned[col_index] == 0)
        {
            if(have_d(col_index,d))
            {
                temp.push_back(col_index);
                remove_d(col_index,d);
            }
        }
    }
    for(int i = row/3*3;i < row/3*3+3;i++)
        for(int j = col/3*3;j temp_Assigned_list, int d )//重新将被删除d的索引位置的域空间加回d
{
    for(int i=0;i temp;
        temp.push_back(row);
        temp.push_back(col);
        temp.push_back(d);
        answer.push_back(temp);//先放入结果队列 
        Assigned[min_index] = d;
        vector temp_Assigned_list = temp_Assigned(min_index,d);//list,里面包含当前选择d约束时受影响的位置链表 

        if(GAC_Enforce() == true)
        {
            if(GAC(level-1))//空格数-1 
            {
                return true;
            }
        }
        Restore_CurDoms(temp_Assigned_list,d);//域空间重新放回d 
        Assigned[min_index]=0;
        answer.pop_back();

    }
    return false;
}

void print_map(int map[9][9])
{
    for(int i=0;i<9;i++)
    {
        cout<<"[ ";
        for(int j=0;j<9;j++)
        {
            cout<