スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ナンプレの解答を求めるプログラム Perl編

ナンプレ (ナンバープレース、数独) の解答を求める Perl によるプログラムの例。

バックトラック法によるプログラムの例。

Windows XP+ActivePerl 5.14.2 で動作確認。

use strict;
use warnings;

use constant ROWS  => 9;  # 盤面の行数
use constant COLS  => 9;  # 盤面の列数
use constant BROWS => 3;  # ブロックの行数
use constant BCOLS => 3;  # ブロックの列数
use constant CELLS => ROWS * COLS;  # 盤面のマスの数
use constant NUMS  => 9;  # 数字の種類 (1~9)
use constant EMPTY => 0;  # マスの空白は0で表す

# 盤面を表示する
sub display {
  my @board = @{$_[0]};

  for( my $i = 0; $i < CELLS; $i++ ) {
    print $board[$i];
    if( $i % NUMS == NUMS - 1 ) {
      print "\n";
    }
    else {
      print ",";
    }
  }
  print "\n";
}

# 数字が重複しているかどうか
sub isDuplicate {
  my @board = @{$_[0]};
  my $p = $_[1];
  my $k = $_[2];

  # 同じ行に k がある 
  my $col = $p % COLS;
  for(my $i = 0; $i < ROWS; $i++) {
    return 1 if( $board[$col+$i*COLS] == $k );
  }

  # 同じ列に k がある
  my $row = int($p / COLS);
  for(my $j = 0; $j < COLS; $j++) {
    return 1 if( $board[$j+$row*COLS] == $k );
  }

  # 同じブロックに k がある
  my $bRow = int($row / BROWS) * BROWS;
  my $bCol = int($col / BCOLS) * BCOLS;
  for(my $i = 0; $i < BROWS; $i++) {
    for(my $j = 0; $j < BCOLS; $j++) {
      return 1 if( $board[($bCol+$j)+($bRow+$i)*COLS] == $k );
    }
  }

  # 重複していない
  return 0;
}

# 全ての解答を求める
sub solve {
  my @board = @{$_[0]};
  my $p = $_[1];

  # ある解答が見つかった
  if( $p >= CELLS ) {
    &display(\@board);  # 解答の表示
    return;
  }

  # 出題時点で数字が書かれていないマスのとき
  if( $board[$p] == EMPTY ) {
    for( my $k = 1; $k <= NUMS; $k++ ) {
      if( ! &isDuplicate(\@board, $p, $k) ) {
        $board[$p] = $k;
        &solve(\@board, $p+1);
        $board[$p] = EMPTY;
      }
    }
  }
  # 出題時点で数字が書かれたマスは素通り
  else {
    &solve(\@board, $p+1);
  }
}

if( $0 eq __FILE__ ) {

  my @board_org = (
    0,0,9,4,0,0,1,0,0,
    4,0,3,0,0,0,0,5,0,
    0,6,0,0,0,3,0,0,0,
    0,0,6,0,4,0,7,2,0,
    3,0,0,2,0,8,0,0,5,
    0,2,1,0,0,0,3,0,0,
    0,0,0,9,7,0,0,0,0,
    7,4,0,0,0,0,6,0,9,
    0,0,2,0,0,1,4,0,0,
  );

  &solve(\@board_org, 0);
}

参考 URL

メディアチップス:数独(ナンバープレイス)

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。