`
128kj
  • 浏览: 600224 次
  • 来自: ...
社区版块
存档分类
最新评论

回溯法入门学习之二(九宫格与数独)

阅读更多
   回溯法的基本做法是搜索解空间,一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。上文“回溯法入门学习之一”http://128kj.iteye.com/blog/1722216中已给出了一个框架:

"深度优先搜索+回溯"递归框架:
函数DFS(节点){
  如果(节点=目标节点) {找到目标,跳出}
  遍历所有下一层节点for(int i=0;i<k;i++){
   标记下一层节点i已访问;
   DFS(下一层的节点i)
   恢复i为未访问
  }

}

下面使用上面框架再解一例(数独问题):


题目大意,如上图(一):
    把一个9行9列的网格,再细分为9个3*3的子网格,要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字,即每行、每列、每个子网格内都不允许出现相同的数字。空格是待填位置,其他均为已填入的数字。

要求填完九宫格并输出(如果有多种结果,则只需输出其中一种),
如果给定的九宫格无法按要求填出来,则输出原来所输入的未填的九宫格。
  如上图一中的9个子网络,我们假设子网格的序号如下编排图(二):

先讨论一下上图(一)中第i行j列的数字是属于哪个子网格的,
由于0<=i、j<=8,我们有图(三):



令a= i/3 , b= j/3 ,根据九宫格的行列与子网格(grid)的关系,我们有图(四):


不难发现 3a+b=k,即 3*(i/3)+j/3=k。即图一中第i行j列的数字,属于第k个子网络

算法分析: DFS+回溯
      1.把所有空格位置找出来,对他们进行dfs填补(用1,2,3,...9去试填)
      2.剪枝方法(九宫格中已有数字的不用试填),把搜索过的相应位置搜索完复位


样例:
Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

import java.util.Scanner;

public class Main{
 private int table[][];//用一个二维数组表示九宫格
 private int pos[];//记录要填的空格位置
 private int posNum;//要填的空格标号(从0开始)
 private boolean rUsed[][];//rUsed[i][x]  标记在第i行中数字x是否出现了

 private boolean cUsed[][];//cUsed[j][y]  标记在第j列中数字y是否出现了

 private boolean sUsed[][];//sUsed[k][x] 标记在第k个3*3子格中数字z是否出现子
 private boolean finish_dfs;//是否已找到了答案

 public void go(){
  Scanner  in=new Scanner(System.in);
  int cnt=in.nextInt();
 
  while((cnt--)!=0){
    //初始化数据
    posNum = 0;
    pos=new int[90];
    table=new int[9][9];
    rUsed=new boolean[9][10];
    cUsed=new boolean[9][10];
    sUsed=new boolean[9][10];
    String line=null;
    
    finish_dfs = false;
    for(int i=0;i< 9;i++){ //准备输入数据
        line=in.next();
	for(int j=0;j< 9;j++){
          table[i][j]=line.charAt(j)-'0';
          if (table[i][j]!=0 ) {
             rUsed[i][table[i][j]] = true;//table[i][j]这个数字在i行中已有了
             cUsed[j][table[i][j]] = true;
             int k = (i/3)*3+(j/3);
             sUsed[k][table[i][j]] = true;//table[i][j]这个数字在第k个小网络中已有了
          }
          else {
               pos[posNum++] = i*9+j;//记录要填的空格位置及标号
          }
       }
      }
    dfs_sudoku(0);
   }
  }
   
   
 private void outre(){//输出结果
    for ( int i = 0; i < 9; i++ ) {
        for ( int j = 0; j < 9; j++ ) {
            System.out.printf( "%d", table[i][j] );
        }
         System.out.println();
     }
    //System.out.println();
  }

  void dfs_sudoku( int n ){//深度优先搜索+回溯,试填第n个空格)
    if ( n >= posNum ) {
         finish_dfs = true;
         outre();
        return;
    }
    //根据要填的空格位置,计算空格的所在的行,列坐标及处在哪个小网络
    int r = pos[n]/9;//空格的行坐标
    int c = pos[n]%9;//空格的列坐标
    int s = (r/3)*3+(c/3);//小网络的标号
    for ( int i = 1; i <= 9 && !finish_dfs; i++ ) {//用1,2,3...9去试填)
        if ( rUsed[r][i] ) continue;//第r行有i
        if ( cUsed[c][i] ) continue;//第c列有i
        if ( sUsed[s][i] ) continue;//第k个小网络有i
        rUsed[r][i] = cUsed[c][i] = sUsed[s][i] = true;
        table[r][c] = i;//第r行c列试填数字i
        dfs_sudoku( n+1 );//递归试填第n+1个空格,成功或失败,如果成功则输出,失败则回溯
        table[r][c] = 0;//回溯
        rUsed[r][i] = cUsed[c][i] = sUsed[s][i] = false;
     }
    return;
  }

  public static void main(String[] args){
    Main ma=new Main();
    ma.go();
   
  }
}
  • 大小: 15.3 KB
  • 大小: 3.6 KB
  • 大小: 18.3 KB
  • 大小: 15.3 KB
0
0
分享到:
评论

相关推荐

    九宫格数独100题及答案(初级可打印版)

    九宫格数独100题及答案(初级可打印版)

    九宫格智力数独200题题+答案.doc

    同时,这些题目也可以作为学习和练习九宫格智力数独的材料,帮助玩家提高自己的逻辑思维能力和解决问题的能力。 在学习和实践九宫格智力数独时,玩家需要掌握一些基本的策略和技巧。例如,玩家需要了解游戏的规则、...

    九宫格数独题目大全.doc

    二、九宫格数独的解决方法: * 使用逻辑推理和排除法来解决九宫格数独 * 首先,玩家需要找到已经填充的数字,然后通过逻辑推理和排除法来填充空白的格子 * 玩家可以使用不同的方法来解决九宫格数独,如使用候选数字...

    九宫格(数独)软件 数独

    标题中的“九宫格(数独)软件 数独”指的是一个专门用于玩数独游戏的计算机软件。数独是一种逻辑推理游戏,源自18世纪的瑞士,流行于21世纪初,规则简单却富有挑战性。它通常在9x9的网格中进行,分为9个3x3的小宫格,...

    九宫格数独题目生成器.rar

    数独是一种逻辑推理游戏,其玩法是在9x9的九宫格内填入数字1至9,每个数字在每一行、每一列以及每一个3x3的小九宫格内只能出现一次。九宫格数独题目生成器就是根据这个规则,通过算法随机生成符合要求的数独盘面。 ...

    C#九宫格(数独)源码

    《C#实现的九宫格(数独)游戏源码解析》 数独,一种源自18世纪瑞士的逻辑推理游戏,近年来在全球范围内备受青睐。它以简单的规则和丰富的挑战性,吸引了无数玩家和程序员的关注。本文将深入探讨一个基于C#编程语言...

    九宫格数独游戏

    《九宫格数独游戏:源代码解析与游戏编程学习指南》 九宫格数独游戏,作为一种逻辑推理和智力挑战的游戏,深受广大玩家喜爱。它不仅锻炼了人们的思维敏捷性,也提升了逻辑分析能力。在本文中,我们将深入探讨这款名...

    九宫格-数独

    标题“九宫格-数独”指的是一个与数学游戏数独相关的编程项目。数独是一种逻辑推理游戏,玩家需要在9x9的格子里填入数字,使得每一行、每一列以及每一个3x3的小九宫格内的数字都恰好出现一次,且不重复。这个项目...

    破解九宫格(数独)

    数独是一种广受欢迎的逻辑推理游戏,它基于一个9x9的网格,被分为9个3x3的小九宫格。每个小九宫格、每一行、每一列都必须填入1到9的数字,且每个数字在各自区域内不得重复。这种游戏锻炼玩家的逻辑思维和推理能力。 ...

    android 九宫格数独游戏

    android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码android 九宫格数独 游戏 源码

    九宫格智力数独200题题答案.doc

    "九宫格智力数独200题题答案.doc" 九宫格智力数独是一种非常流行的智力游戏,旨在提高人们的逻辑思维和推理能力。数独游戏的规则非常简单,即在一个9x9的矩阵中,填充数字1-9,使每行、每列和每个3x3的小矩阵中都...

    Excel制作的九宫格数独游戏,含出题和解题,vba编写

    Excel制作的九宫格数独游戏,含出题和解题,vba编写。

    微信小程序实现九宫格数独

    在这个项目中,我们关注的是如何利用微信小程序来实现一个九宫格数独游戏。 首先,我们需要了解数独的基本规则。数独是一种基于逻辑的数字填充游戏,通常在9x9的九宫格中进行,分为9个3x3的小九宫格。每个小九宫格...

    九宫格数独解法

    - **回溯法**:这是一种试探性的方法,从空格开始尝试填入数字,如果发现违反数独规则(如行、列或小九宫格内有重复数字),则回溯到上一步,尝试下一个可能的数字。这种方法相对简单,但效率较低,特别是在数独盘面...

    九宫格(数独)游戏源代码

    【标题】"九宫格(数独)游戏源代码"是一个关于编程开发的项目,它提供了实现数独游戏的核心逻辑和界面交互的源代码。数独是一种基于逻辑推理的单人益智游戏,通常在9x9的网格上进行,其中部分单元格预先填有数字,...

    java 数独 九宫格

    Java实现的数独九宫格算法是一个典型的编程挑战,它涉及到逻辑推理、回溯和效率优化等技术。数独是一种基于数字填充的逻辑游戏,玩家需要在9x9的网格中填入数字,使得每行、每列以及每个3x3的小宫格内的数字都不重复...

    数独九宫格,excel自动生成版

    下载excel后,打开下方的sheet1,即为九宫格题目,复制到word内打印即可。 详细说明: 1.更改sheet2内的A1单元格内的数字(范围1-9),可以调节数独的难度,1难度最低,9难度最高,建议设置为5以下。 2.sheet2内为...

    Sudoku-九宫格-数独matlab代码

    Sudoku-九宫格-数独matlab代码,matlab需要嵌入凸优化CVX工具包

    Excel制作的九宫格数独游戏,含出题和解题,可设置难度,可生成A4打印,vba编写

    Excel制作的九宫格数独游戏,含出题和解题,可设置难度,可生成A4版面打印,vba编写

    java九宫格数独游戏下载

    九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,九宫格数独,

Global site tag (gtag.js) - Google Analytics