# 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})+|(?>(... 33 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 - ...

21

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} ... 14 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/... 12 Python 2, 47 bytes l=range(1,10) for x in l:print(l*9)[x*8/3:][:9] Try it online! 11 05AB1E, 54 47 bytes 3δôø˜©‚˜9ôI2äí«ø«D€ÙQIÂí‚øε˜Ć}D€ÔQ®9ô€Ås9L¢<PP Takes the input as a 6x27 matrix, kinda like the reference screenshot of the grid. Outputs 1 for truthy, or another integer (usually 0) as falsey. Try it online or verify all test cases. Explanation: Step 1: Transform the input-matrix to a (flattened) list of blocks: δ # Map ... 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 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: ...

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

Python 3, 232 bytes Thanks to those who helped to golf this down. Encryption within encryption... q=lambda x,y:x+y+x+y+x r=lambda a,b,c,d,e:a+q(q(b*3,c),d)+e+"\n" print(((r(*"╔═╤╦╗")+q(q("║ %d │ %d │ %d "*3+"║\n",r(*"╟─┼╫╢")),r(*"╠═╪╬╣"))+r(*"╚═╧╩╝"))%eval(input())).replace(*"0 ")) Try it online! To be golfed.

8

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>... 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, 120 bytes Oh, I remember golfing that back in 2008... And it in fact stopped working in perl 5.12 since implicit setting of @_ by split was removed then. So only try this on a sufficiently old perl. Run with the input on STDIN: sudoku.pl <<< "030001000006000050500000983080006302000050000903800060714000009020000800000400030" sudoku.pl:${/[...

7

C (gcc), 398 395 291 bytes Saved 3 bytes by working through the string reversed, and 104 (!) bytes thanks to Leaky Nun. #include<locale.h> #define q(x,y) x y x y x #define D L"╝"q(q("═══","╧"),"╩")"╚"q(q("\n║"q(q(" & ","│"),"║")"║","\n╢"q(q("───","┼"),"╫")"╟"),"\n╣"q(q("═══","╪"),"╬")"╠")"\n╗"q(q("═══","╤"),"╦")"╔" i;f(int*t){setlocale(LC_ALL,"");...

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 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 APL (Dyalog Unicode), 56 bytes (,⊖⍣(?2)↑a(3+⍳3)(10-⌽a←3?3)){⍺ ⍺⌷9 9⍴∊⌽⍵∘.⌽⍵⊖¨⊂3 3⍴⍳9}⍳3 Try it online! A full program that randomly gives a 9-by-9 matrix of digits. By OP mentioning "it must be possible to obtain at least 9 structurally different boards", I believe it was to prevent using just trivial transformations like reflection and rotation. But ... 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

PHP, 297 bytes <?for(;$l<19;$l++)echo$l&1?strtr(vsprintf(str_pad("",67,"║ %d │ %d │ %d "),array_slice($_GET,9*($l/2^0)-9,9)),0," "):str_pad([╔,╟,╠,╚][$b=$l?$l<18?$l%6<1?2:1:3:0],108,strtr("11101110111".[╦,╫,╬,╩][$b],[[╤,═],[┼,─],[╪,═],[╧,═]][$b])).[╗,╢,╣,╝][$b]," "; Try it online! Expanded for(;$l<19;$l++) # loop thrpugh lines echo\$...

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