17

序章

有効な数独グリッドは、1 から 9 までの数字で満たされ、9 の各サブブロック、行または列で複数回出現する数字はありません。この人気のあるパズルに慣れていない場合は、この記事を読んで詳細を確認してください。

チャレンジ

課題は、満杯ではない可能性のある数独グリッドを検証する最短のプログラムを作成することです。

入力は、グリッドを表す、それぞれ 9 文字の 9 行の文字列になります。空のセルは で表されます.。Validグリッドが有効な場合は出力、そうでない場合は output になります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 バイトのソリューションを提出するために作成したばかりの言語を自由に使用できますが、それはカウントされず、おそらく反対票を獲得するでしょう.

4

14 に答える 14

11

ゴルフスクリプト: 56

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

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

2 つの改行は必要ありません。josefx によって保存された 1 文字 :-) ...

于 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

最初の正規表現は、同じ行と列にある重複をチェックします。2 番目の正規表現は、「同じボックス」内の重複を処理します。

\n最初の正規表現の をリテラル改行 (1 文字) に置き換えるか、Perl 5.12 以降[^\n]では\N(3 文字)に置き換えることで、さらに改善できます。

以前の 168 文字のソリューション: 入力は stdin から、出力は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"
于 2010-12-10T10:17:53.003 に答える
4

パール、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 に答える
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 に答える
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 に答える
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 に答える
2

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を返し（複数の番号を含まない場合）、それ以外の場合は再帰を使用して各リストをチェックします。一番下の行は、このリストのリストを作成し、それをに渡しc()、その結果を使用して、出力する適切なプレフィックスを選択します。

私が非常に気に入っていることの1つは、このソリューションがの「ブロック」位置リストの「自己相似性」を利用していることです@b（これは、別のステートメントに含まれないようにするために何度も冗長に再構築されます@b=...）：i番目の左上の位置パズル全体の中のブロックは、i番目の要素に3を掛けることで見つけることができます@b。

もっと広がる：

# 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

ルア、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

Perl：202

私はModernPerlを読んでいて、何かをコーディングしたいと思っていました...（ちなみにかなりクールな本:)

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

カウントは不要な改行を除外しています。これにはPerl5.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

パイソン: 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

ASL: 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 に答える
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 に答える