Holey Knight's Tour

Question

Given a rectangular board of cells with some number of holes in it, determine whether it is possible to complete a "holey knight's tour" (That is, a path that visits every non-hole cell exactly once using only chess knight moves, not returning to the starting cell) that starts on the top-left cell.

For the sake of completeness of the challenge definition, knights move by teleporting directly to a cell that is two cells away along one axis and one cell along the other axis.

Examples

Using . for open spaces and X for holes

1

. . .
. X .
. . .

YES

2

. . . X
. X . .
. . X .
X . . .

NO

3

. . . . .
X . . . .
. . X . .
. X . . .
. . . . .

YES

4

. . X . .
X . . . X
. . . . .
. X . . .
X . . X X

YES

5

. . . . . .
. . X . . .
. X . . . .
. . . . . .
. . . . . .

NO

Rules and Assumptions

• You must theoretically be able to support boards up to 1000x1000
• Boards do not necessarily have to be square
• As this problem could potentially have exponential time complexity in the worst case, and in an effort to not make testing solutions take forever, board sizes up to 6x6 must return an answer within one minute on modern hardware.
• A board with a hole in the top-left corner (where the knight starts) is always unsolvable

Shortest code wins

Answer 1

Sledgehammer, 29 bytes

⠑⡘⣡⡪⡾⢸⢹⣎⡷⡬⢵⣅⢞⣽⣤⡥⠃⠏⢂⢜⠩⡬⢸⠜⡻⣠⡪⢄⡯

That's not very readable, so here's the corresponding Mathematica code:

 AnyTrue[Thread@
   FindHamiltonianPath[
    Subgraph[KnightTourGraph[#2, #3], 
     o = First /@ StringPosition[#, "."]], 1, o], 
  ListQ@# && Length@# > 0 &] &

This removes unneeded vertices from the knight's graph (first obtained via KnightTourGraph), calls FindHamiltonianPath with all possible end vertices (it either takes nothing and finds any Hamiltonian path, or it takes both a start and an end vertex) and checks whether any paths were actually found.

Example input (for the fourth test case)

{"..X..X...X......X...X..XX", 5, 5}

The first line is a flat version of the grid (obtained by reading it in row-major order).

I have first thought that this doesn't work, but then I investigated and finally found what seems to be a bug in the interpreter: the hammer.wls main script doesn't call postprocess, and (when decoding) it ends up evaluating the code with all slots (#, #2, #3) replaced by variables s1, s2, s3 :(. Fortunately, the interactive app, while even less convenient, doesn't have this bug.

Answer 2

Python 3, 166 bytes

def f(g,s=[0]):w=len(g[0])+2;k='XX'.join(g)+w*'XXX';*p,x=s;return{*s,'.'}>{*p,k[x]}and any(f(g,s+[x+a])|f(g,s+[x-a])for a in(w+2,w-2,w-~w,w+w-1))|len(s)//k.count('.')

Try it online!

Brute force all paths.

Adaptation from my answer to Find the shortest route on an ASCII road.

Answer 3

R, 243 213 bytes

Edit: -30 bytes by merciless code-trimming...

function(p,m,n=1e4,f=function(p,m,x){m[t(p)]=1
d=p+matrix(c(q<-c(1,2,2,1,1,-2,2,-1),-q),2)
`if`(w<-sum(v<-!m[d<-t(d[,!colSums(d<1|d>dim(m))])]),f(d[which(v)[sample(w,1)],],m),!sum(!m))})mean(sapply(1:n,f,p=p,m=m))

Try it online!

This is a stochastic algorithm.

The complete search (163 bytes) of all tours on a 6x6 board without holes can require up to approx 36 (positions) x 2^36 (combinations of already-visited squares or holes), which does not run in a <1 minute time-frame, and even memoising already-tried partial-tours isn't feasible (since unfortunately R vectors are limited to a length of 2^31).

So instead we repeatedly attempt random tours. 1e5 random tours is sufficient to sample the entire, no-hole, 6x6 board and repeatedly find successful tours within 1 minute (although unfortunately not on TIO).

At the cost of 1 wasted byte, the implementation here reports the fraction of successful to unsuccessful attempted tours.

Answer 4

Perl 5, 305 bytes

sub f{my($b,$x,$y)=(@_,1,1);$b=~/.+/;$lx=length$&;$P=sub{($X,$Y)=@_;$X<1||$X>$lx||$Y<1||$Y>$b=~y/\n//?0:($Y-1)*($lx+1)+$X};(!(substr($b,&$P($x,$y)-1,1)=~s,\.,x,)or$b!~/\./)||(any{f($b,@$_)}grep{substr($b,&$P(@$_)-1,1)eq'.'}map[$x+$$_[0],$y+$$_[1]],[2,-1],[2,1],[1,-2],[1,2],[-2,1],[-2,-1],[-1,2],[-1,-2])}

Try it online!