解数独,学编程-Python篇-2

python

问题解决是学习编程、学习计算机科学的核心。

很多少儿编程班都是带孩子一步一步地做一个游戏。学生做出来了,觉得很高兴,也挺有成就感。可是后来一想,除了做这样一个游戏之外,似乎再做别的游戏就不太会了,摸不着头脑。

这种现象出现的主要原因是老师没有教到问题的分析和思维过程。依样画葫芦很容易,但是学生要学到知识的迁移,举一反三,就不那么容易了。

解决数独问题就是一个具体的问题。 我们这一系列文章要通过解决数独问题,教会你怎么分析问题,怎么把问题在程序中表达出来,怎么设计算法,最后怎么编程来解决问题。

有些情况需要学生先理解人力是怎么解决问题的,然后把人解决问题的方法(算法)转换成计算机操作的步骤,然后用编程语言来实现。有些情况计算机解决问题跟人力解决问题的方法是截然不同的,因为计算机和人相比,有自己显著的优点和缺点。设计算法的时候需要充分利用这些优点。

编程解决问题,首先需要知道如何在计算机上表示那些描述问题的数据,然后设计算法,把这些表示转换成其它形式,直到问题解决。

上一篇介绍了解决简单数独问题时,人们常用的办法。 本次我们会介绍数独在Python中的表示方法。

数独在计算机程序中的表示

计算机其实是非常笨的。因为它只懂一些简单的事情,比如数字, 字符, 列表等等这些原生的数据结构。 而其它所有的信息都必须由多种简单的数据结构组合近似地来表示。把事实信息用这些数据来表示可以看做是一个”编码”的过程。

我们要看一下如何对数独编码,在计算机中表示出来。

从上一次的文章中,我们已经给数独中的每个格子都编了号,

  1. 每一列用数字1到9来表示,
  2. 每一行用字母A到I来表示,

那么,第一行第一列就是A1, 第一行第二列就是A2. 最后一行最后一列是I9。


在Python编程语言中,有一种原生的数据结构,叫做列表。 把一些元素放到[] 中,互相之间用,隔开就会创建列表,比如[1,2,3,4,5] 就是一个有5个数字元素的列表。 [’a’,’b’,’c’,’d’,’e’]  是一个含有5个字符元素的列表。   其实列表中的元素类型可以不一样的, [1,2,3,’a’,’b’,’c’] 也是合法的。

有读者可能会问, 数独既有行,也有列,怎么用列表表示呢?  这个问题好解决, 只要列表中套列表就可以了。

数独第一行可以用 [‘A1’, ‘B1’, ‘C1’, ‘D1’, ‘E1’, ‘F1’, ‘G1’, ‘H1’, ‘I1’] 来表示, 第二行可以用 [‘A2’, ‘B2’, ‘C2’, ‘D2’, ‘E2’, ‘F2’, ‘G2’, ‘H2’, ‘I2’]

那么前面两行可以放到同一个列表中,

[ [‘A1’, ‘B1’, ‘C1’, ‘D1’, ‘E1’, ‘F1’, ‘G1’, ‘H1’, ‘I1’],

  [‘A2’, ‘B2’, ‘C2’, ‘D2’, ‘E2’, ‘F2’, ‘G2’, ‘H2’, ‘I2’] ]

我们介绍过单元的概念,就是包含某个格子的行,列和3×3方格。

下面就是包含了一个数独所有单元的列表的例子, 你可以分析一下,是不是这样的。

作业

语法知识:

我们这次讲了列表,列表的生成在Python中的语法是 []。比如下面的语句就生成了一个名字为aList的列表,其中还有三个数字元素。

aList = [1,2,3,4]

如果数独中一个格子中有不确定的值,我们可以把所有的可能的值放进去。 比如下面数独的例子, 我们单看第一行, 用列表可以这样表示:

line1 = [‘123456789′,’7′,’8′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789′,’123456789’]

1. 请用这样的方法, 表示第二行, 第三行

line2= [] ?

line3 = [] ?

2. 我们根据第一行已经给定的数字 7 和8 ,可以判断出第一行其它数字不可能是7或者8, 所以,第一行的表示可以修正为:

line1 = [‘1234569′,’7′,’8′,’1234569′,’1234569′,’1234569′,’1234569′,’1234569′,’1234569’]

请问, 如果我们根据第一列给出的数字信息, 我们可以如何修正第一行?

同样的,我们可以根据第二列给出的数字信息,如何修正第一行?

如何根据左上角3×3的信息,修正第一行?

3. 你能用同样的方法,表示一下别的行,然后修正吗?

如果你遇到了问题,或者想讨论一下,请在下面留言哦。

Leave a Reply

邮箱地址不会被公开。 必填项已用*标注