手把手教孩子学数独,Noip2009靶形数独
分类:计算机编程

计算数独

图片 1

标题叙述

小城和小美国首都以垂怜数学的好学子,前段时间,他们不期而同地迷上了数独游戏,好胜的他

们想用数独来生龙活虎比高低。但常常的数独对她们来讲都过度简单了,于是他们向 Z 学士请教,

Z 硕士拿出了他近来声明的“靶形数独”,作为那三个孩子比试的难题。

靶形数独的方格同普通数唯同样,在 9 格宽×9 格高的大九宫格中有 9 个 3 格宽×3 格

高的小九宫格(用粗桔棕线隔开的)。在这里个大九宫格中,有朝气蓬勃部分数字是已知的,依照那么些数字,利用逻辑推演,在此外的空格上填入 1 到 9 的数字。每一个数字在每种小九宫格内不可能

重复现身,每种数字在每行、每列也不能够重复现身。但靶形数唯有好几和普通数独不一致,即

每三个方格都有贰个分值,並且就像二个目的雷同,离为主越近则分值越高。(如图)

图片 2

上海教室具体的分值分布是:最中间生龙活虎格(海海军蓝区域)为 10 分,海螺红区域外面包车型地铁风姿洒脱圈(红

色区域)种种格子为 9 分,再外面豆蔻梢头圈(深中湖蓝区域)各类格子为 8 分,古铜黑区域外不熟悉机勃勃圈(棕

色区域)每一个格子为 7 分,最外面意气风发圈(玉绿区域)每种格子为 6 分,如上海教室所示。竞技的

渴求是:每一种人必得产生三个加以的数独(每一个给定数独也有差异的填法),何况要争取

越来越高的总分数。而这么些总分数即每一个方格上的分值和姣好那一个数独时填在相应格上的数字

的乘积的总的数量

总分数即各样方格上的分值和完毕那一个数独时填在相应格上的数字

的乘积的总额。如图,在偏下的那些早已填完数字的靶形数独游戏中,总分数为 2829。游戏规定,将以总分数的高低决出输赢。

图片 3

鉴于求胜心切,小城找到了擅长编制程序的你,让你帮他求出,对于给定的靶形数独,能

够拿到的参天资数。

数独文件

000000002
006002000
000030040
000050000
001000006
000400070
050000000
000003109
470009000

01

Kuan爸小编是二个特意喜爱玩数独的人,在小编的无绳话机里下载了很多数独类的App,经常空闲的时候(举例说坐客车、看电视)作者就能够拿出作者的数独App玩上风流浪漫把。数独是三个老小咸宜的游乐。听他们讲最初是起点于中中原人民共和国吧。

下图正是二个行业内部九宫数独:

图片 4

九宫数独

数独的平整相当轻易,举例上海教室的专门的职业九宫数独,供给每行、每列和每宫(即用粗线包围的3*3的正方)中的数字均不可能再一次。

而外九宫数独,标准的数独还会有四宫,和六宫。别的,还会有局地变形数独,譬如徘徊花数独、对角线数独、摩天楼数独等。

图片 5

剑客数独

数独主要能够训练人类对数字的敏感性,培育逻辑思维技巧,以至注意力。因为数独的规行矩步特别简单,所以小编引入我们教孩子们都来玩风度翩翩玩数独。

输入输出格式

输入格式:

 

总共 9 行。每行 9 个整数(各类数都在 0―9 的约束内),表示一个尚无填满的数独方

格,未填的空格用“0”表示。每五个数字之间用一个空格隔离。

 

输出格式:

 

输出文件 sudoku.out 共 1 行。

出口能够获得的靶形数独的最高分数。倘若那些数独无解,则输出整数-1。

 

代码

class Sudoku:
    ALL = set(range(1, 10))

    def __init__(self, sdk_file):
        self.sdk_matrix = [[int(c) for c in line]
                           for line in sdk_file.read().split("n")] if sdk_file else []

    def get_row(self, row):
        return self.sdk_matrix[row]

    def get_col(self, col):
        return [row[col] for row in self.sdk_matrix]

    def get_matrix(self, row, col):
        sr, sc = (row // 3) * 3, (col // 3) * 3
        for r in range(sr, sr   3):
            for c in range(sc, sc   3):
                yield(self.sdk_matrix[r][c])

    def get_avls(self, row, col):
        return self.ALL - (set(self.get_matrix(row, col)) | set(self.get_row(row)) | set(self.get_col(col)))

    def __getitem__(self, n):
        return self.sdk_matrix[n]

    def __str__(self):
        return "n".join([str(row) for row in self.sdk_matrix])

    def clone(self):
        sdk_c = Sudoku(None)
        for row in range(9):
            sdk_c.sdk_matrix.append([])
            for col in range(9):
                sdk_c.sdk_matrix[row].append(self.sdk_matrix[row][col])
        return sdk_c


def get_answer(sdk):
    has_filled, brunch = False, None
    for row in range(9):
        for col in range(9):
            if sdk[row][col] != 0:
                continue
            avls = sdk.get_avls(row, col)
            if len(avls) == 0:
                return False
            elif len(avls) == 1:
                sdk[row][col] = avls.pop()
                has_filled = True
            elif not brunch or len(avls) < len(brunch[0]):
                brunch = (avls, row, col)
    if has_filled:
        answer = get_answer(sdk)
        if answer:
            return answer
    elif brunch:
        for b in brunch[0]:
            sdk_c = sdk.clone()
            sdk_c[brunch[1]][brunch[2]] = b
            answer = get_answer(sdk_c)
            if answer:
                return answer
    else:
        return sdk


with open("4.sdk") as sdk_file:
    sdk = Sudoku(sdk_file)
    answer = get_answer(sdk)
    print(answer)

02

情势独的不二秘技有广大种,最大旨的二种是:

1)宫内消弭法

2)行列消逝法

3)唯意气风发余数法

4)区块淹没法

输入输出样例

输入样例#1:

sudoku1
7 0 0 9 0 0 0 0 1 
1 0 0 0 0 5 9 0 0 
0 0 0 2 0 0 0 8 0 
0 0 5 0 2 0 0 0 3 
0 0 0 0 0 0 6 4 8 
4 1 3 0 0 0 0 0 0 
0 0 7 0 0 2 0 9 0 
2 0 1 0 6 0 8 0 4 
0 8 0 5 0 4 0 1 2

sudoku2
0 0 0 7 0 2 4 5 3 
9 0 0 0 0 8 0 0 0 
7 4 0 0 0 5 0 1 0 
1 9 5 0 8 0 0 0 0 
0 7 0 0 0 0 0 2 5 
0 3 0 5 7 9 1 0 8 
0 0 0 6 0 1 0 0 0 
0 6 0 9 0 0 0 0 1 
0 0 0 0 0 0 0 0 6

出口样例#1:

sudoku1
2829

sudoku2
2852

结果

图片 6

03

那怎么来教,小家伙学习数独呢。借使是零根基的儿女,建议照旧从最简便易行的四宫数独来学,那样能由此协和的大力解出来,对创立孩子的信念是非常常有支持的。同不常候,因为儿女的注意力十分的短,四宫数独平时占用的时间也相当的少。

当四宫数独能够超级快解出来的时候,就可以挑战六宫以至九宫数独了。可是,要在乎,能够天天做1-3道题,可是不可能时刻过长。假使开采孩子对数独的志趣比较浓重,还足以报名出席在首都的数独段位比赛,以致全国中型Mini学数独比赛(已经办成第1届了)。

说明

【数据范围】

五分三的多寡,数独中国和南美洲 0 数的个数不菲于 30。

70%的数目,数独中国和亚洲 0 数的个数不菲于 26。

100%的多寡,数独中国和北美洲 0 数的个数不菲于 24。

NOIP 2009 提高组 第四题

/*************************************************************************************************************************************/

解题方法:

正着搜会卡数据,所以利用倒着搜或许竖着搜的办法

然后尝试写了个启迪式搜索,然则出于价值评估不对,结果80分(不比正着暴力。。)

只怕婴孩地服从顺序搜吧

 

 

代码:

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

int belong[9][9] = {
1,1,1,2,2,2,3,3,3,
1,1,1,2,2,2,3,3,3,
1,1,1,2,2,2,3,3,3,
4,4,4,5,5,5,6,6,6,
4,4,4,5,5,5,6,6,6,
4,4,4,5,5,5,6,6,6,
7,7,7,8,8,8,9,9,9,
7,7,7,8,8,8,9,9,9,
7,7,7,8,8,8,9,9,9
};

int ver[9][9] = {
6,6,6,6,6,6,6,6,6,
6,7,7,7,7,7,7,7,6,
6,7,8,8,8,8,8,7,6,
6,7,8,9,9,9,8,7,6,
6,7,8,9,10,9,8,7,6, 
6,7,8,9,9,9,8,7,6,
6,7,8,8,8,8,8,7,6,
6,7,7,7,7,7,7,7,6,
6,6,6,6,6,6,6,6,6
};


int mp[9][9];
int ans = -1;

bool hangvis[9][10];
bool lievis[9][10];
bool kuaivis[9][10];


void dfs(int now,int as)
{
    if(now == 81)
    {
        ans = max(ans,as);
        return;
    }
    int x = now % 9;
    int y = 8 - now/ 9;
    if(mp[x][y])
    {
        dfs(now   1,as);
        return;
    }
    for(int i = 1;i <= 9;i  )
    {
        if(!hangvis[x][i] && !lievis[y][i] && !kuaivis[belong[x][y]][i])
        {
            hangvis[x][i] = true;
            lievis[y][i] = true;
            kuaivis[belong[x][y]][i] = true;
            mp[x][y] = i;
            dfs(now   1,as   ver[x][y] * i);
            mp[x][y] = 0;
            hangvis[x][i] = false;
            lievis[y][i] = false;
            kuaivis[belong[x][y]][i] = false;
        }
    }


}

int main()
{
    int op = 0; 
    for(int i = 0;i < 9;i  )
        for(int j = 0;j < 9;j  )
        {
            scanf("%d",&mp[i][j]);
            hangvis[i][mp[i][j]] = true;
            lievis[j][mp[i][j]] = true;
            kuaivis[belong[i][j]][mp[i][j]] = true;
            op  = mp[i][j] * ver[i][j];
        }
    dfs(0,op);
    printf("%d",ans);
    return 0;
}

 

流程图

图片 7

04

为了越来越好地鼓励孩子学习的志趣,家长也能够跟子女来一场PK,很风趣的啊。

下图是自身和男女PK的数独题。

图片 8

小学甲组题(和儿女PK结果)

本文由pc28.am发布于计算机编程,转载请注明出处:手把手教孩子学数独,Noip2009靶形数独

上一篇:没有了 下一篇:没有了
猜你喜欢
热门排行
精彩图文
  • 那些年【深入.NET平台和C#编程】
    那些年【深入.NET平台和C#编程】
    一、深入.NET框架 ArrayList (非泛型集合  using System.Collections;) public void Text1(){ ArrayList al = new ArrayList (); al.Add ("刘德化");       //添加元素 al.Add ("张学友
  • 碰着搭建
    碰着搭建
    Appium是移动端的自动化测试工具,类似于前面所说的Selenium,利用它可以驱动Android、iOS等设备完成自动化测试,比如模拟点击、滑动、输入等操作,其官方
  • Django中的CBV和FBV示例介绍
    Django中的CBV和FBV示例介绍
    Django中的CBV和FBV Django中的CBV和FBV示例介绍,djangocbvfbv示例 前言 本文主要给大家介绍了关于Django中CBV和FBV的相关内容,分享出来供大家参考学习,下面话不
  • 将Log4net的配置配置到的独立文件中,Log4Net日志插
    将Log4net的配置配置到的独立文件中,Log4Net日志插
  • Python面向对象编程思想
    Python面向对象编程思想
    Python中的类(一) 1.面向过程编程:计算机通过一系列指令来一步一步完成任务。 面向对象编程——Object OrientedProgramming,简称OOP,是一种程序设计思想。