スポンサーサイト

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

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

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

バックトラック法 (手順を進められるだけ進めていき、行き詰ったら一つ前に戻ってやり直す) によるプログラム。ここでは、再帰呼び出しを使わないプログラム例を紹介します。再帰呼び出しによる C 言語のプログラムは、参考 URL に挙げたメディアチップスさんのウェブサイトにあります。

Windows XP+MinGW (gcc version 4.5.2) で動作確認。

#include <stdio.h>

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

/* 盤面を表示する */
void display(const int board[])
{
  int i;
  for( i = 0; i < CELLS; i++ ) {
    printf("%d", board[i]);
    if( i % NUMS == NUMS - 1 ) {
      printf("\n");
    }
    else {
      printf(",");
    }
  }
  printf("\n");
}

/* 数字が重複しているかどうか */
int isDuplicate(const int board[], int p, int k)
{
  int i, j, col, row, bRow, bCol;

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

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

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

  /* 重複していない */
  return 0;
}

/* 全ての解答を求める */
void solve(const int board_org[])
{
  int board[CELLS];
  int i, k, p;

  /* 盤面のコピー */
  for( i = 0; i < CELLS; i++ ) {
    board[i] = board_org[i];
  }

  p = 0;  /* 位置 */
  while(p >= 0) {

    /* ある解答が見つかった */
    if( p >= CELLS ) {
      /* 解答の表示 */
      display(board);
      /* 別の解答を探しに戻る */
      p--;
      while( board_org[p] != EMPTY ) { p--; }
    }

    /* 出題時点で数字が書かれていないマスのとき */
    if( board_org[p] == EMPTY ) {
      k = board[p];  
      if( k == EMPTY ) { k = 1; }
      while( isDuplicate(board, p, k) ) { k++; }
      /* 行き詰ったら戻ってやり直し */
      if( k > NUMS ) {
        board[p] = EMPTY;
        p--;
        while( board_org[p] != EMPTY ) { p--; }
      }
      /* マスに数字を入れて先に進む */
      else {
        board[p] = k;
        p++;
      }
    }
    /* 出題時点で数字が書かれたマスは素通り */
    else {
      p++;
    }
  }
}

int main()
{
  int 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);

  return 0;
}

参考 URL

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

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

プロフィール

よしいず

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

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

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

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

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

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