forestbelton/solver.html

## solver.html
<!DOCTYPE html>
<html>
<head>
    <style>
        #grid {
            line-height: 0;
        }

        #grid > * {
            margin:0;
            padding:0;
        }

        .node {
            width: 50px;
            height: 50px;
            display: inline-block;
        }
    </style>
</head>
<body>
    <div id="grid"></div>
</body>
<script src="solver.js"></script>
</html>

## solver.js
const EMPTY = 0,
    UNVISITED = 1,
    VISITED = 2,
    CURRENT = 3

const DIRS = {
    UP:    { dx: 0,  dy: -1, dir: 'UP'    },
    DOWN:  { dx: 0,  dy: 1,  dir: 'DOWN'  },
    LEFT:  { dx: -1, dy: 0,  dir: 'LEFT'  },
    RIGHT: { dx: 1,  dy: 0,  dir: 'RIGHT' }
}

const state = {
    grid: [
        [1, 1, 1, 1, 1, 0],
        [0, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 0, 0],
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 0, 0, 1],
        [0, 0, 1, 1, 1, 1]
    ],
    pos: { x: 2, y: 3 }
},
state2 = {
    grid: [
        [1, 1, 1, 1, 1, 0],
        [0, 1, 1, 1, 1, 0],
        [1, 1, 1, 1, 0, 0],
        [1, 0, 1, 1, 1, 1],
        [1, 1, 1, 0, 0, 1],
        [0, 0, 1, 1, 1, 1]
    ],
    pos: { x: 2, y: 3 }
}

function at(grid, x, y) {
    if (x < 0 || x >= grid[0].length) {
        return EMPTY
    } else if (y < 0 || y >= grid.length) {
        return EMPTY
    }

    return grid[y][x]
}

function set(grid, x, y, v) {
    grid[y][x] = v
}

function neighbors(state) {
    const { pos, grid } = state

    return Object.keys(DIRS).map(k => DIRS[k])
        .filter(d => pos.x + d.dx >= 0 && pos.x + d.dx < grid[0].length)
        .filter(d => pos.x + d.dx >= 0 && pos.y + d.dy < grid.length)
        .filter(d => at(grid, pos.x + d.dx, pos.y + d.dy) == UNVISITED)
}

function solved(state) {
    const { grid } = state

    return grid.reduce((acc, row) =>
        row.reduce((acc, cell) => acc && cell != UNVISITED, acc)
    , true)
}

function solve(state) {
    return solve1(state, [])
}

function solve1(state, steps) {
    const { pos, grid } = state

    set(grid, pos.x, pos.y, VISITED)
    if (solved(state)) {
        return steps
    }

    const nbrs = neighbors(state)
    if (nbrs.length == 0) {
        return 'impossible'
    }

    for (nbr of nbrs) {
        const newState = walk(state, nbr)
        const path = solve1(newState, steps.concat(nbr.dir))

        if (path != 'impossible') {
            return path
        }
    }

    return 'impossible'
}

function walk(state, nbr) {
    const newState = {
        grid: state.grid.map(row => row.slice()),
        pos: { x: state.pos.x, y: state.pos.y }
    }
    const { grid, pos } = newState

    while (at(grid, pos.x + nbr.dx, pos.y + nbr.dy) == UNVISITED) {
        pos.x += nbr.dx
        pos.y += nbr.dy

        set(grid, pos.x, pos.y, VISITED)
    }

    return newState
}

const solution = solve(state)
draw(state2, solution)

function drawGrid(state) {
    const { grid, pos } = state
    const nodes = []

    grid.forEach(row => {
        row.forEach(cell => {
            const node = document.createElement('div')

            node.className = 'node'
            node.style.backgroundColor = ['white', 'black', 'red', 'blue'][cell]

            nodes.push(node)
        })

        nodes.push(document.createElement('br'))
    })

    const gridNode = document.getElementById('grid')

    gridNode.innerHTML = ''
    nodes.forEach(node => gridNode.appendChild(node))
}

function draw(state, solution) {
    const { grid, pos } = state

    set(grid, pos.x, pos.y, CURRENT)
    drawGrid(state)

    if (solution.length > 0) {
        set(grid, pos.x, pos.y, VISITED)

        const [h, ...t] = solution
        const nbr = DIRS[h]

        setTimeout(() => {
            const newState = walk(state, nbr)
            draw(newState, t || [])
        }, 250)
    }
}
	<!DOCTYPE html>
	<html>
	<head>
	<style>
	#grid {
	line-height: 0;
	}

	#grid > * {
	margin:0;
	padding:0;
	}

	.node {
	width: 50px;
	height: 50px;
	display: inline-block;
	}
	</style>
	</head>
	<body>
	<div id="grid"></div>
	</body>
	<script src="solver.js"></script>
	</html>
	const EMPTY = 0,
	UNVISITED = 1,
	VISITED = 2,
	CURRENT = 3

	const DIRS = {
	UP: { dx: 0, dy: -1, dir: 'UP' },
	DOWN: { dx: 0, dy: 1, dir: 'DOWN' },
	LEFT: { dx: -1, dy: 0, dir: 'LEFT' },
	RIGHT: { dx: 1, dy: 0, dir: 'RIGHT' }
	}

	const state = {
	grid: [
	[1, 1, 1, 1, 1, 0],
	[0, 1, 1, 1, 1, 0],
	[1, 1, 1, 1, 0, 0],
	[1, 0, 1, 1, 1, 1],
	[1, 1, 1, 0, 0, 1],
	[0, 0, 1, 1, 1, 1]
	],
	pos: { x: 2, y: 3 }
	},
	state2 = {
	grid: [
	[1, 1, 1, 1, 1, 0],
	[0, 1, 1, 1, 1, 0],
	[1, 1, 1, 1, 0, 0],
	[1, 0, 1, 1, 1, 1],
	[1, 1, 1, 0, 0, 1],
	[0, 0, 1, 1, 1, 1]
	],
	pos: { x: 2, y: 3 }
	}

	function at(grid, x, y) {
	if (x < 0 \|\| x >= grid[0].length) {
	return EMPTY
	} else if (y < 0 \|\| y >= grid.length) {
	return EMPTY
	}

	return grid[y][x]
	}

	function set(grid, x, y, v) {
	grid[y][x] = v
	}

	function neighbors(state) {
	const { pos, grid } = state

	return Object.keys(DIRS).map(k => DIRS[k])
	.filter(d => pos.x + d.dx >= 0 && pos.x + d.dx < grid[0].length)
	.filter(d => pos.x + d.dx >= 0 && pos.y + d.dy < grid.length)
	.filter(d => at(grid, pos.x + d.dx, pos.y + d.dy) == UNVISITED)
	}

	function solved(state) {
	const { grid } = state

	return grid.reduce((acc, row) =>
	row.reduce((acc, cell) => acc && cell != UNVISITED, acc)
	, true)
	}

	function solve(state) {
	return solve1(state, [])
	}

	function solve1(state, steps) {
	const { pos, grid } = state

	set(grid, pos.x, pos.y, VISITED)
	if (solved(state)) {
	return steps
	}

	const nbrs = neighbors(state)
	if (nbrs.length == 0) {
	return 'impossible'
	}

	for (nbr of nbrs) {
	const newState = walk(state, nbr)
	const path = solve1(newState, steps.concat(nbr.dir))

	if (path != 'impossible') {
	return path
	}
	}

	return 'impossible'
	}

	function walk(state, nbr) {
	const newState = {
	grid: state.grid.map(row => row.slice()),
	pos: { x: state.pos.x, y: state.pos.y }
	}
	const { grid, pos } = newState

	while (at(grid, pos.x + nbr.dx, pos.y + nbr.dy) == UNVISITED) {
	pos.x += nbr.dx
	pos.y += nbr.dy

	set(grid, pos.x, pos.y, VISITED)
	}

	return newState
	}

	const solution = solve(state)
	draw(state2, solution)

	function drawGrid(state) {
	const { grid, pos } = state
	const nodes = []

	grid.forEach(row => {
	row.forEach(cell => {
	const node = document.createElement('div')

	node.className = 'node'
	node.style.backgroundColor = ['white', 'black', 'red', 'blue'][cell]

	nodes.push(node)
	})

	nodes.push(document.createElement('br'))
	})

	const gridNode = document.getElementById('grid')

	gridNode.innerHTML = ''
	nodes.forEach(node => gridNode.appendChild(node))
	}

	function draw(state, solution) {
	const { grid, pos } = state

	set(grid, pos.x, pos.y, CURRENT)
	drawGrid(state)

	if (solution.length > 0) {
	set(grid, pos.x, pos.y, VISITED)

	const [h, ...t] = solution
	const nbr = DIRS[h]

	setTimeout(() => {
	const newState = walk(state, nbr)
	draw(newState, t \|\| [])
	}, 250)
	}
	}