Shoeisha Technology Media

CodeZine(コードジン)

記事種別から探す

数字パズルを半自動的に解くプログラムの作成

入力可能な場所をガイドするアシストプログラム

  • LINEで送る
  • このエントリーをはてなブックマークに追加
2006/10/05 00:00

最近非常に流行していて、多くの雑誌や単行本が出版されているものに数字パズルがあります。本稿では、これらを解く上で基本的な作業を自動化し、最終判断はコンピュータではなくユーザーに任せようというコンピュータ支援解法に基づいたプログラムを紹介します。

目次
完成図
完成図

はじめに

 最近流行している数字パズルを半自動的に解くプログラムを紹介します。プログラムですべてを自動的に解くわけではないので、頭の体操にもなり、数字パズルに興味が湧いてきます。

対象読者

 パズルの解法やゲームプログラムに興味のある人。

必要な環境

 J2SE 5.0を使っていますが、これより古いバージョンでも、本稿のコードをコンパイルし、実行することができます。ただし、添付のコンパイル済みアプレットの実行には、J2SE Runtime Environment 5.0が必要です。

数字パズル

 最近非常に流行していて、多くの雑誌や単行本が出版されているものに数字パズルがあります。標準的な数字パズルは、3×3のサブグリッド(サブマトリックス)をさらに3×3に並べたもので、サブグリッドには1~9の数字が重複することなく入り、全体のグリッド(9×9)を見ても、縦横に1~9の数字が重複することなく入ります。これだけの条件で空欄に適切な数字を当てはめて行くので、一見簡単のようですが、問題によっては非常に難しいものもあり、頭の体操や暇つぶしに好適です。

数字パズルを解くプログラム

 ネット上には、有償無償の数字パズル解法プログラムが多数存在し、解答のみでなく問題作成のできるものもあります。多くは、バックトラッキング(Backtracking)法と呼ばれるアルゴリズムを使用し、論理的な推測によらず、失敗したら元に戻る試行錯誤を繰り返します。このアルゴリズムは再帰プログラムで記述することができ、プログラマにとっては比較的興味のある対象です。

半自動プログラムで数字パズルを解く

 数字パズルの問題集を求め、鉛筆と消しゴムで必死に解くのも良いのですが、大部分の時間は、注目するマスに入力可能な数字を調べたり、特定の数字を入力できないマスを調べたりに費やしています。本稿で紹介するプログラムは、この作業を自動化して、最終的な判断は、コンピュータではなくユーザーに任せようというComputer Assisted Solving(コンピュータ支援解法)の考え方です。

 ただし、入力できる数字が1個に限定される場合には、本稿のプログラムが自動的に数字を確定しますので、ある程度解答が進むと、瞬時的に自動的に全体を解答してしまう場合もあります。

 バックトラッキング手法を味わってみたいユーザーのために「試行モード」を追加しました。やってみて失敗したら、元に戻せますので、別の選択肢で再度繰り返すことができます。ただし、このモードは安易に使わないでください。数字パズルを解く楽しみが失われてしまいます。上級の問題以外には、まず必要ないはずです。

プログラムの概要

 ボタンなど画面上をクリックする度に呼び出されるpaint()メソッドには、次の内容が記述されています。

  1. モードの種別を表示する
  2. 「出題モード」「解答モード」「試行モード」の区別を、画面右に表示します。
  1. 9×9のグリッドを描く
  2. 縦横共に、3本ごとに線を太くしてサブグリッドを示します。
  1. グレイ領域(入力禁止領域)を設定する
  2. 9×9のグリッドをすべてスキャンし、ラジオボタンで指定した数字(selected_number)と同じ問題、解答または試行の数字が存在すれば、それが含まれる3×3サブグリッド、横列、縦列をグレイ表示して、入力を禁止します。
  1. 入力可能な数字をマスの内部に表示する
  2. 問題、解答、試行のいずれの数字も入力されていないマスに対して、サブグリッド内、横列、縦列を調べて、そこに入力可能な数字を小さいフォントで表示します。
  1. 入力可能な数字が1個のみの場合は、それを自動的に入力する
  2. 4.の結果を利用し、「解答モード」の場合は解答入力として、「試行モード」の場合は試行入力として自動的に入力します。
  1. 問題、解答、試行の既に入力された数字を表示する
  2. 問題は黒で、解答は青のイタリックで、試行は赤のイタリックで入力された数字を表示します。

 9×9のグリッド内のマスをマウスでクリックした場合、次の動作をします。

  • 出題モード
  • グレイ表示されていない場合には、ラジオボタンで選択した数字(selected_number)を問題として設定します。グレイ表示されている場合は、ビープ音で警告します。
  • 解答モード
  • グレイ表示されてなく、問題が入力されてない場合には、ラジオボタンで選択した数字を解答として設定します。グレイ表示されているか問題が存在するか、いずれかの場合は、ビープ音で警告します。
  • 試行モード
  • グレイ表示されてなく、問題も解答も入力されてない場合には、ラジオボタンで選択した数字を試行として設定します。グレイ表示されているか問題または解答が存在する場合は、ビープ音で警告します。

  • LINEで送る
  • このエントリーをはてなブックマークに追加

著者プロフィール

  • 石立 喬(イシダテ タカシ)

    1955年東京工大卒。同年、NECへ入社し、NEC初のコンピュータの開発に参画。磁気メモリ、半導体メモリの開発、LSI設計などを経て、1989年帝京大学理工学部教授。情報、通信、電子関係の教育を担当。2002年定年により退職し現在に至る。2000年より、Webサイト「Visual C++の勉強部屋」...

バックナンバー

連載:Javaで学ぶグラフィックス処理

もっと読む

All contents copyright © 2005-2017 Shoeisha Co., Ltd. All rights reserved. ver.1.5