# Can maze be solved?

The puzzle

• Print 0 if a maze n*m can not be solved
• Print 1 if a maze n*m 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):

[[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]]

XXXXXXXXX
XS     XX
X     X X
X    X  X
XX     FX
XXXXXXXXX

0 = can pass through
1 = can not pass trough
[n] is the last block of the first line
[m] 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

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

# CJam, 42413936 35 bytes

Wq3>~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW=  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]]  • @Optimizer Thanks for that. But then I found a shorter way... – jimmy23013 Dec 23 '14 at 16:04 • q2Wts~_s,{{[{_2$+0<{e<_}*}*]}%z}*sW= - 36. Although it assumes that the first three characters of the input will be [[0 – Optimizer Dec 23 '14 at 16:28

# Dyalog APL, 27 characters

⊃⌽∨.∧⍨⍣≡1≥+/¨|∘.-⍨,(~×⍳∘⍴)⎕

⎕ 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

# Python, 164 bytes

def s(a):
d=[(0,0)]
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)>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.

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

/.*/;s/(^0|A)(.{@{+}})?0/A$2A/s||s/0(.{@{+}})?A/A$1A/s?redo:say/A$/+0  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!) Explanations: 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)

• For this test case, your code considers the maze solvable even if the final position is 1. – Jitse Nov 7 at 10:57
• @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! – Dada Nov 7 at 11:17
• Oh, right! Thanks for the clarification, I like this approach. – Jitse Nov 7 at 11:20
• @Jitse thanks, that's one of my favorite golfs :) – Dada Nov 7 at 11:21

# Ruby, 133130 129 characters

a=eval gets
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o,y+o
f[d,e]if a[d]&&a[d][e]==0}}
f[0,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.

• Will this treat the maze as solvable if it already contains a 1 at (n,m)? – trichoplax Dec 23 '14 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.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:

......#;.....#.;....#..;#......

• 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. – Pavel Jan 5 '17 at 5:05

## Python 184 188

def f(a,x=0,y=0,h=[]):s=h+[[x,y]];X,Y=len(a),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, 147 bytes

def f(g,s=):w=len(g)+1;*p,x=s;return~-(x in p)*~-[j for i in g+[w*]for j in+i][x]and max(f(g,s+[x+a])for a in(-1,1,-w,w))or x==w*len(g)


Try it online!

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)and m[x][y]<1and((x,y)==(len(m)-1,len(m)-1)or any(0<=i<len(m)and 0<=j<len(m)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!