• Print 0 if an n*m maze cannot be solved
  • Print 1 if an n*m maze can be solved (in 1 or more ways)

(so I'm not asking for paths but if it's possible to solve!!!)


Input array(2d):


XS     XX
X     X X
X    X  X
XX     FX

0 = can pass through
1 = can not pass trough
[0][n] is the last block of the first line
[m][0] is the first block of the last line

Rule The start position is 0,0 and the end position is n,m You can only move horizontally and vertically Shortest code wins

  • \$\begingroup\$ Should the input be a string or an array? \$\endgroup\$
    – apsillers
    Commented Dec 23, 2014 at 14:36
  • 3
    \$\begingroup\$ If there is a 1 (wall) at (n,m) should the code return 0? \$\endgroup\$ Commented Dec 23, 2014 at 15:17
  • 3
    \$\begingroup\$ (Same for a wall at (0,0)?) \$\endgroup\$ Commented Dec 23, 2014 at 15:18
  • 4
    \$\begingroup\$ You say it's a n×m maze, but your indexing implies that it's an (n+1)×(m+1) maze. \$\endgroup\$ Commented Dec 23, 2014 at 20:33
  • 4
    \$\begingroup\$ I am looking forward to the regex solution=) \$\endgroup\$
    – flawr
    Commented Dec 23, 2014 at 21:25

10 Answers 10


Dyalog APL, 27 characters


evaluated input. APL distinguishes between a matrix and a vector of vectors. This program assumes that the input is a matrix.

(~×⍳∘⍴)A is a fork equivalent to (~A) × ⍳⍴A. It's needed to avoid mentioning twice or introducing a variable.

⍴A is the shape of A. For a 4-by-7 matrix the shape is 4 7.

is the index generator. ⍳4 is 1 2 3 4. ⍳4 7 is the vectors (1 1)(1 2)...(4 7) arranged in a 4-by-7 matrix.

~A flips the bits of A.

× by multiplying ⍳⍴A by the flipped bits, we preserve the coordinates of all free cells and turn all walls into 0 0.

, ravels the matrix of coordinate pairs, i.e. linearizes it into a vector. In this case the vector will consist of pairs.

∘.-⍨A or A∘.-A subtracts elements of A pairwise. Note that here the elements of A are themselves pairs.

| absolute value

+/¨ sum each pair of absolute values. This gives us the grid distances between every pair of cells in the maze, save for walls.

1≥ we are only intrested in neighbours at a distance no more than 1, this also excludes walls. Now we have a graph's adjacency matrix.

∨.∧⍨⍣≡ Floyd--Warshall's transitive closure algorithm

(f⍣n)A (not used here) where n is an integer is the power operator. It applies f to A n times: f f ... f A.

(f⍣g)A where g is a function, is the fixed point operator, a.k.a. "power limit". It keeps on computing the series A, f A, f f A, ... until ((f⍣i)A) g ((f⍣(i+1))A) returns true for some i. In this case we use match () as g.

∨.∧⍨A or A∨.∧A is a step in Floyd's algorithm. f.g is a generalisation of matrix multiplication (+.×), here we use conjunction () and disjunction () in place of + and ×.

⊃⌽ After ⍣≡ has applied the step enough times and reached a stable state, we must look up the top-right corner of the matrix to get the result, so we flip it () and take the first, top-left item ().

Visualization of ⍣≡'s steps


CJam, 42 41 39 36 35 bytes


Based on the ideas in this answer.

4 bytes thanks to Optimizer.

Input format:

[[0 0 0 0 0 0 1] [0 0 0 0 0 1 0] [0 0 0 0 1 0 0] [1 0 0 0 0 0 0]]
  • \$\begingroup\$ @Optimizer Thanks for that. But then I found a shorter way... \$\endgroup\$
    – jimmy23013
    Commented Dec 23, 2014 at 16:04
  • 1
    \$\begingroup\$ q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW= - 36. Although it assumes that the first three characters of the input will be [[0 \$\endgroup\$
    – Optimizer
    Commented Dec 23, 2014 at 16:28

Python, 164 bytes

def s(a):
 while d:i,j=d.pop();a[i][j]=2;d+=[(x,y)for x,y in[(i-1,j),(i,j-1),(i+1,j),(i,j+1)]if len(a[0])>y>-1<x<len(a)and a[x][y]<1]
 return a[-1][-1]>1

I was reluctant to post this because it's practically how I'd normally do flood fill, just lightly golfed. But here it is anyway.

  • \$\begingroup\$ (x,y) is in [(i-1,j),(i,j-1),(i+1,j),(i,j+1)] iff abs(x-i)+abs(y-j)<2, although I'm not sure if that can help \$\endgroup\$
    – Stef
    Commented Aug 26, 2020 at 13:20

Perl, 73 bytes

69 bytes of code + 4 bytes for -n0E (not sure how the tags where counted in 2014, so I counted them for 4 instead of 2, but it doesn't matter a lot).


Try it online! (and if you replace the 1111011 line with 1111111, the maze isn't solvable anymore, and the output will be 0 instead of 1 : Try it online!)


This code will find every reachable cell of the maze (and mark them with a A): if a cell touches a cell marked with a A, the it's reachable and we mark it with a A too; and we do that again (redo). That's done thanks to two regex: s/(^0|A)(.{@{+}})?0/A$2A/s checks if a space is on the right or the bottom of a A, while s/0(.{@{+}})?A/A$1A/s checks if a space is on the left or on top of a A. At the end, if the last cell contains a A it's reachable, otherwise it's not (that's what say/A$/+0 checks; the +0 is here to make sure the result will be 0 or 1 instead of empty string and 1).
Note that /.*/ will match an entire line, thus setting @+ to the index of the end of the first line, which happens to be the size of a line, which allow use to use .{@{+}} to match exactly as many character as there are on a line. (@{+} is equivalent to @+, but only the former can be used in regex)

  • \$\begingroup\$ For this test case, your code considers the maze solvable even if the final position is 1. \$\endgroup\$
    – Jitse
    Commented Nov 7, 2019 at 10:57
  • \$\begingroup\$ @Jitse Good catch. Actually, it was because the TIO links were not using the right code (I guess it was some earlier version and I didn't spot it). The answer is still valid, and I've updated the TIO links. Your example works then fine: Try it online! \$\endgroup\$
    – Dada
    Commented Nov 7, 2019 at 11:17
  • \$\begingroup\$ Oh, right! Thanks for the clarification, I like this approach. \$\endgroup\$
    – Jitse
    Commented Nov 7, 2019 at 11:20
  • \$\begingroup\$ @Jitse thanks, that's one of my favorite golfs :) \$\endgroup\$
    – Dada
    Commented Nov 7, 2019 at 11:21

Ruby, 133 130 129 characters

a=eval gets
f[d,e]if a[d]&&a[d][e]==0}}
p a[-1][-1]

Input on STDIN, outputs 1 or 0 on STDOUT.

Annoyingly long. It simply does a flood-fill of 1s from (0, 0), and then checks to see whether the "end" square is a 1.

  • \$\begingroup\$ Will this treat the maze as solvable if it already contains a 1 at (n,m)? \$\endgroup\$ Commented Dec 23, 2014 at 15:18

Java, 418 bytes

import java.util.Scanner;public class Solvable{static int w,h;public static void main(String[] a){String[]i=new Scanner(System.in).nextLine().split(";");h=i.length+2;w=i[0].length()+2;int[]m=new int[w * h];for(int x=1;x<w-1;x++)for(int y=1;y<h-1;y++)m[y*w+x]=i[y-1].charAt(x-1)<'.'?0:1;f(m,w+1);System.out.println(m[w*h-w-2]>0?0:1);}static void f(int[]m,int i){if(m[i]>0){m[i]--;f(m,i-1);f(m,i+1);f(m,i-w);f(m,i+w);}}}

My first code golf. I don't know why I chose Java - it's so bad for golfing xD

Example maze would be inputted via stdin like this:

  • 1
    \$\begingroup\$ Pro tip: name your class something one character long, ditch the space between String[] and a, and take input from command line arguments rather than StdIn, which is allowed. \$\endgroup\$
    – Pavel
    Commented Jan 5, 2017 at 5:05

Python 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a[0]),len(a);return([x,y]in h)==(x>=X)==(y>=Y)==(x<0)==(y<0)==a[y][x]<(x==X-1and y==Y-1or f(a,x-1,y,s)|f(a,x+1,y,s)|f(a,x,y-1,s)|f(a,x,y+1,s))

This got much longer than I thought it would be :( Anyway, I'll add an explanation once I can't golf it any longer.


J, 75 chars

Powering of the adjacency matrix (very time and memory inefficient). (Is it called powering in English?)

   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:)))

Some test cases:

   m1=. 0 0 0 0 0 0 1,. 0 0 0 0 0 1 0,.  0 0 0 0 1 0 0,. 1 0 0 0 0 0 0
   m2=. 0 1 1 ,. 0 0 0
   m3=. 0 1 0 ,. 1 1 0
   m4=. 0 1 1 0 ,. 0 0 1 0
   ({.@{:@(+./ .*.^:_~)@(+:/~@,*2>(>@[+/@:|@:->@])"0/~@,@(i.@#<@,"0/i.@#@|:))) every m1;m2;m3;m4
1 1 0 0

Python 3, 136 bytes

def f(g,x=0,*p):w=len(g[0])+1;l=w*len(g);return~x%w*(-1<x<l)*~-(x in p)and any(g[x//w][x%w]and f(g,x+a,*p,x)for a in(1,-1,w,-w))or-~x==l

Try it online!

Uses 0 for wall, 1 for free space.

Port of my answer to Find the shortest route on an ASCII road.


Python 3, 184 bytes

f=lambda m,x=0,y=0,n=0:n<len(m)*len(m[0])and m[x][y]<1and((x,y)==(len(m)-1,len(m[0])-1)or any(0<=i<len(m)and 0<=j<len(m[0])and f(m,i,j,n+1)for i,j in[(x-1,y),(x,y-1),(x+1,y),(x,y+1)]))

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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