UVa 291 - The House Of Santa Claus

Problem link

Keyword: graph, brute force

Algorithm:

Note that there may be an algorithm with higher efficiency.
I used brute force method to generate all possible drawings (in permutation) and check the validity.
A solution is said to be ok if all vertexes are drawn only once.
If the solution is correct, then print it out.

Code:

#include<cstdio>

#include<algorithm>

using namespace std;

int all[] = { 12, 13, 15, 23, 25, 34, 35, 45 };

bool ok( char *s )

{

    int use[ 9 ] = { 0 };

    for( int i = 0; i < 8; ++i )

        ++use[ find( all, all+8, max( s[i], s[i+1] ) + min( s[i], s[i+1] ) * 10 - 528 ) - all ];

    for( int i = 0; i < 8; ++i )

        if( use[ i ] != 1 )

            return false;

    return true;

}



int main()

{

    char order[] = { "112334552" };

    do

        if( ok( order ) )

            printf( "%s\n", order );

    while( next_permutation( order+1, order+8 ) );



    return 0;

}