引言
有效的数独网格由数字1到9填充,数字在9的每个子块中只出现一次,行或列。如果您不熟悉这个流行的难题,请阅读this article以了解更多详细信息。
挑战
挑战是编写最短的程序来验证可能不满的数独网格。
输入是一个9行的字符串,每行9个字符,代表网格。空单元格将由.
表示。如果网格有效,则输出应为Valid
,否则输出为Invalid
。
示例
输入
123...789
...456...
456...123
789...456
...123...
564...897
...231...
897...564
...564...
输出
Valid
输入
123456789
987654321
123456789
123456789
987654321
123456789
123456789
987654321
123456789
输出
Invalid
编码高尔夫规则
请以任何语言发布您的最短代码,以解决此问题。输入和输出可以通过stdin和stdout处理,也可以由您选择的其他文件处理。
Winner将是在此问题发布之前已存在实现的语言中最短的解决方案(按字节计数)。因此,虽然你可以自由地使用你刚刚编写的语言来提交一个0字节的解决方案,但它不会算数,而且你可能会得到反对票。
发布于 2010-12-10 19:07:23
Golfscript: 56
n%{zip''+9/.{'.'-..&=}%$0=\}:|2*{3/}%|;**"InvV"3/="alid"
发布于 2010-12-11 02:05:53
Perl,153个字符
@B
包含板的81个元素。
&E
测试@B
的子集是否包含任何重复的数字
主循环验证拼图的每一列、“块”和行
sub E{$V+="@B[@_]"=~/(\d).*\1/}
@B=map/\S/g,<>;
for$d(@b=0..80){
E grep$d==$_%9,@b;
E grep$d==int(($_%9)/3)+3*int$_/27,@b;
E$d*9..$d*9+8}
print$V?Inv:V,alid,$/
发布于 2010-12-10 20:56:37
Perl: 186
输入来自标准输入,输出到标准输出,输入中换行符可选。
@y=map/\S/g,<>;
sub c{(join'',map$y[$_],@$h)=~/(\d).*\1/|c(@_)if$h=pop}
print(('V','Inv')[c map{$x=$_;[$_*9..$_*9+8],[grep$_%9==$x,0..80],[map$_+3*$b[$x],@b=grep$_%9<3,0..20]}0..8],'alid')
(添加换行符是为了“清晰”。)
c()
是一个函数,它根据作为参数传递的位置编号列表检查@y
中的输入。如果所有位置列表都有效(包含的数字不超过一次),则返回0;否则返回1,使用递归检查每个列表。最后一行代码构建这个列表列表,将其传递给c()
,并使用结果选择要输出的正确前缀。
我非常喜欢的一件事是,这个解决方案利用了@b
中“块”位置列表中的“自相似性”(为了避免在单独的语句中有@b=...
,它被冗余地重建了很多次):整个拼图中第i个块的左上角位置可以通过将@b
中的第i个元素乘以3来找到。
更多信息:
# Grab input into an array of individual characters, discarding whitespace
@y = map /\S/g, <>;
# Takes a list of position lists.
# Returns 0 if all position lists are valid, 1 otherwise.
sub c {
# Pop the last list into $h, extract the characters at these positions with
# map, and check the result for multiple occurences of
# any digit using a regex. Note | behaves like || here but is shorter ;)
# If the match fails, try again with the remaining list of position lists.
# Because Perl returns the last expression evaluated, if we are at the
# end of the list, the pop will return undef, and this will be passed back
# which is what we want as it evaluates to false.
(join '', map $y[$_], @$h) =~ /(\d).*\1/ | c(@_) if $h = pop
}
# Make a list of position lists with map and pass it to c().
print(('V','Inv')[c map {
$x=$_; # Save the outer "loop" variable
[$_*9..$_*9+8], # Columns
[grep$_%9==$x,0..80], # Rows
[map$_+3*$b[$x],@b=grep$_%9<3,0..20] # Blocks
} 0..8], # Generates 1 column, row and block each time
'alid')
https://stackoverflow.com/questions/4406970
复制相似问题