/****************************/
/* 8 パズルの解法 */
/* Coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
public class Test {
public static void main (String[] args)
{
S_Eight win = new S_Eight("8 パズルの解法（ Swing ）");
}
}
class S_Eight extends JFrame implements ItemListener {
int MAX = 1000; // 最大試行回数
int g[][]; // 目標状態
int kodomo[][][]; // [i][0][j] : 適用した規則番号
// [i][1][j] : 適用後の状態
int n_o_pattern; // 展開された状態の数
int oya[]; // 親の状態番号
int pattern[][][]; // 現在の状態
int s_method = 1; // 探索方法
// =1 : 横型
// =2 : 縦型
// =3 : 深さ＋目標状態と異なるコマの数
// =4 : h(n) = p(n) + 3s(n)
// p(n) : 目標状態からの距離
// s(n) : =0 : 次の駒が正しい順序のとき(中心の駒を除く)
// =2 : 次の駒が誤った順序のとき(中心の駒を除く)
// =1 : 中心の駒
int tenkai[]; // =0 : 未展開（葉）の状態
// =1 : 展開済みの状態
double hukasa[][]; // [i][0] : 状態のの深さ
// [i][1] : 評価関数の値
double max_depth = 10; // 最大探索深さ
JComboBox choice;
JTextField trial, depth;
S_Eight dt = this;
/******************/
/* コンストラクタ */
/******************/
S_Eight(String name)
{
// JFrameクラスのコンストラクタ（Windowのタイトルを引き渡す）
super(name);
// Windowの大きさ
setSize(300, 200);
// レイアウトの変更
Container cp = getContentPane();
cp.setBackground(Color.white);
JPanel jp = new JPanel();
jp.setLayout(new GridLayout(4, 2, 5, 10));
jp.setBackground(Color.white);
cp.add(jp);
Font f = new Font("TimesRoman", Font.BOLD, 20);
// スクロールリスト & テキストフィールド
JLabel fill1 = new JLabel("最大試行回数");
fill1.setFont(f);
jp.add(fill1);
trial = new JTextField("1000", 10);
trial.setBackground(Color.white);
trial.setFont(f);
jp.add(trial);
JLabel fill2 = new JLabel("探索方法");
fill2.setFont(f);
jp.add(fill2);
choice = new JComboBox ();
choice.setBackground(Color.white);
choice.setFont(f);
choice.addItem("横型探索");
choice.addItem("縦型探索");
choice.addItem("評価関数１");
choice.addItem("評価関数２");
jp.add(choice);
choice.addItemListener(this);
JLabel fill3 = new JLabel("最大探索深さ");
fill3.setFont(f);
jp.add(fill3);
depth = new JTextField("10", 10);
depth.setBackground(Color.white);
depth.setFont(f);
jp.add(depth);
// OK ボタンの設定
JLabel fill4 = new JLabel(" スタート？");
fill4.setFont(f);
jp.add(fill4);
JButton bt = new JButton("OK");
bt.setFont(f);
bt.addMouseListener(new ClickMouse());
jp.add(bt);
// ウィンドウを表示
setVisible(true);
// イベントアダプタ
addWindowListener(new WinEnd());
}
/******************************/
/* 上，左，下，右の余白の設定 */
/******************************/
public Insets getInsets()
{
return new Insets(50, 20, 20, 20);
}
/******************************/
/* チョイスコントロールの処理 */
/******************************/
public void itemStateChanged(ItemEvent e)
{
if (e.getItemSelectable() == choice) {
s_method = choice.getSelectedIndex() + 1;
}
}
/********************************/
/* OKボタンが押されたときの処理 */
/********************************/
class ClickMouse extends MouseAdapter
{
/************************************/
/* マウスがクリックされたときの処理 */
/************************************/
public void mouseClicked(MouseEvent e)
{
int i1;
// 領域の確保
MAX = Integer.parseInt(trial.getText());
max_depth = Integer.parseInt(depth.getText());
g = new int [3][3];
kodomo = new int [MAX][2][4];
oya = new int [MAX];
pattern = new int [MAX][3][3];
tenkai = new int [MAX];
hukasa = new double [MAX][2];
// 初期設定
n_o_pattern = 0;
hukasa[0][0] = 0.0;
tenkai[0] = 0;
oya[0] = 0;
for (i1 = 0; i1 < 4; i1++)
kodomo[0][0][i1] = 0;
// ゴールの設定
g[0][0] = 1;
g[0][1] = 2;
g[0][2] = 3;
g[1][0] = 8;
g[1][1] = 0;
g[1][2] = 4;
g[2][0] = 7;
g[2][1] = 6;
g[2][2] = 5;
// 初期状態の設定
S_Initial initial = new S_Initial(dt);
}
}
/************/
/* 終了処理 */
/************/
class WinEnd extends WindowAdapter
{
public void windowClosing(WindowEvent e) {
System.exit(0);
}
}
}
/****************************/
/* クラスS_Initialの定義 */
/* （初期状態の入力） */
/****************************/
class S_Initial extends JFrame {
int err = 0; // エラーの有無
private int n; // 行・列の数
private S_Eight dt;
private S_Initial in = this;
JTextField a[][];
JLabel f[];
Error_p ep;
/*******************************************/
/* コンストラクタ */
/* dt_i : S_Eightクラスのオブジェクト */
/*******************************************/
S_Initial(S_Eight dt_i)
{
// Frameクラスのコンストラクタの呼び出し
super("初期状態");
// レイアウトの変更
n = 3;
dt = dt_i;
a = new JTextField [n][n];
f = new JLabel [n-1];
Container cp = getContentPane();
cp.setBackground(Color.white);
cp.setLayout(null);
JPanel jp = new JPanel();
jp.setBackground(Color.white);
cp.add(jp);
jp.setLayout(new BorderLayout(5, 10));
JPanel pn = new JPanel();
pn.setBackground(Color.white);
pn.setLayout(new GridLayout(n, n+1, 5, 10));
jp.add(pn, BorderLayout.NORTH);
Font fn = new Font("TimesRoman", Font.BOLD, 20);
// テキストフィールドの設定
int i1, i2;
for (i1 = 0; i1 < n; i1++) {
for (i2 = 0; i2 < n; i2++) {
a[i1][i2] = new JTextField(2);
a[i1][i2].setFont(fn);
pn.add(a[i1][i2]);
}
if (i1 < n-1) {
f[i1] = new JLabel();
pn.add(f[i1]);
}
}
// OK ボタンの設定
JButton bt = new JButton("OK");
bt.setFont(fn);
bt.addMouseListener(new ClickMouse());
pn.add(bt);
// メッセージパネルの追加
ep = new Error_p(this);
ep.setBackground(Color.white);
jp.add(ep, BorderLayout.CENTER);
// Windowサイズを設定
setSize(350, 250);
// ウィンドウを表示
setVisible(true);
Insets in = getInsets();
jp.setLocation(10, 10);
jp.setSize(350-in.left-in.right-20, 250-in.top-in.bottom-20);
// イベントアダプタ
addWindowListener(new WinEnd());
}
/********************************/
/* OKボタンが押されたときの処理 */
/********************************/
class ClickMouse extends MouseAdapter
{
/************************************/
/* マウスがクリックされたときの処理 */
/************************************/
public void mouseClicked(MouseEvent e)
{
int i1, i2, i3, i4, k, k1;
err = 0;
/*
入力データの処理
*/
for (i1 = 0; i1 < n && err == 0; i1++) {
for (i2 = 0; i2 < n && err == 0; i2++) {
if ((a[i1][i2].getText()).length() <= 0)
dt.pattern[0][i1][i2] = 0;
else
dt.pattern[0][i1][i2] = Integer.parseInt(a[i1][i2].getText());
if (dt.pattern[0][i1][i2] < 0 || dt.pattern[0][i1][i2] > 8)
err = 1;
else {
for (i3 = 0; i3 <= i1 && err == 0; i3++) {
k1 = (i3 == i1) ? i2 : n;
for (i4 = 0; i4 < k1 && err == 0; i4++) {
if (dt.pattern[0][i1][i2] == dt.pattern[0][i3][i4])
err = 1;
}
}
}
}
}
ep.repaint();
// 解を見つける
if (err == 0) {
in.setVisible(false);
Eight eight = new Eight(dt);
}
}
}
/************/
/* 終了処理 */
/************/
class WinEnd extends WindowAdapter
{
public void windowClosing(WindowEvent e) {
in.setVisible(false);
}
}
}
/**************************/
/* エラーメッセージの表示 */
/**************************/
class Error_p extends JPanel {
S_Initial in;
Error_p(S_Initial in1)
{
in = in1;
}
public void paintComponent (Graphics g)
{
super.paintComponent(g); // 親クラスの描画(必ず必要)
// フォントの設定
Font f = new Font("TimesRoman", Font.BOLD, 20);
g.setFont(f);
// エラーメッセージの出力
int x = 10;
int y = 25;
if (in.err == 0)
g.drawString(" ", x, y);
else {
g.setColor(Color.red);
g.drawString("*** Error ***", x, y);
g.setColor(Color.black);
}
}
}
/************************/
/* クラスEightの定義 */
/* （問題を解く） */
/************************/
class Eight extends JFrame {
private S_Eight dt;
private Eight et = this;
private JTextArea text;
/*******************************************/
/* コンストラクタ */
/* dt_i : S_Eightクラスのオブジェクト */
/*******************************************/
Eight(S_Eight dt_i)
{
// JFrameクラスのコンストラクタの呼び出し
super("８パズル");
// テキストエリアの設定
dt = dt_i;
Container cp = getContentPane();
cp.setBackground(Color.white);
JPanel jp = new JPanel();
cp.setLayout(null);
jp.setBackground(Color.white);
cp.add(jp);
Font f = new Font("TimesRoman", Font.BOLD, 20);
text = new JTextArea("", 15, 25);
text.setFont(f);
JScrollPane sp = new JScrollPane(text);
jp.add(sp);
// Windowサイズを設定
setSize(470, 450);
// ウィンドウを表示
setVisible(true);
Insets in = getInsets();
jp.setLocation(10, 10);
jp.setSize(470-in.left-in.right-20, 450-in.top-in.bottom-20);
// イベントアダプタ
addWindowListener(new WinEnd());
// 実行
solve();
}
/********************/
/* ８－パズルを解く */
/********************/
public void solve()
{
int i1, i2, i3, pt = 0, rl = 0, sw = 0;
int ptn[][] = new int [3][3];
int ptn1[][] = new int [3][3];
int rl1[] = new int [1];
double pf, pf1;
/*
問題解決
*/
while (sw == 0) {
// 規則の探索
pf = 99999.0;
for (i1 = 0; i1 <= dt.n_o_pattern; i1++) {
if (dt.tenkai[i1] == 0) {
pf1 = fire(i1, rl1, ptn1); // 適用規則と評価関数の計算
if (pf1 > 10000.0)
dt.tenkai[i1] = 1;
else {
if (pf1 < pf) { // 最小評価関数規則の選択 */
pf = pf1; // 評価関数値
pt = i1; // 展開パターン
rl = rl1[0]; // 適用規則
for (i2 = 0; i2 < 3; i2++) { // 規則適用後のパターン
for (i3 = 0; i3 < 3; i3++)
ptn[i2][i3] = ptn1[i2][i3];
}
}
}
}
}
// 適用可能規則なし
if (pf > 10000.0) {
sw = 1;
text.insert("解決できませんでした！\n", 0);
}
// 規則の適用
else {
dt.n_o_pattern += 1;
// 制限回数超過
if (dt.n_o_pattern >= dt.MAX) {
sw = 1;
text.insert("解決できませんでした！\n", 0);
}
// 制限回数以内
else {
dt.oya[dt.n_o_pattern] = pt;
dt.hukasa[dt.n_o_pattern][0] = dt.hukasa[pt][0] + 1.0;
dt.hukasa[dt.n_o_pattern][1] = pf;
dt.tenkai[dt.n_o_pattern] = 0;
for (i1 = 0; i1 < 4; i1++)
dt.kodomo[dt.n_o_pattern][0][i1] = 0;
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++)
dt.pattern[dt.n_o_pattern][i1][i2] = ptn[i1][i2];
}
sw = 1;
for (i1 = 0; i1 < 4 && sw > 0; i1++) {
if (dt.kodomo[pt][0][i1] == 0) {
sw = 0;
dt.kodomo[pt][0][i1] = rl;
dt.kodomo[pt][1][i1] = dt.n_o_pattern;
}
}
// 目標達成のチェック
sw = 1;
for (i1 = 0; i1 < 3 && sw > 0; i1++) {
for (i2 = 0; i2 < 3 && sw > 0; i2++) {
if (ptn[i1][i2] != dt.g[i1][i2])
sw = 0;
}
}
// 目標達成
if (sw > 0) {
pt = dt.n_o_pattern;
text.insert("成功！！\n", 0);
while (pt > 0) {
p_pattern(pt);
pt = dt.oya[pt];
}
p_pattern(0);
}
}
}
}
}
/*****************************************/
/* 適用可能な規則を選ぶ */
/* pt : パターン番号 */
/* rl : 適用規則番号 */
/* ptn[i][j] : 規則適用後のパターン */
/* return : 評価関数の値 */
/* 有効な規則の集合 */
/* 13 : IF [0][0]=0 THEN RIGHT */
/* 14 : IF [0][0]=0 THEN DOWN */
/* 21 : IF [0][1]=0 THEN LEFT */
/* 23 : IF [0][1]=0 THEN RIGHT */
/* 24 : IF [0][1]=0 THEN DOWN */
/* 31 : IF [0][2]=0 THEN LEFT */
/* 34 : IF [0][2]=0 THEN DOWN */
/* 42 : IF [1][0]=0 THEN UP */
/* 43 : IF [1][0]=0 THEN RIGHT */
/* 44 : IF [1][0]=0 THEN DOWN */
/* 51 : IF [1][1]=0 THEN LEFT */
/* 52 : IF [1][1]=0 THEN UP */
/* 53 : IF [1][1]=0 THEN RIGHT */
/* 54 : IF [1][1]=0 THEN DOWN */
/* 61 : IF [1][2]=0 THEN LEFT */
/* 62 : IF [1][2]=0 THEN UP */
/* 64 : IF [1][2]=0 THEN DOWN */
/* 72 : IF [2][0]=0 THEN UP */
/* 73 : IF [2][0]=0 THEN RIGHT */
/* 81 : IF [2][1]=0 THEN LEFT */
/* 82 : IF [2][1]=0 THEN UP */
/* 83 : IF [2][1]=0 THEN RIGHT */
/* 91 : IF [2][2]=0 THEN LEFT */
/* 92 : IF [2][2]=0 THEN UP */
/* 最初の数字：空白の位置 */
/* 次の数字 ：空白を移動する方向 */
/*****************************************/
public double fire(int pt, int [] rl,int [][] ptn)
{
int i1, i2, i3, i4, k1, sw;
int ptn1[][] = new int [3][3];
double pf;
double pf1[] = new double [1];
pf = 99999.0;
for (i1 = 1; i1 <= 9; i1++) {
for (i2 = 1; i2 <= 4; i2++) {
k1 = 10 * i1 + i2;
sw = rule(pt, pf1, k1, ptn1);
if (sw > 0) {
if (pf1[0] < pf) {
pf = pf1[0];
rl[0] = k1;
for (i3 = 0; i3 < 3; i3++) {
for (i4 = 0; i4 < 3; i4++)
ptn[i3][i4] = ptn1[i3][i4];
}
}
}
}
}
return pf;
}
/**********************************************************/
/* 規則が適用か否かを調べ、かつ、適用後の評価関数値を計算 */
/* pt : パターン番号 */
/* pf : 評価関数の値 */
/* rl : 適用規則番号 */
/* ptn[i][j] : 規則適用後のパターン */
/* return : =0 : 適用不可能 */
/* =1 : 適用可能 */
/**********************************************************/
public int rule(int pt, double [] pf, int rl, int [][] ptn)
{
int i1, i2, i3, k1, k2, k3, sw;
double pi[] = new double [1];
sw = 1;
/*
既に適用した規則か否かのチェック
*/
for (i1 = 0; i1 < 4 && sw > 0; i1++) {
if (rl == dt.kodomo[pt][0][i1])
sw = 0;
}
/*
物理的適用可能性のチェック
*/
if (sw > 0) {
k1 = rl / 10;
k2 = rl % 10;
sw = -1;
for (i1 = 0; i1 < 3 && sw < 0; i1++) {
for (i2 = 0; i2 < 3 && sw < 0; i2++) {
if (dt.pattern[pt][i1][i2] == 0) {
sw = 1;
k3 = 3 * i1 + i2 + 1;
if (k1 != k3) // 位置が不適当
sw = 0;
else { // 移動方向のチェック
if (i1 == 0 && k2 == 2)
sw = 0;
if (i1 == 2 && k2 == 4)
sw = 0;
if (i2 == 0 && k2 == 1)
sw = 0;
if (i2 == 2 && k2 == 3)
sw = 0;
}
}
}
}
/*
規則の適用
*/
if (sw > 0) {
apply(pt,rl,ptn);
/*
既に展開したパターンに同じものがあるか否かのチェック
*/
for (i1 = 0; i1 <= dt.n_o_pattern && sw > 0; i1++) {
sw = 0;
for (i2 = 0; i2 < 3 && sw == 0; i2++) {
for (i3 = 0; i3 < 3 && sw == 0; i3++) {
if (ptn[i2][i3] != dt.pattern[i1][i2][i3])
sw = 1;
}
}
if (sw == 0 && dt.s_method == 2) {
if (dt.hukasa[i1][0] > dt.hukasa[pt][0]+1.0)
sw = 1;
}
}
/*
評価関数の計算
*/
if (sw > 0) {
sw = cal_pf(pt, pi, ptn);
pf[0] = pi[0];
}
}
}
return sw;
}
/*****************************************/
/* 与えられた規則を適用する */
/* pt : パターン番号 */
/* rl : 適用規則番号 */
/* ptn : 規則適用後のパターン */
/*****************************************/
public void apply(int pt, int rl, int [][] ptn)
{
int i1, i2, j1, j2, k1 = 0, k2 = 0, l1, l2;
/*
適用前のパターン
*/
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++)
ptn[i1][i2] = dt.pattern[pt][i1][i2];
}
/*
規則適用後のパターン
*/
l1 = rl / 10;
l2 = rl % 10;
// 適用前の空白の位置
j1 = (l1 - 1) / 3;
j2 = (l1 - 1) % 3;
// 適用後の空白の位置
switch (l2) {
case 1 :
k1 = j1;
k2 = j2 - 1;
break;
case 2 :
k1 = j1 - 1;
k2 = j2;
break;
case 3 :
k1 = j1;
k2 = j2 + 1;
break;
case 4 :
k1 = j1 + 1;
k2 = j2;
break;
}
/*
適用後のパターン
*/
ptn[j1][j2] = ptn[k1][k2];
ptn[k1][k2] = 0;
}
/**************************************************************/
/* 評価関数の値を計算する */
/* pt : パターン番号 */
/* pf : 評価関数の値 */
/* ptn[i][j] : 規則適用後のパターン(縦型、横型では未使用)*/
/* return : =0 : 適用不可能(縦型探索で深さ制限を越えた時 */
/* =1 : 適用可能(その他) */
/**************************************************************/
public int cal_pf(int pt, double [] pf,int [][] ptn)
{
int i1, i2, i3, i4, j1, j2, kyori, pos, seq, ssw, sw;
sw = 1;
switch (dt.s_method) {
/*
横型探索
*/
case 1 :
pf[0] = dt.hukasa[pt][0];
break;
/*
縦型探索
*/
case 2 :
if (dt.hukasa[pt][0] < dt.max_depth)
pf[0] = -dt.hukasa[pt][0];
else
sw = 0;
break;
/*
深さ＋目標状態と異なる位置の数
*/
case 3 :
pos = 0;
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
if (ptn[i1][i2] != 0) {
if (ptn[i1][i2] != dt.g[i1][i2])
pos += 1;
}
}
}
pf[0] = dt.hukasa[pt][0] + (double)pos;
break;
/*
h(n) = p(n) + 3s(n)
p(n) : 目標状態からの距離
s(n) : =0 : 次の駒が正しい順序の時(中心の駒を除く)
=2 : 次の駒が誤った順序の時(中心の駒を除く)
=1 : 中心の駒
*/
case 4 :
kyori = 0;
for (i1 = 0; i1 < 3; i1++) {
for (i2 = 0; i2 < 3; i2++) {
if (ptn[i1][i2] != 0) {
// 距離の計算
ssw = 0;
for (i3 = 0; i3 < 3 && ssw == 0; i3++) {
for (i4 = 0; i4 < 3 && ssw == 0; i4++) {
if (ptn[i1][i2] == dt.g[i3][i4]) {
kyori += (Math.abs(i3-i1) + Math.abs(i4-i2));
ssw = 1;
}
}
}
// 次の駒の位置のチェック
seq = 2;
if (i1 == 1 && i2 == 1) // 中心の駒
seq = 1;
else { // 中心以外の駒
if (i1 == 0) {
if (i2 == 2) {
j1 = 1;
j2 = 2;
}
else {
j1 = i1;
j2 = i2 + 1;
}
}
else {
if (i1 == 1) {
if (i2 == 0) {
j1 = 0;
j2 = 0;
}
else {
j1 = 2;
j2 = 2;
}
}
else {
if (i2 == 0) {
j1 = 1;
j2 = 0;
}
else {
j1 = i1;
j2 = i2 - 1;
}
}
}
if (ptn[i1][i2] == 8) {
if (ptn[j1][j2] == 1)
seq = 0;
}
else {
if (ptn[j1][j2] == ptn[i1][i2]+1)
seq = 0;
}
}
kyori += (3 * seq);
}
}
}
pf[0] = dt.hukasa[pt][0] + (double)kyori;
break;
/*
その他
*/
default :
pf[0] = dt.hukasa[pt][0];
break;
}
return sw;
}
/****************************/
/* 与えられたパターンの出力 */
/* pt : パターン番号 */
/****************************/
public void p_pattern(int pt)
{
int i1, i2;
String str;
for (i1 = 2; i1 >= 0; i1--) {
str = " ";
for (i2 = 0; i2 < 3; i2++)
str += Integer.toString(dt.pattern[pt][i1][i2]);
str += "\n";
text.insert(str, 0);
}
str = "状態番号 ";
str += Integer.toString(pt);
str += " 深さ＝ ";
str += Integer.toString((int)dt.hukasa[pt][0]);
str += " 評価＝ ";
str += Integer.toString((int)dt.hukasa[pt][1]);
text.insert(str + "\n", 0);
}
/************/
/* 終了処理 */
/************/
class WinEnd extends WindowAdapter
{
public void windowClosing(WindowEvent e) {
et.setVisible(false);
}
}
}