412012-01-25 00:55:25masahiko402012-01-12 07:48:54masahiko392012-01-12 07:28:24masahiko382012-01-12 07:17:18masahiko372012-01-11 12:17:20masahiko362012-01-11 11:55:37masahiko352012-01-11 11:55:25masahiko名前を'ばらばらにする'から変更。342011-01-10 00:55:46masahiko332011-01-09 01:26:58masahiko322011-01-09 01:15:48masahiko312011-01-09 01:14:16masahiko302010-01-13 00:34:28masahiko292010-01-12 02:31:25masahiko282010-01-05 02:26:14masahiko272010-01-05 02:20:27masahiko262010-01-05 02:14:31masahiko252010-01-05 02:09:34masahiko242010-01-05 02:00:43masahiko232010-01-05 01:57:53masahiko222010-01-05 01:57:18masahiko212010-01-05 01:55:02masahiko202010-01-05 01:32:53masahiko192010-01-05 01:28:16masahiko182010-01-05 01:25:58masahiko172010-01-05 01:10:38masahiko162010-01-05 01:05:01masahiko152010-01-05 00:56:53masahiko142010-01-05 00:53:15masahiko132010-01-05 00:52:17masahiko122010-01-05 00:50:32masahiko112010-01-05 00:47:09masahiko102010-01-05 00:45:11masahiko92009-12-22 12:16:33masahiko82009-12-22 12:11:44masahiko72009-12-22 12:04:41masahiko62009-12-17 07:52:06masahiko52009-12-15 12:40:03masahiko42009-12-15 12:37:31masahiko32009-12-07 01:07:14masahiko22009-12-07 01:04:49masahiko12009-12-04 06:16:15masahiko

右下の１つを除いた他のピースをばらばらに入れ替えた後、 スライドするだけで元の位置に戻すのがこのパズル(１５ゲーム)の問題です。 どんなにばらばらに配置しても元の位置にもどせるのかというと、そうではありません。 元にもどせる配置と、元にもどせない配置があります。 どんな配置だと元にもどせるかを解説した後、 元にもどせる配置だけを作成するメソッドを示します。

並び、置換、互換とその関係の説明をします。

並べるものの一つ一つを数で表すことにすると、 例えば５つのものの並びは (1,2,3,4,5) や (1,3,5,4,2) や (4,3,2,5,1) のように書けます。 並び(4,3,2,5,1)は ４という目印のものが１番目に ３という目印のものが２番目に ２という目印のものが３番目に ５という目印のものが４番目に １という目印のものが５番目に 並んでいることを表しています。

ものの並びの順番を入れ替える操作を(数学の用語では)置換と言います。 たとえば 並び(1,2,3,4,5)を 並び(1,3,5,4,2)に変える操作 も置換の１つです。

置換のうち２つの要素を互いに入れ替えるものを互換といいます。 たとえば 並び(1,2,3,4,5)を 並び(2,1,3,4,5)に変える操作 は互換の１つです。 交換される２つ以外の要素の位置は変わりません。

置換は互換の積で表すことができます。 どんな置換(入れ替え)も、互換(２つの入れ替え)を繰り返すことで行うことができるという意味です。 たとえば、並び(1,2,3,4,5)を並び(1,3,5,4,2)に変えるには 元の状態互換入れ替え後の状態(1,2,3,4,5)2と3を入れ替え(1,3,2,4,5)(1,3,2,4,5)2と5を入れ替え(1,3,5,4,2)と、2回の互換で行うことができました。

何回かの互換を繰り返すことで置換ができることがわかりました。 上の例では2回の互換で目的の置換ができましたが他の手順も考えられます。 元の状態互換入れ替え後の状態(1,2,3,4,5)2と3を入れ替え(1,3,2,4,5)(1,3,2,4,5)2と4を入れ替え(1,3,4,2,5)(1,3,4,2,5)2と5を入れ替え(1,3,4,5,2)(1,3,4,5,2)4と5を入れ替え(1,3,5,4,2)4回の互換で行うことができました。 ほかにもいろいろな手順が考えられます。 しかしどの方法をとっても、 並び(1,2,3,4,5)を並び(1,3,5,4,2)に変えるには 互換の回数は偶数回になります。 どんな置換も互換を繰り返すことでできるが、互換の回数は偶数回か奇数回のどちらかに決まる。 奇数回の互換で表される置換を偶置換といいます。 偶数回の互換で表せれる置換を奇置換といいます。

１５ゲームでは 偶置換の問題は解けますが、奇置換の問題は解けません。 偶置換の問題だけを作るようにプログラムを作成します。

最初に正しい位置に配置した後で 互換を偶数回(50回)行うことで問題を作成します。

５～７行目でもとの配置にしています。。 １０～２４行目が１つの互換を行う処理です。 その外側のforループを偶数回(50回)繰り返すことで偶置換の問題を作り出しています。 １つ１つの互換は ban[x][y]にある内容を、その右隣または直下の内容と入れ替える操作にします。 １０，１１行目ではｘとｙの値を乱数で決めています。 乱数は横の数、縦の数より１つ小さい範囲に制限しています。 互換は下図のどれかが行われ、右下のピースの位置だけは変わりません。 右下隅のピースはゲーム中は取り除くので、このピースを除いた他のピースの置換(互換)だけを考えなければならないからです。 tikan2.png １２～２１行目で乱数の値により、x2,y2の位置をx,yの右か下かのどちらかに決めています。 右隣と入れ換えるときは x2 = x + 1 y2 = y 直下と入れ換えるときは x2 = x y2 = y + 1 となっていればよい。 ２２～２４行目が入れ換えの操作です。 入れ替え元の位置が(x,y)、入れ替え先の位置が(x2,y2)です。 tikan1.png

メソッドshokikaを上で示したものに変更し、動作を確認しなさい。