【数独プログラミング】問題チェック

  • 公開されている数独問題は、解がひとつしかないのが普通だ
    • 解が複数存在する問題は綺麗ではないし、解答を載せる場合にも話がややこしくなる。
  • 先に示したソルバーアルゴリズムでは解を発見したときに、探索をやめてしまうが、問題が唯一解を持つかどうかを判定したい場合は、解をひとつ発見しても探索を継続する。
  • 探索を継続し、2つめの解を発見した場合は、別解を持つことが確定するので、そこで探索をやめる。
  • 探索を終了した時点で、解を発見していた場合は、正しい問題となる。
  • チェック処理には、先のソルバーの約2倍の時間が必要
  • コードは以下のようになる
int g_count;  //  発見した解の個数
bool check() {
  g_count = 0;
  check(0);
  return g_count == 1;
}
bool check(int ix) {
  if( ix が盤面外 ) {  //  解を発見
    if( ++g_count > 1 ) {  // 解を複数発見
      return false;
    }
    //  最初の解を発見した場合は、探索を継続
  }
  for(int n = 1; n <= 9; ++n) {
    盤面[ix] に n を設定
    if( !check(ix+1) ) return false;  //  解を複数発見した場合
  }
  盤面[ix] = 0;
  return true;
}

数独プログラミング:ソルバー

■ 数独ソルバー

  • 数独」(Sudoku, ナンプレ、ナンバープレースとも呼ばれる)は非常に人気のあるパズルで、制約充足問題の一種である。
  • 「ソルバー」とは問題を解くプログラムのことである

■ データ構造

  • 各マスの値(1~9, 空欄は0)を uint8 の数値で表現し、盤面全体を1次元配列で表す。
  • 数値ではなくビットマップを用いる方法もあり、その方が高速になるが、大差ないし、ビットマップに慣れていない人には理解しずらくなるので、本稿では数値とする
  • 盤面は2次元なので2次元配列でもよいのだが、一般的に2次元配列は低速なので、1次元配列とした。

■ アルゴリズム

  • 人間が数独の難問を解くのは大変だが、意外なことに最近のCPUであれば、単純な探索アルゴリズムにより、どんな難問でも短時間で解を求めることができる
  • 探索木の大きさが、人間には膨大でも、CPUにとっては手頃なサイズということだ。
  • 擬似コードは以下の通り
bool solve(int ix) {
  if( ix は盤外? ) return true;  // 解発見
  for(int n=1; n<=9; ++n) {
    if( 盤面[ix] に n を配置可能か? ) {
      盤面[ix] = n;  // 盤面[ix] に n を配置
      if( solve(ix+1) )
        return true;   // 解発見の場合
    }
  }
  盤面[ix] = 0;  //  空欄に戻しておく
  return false;
}
void solve() {
  solve(0);
}
  • 場所に関するループで処理してもよいのだが、再帰関数にした方が(筆者には)直感的でわかりやすいのでそうしている。
  • 上記コードで不明なのは、盤面[ix] に n を配置可能かどうかをどう判定するか?という部分である。
  • ix 位置の縦・横方向、ブロック内に既にその数字が配置されていないかどうかを単純にチェックすればよい
int x = ix % 9;  //  横方向位置
int y = ix % 9;  //  縦方向位置
int x0 = x - x % 3;  // 属するブロックの左端位置
int y0 = y - y % 3;  // 属するブロックの上端位置
int bix0 = y0 * 9 + x0;  // 属するブロックの上左端位置
uint8 used[10] = {0,0,0,0,0,0,0,0,0,0};  //  各数字が既に使われているかどうか
for(int i=0; i<9; ++i) {
  used[m_cell[y*N_HORZ+i]] += 1;
  used[m_cell[i*N_HORZ+x]] += 1;
}
for (int i = 0; i < 3; ++i) {
  for (int k = 0; k < 3; ++k) {
    used[m_cell[ix0 + i*N_HORZ + k]] += 1;
  }
}

以上で準備ができたので、盤面[ix] に n を配置する直前に、used[n] が0かどうかをチェックするとよい

■ パフォーマンス計測

  • 上記アルゴリズムを C++ で実装し、(人間的には)難問100問を解かせ、それに要する時間を計測した。
  • 環境:VS2017, Windows10, Core i7-6700@3.4GHz, 16GBMem
  • 結果:約500ミリ秒/100問 (1問あたり約5ミリ秒)

 

【自分用メモ】#数独 解がひとつだけかチェック

(webで公開されてた)数独の問題100問に対して、解がひとつだけかどうかをチェックするプログラムを書いてみた。
アルゴリズムは単純な探索を用いるものだが、セルの値をビットマップで表現しているために、重複チェックが数値を用いるものに比べるとはるかに高速だ。
また、数字を入れるときに、重複チェックを行うのではなく、数字を使用するたびに各縦横ブロックの使用済みフラグをオンにしている。
結果、100問をチェックするのに要した時間は 0.3036ミリ秒だった。ということは、約30マイクロ秒/問でチェック可能ということになる。

ちなみに、単に解を見つけるだけ(最初の解がみつかった時点で終了)の場合は、220マイクロ秒/100問だった。ひとつだけかチェックする場合の約15倍高速ということになる。

プロジェクトにファイルを追加 #cocos2d-x #AndroidStudio

・ External Buld Files/Android.mk の LOCAL_SRC_FILES 部分を以下のように修正

LOCAL_SRC_FILES := $(LOCAL_PATH)/hellocpp/main.cpp \
$(wildcard $(LOCAL_PATH)/../../../Classes/*.cpp)

・Classes 以下にソース・ファイルを追加
・プロジェクトをいったん閉じて開く
→ プロジェクト名/cpp/MyGame/プロジェクト名/Classes 以下に追加されたソースが表示される

cocos2d-x を Android Studio でビルド

※ 環境:Android Studio 3.0.1, cocos2d-x v3.16

・コマンドラインにて cocos New <プロジェクト名> -l cpp を実行するとプロジェクトが作成される。
・プロジェクト名/proj.android-studio を Android Studio で開く
・→ すこし時間がかかるが、Gradle(=ビルド設定)が自動的にビルドされ、プロジェクト自体のビルドが可能な状態になる。
・Build > Make Project を実行しビルド
・→ それなりに時間かかるが、プロジェクト/proj.android-studio/app/build/outputs/apk/debug に プロジェクト名-debug.apk が作成される
・リリース版をビルドする場合は、Build > Generate Signed APK を実行する
・デフォルトでは Classes 以下が一覧に表示されないので、Gradle.Scripts/settings.gradle をダブルクリックで開き、以下を追加する

include ‘:Classes’
project(‘:Classes’).projectDir = new File(settingsDir, ‘../Classes’)
include ‘:Resources’
project(‘:Resources’).projectDir = new File(settingsDir, ‘../Resources’)

【iOS】provisioning profile(プロビジョニング プロファイル)

iOS アプリ開発に於いて、provisioning profile(プロビジョニング プロファイル)周りは非常にややこしく分かりづらい。しかも、Apple のドキュメントが非常に不親切でわかりづらい。さらに、Apple が操作方法・画面をころころ変えるので、ぐぐって出て来るわかりやすい解説が現状と乖離していることが多く、かえって混乱することもしばしばだ。

provisioning profile

X-code にて、プロジェクト  > General > Signing (Debug, Release) で「provisioning profile」を指定する必要があるので、これを生成しなくてはいけない。

「Signing」とは「署名」のことで、正当な開発者によりビルドされたバイナリであることを証明するためのものだ。
「provisioning profile」とは署名をするためのファイルで、Apple Developper (https://developer.apple.com) > Account > Certificates, ISs & profiles で作成することができる。

「provisioning profile」を生成するには以下の3つが必要である。

  • Certificate(開発者情報)
  • App ID(アプリID)
  • Device(apple 端末情報)

署名はアプリのバイナリに対して正当な開発者がビルドしたことを保証するために行うものなので、最初の2つ(Certificate, App ID)が必要になる。また、iOS アプリを開発するには Apple 端末を所有していることが何故か必要なので、端末情報も必要というわけだ。

Certificate

「Certificate」とは開発者情報のことである。

.CSR:端末で作成した鍵ペアの公開鍵部分(CertificateSigningRequest.certSigningRequest)
.CER:公開鍵を元に Apple Developer で生成した認証(Certificate)ファイル

公開鍵生成

マックにて、アプリケーション / ユーティリティ / キーチェーンアクセス アプリを起動
キーチェーンアクセス > 環境設定 メニューを選び、「証明書」タブを選択し、以下のように選択する。
「オンライン証明書状況プロトコル(OCSP)」:切り
「証明書失効リスト(CRL)」:切り
キーチェーンアクセス > 証明書アシスタント > 認証局に証明書を要求… メニューを選び、
開発者のメアド、通称を入力し(CAのメアドは空欄)、「ディスクに保存」「鍵ペア情報を指定」をチェック
“CertificateSigningRequest.certSigningRequest” をデスクトップ等に保存
鍵のサイズ:2048ビット、アルゴリズム:RSA であることを確認し、【続ける】をタップ → CSR ファイルが保存される

Certificate 生成

Apple Developper (https://developer.apple.com) > Account > Certificates, ISs & profiles に行き、Certificates > All を選び [+] をタップ
「iOS App Development」または「App Store and Ad Hoc」を選び、【Continue】を押し、Upload CSR file で先に保存した “CertificateSigningRequest.certSigningRequest” を選択する。
最後に【Download】を押してダウンロード

Provisioning Profile 生成

Apple Developper (https://developer.apple.com) > Account > Certificates, ISs & profiles にて、Provisioning Profiles > All 選び [+] をタップ。
「iOS App Development」または「Ad Hoc」を選び、【Continue】を押す
App ID を選択し、【Continue】を押す
Certificates を選択し、【Continue】を押す
デバイスを選択し、【Continue】を押す
Provisioning Profile の名前を入力し、【Continue】→ ファイルをダウンロード

 

Qt5 再入門>Hello, World (Label使用、デザイナ非使用)

次はLabelウィジェットは使用するが、デザイナを使用せずに「Hello, World」を表示する方法を見てみよう。

QMainWindow は、ウィンドウ中央に表示するウィジェットを持つ。これを「セントラル・ウィジェット」と呼び、setCentralWidget(QWidget*) で指定することができる。
なので、ui セットアップ後に、Label オブジェクトを生成し、それをセントラル・ウィジェットとして指定してやればよい。

MainWindow::MainWindow(QWidget *parent) : (略)
{
    ui->setupUi(this);
    QLabel *label = new QLabel("Hello, World");
    setCentralWidget(label);
}

演習問題

  1.  QLabel ではなく QPushButton オブジェクトを生成し、セントラル・ウィジェットに指定してみなさい。

 

Qt5 再入門>Hello, World (デザイナ・Label使用)

まずは画面に「Hello, World」を表示してみよう。
それにはいくつかの方法があるが、まずは一番簡単なLabelを使ったものを紹介する。
下図の左側のプロジェクト部分の Form を展開し、mainwindow.ui をダブルクリックする。

そうすると、下図のようなデザイン画面に切り替わるはずだ。
左にウィジェット一覧があるので、そこからテキストを表示するためのウィジェットである Labelを探す。ウィジェットはあまりに多すぎて探すのが大変なので、上部のフィルター部分に「la」と入力すると、下図のように一番下に出てくるぞ。

左側のウィジェット一覧から「Label」をドラッグし中央のフォームにドロップすると、下図の様に Labelウィジェットが画面に配置される。

次に「TextLabel」の部分をダブルクリックし、「Hello, World」とキーボードから入力し、ラベルテキストを変更しよう。

これで、プログラムは完成なので、Ctrl + R を押して、ビルド&実行すると、下図のように表示されるはずだ。

デザイナ右下のプロパティ部分で、フォントやアライメントを指定できるぞ。
下図はフォントを大きくし、左右中央揃えに変更してみたものだ。

Ctrl + R で実行すると下図のようになるぞ。

演習問題

  1.  Label ではなく PushButton を配置し、テキストを「Push Me」してみなさい。

まとめ

  • form>ui ファイルをダブルクリックすることでフォームをデザインできるぞ
  • ウィジェットを画面に貼り付けることができるぞ
  • 目的とするウィジェットを探すときはフィルターを使うと便利だぞ
  • プロパティでウィジェットの属性を変更することができるぞ