数独

 投稿者：永野護  投稿日：2013年 8月30日(金)12時23分6秒
  お世話になります。
以下は数独を解くプログラムです。これを十進BASICで書き換えるとどのようになるのでしょうか。なおデータ入力部は不要です。
/* 数独を解くプログラム  Motonaga Asao  2006/11/18 */
/*                                      2006/11/19 */
/*                                      2006/11/21 */
/*                                      2006/12/16 */
/*                                      2009/01/12 */
#include <stdio.h>

#define True -1
#define False 0

#define N 9
#define N3 3

/* 盤の出力 */
int PrintBan(int Ban[N][N])
{
    int i,j;
    for(i=0;i<N;i++)
    {
        for(j=0;j<N;j++) printf("%5d",Ban[i][j]);
        putchar('\n');
    }
    putchar('\n');
    return 0;
}

/* 空いた枡を見つける */
int findBlank(int *x,int *y,int Ban[N][N])
{
    int i,j;
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
            if (Ban[i][j] == 0)
            {
                *x=i; *y=j;
                return True;
            }
    return False;
}

/* kを枡(x,y)に置けるか ? */
int isOkeru(int x,int y,int k,int Ban[N][N])
{
    int i,j;

    for(i=0;i<N;i++) if (Ban[i][y] == k) return False; /* 横に同じ数はないか */
    for(j=0;j<N;j++) if (Ban[x][j] == k) return False; /* 縦に同じ数はないか */
    for(i=0;i<N3;i++)                                  /* blockに同じ数はないか */
        for(j=0;j<N3;j++)
            if (Ban[N3*(x/N3)+i][N3*(y/N3)+j] == k) return False;
    return True;
}

/* これが問題のバックトラック */
int Try(int Ban[N][N])
{
    int x,y,k;
    if (findBlank(&x,&y,Ban)) /* 盤に空いた枡(x,y)があるか */
    for(k=1;k<=N;k++)
    {
        if(isOkeru(x,y,k,Ban)) /* 枡(x,y)にkを置けるか */
        {
            Ban[x][y] = k; /* 置けるなら置く */
            Try(Ban);      /* 次を確かめる */
            Ban[x][y] = 0; /* 枡(x,y)にkを置けないとして別の置き方はないか */
        }
    }
    else
    {
        printf("Solution\n"); /* 解が見つかった */
        PrintBan(Ban);
    }
    return 0;
}

int main(int argc,char *argv[])
{
    int i,j,Ban[N][N];
    FILE *stream;

    if (argc != 2)
    {
        printf("\nusage : Sudoku filename\n\n");
        return 1;
    }
    if((stream = fopen(argv[1],"r")) == NULL)
    {
        printf("%s がありません。\n",argv[1]);
        return 1;
    }
    for (i=0;i<N;i++)
        for(j=0;j<N;j++) fscanf(stream,"%d",&Ban[i][j]);
    fclose(stream);
    printf("Problem\n");
    PrintBan(Ban);
    Try(Ban);
    return 0;
}

 		 

Re: 数独

 投稿者：山中和義  投稿日：2013年 8月30日(金)19時31分51秒
  > No.3123[元記事へ]

永野護さんへのお返事です。

> 数独を解くプログラムです。これを十進BASICで書き換えるとどのようになるのでしょうか。

ほとんど機械的に同等な命令に置き換えてみました。


!数独を解くプログラム  Motonaga Asao  2009/01/12

LET N=9
LET N3=3

!盤の出力
SUB PrintBan(Ban(,))
   local i,j
   FOR i=0 TO N-1
      FOR j=0 TO N-1
         PRINT USING "###": Ban(i,j);
      NEXT j
      PRINT
   NEXT i
   PRINT
END SUB

!空いた枡を見つける
SUB findBlank(x,y,Ban(,), RET)
   local i,j
   FOR i=0 TO N-1
      FOR j=0 TO N-1
         IF Ban(i,j)=0 THEN
            LET x=i
            LET y=j
            LET RET=-1
            EXIT SUB
         END IF
      NEXT j
   NEXT i
   LET RET=0
END SUB

!kを枡(x,y)に置けるか ?
SUB isOkeru(x,y,k,Ban(,), RET)
   local i,j
   FOR i=0 TO N-1
      IF Ban(i,y)=k THEN
         LET RET=0 ! 横に同じ数はないか
         EXIT SUB
      END IF
   NEXT i
   FOR j=0 TO N-1
      IF Ban(x,j)=k THEN
         LET RET=0 !縦に同じ数はないか
         EXIT SUB
      END IF
   NEXT j
   FOR i=0 TO N3-1 !blockに同じ数はないか
      FOR j=0 TO N3-1
         IF Ban(N3*INT(x/N3)+i,N3*INT(y/N3)+j)=k THEN
            LET RET=0
            EXIT SUB
         END IF
      NEXT j
   NEXT i
   LET RET=-1
END SUB

!これが問題のバックトラック
SUB Try(Ban(,))
   local x,y,k
   CALL findBlank(x,y,Ban, RET) !盤に空いた枡(x,y)があるか
   IF RET<>0 THEN
      FOR k=1 TO N
         CALL isOkeru(x,y,k,Ban, RET) !枡(x,y)にkを置けるか
         IF RET<>0 THEN
            LET Ban(x,y)=k !置けるなら置く
            CALL Try(Ban) !次を確かめる
            LET Ban(x,y)=0 !枡(x,y)にkを置けないとして別の置き方はないか
         END IF
      NEXT k
   ELSE
      PRINT "Solution" !解が見つかった
      CALL PrintBan(Ban)
   END IF
END SUB


DATA 0,0,0, 0,7,0, 9,4,0 !初期配置
DATA 0,7,0, 0,9,0, 0,0,5
DATA 3,0,0, 0,0,5, 0,7,0

DATA 0,8,7, 4,0,0, 1,0,0
DATA 4,6,3, 0,8,0, 0,0,0
DATA 0,0,0, 0,0,7, 0,8,0

DATA 8,0,0, 7,0,0, 0,0,0
DATA 7,0,0, 0,0,0, 0,2,8
DATA 0,5,0, 2,6,8, 0,0,0

DIM Ban(0 TO N-1,0 TO N-1)
MAT READ Ban

PRINT "Problem"
CALL PrintBan(Ban)
CALL Try(Ban)

END


実行結果

Problem
  0  0  0  0  7  0  9  4  0
  0  7  0  0  9  0  0  0  5
  3  0  0  0  0  5  0  7  0
  0  8  7  4  0  0  1  0  0
  4  6  3  0  8  0  0  0  0
  0  0  0  0  0  7  0  8  0
  8  0  0  7  0  0  0  0  0
  7  0  0  0  0  0  0  2  8
  0  5  0  2  6  8  0  0  0

Solution
  2  1  5  8  7  6  9  4  3
  6  7  8  3  9  4  2  1  5
  3  4  9  1  2  5  8  7  6
  5  8  7  4  3  2  1  6  9
  4  6  3  9  8  1  7  5  2
  1  9  2  6  5  7  3  8  4
  8  2  6  7  4  3  5  9  1
  7  3  4  5  1  9  6  2  8
  9  5  1  2  6  8  4  3  7

 		 

数独

 投稿者：永野護  投稿日：2013年 8月31日(土)17時24分38秒
  丁寧な回答に感謝します。お忙しい折お手数をおかけしました。
大変助かりました。
敬具 		 

戻る