Solving the 'wolf, goat, and cabbage problem' with SQL (SQLite dialect)

wolf-goat-cabbage.sql

WITH RECURSIVE
  moves(mask, move_desc) AS (
    VALUES 
      (1, "Farmer crosses alone"),
      (3, "Farmer takes wolf"),
      (5, "Farmer takes goat"),
      (9, "Farmer takes cabbage")
  ),
  states(i, visual) AS (
    SELECT 0, '👨 🐺 🐐 🥬 | 🚣🌊🌊🌊🌊 |'
    UNION ALL
    SELECT
      i + 1,
      (CASE (i+1>>0)&1 WHEN 0 THEN '👨 ' ELSE '   ' END) ||
      (CASE (i+1>>1)&1 WHEN 0 THEN '🐺 ' ELSE '   ' END) ||
      (CASE (i+1>>2)&1 WHEN 0 THEN '🐐 ' ELSE '   ' END) ||
      (CASE (i+1>>3)&1 WHEN 0 THEN '🥬 ' ELSE '   ' END) ||
      (CASE (i+1>>0)&1 WHEN 0 THEN '| 🚣🌊🌊🌊🌊 | ' ELSE '| 🌊🌊🌊🌊🚣 | ' END) ||
      (CASE (i+1>>0)&1 WHEN 1 THEN '👨 ' ELSE '   ' END) ||
      (CASE (i+1>>1)&1 WHEN 1 THEN '🐺 ' ELSE '   ' END) ||
      (CASE (i+1>>2)&1 WHEN 1 THEN '🐐 ' ELSE '   ' END) ||
      (CASE (i+1>>3)&1 WHEN 1 THEN '🥬 ' ELSE '   ' END)
    FROM states
    WHERE i < 15
  ),
  explore(state, path, actions) AS (
    -- start
    SELECT 0, '0', printf('%-20s | %s', 'Start') || visual FROM states WHERE i = 0
    UNION ALL
    SELECT
      state + mask - 2*(state & mask) AS next_state,
      path || ' -> ' || (state + mask - 2*(state & mask)),
      actions || char(10) || printf('%-20s | %s', move_desc) || visual
    FROM explore, moves, states
    WHERE
      -- join with states CTE for visuals
      state + mask - 2*(state & mask) = i
      -- farmer must be with passenger (unless alone)
      AND (mask = 1 OR ((state & 1) = (state & mask) / mask))
      -- avoid revisiting states
      AND instr(path, state + mask - 2*(state & mask)) = 0
      -- wolf + goat unsafe
      AND NOT (
        ((state + mask - 2*(state & mask)) >> 1 & 1)
          = ((state + mask - 2*(state & mask)) >> 2 & 1)
        AND ((state + mask - 2*(state & mask)) >> 0 & 1)
          != ((state + mask - 2*(state & mask)) >> 1 & 1)
      )
      -- goat + cabbage unsafe
      AND NOT (
        ((state + mask - 2*(state & mask)) >> 2 & 1)
          = ((state + mask - 2*(state & mask)) >> 3 & 1)
        AND ((state + mask - 2*(state & mask)) >> 0 & 1)
          != ((state + mask - 2*(state & mask)) >> 2 & 1)
      )
  )
SELECT
  group_concat(actions, char(10) || char(10))
FROM (
  SELECT actions
  FROM explore
  WHERE state = 15
);