数独 with バックトラック法。

2006-04-29 14:01:00 | Prog...

数独をバックトラック法で解くプログラムを作ってみた。

数独。のエントリを書いて、ところでこのバックトラック法ってどんなんだろうとググッてみたら、すんごい単純なアルゴリズムなんですね（＾＾；
まぁ、再起呼び出しする必要があるところがちょこっと難しいぐらいで。

ということで、早速Perlを使って実装してみました。（CでもJavaでもないｗ　ちなみに、Javaはやればやるほど魅力がなくなったので、止めました。どうやったらあんな中途半端で汚くて使えなくて重たくて（※実行し始めるまでが遅すぎ）どうしようもない言語が設計できるんだか・・・　Ruby（これはホントに美しいですね）を見習えとは言わないから、せめてPerlぐらいは見習って欲しいものです）

で、実行してみたのですが、これが思いのほか早くてビックリ。
ほとんど総当りみたいなもんだろうと思っていたので、入力してから平均１分、悪ければ５分以上かかるかなぁ、と思っていたのですが、ためしに解かした３題は、どれも１秒かからないぐらいで解いてしまった・・・
思ったよりも試行錯誤の数が少なくて済んでしまうのかもしれないです。（解析するのはめんどいけど・・・）

暇があれば練習もかねてTkインタフェースのGUI版も作ってみたいですが、とりあえずはCUI版のソースは以下。

==＞ SudokuMatrix.pm ＜==
package SudokuMatrix;

#--------------------------------------------------
# SudokuMatrix 数独の表クラス
#
# =フィールド=
# なし
# 代わりに、オブジェクト自体が9*9の２次元配列
#
# =メソッド=
# $obj new(void); オブジェクトを作成
# $obj オブジェクト
#
# $obj init(void); オブジェクトを初期化
# $obj オブジェクト
#
# void set($i, $j, $num); 数字をセット
# $i 行（１～９）
# $j 列（１～９）
# $num 数字（１～９）
#
# $num get($i, $j); 数字を取得
# $num 数字（１～９）ただし、未定義の場合は０
# $i 行（１～９）
# $j 列（１～９）
#
# void set_matrix($matrix); ２次元配列で数字をセット
# $matrix 9*9の２次元配列のリファレンス
#
# $bool check($i, $j); i行j列の周りで重なりがないかチェック
# $bool 重なりがなければ１、あれば０
# $i 行（１～９）
# $j 列（１～９）
#--------------------------------------------------

sub new{

    my $class = shift @_;

    my $obj = bless [], $class;

    $obj-＞init();

}

sub init{

    my $self = shift @_;

    foreach my $i (1..9){

        foreach my $j (1..9){

            $self-＞[$i-1][$j-1] = 0;

        }

    }

    return $self;

}

sub set{

    my ($self, $i, $j, $num) = @_;

    $self-＞[$i-1][$j-1] = $num;

}

sub get{

    my ($self, $i, $j) = @_;

    return $self-＞[$i-1][$j-1];

}

sub set_matrix{

    my ($self, $matrix) = @_;

    foreach my $i (1..9){

        foreach my $j (1..9){

            $self-＞[$i-1][$j-1] = $matrix-＞[$i-1][$j-1];

        }

    }

}

sub check{

    my ($self, $i, $j) = @_;

    --$i; --$j;

    my $num = $self-＞[$i][$j];

    #横のライン

    foreach(0..8){

        if(($_ != $j) and ($num == $self-＞[$i][$_])){

            return 0;

        }

    }

    #縦のライン

    foreach(0..8){

        if(($_ != $i) and ($num == $self-＞[$_][$j])){

            return 0;

        }

    }

    #箱の中

    my $rel_x = $i % 3; #相対座標

    my $rel_y = $j % 3;

    my $base_x = $i - $rel_x;   #オフセット

    my $base_y = $j - $rel_y;

    foreach(1..2){  #右斜め下へ走査

        ++$rel_x; $rel_x %= 3;

        ++$rel_y; $rel_y %= 3;

        if($num == $self-＞[$base_x + $rel_x][$base_y + $rel_y]){

            return 0;

        }

    }

    ++$rel_x; $rel_x %= 3;

    ++$rel_y; $rel_y %= 3;

    foreach(1..2){  #右斜め上へ走査

        ++$rel_x; $rel_x %= 3;

        $rel_y += 2; $rel_y %= 3;

        if($num == $self-＞[$base_x + $rel_x][$base_y + $rel_y]){

            return 0;

        }

    }

    return 1;

}

1;

==＞ Backtrack.pm ＜==
package Backtrack;

#--------------------------------------------------
# Backtrack バックトラック法による解法アルゴリズム
#
# =フィールド=
# matrix SudokuMatrixクラスのオブジェクト
# katei 仮定しているセルの配列
# nokori 残っているセルの配列
#
# =メソッド=
# $obj new($matrix); 新しいオブジェクトを作成
# $obj オブジェクト
# $matrix SudokuMatrixクラスのオブジェクト
#
# $obj init($matrix); オブジェクトの初期化
# $obj オブジェクト
# $matrix SudokuMatrixクラスのオブジェクト
#
# $bool backtrack(void); バックトラック法を用いる
# $bool 成功すれば1、失敗すれば0を返す
#--------------------------------------------------

use SudokuMatrix;

sub new{

    my ($class, $matrix) = @_;

    my $obj = bless {}, $class;

    $obj-＞init($matrix);

}

sub init{

    my ($self, $matrix) = @_;

    $self-＞{matrix} = $matrix;

    $self-＞{katei} = [];

    $self-＞{nokori} = [];

    foreach my $i (1..9){

        foreach my $j (1..9){

            if($matrix-＞get($i, $j) == 0){

                push @{$self-＞{nokori}}, [$i, $j];

            }

        }

    }

    return $self;

}

sub backtrack{

    my $self = shift @_;

    my $matrix = $self-＞{matrix};

    my $katei = $self-＞{katei};

    my $nokori = $self-＞{nokori};

    #ターゲットの取得

    #残りがなければ1を出力して終了

    my $target;

    if(@$nokori){

        $target = shift @$nokori;

    }else{

        return 1;

    }

    #ターゲットの数字を１つ上げる

    my $num = $matrix-＞get(@$target);

    $num = ($num + 1) % 10;

    $matrix-＞set(@$target, $num);

    #全部試した場合は一つ前に戻る

    #前にもどれなければ0を出力して終了

    if($num == 0){

        unshift @$nokori, $target;

        if(@$katei){

            unshift @$nokori, pop @$katei;

        }else{

            return 0;

        }

        return $self-＞backtrack();

    }

    #チェックをして、大丈夫なら次のセルへ

    #大丈夫でないなら次の数字へ

    if($matrix-＞check(@$target)){

        push @$katei, $target;

        return $self-＞backtrack();

    }else{

        unshift @$nokori, $target;

        return $self-＞backtrack();

    }

}

1;

==＞ CUI.pm ＜==
package CUI;

#--------------------------------------------------
# CUI CUI用のインターフェース
#
# =フィールド=
# silent オプションが指定さえていれば1
# help オプションが指定されていれば1
#
# =メソッド=
# $obj setup(void); 引数を解析してオブジェクトを作成
# $obj 新しいオブジェクト
#
# $matrix make_matrix(void); SudokuMatrixを作成
# $matrix SudokuMatrixクラスのオブジェクト
#
# void print_ans($matrix); 答えを出力
# $matrix SudokuMatrixクラスのオブジェクト
#
# void print_help(void); ヘルプを出力
#--------------------------------------------------

use SudokuMatrix;

$HELP = ＜＜END_OF_HELP;
sudoku 数独をバックトラック法で解くプログラム

数字は標準入力から9×9の行列で入力
各数字は1～9で、空欄には0を入力

=オプション=

 -s, --silent    冗長出力しない

 -h, --help  ヘルプを出力して終了

END_OF_HELP

sub setup{

    my $class = shift @_;

    my $obj = bless {

        silent =＞ 0,

        help =＞ 0,

    }, $class;

    foreach(@ARGV){

        if(/(-s|--silent)/){

            $obj-＞{silent} = 1;

        }

        if(/(-h|--help)/){

            $obj-＞{help} = 1;

        }

    }

    return $obj;

}

sub make_matrix{

    my $self = shift @_;

    unless($self-＞{silent}){

        print "数字を入力してください。\n";

    }

    my $matrix;

    foreach(1..9){

        my $str = ＜STDIN＞;

        chomp($str);

        my @num = split /\s*/, $str;

        push @$matrix, \@num;

    }

    my $obj = SudokuMatrix-＞new();

    $obj-＞set_matrix($matrix);

    return $obj;

}

sub print_ans{

    my ($self, $matrix) = @_;

    unless($self-＞{silent}){

        print "\n答え\n";

    }

    foreach my $i (1..9){

        foreach my $j (1..9){

            my $num =  $matrix-＞get($i, $j);

            print " $num";

        }

        print "\n";

    }

}

sub print_help{

    print $CUI::HELP;

}

1;

==＞ sudoku ＜==
#!/usr/bin/perl

#--------------------------------------------------
# sudoku 数独をバックトラック法で解く(CUI)
#--------------------------------------------------

use SudokuMatrix;
use Backtrack;
use CUI;

my $prog = CUI-＞setup();

if($prog-＞{help}){

    $prog-＞print_help();

    exit;

}

my $matrix = $prog-＞make_matrix();
my $algo = Backtrack-＞new($matrix);

my $result = $algo-＞backtrack();

if($result){

    $prog-＞print_ans($matrix);

}
else{

    "答えが出ませんでした。\n";

}

	【gooブロガー・先着】dアカウント連携でdポイント2,000pt
	ブログを読むだけ。毎月の訪問日数に応じてポイント進呈
	【コメント募集中】goo blogスタッフの気になったニュース
	gooブロガーの今日のひとこと
	訪問者数に応じてdポイント最大1,000pt当たる！

日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

いもあらい。

プログラミングや哲学などについてのメモ。

数独 with バックトラック法。