新しく発言する  EXIT  インデックスへ

パズル「数独」(ヒントつきプレイモード)


  パズル「数独」(ヒントつきプレイモード) 山中和義 2008/05/09 19:06:15  (修正1回)
  つづき 山中和義 2008/05/09 19:07:12  (修正1回)
  │└つづき 山中和義 2008/05/09 19:08:40  (修正1回)
  │ └つづき 山中和義 2008/05/11 20:53:30 
  !9×9数独をプログラムで解く 山中和義 2008/05/12 13:57:38  (修正1回)
   └数独を解く!数独ソルバー 片山博文MZ 2008/08/04 13:11:52 

  パズル「数独」(ヒントつきプレイモード) 山中和義 2008/05/09 19:06:15  (修正1回)  ツリーへ
パズル「数独」(ヒントつきプレイモード)  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2008/05/09 19:06:15 ** この記事は1回修正されてます
!確定/未確定:マスを左クリックすると、プロンプト画面が表示される。
! 確定へ:候補の数字を入力
! 未確定へ:0を入力
! キャンセル:Enterのみ入力
!終了:右クリック


!SET bitmap SIZE 501,501

SET WINDOW 0,11,11,0 !表示領域
SET TEXT JUSTIFY "center","half" !配置基準

DIM m(9,9)
RESTORE 10
MAT READ m !データの読み込み


DO
mouse poll mx,my,left,right

LET ix=INT(mx) !マスに換算する
LET iy=INT(my)

SET DRAW mode hidden !ちらつき防止の開始
CLEAR


!解法2:数字の入る「場所の候補」に着目する
DIM m4(9,9)
FOR k=1 TO 9
MAT m4=ZER

FOR x=1 TO 9 !排他的領域を得る
FOR y=1 TO 9
IF m(y,x)<>0 THEN LET m4(y,x)=k !候補から削除する

IF ABS(m(y,x))=k THEN !同じ数字は、列と行とブロックには入らない
FOR yy=1 TO 9 !列
LET m4(yy,x)=k !候補から削除する
NEXT yy
FOR xx=1 TO 9 !行
LET m4(y,xx)=k
NEXT xx
LET Bx=ToBlock(x) !ブロック
LET By=ToBlock(y)
FOR xx=1 TO 3
FOR yy=1 TO 3
LET m4(By+yy,Bx+xx)=k
NEXT yy
NEXT xx
END IF
NEXT y
NEXT x

!MAT PRINT USING "## ## ## ## ## ## ## ## ##": m4 !debug
!PRINT !debug

FOR x=1 TO 9 !列
LET c=9 !その個数
FOR y=1 TO 9
IF m4(y,x)>0 THEN LET c=c-1 ELSE LET yy=y
NEXT y
IF c=1 THEN CALL box(x,yy,k) !※列、行、ブロックで1つの場合は、確定可能である
NEXT x

FOR y=1 TO 9 !行
LET c=9 !その個数
FOR x=1 TO 9
IF m4(y,x)>0 THEN LET c=c-1 ELSE LET xx=x
NEXT x
IF c=1 THEN CALL box(xx,y,k) !※列、行、ブロックで1つの場合は、確定可能である
NEXT y

FOR x=1 TO 3 !ブロック
FOR y=1 TO 3
LET c=9 !その個数
FOR i=1 TO 3
FOR j=1 TO 3
LET y1=(y-1)*3+j
LET x1=(x-1)*3+i
IF m4(y1,x1)>0 THEN
LET c=c-1
ELSE
LET xx=x1
LET yy=y1
END IF
NEXT j
NEXT i
IF c=1 THEN CALL box(xx,yy,k) !※列、行、ブロックで1つの場合は、確定可能である
NEXT y
NEXT x

NEXT k
  つづき 山中和義 2008/05/09 19:07:12  (修正1回)  ツリーへ
Re: パズル「数独」(ヒントつきプレイモード)  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2008/05/09 19:07:12 ** この記事は1回修正されてます
つづき


!解法1:マスに入る「数字の候補」に着目する
FOR x=1 TO 9 !未確定のマスに対して
FOR y=1 TO 9
IF m(y,x)=0 THEN

LET t$=num$(x,y) !候補を求める

LET c=9 !その個数
FOR i=1 TO 9
IF t$(i:i)=" " THEN LET c=c-1 ELSE LET k=i
NEXT i
IF c>0 THEN !※列、行、ブロックで1つの場合は、確定可能である
IF c=1 THEN CALL box(x,y,k) !そのマスを示す

SET TEXT COLOR 4 !候補を3x3表示する
SET TEXT HEIGHT 0.25
FOR i=1 TO 3
FOR j=1 TO 3
LET k=i+(j-1)*3
PLOT TEXT ,AT x+i*0.3-0.1,y+j*0.3-0.1: t$(k:k)
NEXT j
NEXT i
ELSE
CALL box(x,y,1) !エラー「候補がありません。」
END IF

!PRINT y;x;t$;c !debug

END IF
NEXT y
NEXT x


!確定の「数」(初期値/入力値)の表示
FOR x=1 TO 9
FOR y=1 TO 9
LET k=m(y,x)
IF k<>0 THEN
IF k>0 THEN LET c=1 ELSE LET c=2 ! !黒/青
CALL putc(x,y,c,ABS(k))
END IF
NEXT y
NEXT x


!盤の表示
SET LINE COLOR 1 !黒
FOR x=1 TO 10 !縦線
IF MOD(x,3)=1 THEN SET LINE width 3 ELSE SET LINE width 1
PLOT LINES: x,1; x,10
NEXT x
FOR y=1 TO 10 !横線
IF MOD(y,3)=1 THEN SET LINE width 3 ELSE SET LINE width 1
PLOT LINES: 1,y; 10,y
NEXT y

SET DRAW mode explicit !ちらつき防止の終了
  │└つづき 山中和義 2008/05/09 19:08:40  (修正1回)  ツリーへ
Re: つづき  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2008/05/09 19:08:40 ** この記事は1回修正されてます
つづき


!「数」の入力
IF left=1 THEN !左クリックなら

IF ix<1 OR ix>9 OR iy<1 OR iy>9 THEN
ELSE !盤内なら
IF m(iy,ix)<=0 THEN !入力できるマスなら
SET LINE width 3 !プロンプト
SET LINE COLOR 2
PLOT LINES: ix,iy; ix+1,iy; ix+1,iy+1; ix,iy+1; ix,iy

INPUT PROMPT "数字を入力してください。": a$

IF a$<>"" THEN !キャンセル以外なら
IF a$="0" THEN !元に戻す場合
LET m(iy,ix)=0 !未確定へ
ELSE !確定する場合
LET t$=num$(ix,iy) !整合性を確認する
FOR i=1 TO 9
IF a$=t$(i:i) THEN !候補にあれば
LET m(iy,ix)=-i !※負
EXIT FOR
END IF
NEXT i
IF i>9 THEN PRINT "不正な数字です。"
END IF
END IF
ELSE
PRINT "ここには入力できません。"
END IF
END IF

END IF


LET flg=1 !全マスが確定しているか確認する
FOR x=1 TO 9
FOR y=1 TO 9
IF m(y,x)=0 THEN LET flg=0
NEXT y
NEXT x
IF flg=1 THEN !確定なら
MAT PRINT USING "## ## ## ## ## ## ## ## ##": m !解答の表示

PRINT "終了!"
STOP
END IF

LOOP UNTIL right=1 !右クリックされたら、プログラムを終了する



SUB box(x,y,c) !矩形を描く
SET AREA COLOR 6
PLOT AREA: x,y; x+1,y; x+1,y+1; x,y+1
CALL putc(x,y,8,c)
!LET m(y,x)=-c !確定する
END SUB
SUB putc(x,y,c,n) !文字を表示する
SET TEXT COLOR c
SET TEXT HEIGHT 0.5
PLOT TEXT ,AT x+0.5,y+0.5: STR$(n)
END SUB
  │ └つづき 山中和義 2008/05/11 20:53:30   ツリーへ
Re: つづき  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2008/05/11 20:53:30
つづき


DEF ToBlock(x)=INT((x-1)/3)*3 !マスに換算する

FUNCTION num$(x,y) !マスに入る候補を求める
LET t$="123456789" !使用可能な数字

FOR yy=1 TO 9 !列(縦)に着目
LET k=ABS(m(yy,x))
IF k>0 THEN LET t$(k:k)=" " !使用済みの数を削除する
NEXT yy

FOR xx=1 TO 9 !行(横)に着目
LET k=ABS(m(y,xx))
IF k>0 THEN LET t$(k:k)=" "
NEXT xx

LET Bx=ToBlock(x) !ブロックに着目
LET By=ToBlock(y)
FOR xx=1 TO 3
FOR yy=1 TO 3
LET k=ABS(m(By+yy,Bx+xx))
IF k>0 THEN LET t$(k:k)=" "
NEXT yy
NEXT xx

LET num$=t$ !残った数が候補となる
END FUNCTION



10 DATA 0,0,4, 0,0,0, 0,5,0 !初期データ
DATA 0,0,8, 0,0,0, 2,0,9
DATA 0,0,3, 0,0,4, 0,0,0

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

DATA 0,0,0, 2,0,0, 4,0,0
DATA 3,0,7, 0,0,0, 9,0,0
DATA 0,9,0, 0,0,0, 5,0,0


99 DATA 9,1,4, 6,8,2, 7,5,3 !解答データ ※参考
DATA 5,6,8, 3,7,1, 2,4,9
DATA 2,7,3, 9,5,4, 8,1,6

DATA 1,5,9, 4,2,6, 3,8,7
DATA 8,3,2, 5,1,7, 6,9,4
DATA 7,4,6, 8,3,9, 1,2,5

DATA 6,8,5, 2,9,3, 4,7,1
DATA 3,2,7, 1,4,5, 9,6,8
DATA 4,9,1, 7,6,8, 5,3,2


END
  !9×9数独をプログラムで解く 山中和義 2008/05/12 13:57:38  (修正1回)  ツリーへ
Re: パズル「数独」(ヒントつきプレイモード)  返事を書く  ノートメニュー
山中和義 <drdlxujciw> 2008/05/12 13:57:38 ** この記事は1回修正されてます
!9×9数独をプログラムで解く

DIM m(0 TO 8,0 TO 8)
MAT READ m !問題を読み込む

LET t0=TIME
CALL BackTrack(m,0) !左上から ※左上からの連番
PRINT "計算時間=";TIME-t0


DATA 0,0,4, 0,0,0, 0,5,0 !初期データ
DATA 0,0,8, 0,0,0, 2,0,9
DATA 0,0,3, 0,0,4, 0,0,0

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

DATA 0,0,0, 2,0,0, 4,0,0
DATA 3,0,7, 0,0,0, 9,0,0
DATA 0,9,0, 0,0,0, 5,0,0

END


EXTERNAL SUB BackTrack(m(,),p) !位置pを調査する
IF p<9*9 THEN !すべてが埋まるまで
LET row=INT(p/9) !行と列に換算する
LET col=MOD(p,9)
IF m(row,col)<>0 THEN !数字があれば
CALL BackTrack(m,p+1) !次へ
ELSE !なけらば
FOR k=1 TO 9 !数字1〜9を
IF CheckRule(m, row,col,k)=1 THEN !矛盾なく置ければ
LET m(row,col)=k !ここに置いてみる
CALL BackTrack(m,p+1) !次へ
LET m(row,col)=0 !取り消す
END IF
NEXT k
END IF
ELSE !すべて埋まったら
MAT PRINT USING "# # # # # # # # #": m !解を表示する
PRINT
END IF
END SUB


EXTERNAL FUNCTION CheckRule(m(,), row,col,k) !同じ数があるかどうか確認する
LET CheckRule=0
FOR y=0 TO 8 !列
IF m(y,col)=k THEN EXIT FUNCTION !見つかったので、NG!
NEXT y

FOR x=0 TO 8 !行
IF m(row,x)=k THEN EXIT FUNCTION
NEXT x

LET Bx=INT(col/3)*3 !ブロック
LET By=INT(row/3)*3
FOR x=0 TO 2
FOR y=0 TO 2
IF m(By+y,Bx+x)=k THEN EXIT FUNCTION
NEXT y
NEXT x

LET CheckRule=1 !見つからないので、OK!
END FUNCTION
   └数独を解く!数独ソルバー 片山博文MZ 2008/08/04 13:11:52   ツリーへ
Re: !9×9数独をプログラムで解く  返事を書く  ノートメニュー
片山博文MZ <nmnojyvbut> 2008/08/04 13:11:52
数独を解く! 数独ソルバー
http://www.geocities.co.jp/katayama_hirofumi_mz/sudoku/
パズルの数独を自動的に解くソフトウェアです。

大きな数独ソルバー
http://www.geocities.co.jp/katayama_hirofumi_mz/lsudoku/
パズルの大きな数独(16×16マス)を自動的に解くプログラムです。

 インデックスへ  EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。