21
\$\begingroup\$

Create a Sudoku solution CHECKER

There are oodles of Sudoku SOLVERS here, but I want you to create a solution CHECKER as small as humanly possible (code-golf).

  • A valid entry will be able to either take a 9x9 array as an argument (passed by reference, serialized on the command line, or however you want to take it) or accept an input file that is nine lines of nine numbers for the final grid. See examples of input below.

  • Valid input should be base-10 numbers (1-9)

  • Missing, empty, extra, non-numeric positions, or positions with numbers outside of 1-9 should be rejected as invalid input by returning a non-zero result, printing an error, or both.

  • Your program needs to test whether each number appears once per column, once per line, and once per 3x3 sub-grid. If it passes, return "0" and if not, return a non-zero result.

  • Use of external resources (websites, etc.) is to be avoided.

  • If your solution is a stand-alone program, exiting with a exit status of, or printing, "0" or non-zero for "Pass" or "Fail", respectively, is ok.

Let the smallest answer win!

Input Examples:

c array:

int input[9][9]={{1,2,3,4,5,6,7,8,9},
                 {4,5,6,7,8,9,1,2,3},
                 {7,8,9,1,2,3,4,5,6},
                 {2,3,1,5,6,4,8,9,7},
                 {5,6,4,8,9,7,2,3,1},
                 {8,9,7,2,3,1,5,6,4},
                 {3,1,2,6,4,5,9,7,8},
                 {6,4,5,9,7,8,3,1,2},
                 {9,7,8,3,1,2,6,4,5}
                };

file:

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

The 9 sub-grids:

+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+
\$\endgroup\$

20 Answers 20

5
\$\begingroup\$

GolfScript, 39 characters

.zip.{3/}%zip{~}%3/{[]*}%++{$10,1>=!},,

It takes an array of arrays as input (see online example) and outputs 0 if it is a valid grid.

Short explanation of the code

.zip         # Copy the input array and transpose it
.{3/}%       # Split each line into 3 blocks
zip{~}%      # Transpose these blocks
3/{[]*}%     # Do the same for the lines themselves and join again
++           # Make one large list of 27 9-element arrays 
             # (9 for rows, 9 for columns, 9 for blocks)
{$10,1>=!},  # From those 27 select the ones which are not a permutation of [1 2 3 ... 9]
             #   $      -> sort
             #   10,1>  -> [1 2 3 ... 9]
             #   =!     -> not equal
,            # Count after filtering
\$\endgroup\$
  • \$\begingroup\$ I like that your code's non-zero output is more meaningful than just 1 or -1 \$\endgroup\$ – David Wilkins Mar 3 '14 at 17:02
  • \$\begingroup\$ I really liked your answer but in the end I elected not to go with a golfscript solution. I really hope you understand \$\endgroup\$ – David Wilkins Mar 10 '14 at 14:45
  • 2
    \$\begingroup\$ @DavidWilkins Actually I don't understand - you made the rules (!) and didn't state anywhere that GolfScript was not allowed. \$\endgroup\$ – Howard Mar 10 '14 at 14:51
  • \$\begingroup\$ Your point is entirely valid...in truth I have nothing to justify not choosing your answer. Well played \$\endgroup\$ – David Wilkins Mar 10 '14 at 14:53
10
\$\begingroup\$

Python, 103

I hate sudoku.

b = [[1,2,3,4,5,6,7,8,9],
     [4,5,6,7,8,9,1,2,3],
     [7,8,9,1,2,3,4,5,6],
     [2,3,1,5,6,4,8,9,7],
     [5,6,4,8,9,7,2,3,1],
     [8,9,7,2,3,1,5,6,4],
     [3,1,2,6,4,5,9,7,8],
     [6,4,5,9,7,8,3,1,2],
     [9,7,8,3,1,2,6,4,5]]

e=enumerate;print 243-len(set((a,t)for(i,r)in e(b)for(j,t)in e(r)for a in e([i,j,i/3*3+j/3]*(0<t<10))))

How it works: each row, column, and block must have each number from 1 to 9. So for each 0 <= i, j < 9, the cell i,j is in block 3*floor(i/3) + floor(j/3). Thus, there are 243 requirements to satisfy. I make each requirement a tuple ((item index,item type number),symbol) where item index is a number between 0 and 8 (inclusive), item type number is 0,1, or 2 to denote row, column or block respectively, and symbol is the entry b[i][j].

Edit: I mistakenly didn't check for valid entries. Now I do.

\$\endgroup\$
  • \$\begingroup\$ Your program should output 0 if the solution passes, not True \$\endgroup\$ – David Wilkins Mar 3 '14 at 17:41
  • \$\begingroup\$ @DavidWilkins what an odd requirement. Fixed. \$\endgroup\$ – boothby Mar 3 '14 at 20:36
  • \$\begingroup\$ You sir get my vote just for the way you started your answer :D \$\endgroup\$ – Teun Pronk Mar 4 '14 at 10:02
9
\$\begingroup\$

APL (46)

{∧/,↑∊∘Z¨(/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9),(↓⍵),↓⍉⍵}

This takes a 9-by-9 matrix. The example one can be entered on TryAPL like so:

     sudoku ← ↑(1 2 3 4 5 6 7 8 9)(4 5 6 7 8 9 1 2 3)(7 8 9 1 2 3 4 5 6)(2 3 1 5 6 4 8 9 7)(5 6 4 8 9 7 2 3 1)(8 9 7 2 3 1 5 6 4)(3 1 2 6 4 5 9 7 8)(6 4 5 9 7 8 3 1 2)(9 7 8 3 1 2 6 4 5)
     {∧/,↑∊∘Z¨(/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9),(↓⍵),↓⍉⍵} sudoku
1

Explanation:

  • ↓⍉⍵: get the columns of ,
  • ↓⍵: get the rows of ,
  • 3/3⌿3 3⍴Z←⍳9: make a 3-by-3 matrix containing the numbers 1 to 9, then triplicate each number in both directions, giving a 9-by-9 matrix with the numbers 1 to 9 indicating each group,
  • Z∘.=: for each number 1 to 9, make a bitmask for the given group,
  • /∘(,⍵)¨: and mask with each, giving the groups of .
  • ∊∘Z¨: for each sub-array, see if it contains the numbers 1 to 9,
  • ∧/,↑: take the logical and of all of these numbers together.
\$\endgroup\$
  • \$\begingroup\$ +1 Nice! But the 3×3 groups can be golfed some more. For example this ↓9 9⍴1 3 2⍉3 3 9⍴⍵ is equivalent to /∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9 but quite shorter. I'm sure there are even shorter formulas. \$\endgroup\$ – Tobia Mar 1 '14 at 15:31
  • \$\begingroup\$ Also, you could concatenate the matrices by 1st dimension and perform a single split at the end: ↓(9 9⍴1 3 2⍉3 3 9⍴⍵)⍪⍵⍪⍉⍵ \$\endgroup\$ – Tobia Mar 1 '14 at 15:42
  • \$\begingroup\$ There's a bug: this code ∊∘Z¨ is testing whether each sub-array (row, column or block) is only made of numbers 1 to 9. It's not testing whether all numbers are represented. You need to do something like Z∘.∊ which tests that every number in Z is contained in every sub-array. \$\endgroup\$ – Tobia Mar 1 '14 at 15:54
  • \$\begingroup\$ And this ∧/,↑ can be shortened to ∧/∊. I'm done, I'm done! ;-) \$\endgroup\$ – Tobia Mar 1 '14 at 15:55
  • \$\begingroup\$ Very compact, but you missed one critical point that I can see right off: If it passes, return "0" and if not, return a non-zero result. \$\endgroup\$ – David Wilkins Mar 3 '14 at 16:40
5
\$\begingroup\$

Java/C# - 183/180 181/178 173/170 bytes

boolean s(int[][]a){int x=0,y,j;int[]u=new int[27];for(;x<(y=9);x++)while(y>0){j=1<<a[x][--y];u[x]|=j;u[y+9]|=j;u[x/3+y/3*3+18]|=j;}for(x=0;x<27;)y+=u[x++];return y==27603;}

(Change boolean to bool for C#)

Formatted:

boolean s(int[][] a){
    int x=0, y, j;
    int[] u=new int[27];
    for(;x<(y=9);x++)
        while(y>0){
            j=1<<a[x][--y];
            u[x]|=j;
            u[y+9]|=j;
            u[x/3+y/3*3+18]|=j;
        }

    for(x=0;x<27;)
        y+=u[x++];

    return y==27603;
}

The method creates an array u with 27 bitmasks, representing the digits found in the nine rows, columns and squares.

It then iterates over all cells, performing the operation 1 << a[x][y] to create a bitmask representing the digit and ORs its column, row and square bitmask with it.

It then iterates over all 27 bitmasks, ensuring that they all add up to 27594 (1022*9, 1022 being the bitmask for all digits 1-9 being present). (Note that y ends up as 27603 due to it already containing 9 following the double loop.)

Edit: Accidentally left in a %3 that's no longer necessary.

Edit 2: Inspired by Bryce Wagner's comment, the code has been compressed a bit more.

\$\endgroup\$
  • \$\begingroup\$ Almost the same algorithm in C# 149 chars (but only if Linq is allowed): bool s(int[]a){int x=0,y,j;var u=new int[27];while(x++<(y=9))while(y>0){j=1<<a[x+9*--y];u[x]|=j;u[y+9]|=j;u[x/3+y/3*3+18]|=j;}return u.Sum()==27594;} \$\endgroup\$ – Bryce Wagner Mar 2 '14 at 4:56
  • \$\begingroup\$ @BryceWagner Linq would indeed be useful. However, my solution is for Java with C# being an afterthought (not even mentioned in the original post) and thus lower priority. I also used one-dimensional arrays for compactness at the start before deciding against it (as the examples use two-dimensional ones). Nevertheless, your code gave me a few ideas for how a few more bytes could be shaved off. :) \$\endgroup\$ – Smallhacker Mar 2 '14 at 13:45
3
\$\begingroup\$

python = 196

Not the most golfed, but the idea is there. Sets are pretty useful.

Board:

b = [[1,2,3,4,5,6,7,8,9],
     [4,5,6,7,8,9,1,2,3],
     [7,8,9,1,2,3,4,5,6],
     [2,3,1,5,6,4,8,9,7],
     [5,6,4,8,9,7,2,3,1],
     [8,9,7,2,3,1,5,6,4],
     [3,1,2,6,4,5,9,7,8],
     [6,4,5,9,7,8,3,1,2],
     [9,7,8,3,1,2,6,4,5]]

Program:

n={1,2,3,4,5,6,7,8,9};z=0
for r in b:
 if set(r)!=n:z=1
for i in zip(*b):
 if set(i)!=n:z=1
for i in (0,3,6):
 for j in (0,3,6):
  k=j+3
  if set(b[i][j:k]+b[i+1][j:k]+b[i+2][j:k])!=n:z=1
print(z)
\$\endgroup\$
  • \$\begingroup\$ s/{1,2,3,4,5,6,7,8,9}/set(range(1,10))/ saves 3 characters. \$\endgroup\$ – MatrixFrog Mar 1 '14 at 6:56
  • \$\begingroup\$ In Python 3.5 you can use n={*range(1,10)}, but that's newer than the challenge. Instead use set(range(1,10)) as MatrixFrog said. \$\endgroup\$ – mbomb007 Sep 19 '16 at 19:45
3
\$\begingroup\$

Java - 385 306 328 260 characters

Edit: I foolishly misread the instructions that the answer had to be a complete program. Since it can be just a valid function, I've rewritten and minimized to be a function, and rewritten my solution introduction with that in mind.

So, as a challenge to myself I thought I'd try to make the smallest Java solution checker.

To achieve this I assume that the sudoku puzzle will be passed in as a java multidimensional array, like so:

s(new int[][] {
    {1,2,3,4,5,6,7,8,9},
    {4,5,6,7,8,9,1,2,3},
    {7,8,9,1,2,3,4,5,6},
    {2,3,1,5,6,4,8,9,7},
    {5,6,4,8,9,7,2,3,1},
    {8,9,7,2,3,1,5,6,4},
    {3,1,2,6,4,5,9,7,8},
    {6,4,5,9,7,8,3,1,2},
    {9,7,8,3,1,2,6,4,5}});

Then, we have the actual solver, which returns "0" if valid solution, "1" if not.

Fully golfed:

int s(int[][] s){int i=0,j,k=1;long[] f=new long[9];long r=0L,c=r,g=r,z=45L,q=r;for(f[0]=1L;k<9;){f[k]=f[k-1]*49;z+=f[k++]*45;}for(;i<9;i++){for(j=0;j<9;){k=s[i][j];r+=k*f[i];c+=k*f[j];g+=k*f[j++/3+3*(i/3)];q+=5*f[k-1];}}return (r==z&&c==z&&g==z&&q==z)?0:1;}

Readable:

    int s(int[][] s) {
        int i=0,j,k=1;
        long[] f=new long[9]; 
        long r=0L,c=r,g=r,z=45L,q=r;
        for(f[0]=1L;k<9;){f[k]=f[k-1]*49;z+=f[k++]*45;}
        for(;i<9;i++) {
            for (j=0;j<9;) {
                k=s[i][j];
                r+=k*f[i];
                c+=k*f[j];
                g+=k*f[j++/3+3*(i/3)];
                q+=5*f[k-1];
            }
        }
        return (r==z&&c==z&&g==z&&q==z)?0:1;
    }

So how does this work? I basically just create my own number base with sufficient resolution in each digit that I only have to do three numeric comparisons after passing through the puzzle once to know if it's valid. I chose base 49 for this problem, but any base larger than 45 would be sufficient.

A (hopefully) clear example: imagine that every "row" in the sudoku puzzle is a single digit in a base-49 number. We'll represent each digit in the base-49 number as a base-10 number in a vector for simplicity. So, if all rows are "correct" we expect the following base-49 number (as a base-10 vector):

(45,45,45,45,45,45,45,45,45)

or converted to a single base-10 number: 1526637748041045

Follow similar logic for all the columns, and same for the "sub-grids". Any value encountered in the final analysis that doesn't equal this "ideal number" means the puzzle solution is invalid.

Edit to solve all-5s vulnerability and other related issues: I add a fourth base-49 number, based on the idea that there should be 9 of each number in every puzzle. So, I add 5 to each digit in the base-49 number for each occurrence of the base-10 number that represents the digit's index. An example, if there are 10 9's and 9 8's, 9 7's, 8 6's, and 9 of all others, you'd get a base-49 number (as a base-10 vector of size 10 to deal with overflow):

(1, 1, 45, 45, 40, 45, 45, 45, 45, 45)

Which will fail when compared against our "ideal" base-49 number.

My solution takes advantage of this mathematical solution, to avoid as much as possible looping and comparison. I simply use a long value to store each base-49 number as a base-10 number and use a lookup array to get the "factors" for each base-49 digit during column/row/subgrid check value computation.

As Java isn't designed to be concise, being careful in the mathematical construction was the only way I figured I could construct a concise checker.

Let me know what you think.

\$\endgroup\$
  • 1
    \$\begingroup\$ Actually, this suffers from the same vulnerability mentioned by @steve-verrill -- all 5's, or any set of numbers that sums to 45, will "trick" the solver. I'm going to revise. I have an idea how to beat that. \$\endgroup\$ – ProgrammerDan Mar 1 '14 at 4:54
  • \$\begingroup\$ I've addressed this vulnerability in my latest update. Now that case is addressed, and all others of its type. Basically, it was a serious oversight not to deal with "counts" of each type of base-10 digit. I now perform that check directly, but using the same mathematical approach (base-49 number). \$\endgroup\$ – ProgrammerDan Mar 1 '14 at 5:17
  • \$\begingroup\$ Dan, thanks for the acknowlegement. I saw it and wondered why I wasn't notified, but I see you put a dash in my name. This seems to have confused the system. Simply omit the space. I will consider changing the way my name is displayed. \$\endgroup\$ – Level River St Mar 1 '14 at 5:48
  • \$\begingroup\$ Ahha, that explains it. Thanks @steveverrill -- I'm still getting accustomed to the stackexchange way of doing things. That said, your concise exploit of the sum-45 principle was brilliantly stated. Made my solution longer to overcome it, but that's life! \$\endgroup\$ – ProgrammerDan Mar 1 '14 at 6:07
3
\$\begingroup\$

R 145

function(x)colSums(do.call(rbind,lapply(list(R<-row(b<-matrix(1,9,9)),C<-col(b),(R-1)%/%3+1+3*(C-1)%/%3),sapply,`==`,1:9))%*%c(2^(x-1))==511)==27

The de-golfed code (more or less) can be found here https://stackoverflow.com/a/21691541/1201032.

\$\endgroup\$
  • \$\begingroup\$ can you provide a working example on a site like r-fiddle? r-fiddle.org/# \$\endgroup\$ – David Wilkins Mar 7 '14 at 15:55
3
\$\begingroup\$

Haskell (Lambdabot), 65 bytes

k x=and$(all$([1..9]==).sort)<$>[x,transpose x,join$chunksOf 3 x]
\$\endgroup\$
2
\$\begingroup\$

Perl, 193 bytes

for(@x=1..9){$i=$_-1;@y=();push@y,$a[$i][$_-1]for@x;@y=sort@y;$r+=@y~~@x;@y=();push@y,$a[3*int($i/3)+$_/3][3*($i%3)+$_%3]for 0..8;@y=sort@y;$r+=@y~~@x}for(@a){@y=sort@$_;$r+=@y~~@x}exit($r!=27)

Input is expected in array form:

@a=(
    [1,2,3,4,5,6,7,8,9],
    [4,5,6,7,8,9,1,2,3],
    [7,8,9,1,2,3,4,5,6],
    [2,3,1,5,6,4,8,9,7],
    [5,6,4,8,9,7,2,3,1],
    [8,9,7,2,3,1,5,6,4],
    [3,1,2,6,4,5,9,7,8],
    [6,4,5,9,7,8,3,1,2],
    [9,7,8,3,1,2,6,4,5]
);

Exit code is 0, if @a is a solution, otherwise 1 is returned.

Ungolfed version:

@x = (1..9);
for (@x) {
    $i = $_ - 1;
    # columns
    @y = ();
    for (@x) {
        push @y, $a[$i][$_-1];
    }
    @y = sort @y;
    $r += @y ~~ @x;
    # sub arrays
    @y = ();
    for (0..8) {
        push @y, $a[ 3 * int($i / 3) + $_ / 3 ][ 3 * ($i % 3) + $_ % 3 ];
    }
    @y = sort @y;
    $r += @y ~~ @x
}
# rows
for (@a) {
    @y = sort @$_;
    $r += @y ~~ @x
}
exit ($r != 27);

Each of the 9 rows, 9 columns and 9 sub arrays are put into a sorted array and checked, whether it matches the array (1..9). The number $r is incremented for each successful match that must sum up to 27 for a valid solution.

\$\endgroup\$
2
\$\begingroup\$

J 52 54

-.*/,(9=#)@~.@,"2(0 3 16 A.i.4)&|:(4#3)($,)".;._2]0 :0

Takes it's argument pasted on the command line, ended with a ) as:

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5
)

Returns 1 if passed, 0 if not.

Internally, it converts the 9x9 grid to a 3x3x3x3 grid, and does some permutations on the axes to get the wanted unit (rows, lines and boxes) in the last 2 dimensions.

After doing that, it is checked that each unit has has 9 unique values.

Probably far from perfect, but beats the majority already ;-)

\$\endgroup\$
  • \$\begingroup\$ At first glance, you've been caught by the same requirement as some of the others....Your returns should be reversed...0 for pass, non-zero for fail \$\endgroup\$ – David Wilkins Mar 5 '14 at 14:52
  • \$\begingroup\$ 0 for pass is idiotic. There is a reason Boole chose 1 for true and 0 for false. But you are right. Adds 2 characters. \$\endgroup\$ – jpjacobs Mar 5 '14 at 15:55
  • \$\begingroup\$ Think of it as an exit status, not a boolean value \$\endgroup\$ – David Wilkins Mar 5 '14 at 15:58
  • \$\begingroup\$ I'm choosing your answer because it works. You followed the rules and your program is very short. Thanks! \$\endgroup\$ – David Wilkins Mar 10 '14 at 14:44
  • \$\begingroup\$ Well I fibbed...In truth I can't justify not choosing the Golfscript answer that is shorter than yours...But kudos for 2nd place \$\endgroup\$ – David Wilkins Mar 10 '14 at 14:54
2
\$\begingroup\$

Mathematica, 84 79 chars

f=Tr[Norm[Sort@#-Range@9]&/@Join[#,Thread@#,Flatten/@Join@@#~Partition~{3,3}]]&

Examples:

f[{{1,2,3,4,5,6,7,8,9},
   {4,5,6,7,8,9,1,2,3},
   {7,8,9,1,2,3,4,5,6},
   {2,3,1,5,6,4,8,9,7},
   {5,6,4,8,9,7,2,3,1},
   {8,9,7,2,3,1,5,6,4},
   {3,1,2,6,4,5,9,7,8},
   {6,4,5,9,7,8,3,1,2},
   {9,7,8,3,1,2,6,4,5}}]

0

f[{{2,1,3,4,5,6,7,8,9},
   {4,5,6,7,8,9,1,2,3},
   {7,8,9,1,2,3,4,5,6},
   {2,3,1,5,6,4,8,9,7},
   {5,6,4,8,9,7,2,3,1},
   {8,9,7,2,3,1,5,6,4},
   {3,1,2,6,4,5,9,7,8},
   {6,4,5,9,7,8,3,1,2},
   {9,7,8,3,1,2,6,4,5}}]

2

f[{{0,2,3,4,5,6,7,8,9},
   {4,5,6,7,8,9,1,2,3},
   {7,8,9,1,2,3,4,5,6},
   {2,3,1,5,6,4,8,9,7},
   {5,6,4,8,9,7,2,3,1},
   {8,9,7,2,3,1,5,6,4},
   {3,1,2,6,4,5,9,7,8},
   {6,4,5,9,7,8,3,1,2},
   {9,7,8,3,1,2,6,4,5}}]

3

\$\endgroup\$
  • \$\begingroup\$ Your third output example: Is 3 always indicative of invalid input, or is it sometimes a response to a failed solution? \$\endgroup\$ – David Wilkins Mar 7 '14 at 12:49
2
\$\begingroup\$

Javascript ES6, 150 chars

Takes input as a 81-char string without any delimeters.

s=>s.match("^(?=(#.{0,8}#.{9})+$)(?=(#(.{9}){0,8}#.){9})((#.?.?(.{9}){0,2}#...){3}.{18})+$".replace(/#(.*?)#/g,"123456789".replace(/./g,"(?=$$1$&)")))

Function returns null as negative answer and an array with original string in first element as a positive one. Can change to bool by adding !! to the function begining.

Test (see related challenge for more detais):

f=s=>s.match("^(?=(#.{0,8}#.{9})+$)(?=(#(.{9}){0,8}#.){9})((#.?.?(.{9}){0,2}#...){3}.{18})+$".replace(/#(.*?)#/g,"123456789".replace(/./g,"(?=$$1$&)")))
;`123456789456789123789123456231564897564897231897231564312645978645978312978312645
725893461841657392396142758473516829168429537952378146234761985687935214519284673
395412678824376591671589243156928437249735186738641925983164752412857369567293814
679543182158926473432817659567381294914265738283479561345792816896154327721638945
867539142324167859159482736275398614936241587481756923592873461743615298618924375
954217683861453729372968145516832497249675318783149256437581962695324871128796534
271459386435168927986273541518734269769821435342596178194387652657942813823615794
237541896186927345495386721743269158569178432812435679378652914924813567651794283
168279435459863271273415986821354769734692518596781342615947823387526194942138657
863459712415273869279168354526387941947615238138942576781596423354821697692734185
768593142423176859951428736184765923572389614639214587816942375295837461347651298`
.split`
`.every(f)
&&
`519284673725893461841657392396142758473516829168429537952378146234761985687935214
839541267182437659367158924715692843624973518573864192298316475941285736456729381
679543182158926473432817659567381294914256738283479561345792816896154327721638945
867539142324167859159482736275398684936241517481756923592873461743615298618924375
754219683861453729372968145516832497249675318983147256437581962695324871128796534
271459386435168927986273541518734269769828435342596178194387652657942813823615794
237541896186927345378652914743269158569178432812435679495386721924813567651794283
168759432459613278273165984821594763734982516596821347615437829387246195942378651
869887283619214453457338664548525781275424668379969727517385163319223917621449519
894158578962859187461322315913849812241742157275462973384219294849882291119423759
123456789456789123564897231231564897789123456897231564312645978645978312978312645
145278369256389147364197258478512693589623471697431582712845936823956714931764825`
.split`
`.every(s => !f(s))
\$\endgroup\$
  • \$\begingroup\$ That's one ridiculous regex... Amazing work. \$\endgroup\$ – ETHproductions Dec 15 '16 at 16:53
2
\$\begingroup\$

R, 63 50 bytes

Assumes the input m is a 9x9 matrix of numbers.

all(apply(m,1,match,x=1:9),apply(m,2,match,x=1:9))

I was right that further golfing was possible.

Explanation:

    apply(m,1,match,x=1:9),

Take m, and for each row, apply the match function. We specify a further argument x=1:9 to be passed to match. x is the default first position argument, and therefore each row is placed in the second argument position, which is table. The function match looks for instances of x in table. In this case, then, it's looking for 1:9 (the numbers 1 through 9) in each row. For each of 1:9, it will return TRUE (or FALSE) if that number is found (or not).

So, this yields a series of 81 boolean values.

                           apply(m,2,match,x=1:9)

Repeat the above for each column of the input.

all(                                             )

Finally, all checks if every element of the list of booleans is TRUE. This will be the case if and only if the solution is correct (i.e. each number 1:9 is present only once in each column and each row).

Old approach:

for(i in 1:2)F=F+apply(m,i,function(x)sort(x)==1:9);sum(F)==162

It takes each row, sorts it, and then compares it to [1, 2, ... 9]. A correct row should match exactly. Then it does the same for each column. In total, we should have 162 exact matches, which is what the final portion checks for. There is likely some scope for further golfing here...

\$\endgroup\$
  • \$\begingroup\$ It looks like you are checking for columns and rows, but not for boxes... \$\endgroup\$ – JayCe May 27 '18 at 0:50
1
\$\begingroup\$

Haskell - 175

import Data.List
c=concat
m=map
q=[1..9]
w=length.c.m (\x->(x\\q)++(q\\x))
b x=c.m(take 3.drop(3*mod x 3)).take 3.drop(3*div x 3)
v i=sum$m(w)[i,transpose i,[b x i|x<-[0..8]]]

The function v is the one to call. It works by getting the difference of each rows, column and block against the list [1..9] and summing up the lengths of those difference lists.

Demo using the example Sudoku:

*Main> :l so-22443.hs 
[1 of 1] Compiling Main             ( so-22443.hs, interpreted )
Ok, modules loaded: Main.
*Main> v [[1,2,3,4,5,6,7,8,9],[4,5,6,7,8,9,1,2,3],[7,8,9,1,2,3,4,5,6],[2,3,1,5,6,4,8,9,7],[5,6,4,8,9,7,2,3,1],[8,9,7,2,3,1,5,6,4],[3,1,2,6,4,5,9,7,8],[6,4,5,9,7,8,3,1,2],[9,7,8,3,1,2,6,4,5]]
0
\$\endgroup\$
1
\$\begingroup\$

Javascript - 149 Characters

r=[];c=[];g=[];for(i=9;i;)r[o=--i]=c[i]=g[i]=36;for(x in a)for(y in z=a[x]){r[v=z[y]-1]-=y;c[v]-=x;g[v]-=3*(x/3|0)+y/3|0}for(i in r)o|=r[i]|c[i]|g[i]

Expects an array a to exist and creates a variable o for output which is 0 on success and non-zero otherwise.

Works by checking that the sum of the position at which each value occurs for each row, column and 3*3 grid equals 36 (0+1+2+3+4+5+6+7+8).

Testing

a=[
    [1,2,3, 4,5,6, 7,8,9],
    [4,5,6, 7,8,9, 1,2,3],
    [7,8,9, 1,2,3, 4,5,6],

    [2,3,1, 5,6,4, 8,9,7],
    [5,6,4, 8,9,7, 2,3,1],
    [8,9,7, 2,3,1, 5,6,4],

    [3,1,2, 6,4,5, 9,7,8],
    [6,4,5, 9,7,8, 3,1,2],
    [9,7,8, 3,1,2, 6,4,5]
  ];

Gives 'o=0'

a=[
    [1,2,3, 4,5,6, 7,8,9],
    [4,5,6, 7,8,9, 1,2,3],
    [7,8,9, 1,2,3, 4,5,6],

    [2,3,1, 5,6,4, 8,9,7],
    [5,6,4, 8,9,7, 2,3,1],
    [8,9,7, 2,3,1, 5,6,4],

    [3,1,2, 6,4,5, 9,7,8],
    [6,4,5, 9,7,8, 3,1,2],
    [9,7,8, 3,1,2, 6,5,4]
  ];

(Last 2 digits swapped)

Gives o=-1

a=[
    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5],

    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5],

    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5],
    [5,5,5, 5,5,5, 5,5,5]
  ];

Gives o=-284

\$\endgroup\$
1
\$\begingroup\$

Haskell, 121 130 127 bytes (87 Lambdabot)

import Data.List
import Data.List.Split
c=concat
t=transpose
k=chunksOf
p x=all(==[1..9])$(sort<$>)=<<[x,t x,k 9.c.c.t$k 3<$>x]

uses:

-- k 9.c.c.t$k 3<$> x = chunksOf 9 $ concat $ concat $ transpose $ map chunksOf 3 x

let ts = k 9$[10*a+b|a<-[1..9],b<-[1..9]] --yep, this is ugly
in k 9.c.c.t$k 3<$>ts
-- prints:
--[[11,12,13,21,22,23,31,32,33],[41,42,43,51,52,53,61,62,63],[71,72,73,81,82,83,91,92,93],[14,15,16,24,25,26,34,35,36],[44,45,46,54,55,56,64,65,66],[74,75,76,84,85,86,94,95,96],[17,18,19,27,28,29,37,38,39],[47,48,49,57,58,59,67,68,69],[77,78,79,87,88,89,97,98,99]]

Lambdabot loads Data.List and Data.List.Split by default (I don't think BlackCap's solution checks the boxes).

Ideas for improvement welcome

//Edit: I messed up :)
//Edit: 3 bytes saved by BlackCap

\$\endgroup\$
  • \$\begingroup\$ You're right, I failed to notice that checking the rows and columns aren't enough.. \$\endgroup\$ – BlackCap Sep 19 '16 at 18:00
  • \$\begingroup\$ well, I messed up as well :) \$\endgroup\$ – michi7x7 Sep 19 '16 at 18:07
  • 1
    \$\begingroup\$ You can replace (map sort) with (sort<$>) \$\endgroup\$ – BlackCap Sep 19 '16 at 18:15
  • 1
    \$\begingroup\$ And .c$(sort<$>)<$> with $(sort<$>)=<< \$\endgroup\$ – BlackCap Sep 19 '16 at 18:18
  • \$\begingroup\$ oh my, should have remembered those 2 \$\endgroup\$ – michi7x7 Sep 19 '16 at 18:22
1
\$\begingroup\$

05AB1E, 36 bytes |NoN-Competing|

|©vy3ô})3ôøvyJvyê}}®øvyê}®vyê})êžh¦Q

Try it online!

1 is true, anything else is false.

\$\endgroup\$
0
\$\begingroup\$

Clojure, 151 bytes

Quite long, but others seem to be as well. Also annoying that union of sets requires a require, so I used a concat of vectors instead.

Iterates over each row and column and if the value is between 1 and 9 it emits three vectors, one for row, col and 3x3 cell. Returns 0 on success and nil otherwise, with two extra characters could return 1 on fail. Handles numbers outside of 1 - 9 by returning nil but will crash on other anomalies such as non-integer values. Quotients are 0 - 2 so it is safe to use values 8 and 9 to differentiate cell values from rows and columns.

(fn[s](if(= 243(count(set(apply concat(for[i(range 9)j(range 9)](let[v(nth(nth s i)j)q #(quot % 3)](if(<= 1 v 9)[[8 v i][9 v j][(q i)(q j)v]])))))))0))

Input is a nested vector of vectors (so that nth works):

(def sudoku [[1 2 3 4 5 6 7 8 9]
             [4 5 6 7 8 9 1 2 3] 
             [7 8 9 1 2 3 4 5 6] 
             [2 3 1 5 6 4 8 9 7] 
             [5 6 4 8 9 7 2 3 1] 
             [8 9 7 2 3 1 5 6 4] 
             [3 1 2 6 4 5 9 7 8] 
             [6 4 5 9 7 8 3 1 2] 
             [9 7 8 3 1 2 6 4 5]])

Ungolfed:

(defn f [s]
  (->> (for [i (range 9) j (range 9)]
         (let [v (-> s (nth i) (nth j)) q #(quot % 3)]
           (if (<= 1 v 9)
             [[:row v i] [:col v j] [:cell [(q i) (q j)] v]])))
    (apply concat)
    set
    count
    (#(if (= 243 %) :pass :fail))))
\$\endgroup\$
0
\$\begingroup\$

PHP, 196 190 bytes

while($i<9){for($b=$c=$k=$y="";$y++<9;)$b.=($a=$argv)[$y][$i];for(;$k<3;)$c.=substr($a[++$k+$i-$i%3],$i%3*3,3);if(($u=count_chars)($a[++$i],3)<($d=123456789)|$u($b,3)<$d|$u($c,3)<$d)die(1);}

Program takes 9 separate command line arguments (one string of digits for each line of the grid);
exits with 1 (error) for invalid, 0 (ok) for valid.

Run with php -nr '<code>' <row1> <row2> ....

breakdown

while($i<9)
{
    for($b=$c=$k=$y="";$y++<9;)$b.=($a=$argv)[$y][$i];  // column to string
    for(;$k++<3;)$c.=substr($a[$i-$i%3+$k],$i%3*3,3);   // sub-grid to string
    if(($u=count_chars)($a[++$i],3)<($d=123456789)      // check row
        |$u($b,3)<$d                                    // check column
        |$u($c,3)<$d                                    // check sub-grid
    )die(1);                                            // test failed: exit with 1
}

explanation

count_chars counts characters in a string and usually creates an array with ascii codes as keys and character count as values; but with 3 as mode parameter, it creates a sorted string from the characters; and that can easily be compared to the number with the wanted digits.

The comparison does not only check for duplicates, but also includes the check for invalid characters. And it only requires <, not !=, because this is numeric comparison: PHP will interpret the string as a number as far as it can. 123e56789, 0x3456789 or similar cannot appear, because the characters are sorted; and any pure integer with a digit missing is smaller than 123456789 ... and .23456789 too, of course.

$a=$argv saves one byte, $d=123456789 saves nine and $u=count_chars saves 13.

\$\endgroup\$
-1
\$\begingroup\$

C# - 306 298 288 characters

The following Console program was used to call the checking function;

static void Main(string[] args)
    {
        int[,] i={{1,2,3,4,5,6,7,8,9},
             {4,5,6,7,8,9,1,2,3},
             {7,8,9,1,2,3,4,5,6},
             {2,3,1,5,6,4,8,9,7},
             {5,6,4,8,9,7,2,3,1},
             {8,9,7,2,3,1,5,6,4},
             {3,1,2,6,4,5,9,7,8},
             {6,4,5,9,7,8,3,1,2},
             {9,7,8,3,1,2,6,4,5}
            };

            Console.Write(P(i).ToString());
    }

All this does is initialise the array and pass it into the checking function P.

The checking function is as below (in Golfed form);

private static int P(int[,]i){int[]r=new int[9],c=new int[9],g=new int[9];for(int p=0;p<9;p++){r[p]=45;c[p]=45;g[p]=45;}for(int y=0;y<9;y++){for(int x=0;x<9;x++){r[y]-=i[x,y];c[x]-=i[x,y];int k=(x/3)+((y/3)*3);g[k]-=i[x,y];}}for(int p=0;p<9;p++)if(r[p]>0|c[p]>0|g[p]>0)return 1;return 0;}

Or in fully laid out form;

    private static int P(int[,] i)
    {
        int[] r = new int[9],c = new int[9],g = new int[9];
        for (int p = 0; p < 9; p++)
        {
            r[p] = 45;
            c[p] = 45;
            g[p] = 45;
        }

        for (int y = 0; y < 9; y++)
        {
            for (int x = 0; x < 9; x++)
            {
                r[y] -= i[x, y];

                c[x] -= i[x, y];

                int k = (x / 3) + ((y / 3) * 3);
                g[k] -= i[x, y];
            }
        }

        for (int p = 0; p < 9; p++)
            if (r[p] > 0 | c[p] > 0 | g[p] > 0) return 1;

        return 0;
    }

This uses the idea that all columns, rows and sub-grids should add up to 45. It works through the input array and subtracts the value of each position from it's row, column and sub-grid. Once complete it then checks that none of the rows, columns or sub-grids still have a value.

As requested returns a 0 if the array is a valid Sudoku solution and non-zero (1) where it's not.

\$\endgroup\$
  • \$\begingroup\$ I think you can save some chars by using private static int P(int[,]i){int[]r=new int[9],c=new int[9],g=new int[9]; instead. (Note the removal of the space after the close square bracket ].) Also, I'm not sure but I think you may get rid of the private static. \$\endgroup\$ – ace Feb 28 '14 at 23:24
  • \$\begingroup\$ Also, for the last part, in C we can remove some braces i.e. for(int p=0;p<9;p++)if(r[p]>0|c[p]>0|g[p]>0)return 1;return 0;}, not sure if it works in C# though. (I don't actually know C#) \$\endgroup\$ – ace Feb 28 '14 at 23:27
  • \$\begingroup\$ @ace - I've made several enhancements based on your suggestions. Now down to 298 chars. \$\endgroup\$ – Will Mar 1 '14 at 0:42
  • \$\begingroup\$ Trimmed another 10 chars based on comments from @ace. \$\endgroup\$ – Will Mar 1 '14 at 0:48
  • 1
    \$\begingroup\$ What happens with an array full of number 5's? All rows, columns and squares add up to 45. \$\endgroup\$ – Level River St Mar 1 '14 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.