• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ2676 – Sudoku

    ACM-POJ EXP 164阅读 0评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    九宫格问题,也有人叫数独问题

    把一个9行9列的网格,再细分为9个3*3的子网格,要求每行、每列、每个子网格内都只能使用一次1~9中的一个数字,即每行、每列、每个子网格内都不允许出现相同的数字。

    0是待填位置,其他均为已填入的数字。

    要求填完九宫格并输出(如果有多种结果,则只需输出其中一种)

    如果给定的九宫格无法按要求填出来,则输出原来所输入的未填的九宫格

    解题思路

    DFS试探,失败则回溯

    用三个数组进行标记每行、每列、每个子网格已用的数字,用于剪枝

    bool row[10][10]; //row[i][x] 标记在第i行中数字x是否出现了

    bool col[10][10]; //col[j][y] 标记在第j列中数字y是否出现了

    bool grid[10][10]; //grid[k][x] 标记在第k个3*3子格中数字z是否出现了

    row 和 col的标记比较好处理,关键是找出grid子网格的序号与 行i列j的关系

    即要知道第i行j列的数字是属于哪个子网格的

    首先我们假设子网格的序号如下编排:

    由于1<=i、j<=9,我们有: (其中“/”是C++中对整数的除法)

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

    不难发现 3a+b=k

    即 3*(i/3)+j/3=k

    又我在程序中使用的数组下标为 1~9,grid编号也为1~9

    因此上面的关系式可变形为 3*((i-1)/3)+(j-1)/3+1=k

    有了这个推导的关系式,问题的处理就变得非常简单了,直接DFS即可

    转载请注明:EXP 技术分享博客 » POJ2676 – Sudoku

    喜欢 (0) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址