チェスのナイトは上下左右4方向に2マス進んで、進行方向左に１マスまたは右に１マス、合計８箇所に進むことができる。 将棋の桂馬は２箇所に進むことができるので、チェスのナイトは「八方桂」とも呼ばれる（下図参照）。

wd x ht の盤面において、ナイトを動かして各マスを全て通り、かつ元に戻ってくる問題を「クローズド・ナイト・ツアー」と呼ぶ。

本問題の盤面データ構造は下図のような1次元配列を使用し（マス内の数字は配列インデックス）、 処理を高速化するために、各マスから移動可能なマスをその下のように予め計算し、m_connects に格納しておくものとする。

上記を理解した上で、以下のメンバ関数を実装し、クローズド・ナイト・ツアーの解の数を計算可能にしなさい。

・盤面幅・高さを引数で受け取り、クローズド・ナイト・ツアーの解の数を返すメンバ関数 int Board::countKnightTour(int wd, int ht)
・ナイトが ix に来た場合、その移動可能先の連結数を増やすメンバ関数 void incNConnect(int ix)
・ナイトが ix に来た場合、その移動可能先の連結数を減らすメンバ関数 bool decNConnect(int ix, int& ix1)
・ナイトが ix 位置にn番目に移動した場合の処理を行うメンバ関数 void KnightTour(int n, int ix)

#include <iostream>       //  標準入出力ライブラリ
#include <vector>
#include <string>
using namespace std;    //  std 名前空間使用
typedef unsigned char uchar;
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
class Board {
public:
    Board(int wd = 10, int ht = 3) {
        setSize(wd, ht);
    }
public:
    inline int xyToIX(int x, int y) const { return x + y * m_BD_WIDTH; }
    inline bool isInner(int x, int y) const { return x >= 0 && x < m_BD_WIDTH && y >= 0 && y < m_BD_HEIGHT; }
    void printNth() const {     //  m_nth[] 盤面表示
        for (int y = 0; y < m_BD_HEIGHT; ++y) {
            for (int x = 0; x < m_BD_WIDTH; ++x) {
                auto t = to_string((int)m_nth[x+y*m_BD_WIDTH]);
                if (t.size() < 2) t = ' ' + t;
                cout << t << " ";
            }
            cout << "\n";
        }
        cout << "\n";
    }
    void printConnects() const {    //  連結数、連結リスト表示
        for (int i = 0; i != m_BD_SIZE; ++i) {
            cout << i << ": " << (int)m_nConnect[i] << " {";
            for (auto& x : m_connects[i]) cout << (int)x << ", "; cout << "}\n";
        }
        cout << "\n";
    }
    void setSize(int wd, int ht) {  //  サイズ設定
        m_BD_WIDTH = wd;
        m_BD_HEIGHT = ht;
        m_BD_SIZE = wd * ht;
        //  nth 配列初期化
        m_nth.resize(m_BD_SIZE);
        for(auto& x: m_nth) x = 0;
        //  連結リスト初期化
        m_nConnect.resize(m_BD_SIZE);
        m_connects.resize(m_BD_SIZE);
        int ix = 0;
        for (int y = 0; y < ht; ++y) {
            for (int x = 0; x < wd; ++x, ++ix) {
                m_connects[ix].clear();
                if (isInner(x - 1, y - 2)) m_connects[ix].push_back(xyToIX(x - 1, y - 2));
                if (isInner(x + 1, y - 2)) m_connects[ix].push_back(xyToIX(x + 1, y - 2));
                if (isInner(x - 2, y - 1)) m_connects[ix].push_back(xyToIX(x - 2, y - 1));
                if (isInner(x + 2, y - 1)) m_connects[ix].push_back(xyToIX(x + 2, y - 1));
                if (isInner(x - 2, y + 1)) m_connects[ix].push_back(xyToIX(x - 2, y + 1));
                if (isInner(x + 2, y + 1)) m_connects[ix].push_back(xyToIX(x + 2, y + 1));
                if (isInner(x - 1, y + 2)) m_connects[ix].push_back(xyToIX(x - 1, y + 2));
                if (isInner(x + 1, y + 2)) m_connects[ix].push_back(xyToIX(x + 1, y + 2));
            }
        }
        //  連結数配列初期化
        for (int i = 0; i != m_BD_SIZE; ++i) {
            m_nConnect[i] = (uchar)m_connects[i].size();
        }
    }
    //  ix に連結しているセルの連結数を減らす
    //  連結数が1になったセルがあれば、そこに強制移動になるので ix1 にその位置を設定
    //  連結数が1になったセル複数ある場合はデッドエンドなので false を返す
    bool decNConnect(int ix, int& ix1) {
        //  ToDo: ここにコードを追加し、ナイトが ix に来た場合、その移動可能先の連結数を減らす
        return true;
    }
    void incNConnect(int ix) {
        //  ToDo: ここにコードを追加し、ナイトが ix に来た場合、その移動可能先の連結数を増やす
    }
    void KnightTour(int n, int ix) {
        //  ToDo: ここにn番目のナイトが ix 位置に移動した場合の処理を追加
    }
    int countKnightTour(int wd, int ht) {
        return 0;   //  ToDo: ここにコードを追加し、wd x ht 盤面でのクローズド・ナイト・ツアーの解数を返す
    }
private:
    int m_count = 0;
    int m_BD_WIDTH;     //  盤面幅
    int m_BD_HEIGHT;    //  盤面高
    int m_BD_SIZE;
    vector<uchar>   m_nth;          //  何番目にそのセルを訪れたか（1..盤面サイズ）
    vector<uchar>   m_nConnect;     //  各セル連結数
    vector<vector<uchar>>   m_connects;     //  各セルと連結しているセルインデックスリスト
};
int main() {
    Board bd;
    DO_TEST( bd.countKnightTour(3, 3) == 0 );
    DO_TEST( bd.countKnightTour(10, 3) == 16 );
    DO_TEST( bd.countKnightTour(3, 10) == 16 );
    DO_TEST( bd.countKnightTour(6, 5) == 8 );
    DO_TEST( bd.countKnightTour(6, 6) == 9862 );
    DO_TEST( bd.countKnightTour(6, 7) == 1067638 );
    cout << "\nGood Job!\n";
    return 0;
}

    bool decNConnect(int ix, int& ix1) {    //  ナイトが ix に来た場合、その移動可能先の連結数を減らす
        int nc1 = 0;    //  連結数が1になったセル数
        for(auto& dst: m_connects[ix]) {    //  そのセルの全連結セルについて
            if( m_nth[dst] == 0 ) {     //  未巡回の場合
                if( --m_nConnect[dst] == 1 ) {      //  連結数を減らし、それが1であれば
                    ++nc1;
                    ix1 = dst;      //  強制移動先設定
                }
            }
        }
        return nc1 <= 1;        //  連結数１のマスが１個以下ならOK、そうでなければ枝刈りされる
    }
    void incNConnect(int ix) {      //  ナイトが ix に来た場合、その移動可能先の連結数を増やす
        for(auto& dst: m_connects[ix]) {    //  そのセルの全連結セルについて
            if( m_nth[dst] == 0 )       //  未巡回の場合
                ++m_nConnect[dst];      //  連結数をインクリメント
        }
    }
    void KnightTour(int n, int ix) {    //  ナイトが n 番目の巡回先として ix に来た場合の処理
        m_nth[ix] = n;
        //printNth();
        if( ix == xyToIX(1, 2) ) {      //  最後のマスに来た場合
            if( n == m_BD_SIZE ) {      //  全マスを巡回済みの場合
                ++m_count;              //  解個数インクリメント
                if (m_count % 10000 == 0) cout << ".";
            }
            m_nth[ix] = 0;
            return;
        }
        int ix1 = -1;
        if (!decNConnect(ix, ix1)) {    //  ix に連結しているセルの連結数を減らす
            //  袋小路の場合 → 枝刈り
            //cout << "Dead End\n";
            m_nth[ix] = 0;
            incNConnect(ix);
            //assert( nc == g_nConnect );
            return;
        }
        if( ix1 >= 0 ) {    //  強制移動の場合
            KnightTour(n+1, ix1);
        } else {
            for(auto& dst: m_connects[ix]) {    //  ix の連結先を探索
                if( m_nth[dst] == 0 )   //  未巡回の場合
                    KnightTour(n+1, dst);   //  自分自身を再帰コール
            }
        }
        m_nth[ix] = 0;
        incNConnect(ix);    //  ix に連結しているセルの連結数を元に戻す
    }
    int countKnightTour(int wd, int ht) {
        setSize(wd, ht);
        //
        m_count = 0;
        m_nth[0] = 1;       //  左上隅から開始
        KnightTour(2, xyToIX(2, 1));     //  最初は (2, 1) に移動
        return m_count;
    }