/* Solves the knight tours using backtracking */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <time.h>
#include <ctype.h>

#define USE_ASM 1

#define ARRAY_SIZE(x) (sizeof(x)/sizeof(x[0]))

/* defines */
#define BOARD_MASK 0xFFFFFFFFFFFFFFFFULL
#define SQ(X)  (1ULL << (X))
#define AFILE  0x0101010101010101ULL
#define BFILE  0x0202020202020202ULL
#define CFILE  0x0404040404040404ULL
#define DFILE  0x0808080808080808ULL
#define EFILE  0x1010101010101010ULL
#define FFILE  0x2020202020202020ULL
#define GFILE  0x4040404040404040ULL
#define HFILE  0x8080808080808080ULL

typedef unsigned int uint;
typedef uint64_t     board_t;

/* the struct in which we save our path that
 * the knight take to solve the tour */
typedef struct Solution_
{
    uint moves[64];
    uint nmoves;
} Solution;

/* the struct that holds everything */
typedef struct KT_
{
    size_t   nsolutions;
    uint     pos;
    Solution cursolution;
    board_t  board, solved;
} KT;

/* data */
static KT kt;
static board_t knight_moves[64];
static int     knight_popcount[64];

/* functions */
static void        init           (void);
static void        setup          (KT *kt, const char *startpos);
static size_t      gen_moves      (KT *kt, uint *moves);
static void        solve          (KT *kt);
static int         lsb            (board_t v);
static void        make_move      (KT *kt, uint move);
static void        undo_move      (KT *kt, uint move);
static void        print_board    (KT *kt, int solved);
static void        print_solution (Solution *s);
static int         popcount       (board_t b);

int main(int argc, char *argv[])
{
    time_t start;

    if (argc < 2 || (argv[1][0] < 'a'  || argv[1][0] > 'h') ||
                    (argv[1][1] <= '0' || argv[1][1] >= '9'))
    {
        printf("Usage: <square to solve>\n");
        return 1;
    }

    init();
    setup(&kt, argv[1]);
    printf("Solving\n");
    print_board(&kt, 1);
    start = time(NULL);
    solve(&kt);
    printf("Took %d seconds.\n", time(NULL) - start);
    return 0;
}

/* return lsb of a bit, used for extracting move sequences
 * from the bitboard */
static int lsb(board_t v)
{

/* this is x86 32 bit asm */
#if USE_ASM

    int x;
      __asm__(
          "bsfl %1, %0\n\t"
          "jnz done\n\t"
          "bsfl %2, %0\n\t"
          "addl $32, %0\n\t"
          "done:\n\t"
          : "=r" (x)
          : "r" (v & 0xFFFFFFFFUL), "0" ((v >> 32) & 0xFFFFFFFFUL)
         );
      return x;

#else
    uint  i;

    for (i = 0; i < 64; i += 4)
    {
        if (v & SQ(i))
            return i;

        if (v & SQ(i+1))
            return i+1;

        if (v & SQ(i+2))
            return i + 2;

        if (v & SQ(i+3))
            return i + 3;
    }

    return 0;

#endif

}

static int popcount(board_t v)
{
    int ret   = 0;
    board_t b = v;

    while (b)
    {
        b &= (b - 1);
        ret++;
    }

    return ret;
}

/* init stuff */
static void init(void)
{
    int i;

    /* pre-compute the knight moves
     * so we can generate knight moves quickly */
    for (i = 0; i < 64; i++)
    {
        knight_moves[i] = ((SQ(i) << 17) & ~(AFILE))         |
                          ((SQ(i) << 15) & ~(HFILE))         |
                          ((SQ(i) << 10) & ~(AFILE | BFILE)) |
                          ((SQ(i) <<  6) & ~(GFILE | HFILE)) |
                          ((SQ(i) >> 17) & ~(HFILE))         |
                          ((SQ(i) >> 10) & ~(GFILE | HFILE)) |
                          ((SQ(i) >>  6) & ~(AFILE | BFILE)) |
                          ((SQ(i) >> 15) & ~(AFILE));

        knight_popcount[i] = popcount(knight_moves[i]);
    }
}

/* reset the board to default state */
static void setup(KT *kt, const char *startpos)
{
    size_t i;
    uint sq;

    sq = ((startpos[1] - '1') * 8) + (tolower(startpos[0]) - 'a');

    kt->nsolutions = 0;
    kt->pos        = sq;
    kt->solved     = SQ(sq);
    kt->board      = SQ(sq);

    kt->cursolution.moves[0] = sq;
    kt->cursolution.nmoves   = 1;
}

/* print out the solved board or the current board */
static void print_board(KT *kt, int solved)
{
    board_t b = (solved) ? kt->solved : kt->board;
    board_t sq;
    int     i, k;

    printf("\n");
    for (i = 56; i >= 0; i -= 8)
    {
        for (k = 0; k < 8; k++)
        {
            sq = SQ(i + k);
            if (b & sq)
                printf("N ");
            else
                printf(". ");
        }
        printf("\n");
    }
    printf("\n");
}

/* print out a solution */
static void print_solution(Solution *s)
{
    uint   sq;
    size_t i;
    for (i = 0; i < s->nmoves; i++)
    {
        sq = s->moves[i] & 0x3F;
        printf("Move %d: N%c%d\n", i, (sq & 7) + 'a', (sq / 8) + 1);
    }
    printf("\n");
}

/* make a move */
static void make_move(KT *kt, uint move)
{
    move &= 0x3F;
    kt->pos     = move;
    kt->board   = SQ(move);
    kt->solved |= SQ(move);
}

/* undo a move */
static void undo_move(KT *kt, uint move)
{
    uint oldpos = move >> 8;
    kt->pos     =  oldpos;
    kt->board   =  SQ(oldpos);
    kt->solved &= ~SQ(move & 0x3F);
}

/* generate a move */
static size_t gen_moves(KT *kt, uint *moves)
{
    int       popcnt[2] = { -1 };
    size_t    i         = 0;
    board_t   b         = knight_moves[kt->pos] & ~kt->solved,
                          sq;
    uint      temp,
              oldpos    = kt->pos;

    while (b)
    {
        sq = lsb(b);

        popcnt[0] = popcnt[1];
        popcnt[1] = knight_popcount[sq];

        moves[i]  = sq | (oldpos << 8);

        /* heuristic where the moves are sorted by
         * least degrees of freedom, seems to
         * finds solutions much faster */
        if (popcnt[1] < popcnt[0])
        {
            temp         = moves[i];
            moves[i]     = moves[i - 1];
            moves[i - 1] = temp;
        }

        i++;
        b &= (b - 1);
    }

    return i;
}

/* solve it using backtracking */
static void solve(KT *kt)
{
    size_t i, nmoves;
    uint   moves[16];

    if (kt->solved == BOARD_MASK)
    {
        printf("Solution #%d\n", ++kt->nsolutions);
        print_solution(&kt->cursolution);
        return;
    }

    nmoves = gen_moves(kt, moves);

    for (i = 0; i < nmoves; i++)
    {
        kt->cursolution.moves[kt->cursolution.nmoves++] = moves[i];
        make_move(kt, moves[i]);

        solve(kt);

        kt->cursolution.nmoves--;
        undo_move(kt, moves[i]);
    }
}