17

介绍

一个有效的数独网格用数字 1 到 9 填充，在每个 9 行或列的子块中没有任何数字出现超过一次。如果您不熟悉这个流行的谜题，请阅读本文了解更多详情。

挑战

挑战在于编写最短的程序来验证可能未满的数独网格。

输入将是一串 9 行，每行 9 个字符，代表网格。一个空单元格将由 a 表示.。如果网格有效，您的输出应该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

代码高尔夫规则

请以解决此问题的任何语言发布您的最短代码。输入和输出可以通过标准输入和标准输出或您选择的其他文件来处理。

获胜者将是一种语言中最短的解决方案（按字节数计算），并且在发布此问题之前已经存在实现。因此，尽管您可以自由地使用您刚刚编写的语言来提交 0 字节解决方案，但它不会被计算在内，而且您可能会被否决。

4

14 回答 14

11

高尔夫球手：56

n%{zip''+9/.{'.'-..&=}%$0=\}:|2*{3/}%|;**"InvV"3/="alid"
于 2010-12-10T11:07:22.933 回答
9

C: 165 162 161 160 159

int v[1566],x,y=9,c,b;main(){while(y--)for(x=9;x--+1;)if((c
=getchar()*27)>1242)b|=v[x+c]++|v[y+9+c]++|v[x-x%3+y/3+18+c]
++;puts(b?"Invalid":"Valid");return 0;}

不需要这两个换行符。josefx 保存的一个字符 :-) ...

于 2010-12-11T08:02:32.997 回答
6

哈斯克尔：207 230 218 195 172

import List
t=take 3
h=[t,t.drop 3,drop 6]
v[]="V"
v _="Inv"
f s=v[1|v<-[s,transpose s,[g=<<f s|f<-h,g<-h]],g<-map(filter(/='.'))v,g/=nub g]++"alid\n"
main=interact$f.lines
于 2010-12-10T09:29:34.707 回答
5

珀尔：168 128

$_=join'',<>;@a=/.../g;print+(/(\d)([^\n]{0,8}|(.{10})*.{9})\1/s
+map"@a[$_,$_+3,$_+6]"=~/(\d).*\1/,0..2,9..11,18..20)?Inv:V,alid

第一个正则表达式检查同一行和列中的重复项；第二个正则表达式处理“相同框”中的重复项。

通过将第\n一个正则表达式中的[^\n]\N

早些时候，168 字符解决方案：输入来自标准输入，输出到标准错误，因为它使事情变得如此简单。换行符是可选的，不计算在内。

$_=join'',<>;$m=alid.$/;$n=Inv.$m;/(\d)(\N{0,8}|(.{10})*.{9})\1/s&&
die$n;@a=/.../g;for$i(0,8,17){for$j($i..$i+2){
$_=$a[$j].$a[$j+3].$a[$j+6];/(\d).*\1/&&die$n}}die"V$m"
于 2010-12-10T10:17:53.003 回答
4

蟒蛇：230 221 200 185

首先是 len=199 的可读版本：

import sys
r=range(9)
g=[raw_input()for _ in r]
s=[[]for _ in r*3]
for i in r:
 for j in r:
  n=g[i][j]
  for x in i,9+j,18+i/3*3+j/3:
<T>if n in s[x]:sys.exit('Invalid')
<T>if n>'.':s[x]+=n
print'Valid'

由于 SO 不显示制表符，我曾经<T>表示单个制表符。

PS。同样的方法 minEvilized 减少到 185 个字符：

r=range(9)
g=[raw_input()for _ in r]
s=['']*27
for i in r:
 for j in r:
    for x in i,9+j,18+i/3*3+j/3:n=g[i][j];s[x]+=n[:n>'.']
print['V','Inv'][any(len(e)>len(set(e))for e in s)]+'alid'
于 2010-12-10T08:53:20.407 回答
4

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-10T18:05:53.403 回答
3

蟒蛇：159 158

v=[0]*244
for y in range(9):
 for x,c in enumerate(raw_input()):
  if c>".":
<T>for k in x,y+9,x-x%3+y//3+18:v[k*9+int(c)]+=1
print["Inv","V"][max(v)<2]+"alid"

<T> 是单个制表符

于 2010-12-10T21:24:48.810 回答
3

普通 Lisp：266 252

(princ(let((v(make-hash-table))(r "Valid"))(dotimes(y 9)(dotimes(x
10)(let((c(read-char)))(when(>(char-code c)46)(dolist(k(list x(+ 9
y)(+ 18(floor(/ y 3))(- x(mod x 3)))))(when(>(incf(gethash(+(* k
9)(char-code c)-49)v 0))1)(setf r "Invalid")))))))r))
于 2010-12-11T14:57:08.773 回答
2

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 个位置的左上角整个拼图中的块可以通过将第 i 个元素乘以@b3 来找到。

更分散：

# 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')
于 2010-12-10T12:56:37.073 回答
1

珀尔：202

我正在阅读 Modern Perl 并想编写一些东西……（顺便说一句，这本书很酷：）

while(<>){$i++;$j=0;for$s(split//){$j++;$l{$i}{$s}++;$c{$j}{$s}++;
$q{(int(($i+2)/3)-1)*3+int(($j+2)/3)}{$s}++}}
$e=V;for$i(1..9){for(1..9){$e=Inv if$l{$i}{$_}>1or$c{$i}{$_}>1or$q{$i}{$_}>1}}
print $e.alid

计数排除不必要的换行符。这可能需要 Perl 5.12.2。

更具可读性：

#use feature qw(say);
#use JSON;

#$json = JSON->new->allow_nonref;

while(<>)
{
    $i++;
    $j=0;
    for $s (split //)
    {
        $j++;
        $l{$i}{$s}++;
        $c{$j}{$s}++;
        $q{(int(($i+2)/3)-1)*3+int(($j+2)/3)}{$s}++;
    }
}

#say "lines: ", $json->pretty->encode( \%l );
#say "columns: ", $json->pretty->encode( \%c );
#say "squares: ", $json->pretty->encode( \%q );

$e = V;
for $i (1..9)
{
    for (1..9)
    {
        #say "checking {$i}{$_}: " . $l{$i}{$_} . " / " . $c{$i}{$_} . " / " . $q{$i}{$_};
        $e = Inv if $l{$i}{$_} > 1 or $c{$i}{$_} > 1 or $q{$i}{$_} > 1;
    }
}

print $e.alid;
于 2010-12-10T12:57:26.880 回答
1

红宝石 - 176

f=->x{x.any?{|i|(i-[?.]).uniq!}}
a=[*$<].map{|i|i.scan /./}
puts f[a]||f[a.transpose]||f[a.each_slice(3).flat_map{|b|b.transpose.each_slice(3).map &:flatten}]?'Invalid':'Valid'
于 2010-12-10T15:27:33.390 回答
1

Lua，341 字节

虽然我知道 Lua 不是最好的高尔夫语言，但是，考虑到它的大小，我认为它值得发布；）。非打高尔夫球，评论和错误打印版本，以获得额外的乐趣:)

i=io.read("*a"):gsub("\n","")   -- Get input, and strip newlines
a={{},{},{}} -- checking array, 1=row, 2=columns, 3=squares
for k=1,3 do for l=1,9 do a[k][l]={0,0,0,0,0,0,0,0,0}end end -- fillup array with 0's (just to have non-nils)

for k=1,81 do -- loop over all numbers
    n=tonumber(i:sub(k,k):match'%d') -- get current character, check if it's a digit, and convert to a number
    if n then
        r={math.floor((k-1)/9)+1,(k-1)%9+1} -- Get row and column number
        r[3]=math.floor((r[1]-1)/3)+3*math.floor((r[2]-1)/3)+1 -- Get square number
        for l=1,3 do v=a[l][r[l]] -- 1 = row, 2 = column, 3 = square
            if v[n] then -- not yet eliminated in this row/column/square
                v[n]=nil    
            else
                print("Double "..n.." in "..({"row","column","square"}) [l].." "..r[l]) --error reporting, just for the extra credit :)
                q=1 -- Flag indicating invalidity
            end
        end
    end
end
io.write(q and"In"or"","Valid\n")

高尔夫版本，341 字节

f=math.floor p=io.write i=io.read("*a"):gsub("\n","")a={{},{},{}}for k=1,3 do for l=1,9 do a[k][l]={0,0,0,0,0,0,0,0,0}end end for k=1,81 do n=tonumber(i:sub(k,k):match'%d')if n then r={f((k-1)/9)+1,(k-1)%9+1}r[3]=f((r[1]-1)/3)+1+3*f((r[2]-1)/3)for l=1,3 do v=a[l][r[l]]if v[n]then v[n]=nil else q=1 end end end end p(q and"In"or"","Valid\n")
于 2010-12-10T22:02:01.103 回答
1

蟒蛇：140

v=[(k,c) for y in range(9) for x,c in enumerate(raw_input()) for k in x,y+9,(x/3,y/3) if c>'.']
print["V","Inv"][len(v)>len(set(v))]+"alid"
于 2011-01-02T14:17:24.123 回答
1

翔升：108

args1["\n"x2I3*x;{;{:=T(T'{:i~{^0}?})}}
{;{;{{,0:e}:;{0:^},u eq}}/`/=}:-C
dc C@;{:|}C&{"Valid"}{"Invalid"}?P

ASL 是我制作的受 Golfscript 启发的脚本语言。

于 2011-02-05T15:49:21.693 回答