Developer

競技プログラミング風 C++問題集【第11回】
2021.01.31
Lv3

競技プログラミング風 C++問題集【第11回】

目次

クローズド・ナイト・ツアー(難易度:★★★★☆)

問題

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

競技プログラミング風C++問題集【第11回】_01

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

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

競技プログラミング風C++問題集【第11回】_02

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

・盤面幅・高さを引数で受け取り、クローズド・ナイト・ツアーの解の数を返すメンバ関数 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;
}
ヒント

・左上マスから深さ優先探索を開始し、解の個数をカウントするといいぞ。
・逆順を省くために最初は (2, 1) に移動し、最後は (1, 2) に帰ってくることにすればいいぞ。
・各マスの連結数配列(m_nConnect)を常に更新し、連結数1のマスが1個であればそこに強制的に移動するぞ。
・連結数1のマスが複数ある場合は、デッドエンドなので、枝刈りを行うんだぞ。

解答例
    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;        //  連結数1のマスが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;
    }
解説

クローズド・ナイト・ツアーの解数を求めるには、左上マス (0, 0) から深さ優先探索を開始し、解の個数をカウントするとよい。
また、逆順解を排除するために、最初は (0, 0) から (2, 1) に移動し、最後は (1, 2) から (0, 0) に戻ってくるものとするとよい。
探索中は、decNConnect(), incNConnect() をコールして、常に各マスの連結数(m_nConnect[])を更新する。 このとき、連結先マスの連結数が1になった場合はそこに強制移動する。連結数1のマスが複数できた場合は、 それらのマスは袋小路ということなので、すぐにリターンし、枝刈りを行う。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。