当前位置： 文江博客话题详情

Code Golf：验证数独网格

发布于 2024-10-07 03:25:21 字数 879 浏览 6 评论 0原文

简介

有效的数独网格由数字 1 到 9 填充，并且数字在 9、行或列的每个子块中出现的次数不会超过一次。如果您不熟悉这个流行的谜题，请阅读这篇文章了解更多详细信息。

挑战

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

输入将是一个包含 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 或您选择的其他文件进行处理。

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

原文

Introduction

A valid Sudoku grid is filled with numbers 1 to 9, with no number occurring more than once in each sub-block of 9, row or column. Read this article for further details if you're unfamiliar with this popular puzzle.

Challenge

The challenge is to write the shortest program that validates a Sudoku grid that might not be full.

Input will be a string of 9 lines of 9 characters each, representing the grid. An empty cell will be represented by a .. Your output should be Valid if the grid is valid, otherwise output Invalid.

Example

Input

123...789
...456...
456...123
789...456
...123...
564...897
...231...
897...564
...564...

Output

Valid

Input

123456789
987654321
123456789
123456789
987654321
123456789
123456789
987654321
123456789

Output

Invalid

Code Golf Rules

Please post your shortest code in any language that solves this problem. Input and output may be handled via stdin and stdout or by other files of your choice.

Winner will be the shortest solution (by byte count) in a language with an implementation existing prior to the posting of this question. So while you are free to use a language you've just made up in order to submit a 0-byte solution, it won't count, and you'll probably get downvotes.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（14）

星星的軌跡 2024-10-14 03:25:21

高尔夫球脚本：56

n%{zip''+9/.{'.'-..&=}%$0=\}:|2*{3/}%|;**"InvV"3/="alid"

Golfscript: 56

n%{zip''+9/.{'.'-..&=}%$0=\}:|2*{3/}%|;**"InvV"3/="alid"
回复 原文
罗罗贝儿 2024-10-14 03:25:21

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 保存了一个字符:-) ...

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;}

The two newlines are not needed. One char saved by josefx :-) ...

回复 原文
最偏执的依靠 2024-10-14 03:25:21

哈斯克尔： 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

Haskell: 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
回复 原文
怕倦 2024-10-14 03:25:21

Perl: 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 替换为文字换行符（1 个字符），或者使用 >= Perl 5.12，替换 [^\n] ，可以进一步改进与 \N (3 char)

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

$_=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"

Perl: 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

The first regex checks for duplicates that are in the same row and column; the second regex handles duplicates in the "same box".

Further improvement is possible by replacing the \n in the first regex with a literal newline (1 char), or with >= Perl 5.12, replacing [^\n] with \N (3 char)

Earlier, 168 char solution:
Input is from stdin, output is to stderr because it makes things so easy. Linebreaks are optional and not counted.

$_=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"
回复 原文
安稳善良 2024-10-14 03:25:21

Python： 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 不显示制表符，因此我使用了 < code>表示单个制表符。

附言。同样的方法将 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'

Python: 230 221 200 185

First the readable version at 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'

Since SO doesn't display tab characters, I've used <T> to represent a single tab character.

PS. the same approach minEvilized down to 185 chars:

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'
回复 原文
难理解 2024-10-14 03:25:21

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,$/

Perl, 153 char

@B contains the 81 elements of the board.

&E tests whether a subset of @B contains any duplicate digits

main loop validates each column, "block", and row of the puzzle

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,$/
回复 原文
瑾夏年华 2024-10-14 03:25:21

Python：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"

是单个制表符

Python: 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> is a single tab character

回复 原文
活雷疯 2024-10-14 03:25:21

Common 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))

Common 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))
回复 原文
烟雨凡馨 2024-10-14 03:25:21

Perl：186

输入来自 stdin，输出到 stdout，输入中的换行符可选。

@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')

Perl: 186

Input is from stdin, output to stdout, linebreaks in input optional.

@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')

(Linebreaks added for "clarity".)

c() is a function that checks the input in @y against a list of lists of position numbers passed as an argument. It returns 0 if all position lists are valid (contain no number more than once) and 1 otherwise, using recursion to check each list. The bottom line builds this list of lists, passes it to c() and uses the result to select the right prefix to output.

One thing that I quite like is that this solution takes advantage of "self-similarity" in the "block" position list in @b (which is redundantly rebuilt many times to avoid having @b=... in a separate statement): the top-left position of the ith block within the entire puzzle can be found by multiplying the ith element in @b by 3.

More spread out:

# 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')
回复 原文
来世叙缘 2024-10-14 03:25:21

Perl: 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

Count 排除了不必要的换行符。
这可能需要 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;

Perl: 202

I'm reading Modern Perl and felt like coding something... (quite a cool book by the way:)

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

Count is excluding unnecessary newlines.
This may require Perl 5.12.2.

A bit more readable:

#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;
回复 原文
反话 2024-10-14 03:25:21

红宝石 — 176

f=->x{x.any?{|i|(i-[?.]).uniq!}}
a=[*
lt;].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'

Ruby — 176
f=->x{x.any?{|i|(i-[?.]).uniq!}}
a=[*
lt;].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'

 回复 原文 
非要怀念 2024-10-14 03:25:21
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")

Lua, 341 bytes
Although I know that Lua isn't the best golfing language, however, considering it's size, I think it's worth posting it ;).
Non-golfed, commented and error-printing version, for extra fun :)
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")

Golfed version, 341 bytes
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")

 回复 原文 
忆沫 2024-10-14 03:25:21
蟒蛇：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"

Python: 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"

 回复 原文 
榕城若虚 2024-10-14 03:25:21
ASL：108
args1["\n"x2I3*x;{;{:=T(T'{:i~{^0}?})}}
{;{;{{,0:e}:;{0:^},u eq}}/`/=}:-C
dc C@;{:|}C&{"Valid"}{"Invalid"}?P

ASL 是我制作的受 Golfscript 启发的脚本语言。
ASL: 108
args1["\n"x2I3*x;{;{:=T(T'{:i~{^0}?})}}
{;{;{{,0:e}:;{0:^},u eq}}/`/=}:-C
dc C@;{:|}C&{"Valid"}{"Invalid"}?P

ASL is a Golfscript inspired scripting language I made.
 回复 原文 
~没有更多了~
关于作者
 Oo萌小芽oO
暂无简介
0 文章
0 评论
22 人气
 发私信
相关话题
更多 
热门标签
操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多 
推荐作者
1CH1MKgiKxn9p
文章 0 评论 0
ゞ记忆︶ㄣ
文章 0 评论 0
JackDx
文章 0 评论 0
信远
文章 0 评论 0
yaoduoduo1995
文章 0 评论 0
霞映澄塘
文章 0 评论 0
更多 
友情链接
文江博客
       
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
     
    原文