カテゴリー別アーカイブ: C++

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

■ 数独ソルバー

  • 数独」(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ミリ秒)

 

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’)

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

Qt5 再入門>空のプロジェクト作成

久々にQtでアプリを作ろうと思ったら、いろいろすっかり忘れていたので、自分の備忘録としてもQt5 を使ったアプリの作成方法を記述しておく。

なお、Qt のバージョンは 5.9, Qt Creator のバージョンは 4.3.1を使用する

空のプロジェクト作成

まずは「ようこそ」の上部中央の【+ 新しいプロジェクト】をクリックして、新しいプロジェクトの作成を開始する。

作成するプロジェクトの種別を指定するダイアログ(下図)が表示される。
通常アプリを作成したいのであれば、下図の様に「アプリケーション」、「Qtウィジェットアプリケーション」を選び、【選択】を押す。

次にプロジェクト名、プロジェクトファイルのパスを入力する。

次にクラス名、ファイル名等を設定できるダイアログが表示される。
通常は特に変更する必要は無い。

最後に、プロジェクト管理、概要が表示されるので、問題が無ければ【完了】を押す。

以上で、プロジェクトが生成される。

プロジェクトが作成できたら Ctrl + R を押してみよう。
下図のような空のウィンドウが表示されるはずだ。

【cocos2d-x v3】 RadioButton の使い方

RadioButton クラスは v3.8 で追加された比較的新しいクラスだ。

  • RadioButtonGroup オブジェクトを生成し、子ノードとしてシーンに追加
  • 選択肢の分だけ、RadioButton を生成し、RadioButtonGroup オブジェクトに 追加し、シーンへも子ノードとして追加する
  • RadioButton オブジェクトにイベントリスナーを指定する
// Create a radio button group
auto radioButtonGroup = RadioButtonGroup::create();
this->addChild(radioButtonGroup);

// Create the radio buttons
for(・・・) {
        RadioButton* radioButton = RadioButton::create("cocosui/radio_button_off.png", "cocosui/radio_button_on.png");
        float posX = startPosX + BUTTON_WIDTH * i;
        radioButton->setPosition(Vec2(posX, winSize.height / 2.0f + 70));
        radioButton->setScale(1.2f);
        radioButton->addEventListener(CC_CALLBACK_2(LabelToggleTypeTest::onChangedRadioButtonSelect, this));
        radioButton->setTag(i);
        radioButtonGroup->addRadioButton(radioButton);
        this->addChild(radioButton);
}

VS2015 余計なフォーマット禁止

VS2015 では、閉じ波括弧「}」を入力すると、勝手にフォーマットしてくれてる。

hoge() {
■

ここで、} を入力すると、{ のところで勝手に改行されてしまう。

hoge() 
{
}■

おいらにとってはまったくよけいなお世話だ。
で、これを禁止するには、ツール>オプション メニューを実行し、
テキストエディター>言語>全般 を開き、「} でブロックをオートフォーマットする (B)」を
OFFにするといいぞ。
temp

QOpenGLWidget 入門 (1)

Qt で OpenGL を使う場合、従来は QGLWidget を使っていたが、
Qt 5.4(?) で QOpenGLWidget が導入され、QGLWidget は非推奨となった。
なので、本稿ではその QOpenGLWidget を試してみることにする。

なお、QGLWidget を使う場合のコードは Qt + OpenGL 入門 を参照してほしい。

再実装が必要なメソッドは以下の3つ。これは QGLWidget の場合と同じだ。

  • void initializeGL()
  • void resizeGL(int w, int h)
  • void paintGL()

QGLWIdget との違いは、OpenGL のコマンドを直接実行するのではなく、

QOpenGLFunctions *f = QOpenGLContext::currentContext()->functions();

で、OpenGL コマンドを実行するためのオブジェクトを取得し、それに対してコマンドを実行するという点だ。

以下に、最も簡単なサンプルとして、背景を明るい緑にするだけのコードを示しておく。

class MyGLWidget : public QOpenGLWidget
{
public:
  MyGLWidget(QWidget *parent) : QOpenGLWidget(parent) { }
protected:
  void initializeGL()
  {
    // Set up the rendering context, load shaders and other resources, etc.:
    QOpenGLFunctions *f = QOpenGLContext::currentContext()->functions();
    f->glClearColor(0.75f, 1.0f, 0.75f, 1.0f);  // 背景色指定
  }
  void resizeGL(int w, int h)
  {
  }
  void paintGL()
  {
  }
};

実行結果は以下のとおり。

temp

■ 演習問題:

  1. 上記サンプルが正しく動作することを確認しなさい
  2. 背景色をグレイに変えてみなさい
  3. 背景色を好きな色に変えてみなさい

 

Qt5 のIME(InputMethod)周り

実は「さくさくエディタ」は最初、Qt5 の勉強もかねて Qt5.0 で開発し始めたのだが、IME(InputMethod)周りが期待したようには動作せず(いったいどうい問題があったのかは覚えてない)、情報が少なく対処も難しそうだったので Qt4.x に変更した経緯がある。

が、もうバージョンも 5.5 になってて、さすがにいろいろ治ってるだろうと、Qt 5.5 でIME周りの動作確認をしてみたところ、以下のコードでちゃんと動作した。
めでたし、めでたし。

void MainWindow::inputMethodEvent(QInputMethodEvent * event)
{
	QWidget::inputMethodEvent(event);
	auto pre = event->preeditString();
	auto txt = event->commitString();
	qDebug() << "inputMethodEvent(): pre = " << pre;
	qDebug() << "inputMethodEvent(): txt = " << txt;
}
QVariant MainWindow::inputMethodQuery( Qt::InputMethodQuery query ) const
{
	if( query == Qt::ImCursorRectangle ) {
		qDebug() << "query == Qt::ImCursorRectangle";
		return QVariant(QRect(m_px, m_py, 1, 1));
	}
	return QMainWindow::inputMethodQuery(query);
}

まとめ:

  • 1文字入力は、keyPressEvent ( QKeyEvent * event ); を再実装する。
  • IME イベントを処理したい場合は setAttribute(Qt::WA_InputMethodEnabled); を実行しておく
  • IME イベント処理は inputMethodEvent(QInputMethodEvent * event); を再実装する。
    • preeditString() で現候補文字を取得
    • commitString() で確定文字を取得
  • IME 候補ウィンド位置は inputMethodQuery( Qt::InputMethodQuery query ) を再実装する
    • query が Qt::ImCursorRectangle の時に、ウィンドウ位置を返す
    • 矩形サイズは無視されるようだが、0, 0 を指定すると左上に表示されてしまう
    • 実際に表示されるのは文字高さ?分だけ下にずれるようだ