# Tag Info

## Hot answers tagged sudoku

41

Ruby regex, 71 78 73 bytes ^(?!.*(?=(.))(.{9}+|(.(?!.{9}*$))+|(?>.(?!.{3}*$)|(.(?!.{27}*$)){7})+)\1) I don't really know Ruby but apparently it doesn't complain about cascaded quantifiers. Try it here. .NET regex, 79 78 75 or 77 bytes Because Martin thinks this is possible... But I guess he will just incorporate these changes too. ^(?!(.)+((.{9})+|(?>(... 34 PCRE, 117 119 130 133 147 bytes ^(?!(.{27})*(...){0,2}(.{9})?.?.?(.).?.?(?=(?2)*$).{6,8}(?3)?\4.{0,17}(?1)*$|.*(.)(.{8}(?3)*|((?!(?3)*$)(|.(?7))))\5) Should also work in Python, Java, etc. flavors. Now with recursion! And the "recursion" feature used non-recursively for "subroutines", which I totally forgot about until I had to use actual recursion.

26

Haskell, 107 points import Control.Monad import Data.List type Elem = Char type Board = [[Elem]] type Constraints = ([Elem],[Elem],[Elem]) digits :: [Elem] digits = "123456789" noCons :: Constraints noCons = ([],[],[]) disjointCons :: Constraints disjointCons = ("123","456","789") -- constraints from a single block - ...

20

Python + Z3, 999899898789789787876789658767666545355432471632124566352413452143214125313214321, optimal Runs in about half an hour, producing 1 3 4 8 9 7 6 2 5 2 9 7 1 5 6 8 3 4 5 6 8 4 2 3 7 9 1 4 7 6 2 1 5 9 8 3 8 5 1 6 3 9 2 4 7 9 2 3 7 8 4 1 5 6 3 8 5 9 6 1 4 7 2 6 4 9 5 7 2 3 1 8 7 1 2 3 4 8 5 6 9 81 79 78 14 15 16 54 57 56 80 12 13 77 52 53 17 55 58 ...

15

.NET regex, 8339 bytes Yes, I know my solution is very naive, since Martin told me he did it in like 130 bytes. In fact, the URL to try it online is so long that I couldn't find a URL shortener that would accept it. (code removed, since it's so long nobody will read it here, and it made the post take forever to load. Just use the "Try it online" ...

14

.NET regex, 121 bytes ^(?!(.{27})*(.{9})?(...){0,2}.?.?(.).?.?(?=(...)*$)(.{9})?.{6,8}\4.{0,17}(.{27})*$|.*(?=(.))((.{9})+|(.(?!(.{9})*$))+)\8) Explanation: ^(?! Invert match (because we're excluding duplicates) (.{27})* Skip 0, 3 or 6 rows (.{9})? Optionally skip another row (...){0,2} ... 12 Python 2, 47 bytes l=range(1,10) for x in l:print(l*9)[x*8/3:][:9] Try it online! 10 Brachylog, 245 bytes /2 = 122.5 @n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w! h"-".|:"|"x:2f. e(~m["0123456789":.];0<.<=9) :ha#d. :@3az:ca:5a. :3a. hs.:=a,?t:9ac:=fl1 :Im:8f:[[I]]z:ca. :Jm:J. :ha. lg:?c. b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d "w (Note that you have to use the version of the language as of this commit. ...

10

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&...

10

Python, 130 points j1:4}*KYm6?D h^('gni9Xg'# $2{]8=6^l=fF! BS ;1;J:z"^a" \/)gT)sixb"A+ WI?TFvj%:&3-$*ieczL2|aX0 eLbt<tf|mFN'& ;KH_TzKerFa! 7T=1*6]*"s"! The algorithm works by encoding each position in the board, one at a time, into a big integer. For each position, it calculates the possible values given all the assignments encoded so ... 10 C++ - 0.201s official score Using Tdoku (code; design; benchmarks) gives these results: ~/tdoku lscpu | grep Model.name Model name: Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz ~/tdoku # build: ~/tdoku CC=clang-8 CXX=clang++-8 ./BUILD.sh ~/tdoku clang -o solve example/solve.c build/libtdoku.a ~/tdoku # adjust input format: ~/tdoku sed -e "s/... 9 Python, 188 bytes This is a further shortened version of my winning submission for CodeSprint Sudoku, modified for command line input instead of stdin (as per the OP): def f(s): x=s.find('0') if x<0:print s;exit() [c in[(x-y)%9*(x/9^y/9)*(x/27^y/27|x%9/3^y%9/3)or s[y]for y in range(81)]or f(s[:x]+c+s[x+1:])for c in'%d'%5**18] import sys f(sys.argv[1])... 9 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⍴... 9 Jelly, 13 12 9 bytes ŻcṚ+Ḋ²S Try it online! Or see the test-suite. How? This code is calculating \sum_{k=\lceil\frac{n}{2}\rceil}^{n}\big(\binom{k}{n-k}+\binom{k+1}{n-(k+1)}\big)^2 (where$k$starts at$0$rather than$\lceil\frac{n}{2}\rceil$...the additional terms are$0\$ but allows a reversal trick) ŻcṚ$+Ḋ$²S - Link: ...

8

C - 2,361,024 2,509,949 clues Remove clues starting from the last cell if a brute force solver finds only one unique solution. Second try: use heuristic to decide in which order to remove clues instead of starting from the last. This makes the code run much slower (20 minutes instead of 2 to calculate the result). I could make the solver faster, to ...

8

PCRE, 3579 bytes An absolutely terrible brute force solution. Negative lookbehinds ahoy! I spent way too much time on this to abandon it, so here it is, for posterity's sake. On the bright side, if Sudoku suddenly starts using a different set of 9 characters, this'll still work, I guess... http://pastebin.com/raw/CwtviGkC I don't know how to operate Retina, ...

8

Ruby flavour, 75 74 bytes Thanks to jimmy23013 for saving 1 byte. ^(?!(.{9}*(.|(.)){,8}|.*(\g<2>.{8})*|.{27}?.{3}?(\g<2>{3}.{6}){,2}.?.?)\3). Test it here. Now that it's finally beaten, I can share my own solution. :) I discovered an interesting (maybe new?) regex technique in the process (the (.|(.)){,8}\3 part), which would probably be ...

8

T-SQL, 96 89 bytes Found one shorter than the trivial output! SELECT SUBSTRING('12345678912345678',0+value,9)FROM STRING_SPLIT('1,4,7,2,5,8,3,6,9',',') Extracts 9-character strings starting at different points, as defined by the in-memory table created by STRING_SPLIT (which is supported on SQL 2016 and later). The 0+value was the shortest way I could do an ...

8

Node.js, 8.231s 6.735s official score Takes the file name as argument. The input file may already contain the solutions in the format described in the challenge, in which case the program will compare them with its own solutions. The results are saved in 'sudoku.log'. Code 'use strict'; const fs = require('fs'); const BLOCK = []; const BLOCK_NDX = [...

7

perl - score 115 113 103 113 Output: "#1!A_mb_jB) FEIV1JH~vn" $\\XRU*LXea. EBIC5fPxklB 5>jM7(+0MrM !'Wu9FS2d~!W ":R60C"}z!k :B&Jg[fL%\j "L28Y?3Q>4w o0xPz8)_i%- Output: # note this line is empty S}_h|bt:za %.j0.6w>?RM+ :H$>a>Cy{7C '57UHjcWQmcw owmK0NF?!Fv # }aYExcZlpD nGl^K]xH(.\ 9ii]I$voC,x !:MR0>I>... 7 Jelly, 7 bytes 9Rṙ%3$Þ Try it online! And a little bit of this... -1 thanks to Jonathan Allan('s thinking?)

6

CJam, 309 bytes This is just a quick baseline solution. I'm sorry I did this in a golfing language, but it was actually the simplest way to do it. I'll add an explanation of the actual code tomorrow, but I've outlined the algorithm below. Encoder q~{);}%);:+:(9b95b32f+:c Decoder l:i32f-95b9bW%[0]64*+64<W%:)8/{_:+45\-+}%z{_:+45\-+}%z` Test it here. ...

6

Mathematica, score: 130 9 Update: After this answer was posted, it inspired a new loophole closer: "Optimising for the given test cases". I will however leave this answer as is, as an example of the loophole. Feel free to downvote. I won't be hurt. This encodes a cell at a time in raster order, and for each cell rules out its value appropriately for ...

6

Python 2.7, 107 chars total TL;DR brute-force enumeration of 3x3 squares with top+left constraints test cases: import itertools inputs = """ 9 7 3 5 8 1 4 2 6 5 2 6 4 7 3 1 9 8 1 8 4 2 9 6 7 5 3 2 4 7 8 6 5 3 1 9 3 9 8 1 2 4 6 7 5 6 5 1 7 3 9 8 4 2 8 1 9 3 4 2 5 6 7 7 6 5 9 1 8 2 3 4 4 3 2 6 5 7 9 8 1 7 2 4 8 6 5 1 9 3 1 6 9 2 4 3 8 7 5 3 8 5 1 9 7 2 4 ...

6

Javascript regex, 532 530 481 463 chars Validate rows: /^((?=.{0,8}1)(?=.{0,8}2)(?=.{0,8}3)(?=.{0,8}4)(?=.{0,8}5)(?=.{0,8}6)(?=.{0,8}7)(?=.{0,8}8)(?=.{0,8}9).{9})+$/ Validate columns: /^((?=(.{9}){0,8}1)(?=(.{9}){0,8}2)(?=(.{9}){0,8}3)(?=(.{9}){0,8}4)(?=(.{9}){0,8}5)(?=(.{9}){0,8}6)(?=(.{9}){0,8}7)(?=(.{9}){0,8}8)(?=(.{9}){0,8}9).){9}/ Validate square ... 6 Python 2, 53 bytes r=range(9) for i in r:print[1+(j*10/3+i)%9for j in r] Try it online! Alternatives: Python 2, 53 bytes i=0;exec"print[1+(i/3+j)%9for j in range(9)];i-=8;"*9 Try it online! Python 2, 54 bytes for i in range(81):print(i/9*10/3+i)%9+1,'\n'*(i%9>7), i=0;exec"print[1+(i/3+j)%9for j in range(9)];i+=10;"*9 r=range(9);print[[1+(i*10/3+... 6 Jelly, 24 bytes ,ZµŒgaS$€F)Zṣ€0Ṣ<JƊ€€)FẸ Try it online! A monadic link taking as its argument the grid as a matrix with 1 representing squares needing a number and 0 representing the spacers. Returns 0 if the grid is Latin and 1 if not. Explanation Main link, takes a matrix of 1s and 0s as its argument, z , | Pair with: Z ...

5

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

5

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

Only top voted, non community-wiki answers of a minimum length are eligible