# Tag Info

## Hot answers tagged puzzle-solver

31

BBC BASIC, 570 514 490 bytes ASCII Download interpreter at http://www.bbcbasic.co.uk/bbcwin/download.html 435 bytes tokenised Full program displays an input from L.bmp on the screen, then modifies it to find a solution. *DISPLAY L t=PI/8q=FNa(1) DEFFNa(n)IFn=7END LOCALz,j,p,i,c,s,x,y,m,u,v F.z=0TO99u=z MOD10*100v=z DIV10*100ORIGINu,v F.j=0TO12S.4p=0F.i=j+...

26

C++ - 1123 Since nobody posted any answer so far, I decided to simplify and golf my 2004 solution. It's still far behind the shortest one I mentioned in the question. #include<iostream> #include<vector> #define G(i,x,y)for(int i=x;i^y;i++) #define h(x)s[a[x]/q*q+(a[x]+j)%q-42] #define B(x)D=x;E=O.substr(j*3,3);G(i,0,3)E+=F[5-F.find(E[2-i])];G(i,...

24

Python 1166 bytes A considerable amount of whitespace has been left for the sake of readability. Size is measured after removing this whitespace, and changing various indentation levels to Tab, Tab Space, Tab Tab, etc. I've also avoided any golfing which affected the performance too drastically. T=[] S=[0]*20,'QTRXadbhEIFJUVZYeijf',0 I='FBRLUD' G=[(~i%8,i/...

19

Ruby, 85 bytes f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0} Try it online! Explanation The first step is to establish a recursive divide and conquer strategy to solve subproblems. I will use the variables $l=[l_1,l_2,...,l_x]$ for the list of clues, $x$ for the number of clues and $n$ for the ...

17

The shortest game of halma is 49 moves 49 move solution Proof there is no 48-move solution Code used for this solution The code now supports pass Notice that the 47 move solution in the paper is for the army transfer problem, not for the shortest game of halma I'll hopefully get to doing a proper writeup this weekend

15

C# - 2,098,382 steps I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post an answer. There is certainly ways to improve this further more. I think going under the 2M steps might be possible. It took approx 7 hours to generate results. Here is a txt file with all solutions, in case ...

15

05AB1E, 23 11 8 bytes ΔÍN-;иg= Try it online! Uses 0-based indexing. Explanation: # start from the implicit input Δ # loop forever Í # subtract 2 N- # subtract the current iteration number ; # divide by 2 и # create a list of length x g # get the length of the list = ...

13

Octave, 334 313 bytes Since the challenge may seem a bit daunting, I present my own solution. I did not formally prove that this method works (I guess that will come down to proving that the algorithm will never get stuck in a loop), but so far it works perfectly, doing 100x100 testcases within 15 seconds. Note that I chose to use a function with side ...

12

Ruby, 742 characters r=->y{y.split.map{|x|[*x.chars]}} G=r['UF UR UB UL DF DR DB DL FR FL BR BL UFR URB UBL ULF DRF DFL DLB DBR'] o=r[gets] x=[];[[%w{U UU UUU L LL LLL}+D=%w{D DD DDD},0],[%w{FDFFF RFDFFFRRR}+D,12],[%w{DDDRRRDRDFDDDFFF DLDDDLLLDDDFFFDF}+D,8],[%w{DFLDLLLDDDFFF RDUUUFDUUULDUUUBDUUU}+D,4],[%w{LDDDRRRDLLLDDDRD RRRDLDDDRDLLLDDD LFFFLLLFLFFFLLLF}...

12

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

11

Python - 48 characters exec("".join(map(chr,map(len,' ...

11

Python 2.7: 544 bytes -50% = 272 bytes** import sys;o=''.join;r=range;a=sys.argv[1];a=o([(' ',x)[x in a[12]+a[19]+a[22]] for x in a]);v={a:''};w={' '*4+(a[12]*2+' '*4+a[19]*2)*2+a[22]*4:''} m=lambda a,k:o([a[([0x55a5498531bb9ac58d10a98a4788e0,0xbdab49ca307b9ac2916a4a0e608c02,0xbd9109ca233beac5a92233a842b420][k]>>5*i)%32] for i in r(24)]) def z(d,h): ...

10

C, via the preprocessor I think the ANSI committee made a conscious choice not to extend the C preprocessor to the point of being Turing-complete. In any case, it's not really powerful enough to solve the eight queens problem. Not in any sort of general fashion. But it can be done, if you're willing to hard-code the loop counters. There's no real way to ...

10

Python – 10,800,000 steps As a last-place reference solution, consider this sequence: print "123456" * 18 Cycling through all the colours n times means that every square n steps away will be guaranteed to be of the same colour as the center square. Every square is at most 18 steps away from the center, so 18 cycles will guarantee all the squares ...

10

Python 2, 115 bytes n=input() for F in range(4): t=[F];b=0;exec"x=(-n[b]-sum(t[-2:]))%4;t+=x,;b+=1;"*len(n) if x<1:print t[:-1];break This is the golfed version of the program I wrote while discussing the problem with Martin. Input is a list via STDIN. Output is a list representing the last solution found if there is a solution, or zero if ...

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

Pyth, 66 ?"Yes".Am>2sm^-.uk2Cm.Dx"qwertyuiopasdfghjkl*zxcvbnm"b9.5dC,ztz"No Try it here. I was surprised to learn Pyth doesn't have a hypotenuse function, so this will likely be beat by a different language. I'll propose a hypotenuse function to Pyth, so this atrocity won't happen in the future. Explanation I transform the ...

9

Python - 1669 Still pretty long, but fast enough to run the last example in under a second on my computer. It's probably possible to make shorter at the cost of speed, but for now it is pretty much equivalent to the ungolfed code. Example output for last test case: 0 11 1 11 2 11 3 11 4 11 4 10 3 10 2 10 1 10 1 9 2 9 3 9 4 9 4 8 3 8 3 7 4 7 5 7 5 6 5 5 6 5 6 ...

9

Haskell, 242 230 201 199 177 163 160 149 131 bytes import Data.Lists m=map a#b=[x|x<-m(chunk$length b).mapM id$[0,1]<$(a>>b),g x==a,g(transpose x)==b] g=m$list[0]id.m sum.wordsBy(<1) Finally under 200 bytes, credit to @Bergi. Huge thanks to @nimi for helping almost halving the size. Wow. Almost at half size now, partly because of me but ...

9

Python 2, 75 bytes f=lambda n,i=0:n>=i<<i and f(n,i+1)or[min(n,2**j*i-i+j)for j in range(1,i)] Try it online! Explanation: Builds a sequence of 'binary' chunks, with a base number matching the number of cuts. Eg: 63 can be done in 3 cuts, which means a partition in base-4 (as we have 3 single rings): Cuts: 5, 14, 31, which gives chains of 4 1 8 1 ...

8

Java - 2,480,714 steps I made a little mistake before (I put one crucial sentence before a loop instead of in the loop: import java.io.*; public class HerjanPaintAI { BufferedReader r; String[] map = new String[19]; char[][] colors = new char[19][19]; boolean[][] reached = new boolean[19][19], checked = new boolean[19][19]; int[] ...

8

C#, M = 2535 This implements* the system which I described mathematically on the thread which provoked this contest. I claim the 300 rep bonus. The program self-tests if you run it either without command-line arguments or with --test as a command-line argument; for spy 1, run with --spy1, and for spy 2 with --spy2. In each case it takes the number which I ...

8

Python 2, 305 This is the golfed version. It is practically unusable for n > 3, as the time (and space) complexity is like 3n2... actually that may be way too low for the time. Anyway, the function accepts a list of strings. def f(i): Z=range;r=map(__import__('fractions').Fraction,i);R=r[1:];n=len(R);L=[[[1]*n,[0]]];g=0 for m,p in L: for d in([v/3**i%...

8

MATL, 68 59 58 bytes '?'7XJQtX"'s'jh5e"@2#1)t35>)-1l8t_4$h9M)b'nsew'=8M*sJ+XJ+( Try it online! Explanation The map is kept in the bottom of the stack and gradually filled. The current position of the explorer is stored in clipboard J. The map uses matrix coordinates, so (1,1) is upper left. In addition, column-major linear indexing is used. ... 8 JavaScript (ES6), 25 bytes x=>y=>((x<3?x:3)+x)*y/2+1 x=>y=>(x<3?x+x:x+3)*y/2+1 x=>y=>(x<3?x:(x+3)/2)*y+1 x=>y=>(x<3?x:x/2+1.5)*y+1 All of these compute the same value; I can't seem to come up with a shorter formulation. When x is less than 3, you take as much water as you can and walk as far as you can, which is simply ... 8 R, 77 69 bytes -8 bytes thanks to Aaron Hayman pmin(n<-scan(),0:(k=sum((a=2:n)*2^a<=n))+cumsum((k+2)*2^(0:k))+1)[-n] Try it online! Let $k$ be the number of cuts needed; $k$ is the smallest integer such that $(k+1)\cdot2^k\geq n$. Indeed, a possible solution is then to have subchains of lengths $1,1,\ldots,1$ ($k$ times) and \$(k+1), 2(k+...

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

Here's a C++11 solution without any templates: constexpr int trypos( int work, int col, int row, int rows, int diags1, int diags2, int rowbit, int diag1bit, int diag2bit); constexpr int place( int result, int work, int col, int row, int rows, int diags1, int diags2) { return result != 0 ? result : col == 8 ? work : row == 8 ?...

7

PyPy, 195 moves, ~12 seconds computation Computes optimal solutions using IDA* with a 'walking distance' heuristic augmented with linear conflicts. Here are the optimal solutions: 5 1 7 3 9 2 11 4 13 6 15 8 0 10 14 12 Down, Down, Down, Left, Up, Up, Up, Left, Down, Down, Down, Left, Up, Up, Up 2 5 13 12 1 0 3 15 9 7 14 6 10 11 8 4 Left,...

7

SWI Prolog, 183 characters m(A,A). m([i],[i,u]). m([i,i,i|T],B):-m([u|T],B). m([u,u|T],B):-m(T,B). n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)). n(A,B):-m(A,B). s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y). How about some Prolog, (since nobody has answered in 6 months). To run, just use "s(mi,mu)." The code breaks up atoms into chars, then searches for ...

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