[UVa] 291 The House of Santa Claus.cpp

#include <cstdio>
#include <vector>
using namespace std;

vector<int> toNxt[6] = {{}, {2,3,5}, {1,3,5}, {1,2,4,5}, {3,5}, {1,2,3,4}};
bool choosed[6][6] = {0};
int ans[9];

void func(int n, int Len)
{
    if (Len == 9) {
        for (int &a : ans)
            printf("%d", a);
        putchar('\n');
    }
    for (int nxt : toNxt[n]) {
        if (choosed[n][nxt] == 0 && choosed[nxt][n] == 0) {
            choosed[n][nxt] = 1, choosed[nxt][n] = 1;
            ans[Len] = nxt;

            func(nxt, Len + 1);

            choosed[n][nxt] = 0, choosed[nxt][n] = 0;
        }
    }
}
int main()
{
    ans[0] = 1;
    func(1,1);
}

// Ans
/*
123153452
123154352
123451352
123453152
123513452
123543152
125134532
125135432
125315432
125345132
125431532
125435132
132153452
132154352
132534512
132543512
134512352
134512532
134521532
134523512
134532152
134532512
135123452
135125432
135215432
135234512
135432152
135432512
152134532
152135432
152345312
152354312
153123452
153125432
153213452
153254312
153452132
153452312
154312352
154312532
154321352
154325312
154352132
154352312
*/