English

blogs

数独解法プログラム 数独の解の見つけ方

数独解法プログラム

この記事では、再帰法を用いた数独の解を見つけ方について説明します。まずコードを使わず、図を見ながら考え方から入ります。その後、Javaコードをお見せします。この解決法は白紙の状態からだけではなく、埋められているマスがあっても、この時点で正しい組み合わせであれば解を見つけてくれます。

こちらからデモプログラムをダウンロードできます。Javaのソース・プロジェクトはGithubから落とせます。ちなみにこのページの下に載せてあるのは解を見つけるために必要なメソッドだけです。

考え方

1. 左上のマスから始めます。左から右へ、上から下へ、というふうに一マスずつ進んでいきます。

2. もし、このマスが右下の最後のマスを訪れた後なら、現在のマスは[9][0]になります。この行が9なら、「全てのマスを通った」という意味のtrueの値を返します。メソッドの中でまずこれを確かめます。

3. 1から9の9つの数字を配列に重複がないよう用意する。再帰メソッドの中でマスの候補として一つずつテストしていきます。


[Continue reading…]

円形と矩形(角度あり)の衝突判定

円と矩形(角度あり)

円形と角度のついた傾きありの矩形の衝突判定の実装の仕方を説明します。衝突判定(または当たり判定)とは、物体Aと物体Bが接触しているかを判定する事です。円はxy座標と半径を所持します。矩形はxy座標、横幅、縦幅、角度を持つとします。ここでは、矩形の回転は矩形の中心点を回転の中心とします。

アプレット、図、コードを用いて説明していきましょう。円形と角度変化なしの矩形の衝突判定の参考として、こちらの記事を読ませていただきました。

[Continue reading…]

穴堀り法 迷路生成アルゴリズム

穴掘り法とは

穴掘り法は迷路生成アルゴリズムの一つです。他にも棒倒し法・壁伸ばし法等がありますが、ここでは穴掘り法をJavaのコードを見ながら説明したいと思います。再帰法を使って紹介します。

穴掘り法の主な考え方は、ランダムな開始地点から開いている方向に2マス単位で進みながら通路を作っていきます。4方向共行き止まりになったら、方向が一つでも開いているマスへ戻り、そこからまた掘っていきます。

説明

迷路を表現するのに、縦横奇数の大きさの2次元配列を使います。0を通路、1を壁とします。(解説の絵では0をオレンジ、1を黒で表現)縦の列をcol(column)、横の列をrowと呼びます。

Explanation 1

全てのマスを1(壁)にします。

[Continue reading…]