你会如何编程呢？ [英] How would you program this?
问题描述
日报中有一个数字拼图。
因为我在Python项目之间，我认为编写一个程序可能会很有趣解决它.... 20分钟的工作，最多
仔细观察后，很明显它不是一个简单的事情。程序。你会怎么做？
这个难题：一个4 x 4网格。行被加总（和给定），
cols求和（和给定），两个对角线相加，
并给出。另外，给出了4条线索，但是这4条线路中没有一条在同一行或列中。
来自今天的论文的例子： ..解决时间是8分钟，1秒，
所以他们说。
允许数字的集合是1到9
行：
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
总和：
24 ，18,31,31
Diag sums：
3 + F + K + P = 24
M + J + 8 + D = 24
第一个冲动是用嵌套的for循环来强制它，
但计算器显示可能的组合是
9 ^ 12 = 5,159,780,352，这需要花费太长时间。
另一种方法是检查每个方格并确定
是什么合理的数字范围。例如，
如果A + 9 + C + D = 14，那么A，C，D只能有1或2或3的值，
会大大减少A，C和D的for循环范围。
虽然有用，但它仍然是一个手动任务。
我不能不认为有更好的方法。如果你有一个真正的Python
项目，这不值得你花时间，但如果是一个学生，可能是一个很好的运动来思考你的''这样做。
Norm B
There is a number puzzle which appears in the daily paper.
Because I''m between Python projects, I thought it might be
fun to write a program to solve it....20 minute job, max.
On closer inspection, it became apparent that it''s not a
simple thing to program. How would you approach it?
The puzzle: a 4 x 4 grid. The rows are summed (and given), the
cols are summed (and given), and the two diagonals are summed,
and given. In addition, 4 clues are given, but none of the 4 are in
the same row or col.
Example from today''s paper:...solution time is 8 minutes, 1 second,
so they say.
The set of allowable numbers is 1 thru 9
Rows:
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums:
24, 18, 31, 31
Diag sums:
3 + F + K + P = 24
M + J + 8 + D = 24
The first impulse is to just brute force it with nested for loops,
but the calculator shows the possible combinations are
9^12 = 5,159,780,352, which would take much too long.
Another approach would be to inspect each square and determine
what the range of reasonable numbers would be. For example,
if A + 9 + C + D = 14, then A, C, D can only have a value of 1 or 2 or 3,
which would greatly reduce the for loop range of A, C and D.
While useful, it''s still a manual task.
I can''t help but think there''s a better way. If you have a real Python
project, this isn''t worth your time, but if a student, it might be a good
exercise to think how you''d do it.
Norm B
推荐答案
" engsol" <恩******** @ peak.org>在消息中写道
news：sa ******************************** @ 4ax.com ...
"engsol" <en********@peak.org> wrote in message
news:sa********************************@4ax.com...
日报中有一个数字拼图。
因为我在Python项目之间，我认为编写一个程序可能很有趣要解决它...... 20分钟的工作，最多
仔细观察，很明显，编程不是一件简单的事情。你会如何接近它？
这个难题：4 x 4网格。行被求和（给定），
cols求和（和给定），两个对角线相加，
和给定。另外，给出了4条线索，但是4条线路中没有一条在同一行或列中。
今天的论文中的例子：......解决方案时间是8分钟， 1秒，
所以他们说。
允许数字的集合是1到9
行：
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums ：
24,18,31,31
Diag sums：
3 + F + K + P = 24
M + J + 8 + D = 24
第一个冲动是用嵌套的for循环强制它，
但计算器显示可能的组合是
9 ^ 12 = 5,159,780,352，这将花费太长时间。
There is a number puzzle which appears in the daily paper.
Because I''m between Python projects, I thought it might be
fun to write a program to solve it....20 minute job, max.
On closer inspection, it became apparent that it''s not a
simple thing to program. How would you approach it?
The puzzle: a 4 x 4 grid. The rows are summed (and given), the
cols are summed (and given), and the two diagonals are summed,
and given. In addition, 4 clues are given, but none of the 4 are in
the same row or col.
Example from today''s paper:...solution time is 8 minutes, 1 second,
so they say.
The set of allowable numbers is 1 thru 9
Rows:
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums:
24, 18, 31, 31
Diag sums:
3 + F + K + P = 24
M + J + 8 + D = 24
The first impulse is to just brute force it with nested for loops,
but the calculator shows the possible combinations are
9^12 = 5,159,780,352, which would take much too long.
你所拥有的是11个变量中的10个线性方程组。通常
不足以生成一个独特的解决方案
，但所有
变量必须具有该范围内值的额外约束1..9可能会让你获得一个
独特的解决方案。我建议你使用谷歌来解决
联线性方程式的技巧。
-
我实际上没看过我的hotmail如果你真的想和我联系，你可以用
来代替hotmail。
What you have is a set of 10 linear equations in 11 variables. Normally
that isn''t
enough to generate a unique solution, but the additional constraint that all
variables must have values in the range 1..9 probably will get you to a
unique solution. I suggest you Google for techniques for solving
"simultaneous linear equations".
--
I don''t actually read my hotmail account, but you can replace hotmail with
excite if you really want to reach me.
行：
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31 M + 7 + O + P = 25
总和：
24,18,31,31
Diag sums：
3 + F + K + P = 24
M + J + 8 + D = 24
Rows:
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums:
24, 18, 31, 31
Diag sums:
3 + F + K + P = 24
M + J + 8 + D = 24
这是一个由12个变量和10个方程组成的系统。看起来会有
不止一个解决方案（如果我记得我的8年级代数 - 它的开头是
变得非常模糊）。给定一组适当的线性方程组，我认为numarray和
科学python有非常方便的工具。一本介绍性的线性
代数书可以提供你需要了解的关于这个主题的一切。
-
James Stroud，Ph .D。
加州大学洛杉矶分校基因组学和蛋白质组学研究所
专栏951570
洛杉矶，CA 90095
This is a system of 12 variables and 10 equations. Looks like there will be
more than one solution (if I remember my 8th grade algebra--its beginning to
get very foggy). Given a proper set of linear equations, I think numarray and
scientific python have very convenient tools for this. An introductory linear
algebra book can provide everything you need to know about this topic.
--
James Stroud, Ph.D.
UCLA-DOE Institute for Genomics and Proteomics
Box 951570
Los Angeles, CA 90095
engsol写道：
engsol wrote:
日报中有一个数字拼图。
因为我在Python项目之间，我认为写一个程序解决它可能很有趣...... 20分钟的工作，最多
仔细观察，很明显它不是一个
编程很简单。
不开玩笑 - 这是一个受限制的整数编程问题。那些可以是非常讨厌的。这个很简单，线性只有12
未知数。但是，它们非常快速地变得非常困难。有关这类问题的完整的
优化教科书。
你会如何处理它？<br />
这个难题：a 4 x 4网格。行被求和（给定），
cols求和（和给定），两个对角线相加，
和给定。另外，给出了4条线索，但是4条线路中没有一条在同一行或列中。
今天的论文中的例子：......解决方案时间是8分钟， 1秒，
所以他们说。
允许数字的集合是1到9
行：
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums ：
24,18,31,31
Diag sums：
3 + F + K + P = 24
M + J + 8 + D = 24
第一个冲动是用嵌套的for循环强制它，
但计算器显示可能的组合是
9 ^ 12 = 5,159,780,352，这将花费太长时间。
There is a number puzzle which appears in the daily paper.
Because I''m between Python projects, I thought it might be
fun to write a program to solve it....20 minute job, max.
On closer inspection, it became apparent that it''s not a
simple thing to program.
No kidding--it''s a constrained integer programming problem. Those can
be pretty nasty. This one is pretty simple, being linear with only 12
unknowns. However, they get very difficult very fast. There are whole
optimization textbooks written on this kind of problem.
How would you approach it?
The puzzle: a 4 x 4 grid. The rows are summed (and given), the
cols are summed (and given), and the two diagonals are summed,
and given. In addition, 4 clues are given, but none of the 4 are in
the same row or col.
Example from today''s paper:...solution time is 8 minutes, 1 second,
so they say.
The set of allowable numbers is 1 thru 9
Rows:
3 + B + C + D = 22
E + F + 8 + H = 26
I + J + K + 8 = 31
M + 7 + O + P = 25
Col sums:
24, 18, 31, 31
Diag sums:
3 + F + K + P = 24
M + J + 8 + D = 24
The first impulse is to just brute force it with nested for loops,
but the calculator shows the possible combinations are
9^12 = 5,159,780,352, which would take much too long.
没必要。
看起来有12个未知数和10个方程式，所有方程式
是线性的。任何两个变量都完全决定了其他变量的价值：我们只需要解决线性方程就可以得到它们。
一旦你找到了所有其他变量，检查它们是否都满足
constaint（即，它们都是从1到9的整数）。
在Python中，这很容易与Numeric / numarray;纯粹的Python我不会想要尝试（这就是数字的用途），但这是可能的。
所以我们'已经将问题减少到暴力迫使2个变量，这是
只有81个组合;绝对可行。
-
CARL银行
Not necessary.
It looks like there are 12 unknowns and 10 equations, and all equations
are linear. Any two variables completely determine the values of all
the others: we just need to solve the linear equations to get them.
Once you''ve found all the others, check to see if they all satisfy the
constaint (i.e., they''re all integers from 1 to 9).
In Python, this is easy with Numeric/numarray; pure Python I wouldn''t
want to try (that''s what Numeric is for), but it''s possible.
So we''ve reduced the problem to brute forcing 2 variables, which is
only 81 combinations; definitely doable.
--
CARL BANKS
这篇关于你会如何编程呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
