Code Golf: Validate Sudoku Grid

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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