http://www.carrefourstation.com

POJ2676 2918 Sudoku 暴搜

POJ2676 2918 Sudoku 暴搜

#include 
#include 
#include 
#include 
using namespace std;
int s[][2] = {{1,1},{1,4},{1,7},{4,1},{4,4},{4,7},{7,1},{7,4},{7,7}};
int a[10][10];
int ch[] = {0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
    };
int check(int step,int k){
    int x = step/9;
    int y = step%9;
    for(int i = 0;i < 9;i++){
        if(a[x][i] == k)return 0;
        if(a[i][y] == k)return 0;
    }
    int q = ch[step];
    x = s[q][0];
    y = s[q][1];
    for(int i = -1;i <= 1;i++){
        for(int j = -1;j <= 1;j ++){
            if(a[x+i][y+j]==k){
                return 0;
            }
        }
    }
    return 1;
}
int fun(int step){
    if(step >= 81) return 1;
    if(a[step/9][step%9] != 0){
       return fun(step+1);
    }
    for(int i = 1;i <= 9;i++){
        if(check(step,i)){
            a[step/9][step%9] = i;
            if(fun(step+1)){
                return 1;
            }
            a[step/9][step%9] = 0;
        }
    }
    return 0;
}
int main(){
    int t;
    cin >> t;
    while(t--){
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                scanf(%1d,&a[i][j]);
            }
        }
        fun(0);
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                printf(%d,a[i][j]);
            }
            printf(
);
        }
        printf(
);
    }
    return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
int s[][2] = {{1,1},{1,4},{1,7},{4,1},{4,4},{4,7},{7,1},{7,4},{7,7}};
int a[10][10];
int ch[] = {0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            0,0,0,1,1,1,2,2,2,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            3,3,3,4,4,4,5,5,5,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
            6,6,6,7,7,7,8,8,8,
    };
int check(int step,int k){
    int x = step/9;
    int y = step%9;
    for(int i = 0;i < 9;i++){
        if(a[x][i] == k)return 0;
        if(a[i][y] == k)return 0;
    }
    int q = ch[step];
    x = s[q][0];
    y = s[q][1];
    for(int i = -1;i <= 1;i++){
        for(int j = -1;j <= 1;j ++){
            if(a[x+i][y+j]==k){
                return 0;
            }
        }
    }
    return 1;
}
int fun(int step){
    if(step >= 81) return 1;
    if(a[step/9][step%9] != 0){
       return fun(step+1);
    }
    for(int i = 1;i <= 9;i++){
        if(check(step,i)){
            a[step/9][step%9] = i;
            if(fun(step+1)){
                return 1;
            }
            a[step/9][step%9] = 0;
        }
    }
    return 0;
}
int main(){
    int t;
    cin >> t;
    int T = 1;
    while(t--){
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                scanf(%1d,&a[i][j]);
            }
        }
        fun(0);
        printf(Scenario #%d:
,T++);
        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                printf(%d,a[i][j]);
            }
            printf(
);
        }
        printf(
);
    }
    return 0;
}

 

2918 Sudoku 暴搜 #include #include #include #include using namespace std;int s[][2] = {{1,1},{1,4},{1,7},{4,1},{4,4},{4,7},{7,1},{7,4},{7,7}};int a[10][10];int ch[] = {0,...

LeetCode36:Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

新蒲京娱乐场 1

A partially filled sudoku which is valid.

 

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

 

那道题生龙活虎看正是用空间来换取时间,符合规律意况下应当每行实行相比,每列举办相比较,然后每一个网格开展比较,不过种种比较都有叁个双层循环。

能够依赖STL中的set来开展推断是还是不是曾经存在该因素,规范的长空换取时间的章程。

runtime:24ms

 

class Solution {
public:
    bool isValidSudoku(vector>& board) {
        unordered_set rows[9];//每一行一个set来判断改行是否存在重复元素
        unordered_set columns[9];//每一列一个set用来判断该列是否存在重复元素
        unordered_set grids[3][3];//每一个3*3网格一个set来判断该网格是否存在重复元素
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    char tmp=board[i][j];
                    if(!rows[i].insert(tmp).second||!columns[j].insert(tmp).second||!grids[i/3][j/3].insert(tmp).second)
                    return false;

                }
            }

        }
        return true;

    }
};

除了行使STL外由于那道题比较容易,能够动用和地点同样的方法自身定义一个掩码。

 

用一个int rows[9][9]来记录行的掩码

用一个int column[9][9]来记录列的掩码

用一个int gird[3][3][9]来记录网格的掩码。

runtime:12ms

运作时刻少了百分之五十!!!!

 

class Solution {
public:  
       bool isValidSudoku(vector>& board) {
             int rows[9][9]={0};
             int columns[9][9]={0};
             int grids[3][3][9]={0};

            for(int i=0;i<9;i++)
            {
                for(int j=0;j<9;j++)
                {
                    if(board[i][j]!='.')
                    {
                           char tmp=board[i][j];
                           int index=tmp-'1';

                           if(rows[i][index]++)
                               return false;

                           if(columns[j][index]++)
                                return false;

                            if(grids[i/3][j/3][index]++)
                                return false;  
                    }

                }
            }
            return true;

        }


};

 

 

Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the...

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

 

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

              Dancing Links 在追寻中的应用 

新蒲京娱乐场 2

1.1    Dancing Links是什么 

A partially filled sudoku which is valid.

     Dancing Links  是knuth 在此几年写的意气风发篇散文,在小编眼里是大器晚成类寻找 

主题材料含义:数独板被有个别填充,空格部分用'.'来填充。 一个片段填充的数组是还是不是有效只需求看其填写的风姿浪漫对就能够

标题标通用优化, 因而笔者把它写下去,希望能在较量中拿到一定的选拔。 

三个数独合法的正规化如下

1.2    Dancing  Links的要紧原理是如何 

  1. 每生机勃勃行每一列必得包罗1-9里头的每种数字(满含1和9卡塔 尔(阿拉伯语:قطر‎

  2. 每三个小的正方形矩阵中必得含有1-9中间的每多个数字(满含1和9卡塔 尔(阿拉伯语:قطر‎

    1 public boolean isValidSudoku(char[][] board) { 2 for(int i = 0; i<9; i++){ 3 HashSet rows = new HashSet(); 4 HashSet columns = new HashSet(); 5 HashSet cube = new HashSet(); 6 for (int j = 0; j < 9;j++){ 7 if(board[i][j]!='.' && !rows.add(board[i][j])) 8 return false; 9 if(board[j][i]!='.' && !columns.add(board[j][i])) 10 return false; 11 12 //总括当前小方格所在的四方形 13 int RowIndex = 3(i/3); 14 int ColIndex = 3(i%3); 15 if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3])) 16 return false; 17 } 18 } 19 return true;
    20 }

     Dancing Links 主假诺用双向十字链表来存款和储蓄疏弃矩阵,来达到在找寻 

 

中的优化。在搜索难题中,所必要仓库储存的矩阵往往趁着递归的深化会变得越 

来越萧条,这种气象用Dancing Links 来存款和储蓄矩阵,往往能够拿走蛮好的 

效果。 

1.3    这篇诗歌与knuth故事集的两样 

     本篇故事集是对Dancing Links 在竞赛的行使的三个介绍,并列举了多少个 

竞赛中的例题。原来的文章能够在这里下载到: 

      jchu/publicportal/sudoku/0011047.pdf 

     相对于本文,小编更建议去读者去看knuth的初藳,本文能够视作三个参 

考。本文还介绍了Sukudo难点和三个Dancing Links的三个变种难题。 

                             2     双向链表 

2.1    双向链表的寄放结构 

     双向链表的仓储结构往往是有多少个空的结点来代表头指针。然后每黄金时代 

个结点有三个pre值域和一个next值域。要是是十字链表的话,结点中指针 

的值域会形成多少个。 

2.2    双向链表的应用 

     众人周知,在单向链表中删去叁个结点是非常麻烦,并且不算的。双向 

链表有着玄妙的协会,能够渔人之利的删减放肆一个结点。犹如下操作: 

                     L[R[x]]新蒲京娱乐场,  =  L[x],  R[L[x]] =   R[x];                  

百依百顺有写过双向链表经验的人对这两句话明确不会目生. 

2.3    双向链表的死灰复然 

     在双向链表中删除三个结点只要用(1) 就能够了,然后来看上边这一段 

代码: 

                        L[R[x]] = x, R[L[x]]澳门新莆京手机网站, = x;                     (2) 

这段代码会将已经去除掉的结点,重新扩充加回双向链表中。第一遍见到这段 

代码的您是否会以为特别奇异?你有一点都不小希望会说在链表中开展删减操作但 

是不自由内存的话是不好的编制程序习于旧贯,会促成内部存款和储蓄器溢出错误。然而在那间, 

大家要的便是这么的法力。 

     我们在链表中删去,只是进行一个标志,并不实行真正的清空内部存款和储蓄器操 

作。那样大家后来便能够用(2) 实行复原操作了。 

     你也是有比超级大可能率会说这段代码会有哪些用?上面就让大家来真的看看(2) 强 

大的威力。(2)才是Dancing Links  的焦点. 

                  3    Exact  Cover Problem 

3.1    Description 

     上节所说的双向链表的复原操作会在本节中有重大的功用。下边先让 

笔者们来看三个标题(Exact Cover Problem)。 

     给定一个01矩阵, 以往要选用部分行,使得每一列有且只有贰个1.  事例 

如下: 

                          0   0  1   0  1  1   0  

                          1   0  0   1  0  0   1 

                          0   1  1   0  0  1   0                   (3) 

                          1   0  0   1  0  0   0 

                          0   1  0   0  0  0   1  

                          0   0  0   1  1  0   1  

对于如上所示的矩阵(3),大家取行会集{1, 4, 5} 便可使每一列有且唯有大器晚成 

个1。 

3.2    Solving  an  exact  cover problem 

     很明白,exact cover problem 是三个不可能用多项式算法清除的标题,解 

决方法只有追寻!  且看如下找出代码: 

if  (A is  empty)  { \A  is  the 0-1  matrix. 

     the problem   is solved; 

     return  ; 

choose  a  column,  c, 

     that  is unremoved   and  has fewest   elements.;      ...(1) 

郑重声明:本文版权归澳门新莆京手机网站所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。