An answer of http://nabetani.sakura.ne.jp/hena/ord27raswi/

raswi.cpp

// clang++ -stdlib=libc++ -std=c++1y raswi.cpp
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <functional>
#include <unordered_map>

using namespace std;

using rail_t = unordered_map<string, vector<string>>;

string join(const vector<string> &v, const string &separator)
{
    vector<string> res;
    transform(v.begin(), v.end(), back_inserter(res),
              [&](const string &s) { return res.size() + 1 == v.size() ? s : s + separator; });
    return accumulate(res.begin(), res.end(), string(""));
}

bool is_goal(const string &pos)
{
    const string goal = "456";
    return goal.find(pos) != string::npos;
}

void rec(const string &start_pos, const string &cur_pos, const string &prohibited, vector<string> &v)
{
    static const rail_t rail = {
        { "1", {"a", "g"} }, { "2", {"h", "d"} },
        { "3", {"b", "f"} }, { "a", {"b"} },
        { "b", {"c", "5"} }, { "c", {"4", "6"} },
        { "d", {"c", "e"} }, { "e", {"5"} },
        { "f", {"g"} },      { "g", {"c", "e", "h"} },
        { "h", {"4", "i"} }, { "i", {"6"} },
    };
    
    const vector<string> next_pos = rail.at(cur_pos);
    for(const auto &e : next_pos) {
        if(prohibited.find(e) != string::npos) {
            continue;
        }
        if(is_goal(e)) {
            const string s = start_pos + e;
            if(find(v.begin(), v.end(), s) == v.end()) {
                v.push_back(s);
            }
            continue;
        }
        rec(start_pos, e, prohibited, v);
    }
}

string solve(const string &in)
{
    vector<string> res;
    for(const auto &e : {"1", "2", "3"}) {
        vector<string> v;
        rec(e, e, in, v);
        if(!v.empty()) {
            sort(v.begin(), v.end(), less<string>());
            res.push_back(join(v, ","));
        }
    }
    return res.empty() ? "-" : join(res, ",");
}

void test(const string &in, const string &expected)
{
    const string actual = solve(in);
    cout << (actual == expected ? "OK" : "***NG***") << endl;
}

void test_all()
{
    /*0*/ test("befi", "14,16,24,26");
    /*1*/ test("abc", "14,15,16,24,25,26,34,35,36");
    /*2*/ test("de", "14,15,16,24,26,34,35,36");
    /*3*/ test("fghi", "14,15,16,24,25,26,34,35,36");
    /*4*/ test("abcdefghi", "-");
    /*5*/ test("ag", "24,25,26,34,35,36");
    /*6*/ test("dh", "14,15,16,34,35,36");
    /*7*/ test("bf", "14,15,16,24,25,26");
    /*8*/ test("ch", "15,25,35");
    /*9*/ test("be", "14,16,24,26,34,36");
    /*10*/ test("ci", "14,15,24,25,34,35");
    /*11*/ test("cgi", "15,24,25,35");
    /*12*/ test("acgi", "24,25,35");
    /*13*/ test("cdefghi", "15,35");
    /*14*/ test("acdefghi", "35");
    /*15*/ test("cdegi", "15,24,35");
    /*16*/ test("bcdegi", "24");
    /*17*/ test("afh", "14,15,16,24,25,26,34,35,36");
    /*18*/ test("abfh", "14,15,16,24,25,26");
    /*19*/ test("dfh", "14,15,16,34,35,36");
    /*20*/ test("cdfh", "15,35");
    /*21*/ test("deh", "14,15,16,34,35,36");
    /*22*/ test("cdeh", "15,35");
    /*23*/ test("abefgh", "24,26");
    /*24*/ test("abdefgh", "-");
    /*25*/ test("acfghi", "25,35");
    /*26*/ test("acdfghi", "35");
    /*27*/ test("cegi", "15,24,35");
    /*28*/ test("abcfhi", "15,25");
    /*29*/ test("abcefhi", "-");
    /*30*/ test("abdi", "14,15,16,24,34,35,36");
    /*31*/ test("abdfi", "14,15,16,24");
    /*32*/ test("bdi", "14,15,16,24,34,35,36");
    /*33*/ test("bdfi", "14,15,16,24");
    /*34*/ test("adfh", "14,15,16,34,35,36");
    /*35*/ test("adfgh", "34,35,36");
    /*36*/ test("acdfhi", "15,35");
    /*37*/ test("bcdfgi", "24");
    /*38*/ test("bcdfghi", "-");
    /*39*/ test("defi", "14,15,16,24,34,35,36");
    /*40*/ test("defhi", "14,15,16,34,35,36");
    /*41*/ test("cdefg", "15,24,26,35");
    /*42*/ test("cdefgi", "15,24,35");
    /*43*/ test("bdefg", "24,26");
    /*44*/ test("bdefgi", "24");
}

int main()
{
    test_all();
    return 0;
}