プログラミングのすすめ 第十四歩 数独(ナンプレ)自動回答アプリ 公開 、で扱っていました数独の自動回答アプリですが、こちらも Powershell で作れるか、検討して行きたいと思います。
問題ファイルの形式
プログラミングを進めて行く上でまず問題の形式を定めておきます。こちらは、前回、前々回と同じように、スペースと数字で横9桁、縦9行のテキストファイルとします。
このような、テキストファイルです。
65 87
2 6 4
3 7
268
9 1
536
9 5
8 2 6
54 97
横、縦、ブロックの数字をリストアップ
先ず、空きマスに入る可能性の数字をメモするために、空きマスからみた横筋、縦筋、ブロックに入っている数字をリストする作業から始めます。
下図の黄色のマスから見て、緑のエリアの数字をリストします。
横筋の数字のリストアップ
横筋の数字のリストは簡単です。目的の行をリストすればいいだけです。
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
$n = 1
$tn = 1
foreach ($line in $lines) {
if ($tn -eq $n)
{
$line
}
$n++
}
PS >./outline.ps1
65 87
13,14行は、実行結果です。
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
目的の問題ファイル全体を $lines に読み込んでおきます。
$tn = 1
目的の行を指定します。
foreach ($line in $lines) {
$lines から一行づつ $line に読み込みます。
if ($tn -eq $n)
$n は 1から一つづつインクリメントします。$tn はリストしたい行数です。
$line
行をコンソールに表示します。
$n++
$n を一つづつインクリメントします。
縦筋の数字のリストアップ
縦筋の数字のリストも比較的に簡単です。全行を1から読み込んで、表示する段階で目的の桁だけを表示すればいいだけです。
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
$n = 1
$tn = 1
foreach ($line in $lines) {
$line.Substring($tn-1, 1);
}
PS >./outcolum.ps1
3
5
$line.Substring($tn-1, 1)
桁のインデックスは、0から始まりますので目的の桁は “$tn – 1” で指定します。
ブロックの数字のリストアップ
ブロックの数字のリストは少しややこしくなります。下図のように目的のマスがブロックの真ん中にある場合を考慮する必要があります。
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
$n = 1
$Li = 5 # 行の位置
$Co = 5 # カラムの位置
$LiB = ([math]::Floor(($Li -1)/3) + 1) #Block の行位置のはじめ
if ($LiB -eq 2) { $LiB = 4 }
if ($LiB -eq 3) { $LiB = 7 }
$CoB = ([math]::Floor(($Co -1)/3) + 1) #Block の桁位置のはじめ
if ($CoB -eq 2) { $CoB = 4 }
if ($CoB -eq 3) { $CoB = 7 }
$Li2 = $LiB + 1
$Li3 = $LiB + 2
foreach ($line in $lines) {
if ($LiB,$Li2,$Li3 -contains $n)
{
$line.substring($CoB-1,3)
}
$n++
}
PS >./outblock.ps1
68
53
$Li = 5 # 行の位置
$Co = 5 # カラムの位置
目的のマスの位置は、行の位置 と カラムの位置で指定します。
$LiB = ([math]::Floor(($Li -1)/3) + 1) #Block の行位置のはじめ
[math]::Floor() は、小数点以下切り捨ての整数を返します。 ($Li-1)/3 は、行数が、1~3 のときは、0.xx 、 4~6 の時は、1.xx 、7~9 の時は、 2.xx になります。よって 行数によって0,1,2 が返ります。それに+1することにより、縦方向で何番目のブロックであるかが分かります。1番目のブロックは1行目から始まりますので $LiB は、そのままです。
if ($LiB -eq 2) { $LiB = 4 }
2番目のブロックのときは、始まりは4行目です。
if ($LiB -eq 3) { $LiB = 7 }
3番目のブロックの時は、始まりは7行目です。
$Li2 = $LiB + 1
$Li3 = $LiB + 2
目的のブロックの2行目、3行目の値を $Li2,$Li3 にセットしておきます。
if ($LiB,$Li2,$Li3 -contains $n)
行が目的のブロックの1,2,3行目のときに処理をします。
$line.substring($CoB-1,3)
行からブロックに入っている桁の3桁だけを抜き出します。
ブロックは三つだけなので、前述のようなややこしい計算をしなくてもIf文だけで出来るので、ブロックの行、桁の始めを求めるFunctionを次のように作りました。
function BlockB($nn) {
If ( $nn -lt 4 ) { $Num = 1 }
If ( $nn -gt 3 -and $nn -lt 7 ) { $Num = 4 }
If ( $nn -gt 6 ) { $Num = 7 }
return $Num
}
$Li = 5
$Co = 3
$LiB = BlockB $Li #Block の行位置のはじめ
$CoB = BlockB $Co #Block の桁位置のはじめ
$LiB
$CoB
PS >./BlockFun.ps1
4
1
すべてのマスでリストアップした数字をArray変数に格納
次に実施するのは、アウトプットした数字を変数に入れて、その変数を 1~81 のマス目毎にArray変数に格納しておくことです。
Array変数の準備
PowerShell では、変数の宣言をする必要はないのですが、Array 変数に関しては、いきなり ArrayMemo[0] = $mn いうようにindexを付けることは出来ません。
$mn = 1
$arrayMemo[0] = $mn
PS >./arrayTest.ps1
null 配列にインデックスを付けることはできません。
発生場所 C:\numpre\arrayTest.ps1:2 文字:1
+ $arrayMemo[0] = $mn
+ ~~~~~~~~~~~~~~~~~~~
+ CategoryInfo : InvalidOperation: (:) []、RuntimeException
+ FullyQualifiedErrorId : NullArray
$arrayMemo = 1..9
$arrayMemo
$disp = "Index 5 = " + $arrayMemo[5]
echo $disp
PS >./arrayTest.ps1
1
2
3
4
5
6
7
8
9
Index 5 = 6
$arrayMemo = 1..9
1..9 のように範囲演算子を代入することにより、 $arrayMemo[0] – [8] に 1~9 の数字の入った配列変数が用意されます。
$arrayMemo
インデックスを付けずにarray変数を記述すると、配列のすべての要素が出力されます。
$disp = "Index 5 = " + $arrayMemo[5]
インデックスを付けると、その要素だけが出力されます。
マス目の番号から行、桁を出すFunctionの作成
1-81 の配列を用意してすべてのマスについて、横、縦、ブロックの数字をメモして行きます。準備としてマス目の番号から、行、桁を出すFunction を作成します。
function LiCol ($nb) {
$Li = [math]::Floor(($nb-1)/9) + 1
$Co = $nb % 9
if ($Co -eq 0) { $Co = 9 }
return $Li, $Co
}
PS >LiCol 9
1
9
PS >LiCol 65
8
2
$Li = [math]::Floor(($nb-1)/9) + 1
1行は9桁ですので、マス目の番号から-1して9で割ると、1行目は 0.xx 2行目は 1.xx 以下 9行目は8.xx となり 1を足すと行数になります。
$Co = $nb % 9
if ($Co -eq 0) { $Co = 9 }
% は、乗除算です。 マス目の番号を9で割ったときの余りを求めます。それが桁の番号になります。
ただし、9桁目はあまりがゼロなので、0の場合は9にします。
横方向
目的のマス目から見て横方向のラインにある数字をすべてのマス目で収集します。
$arrayMemo = 1..81
:label01 foreach ( $i in 1..81 ) {
$MemoN = ""
$Li,$Co = LiCol $i
#横方向の数字をメモリーに格納します
$n = 1
foreach ($line in $lines) {
if ($Li -eq $n)
{
if ( $line.Substring($Co - 1,1) -ne " " ) { $arrayMemo[$i - 1 ] = "X" ; Continue label01 }
else
{$MemoN = $line }
}
$n++
}
$arrayMemo[$i - 1 ] = $MemoN
}
PS >$arrayMemo[0,1,2,3,4,5,6,7,8]
65 87
X
X
65 87
65 87
65 87
65 87
X
X
PS >$arrayMemo[9,10,11,12,13,14,15,16,17]
2 6 4
X
2 6 4
2 6 4
X
2 6 4
X
2 6 4
2 6 4
$arrayMemo = 1..81
格納先のArrayの準備です。$arrayMemo[0] – [80] が準備されます。
:label01 foreach ( $i in 1..81 ) {
1~81 の番号について繰り返します。 :label01 は、マス目が空白でなかった場合に Continue lable01 で foreach loop を直ぐに抜けるためにラベルを付けています。
$Li,$Co = LiCol $i
マス目の番号 $i から 行($Li) 桁($Co) を求めます。
if ( $line.Substring($Co - 1,1) -ne " " ) { $arrayMemo[$i - 1 ] = "X" ; Continue label01}
else
{$MemoN = $line }
対象のマス目にすでに数字がある場合は、”X”を代入し、Continue label01 で foreach の先頭に戻り、以後の処理をスキップします。
$arrayMemo[$i - 1 ] = $MemoN
読み込んだ数字を配列変数に入れます。
縦方向を追加
:label01 foreach ( $i in 1..81 ) {
$MemoN = ""
$Li,$Co = LiCol $i
#横方向の数字をメモリーに格納します
$n = 1
foreach ($line in $lines) {
if ($Li -eq $n)
{
if ( $line.Substring($Co - 1,1) -ne " " ) { $arrayMemo[$i - 1 ] = "X" ; Continue label01 }
else
{$MemoN = $line }
}
$n++
}
#縦方向の数字をメモリーに格納します
foreach ($line in $lines) {
$MemoN = $MemoN + $line.Substring( $Co -1, 1);
}
$arrayMemo[$i - 1 ] = $MemoN
}
PS >$arrayMemo[0,1,2,3,4,5,6,7,8]
65 87 3 5
X
X
65 87 76
65 87 6 8 5 2
65 87 39
65 87 4 6 9
X
X
$MemoN = $MemoN + $line.Substring( $Co -1, 1);
前項で横方向の数字を記録した $MemoN に縦方向で拾った数字を追加して行きます。
ブロック内の数字を追加
前項までのコードに次のコードを追加します。
#ブロックの数字をメモリーに格納します
$n = 1
$LiB = BlockB $Li #Block の行位置のはじめ
$CoB = BlockB $Co #Block の桁位置のはじめ
$Li2 = $LiB + 1
$Li3 = $LiB + 2
foreach ($line in $lines) {
if ($LiB,$Li2,$Li3 -contains $n)
{
$MemoN = $MemoN + $line.substring($CoB-1,3)
}
$n++
}
PS >$arrayMemo[0,1,2,3,4,5,6,7,8]
65 87 3 5 65 2 3
X
X
65 87 76 6 7
65 87 6 8 5 2 6 7
65 87 39 6 7
65 87 4 6 9 874
X
X
リストアップした数字からメモへ
ここまでで、対象マスからみて横、縦方向、ブロック内にある数字をリストアップしました。求めたいのは、そのマスに入る可能性のある数字はなにかと言う事なので、配列に格納する前にリストアップした数字から、そちらに変換して 変換したものを配列に格納します。
#リストアップした数字から、入る可能性のある数字を割り出します。
$MemoP = ""
foreach ($num in 1..9) {
If ( $MemoN.Contains($num) ) { }
else
{ $MemoP += $num }
}
$arrayMemo[$i - 1 ] = $MemoP
PS > $arrayMemo[0,1,2,3,4,5,6,7,8]
149
X
X
12349
1349
124
123
X
X
$MemoP = ""
配列に格納する変数を初期化します。
foreach ($num in 1..9) {
If ( $MemoN.Contains($num) ) { }
else
{ $MemoP += $num }
}
これまでリストアップした数字 $MemoN に $num が含まれない時に、$MemoP にその数字を足して行きます。
ヒドゥンシングルのチェック
これまですべての空白マス目で入る可能性の数字を求めてメモに格納しました。次は、それらのメモからヒドゥンシングルあるかをチェックします。
メモした数字で、縦、横、ブロックでみた場合に、一つだけ現れるものを見つけます。以下の赤い数字がヒドゥンシングルです。緑の〇は、横方向のチェックで、青〇は、縦方向で、茶色の〇は、ブロックのチェックで見つかったものです。
横方向でのヒドゥンシングルのチェック
# Check single
$ArraySingle = 1..81
foreach ($i in 1..81 ) { $ArraySingle[$i -1] = 0 }
#横方向でのシングル(メモした数字が一つだけ)を探します
$n = 1
$ArrayC = 1..9
$ArrayP = 1..9
foreach ($i in 1..9){ $arrayC[$i-1] = 0 ; $arrayP[$i-1] = 0 }
foreach ($Li in 1..9) {
foreach ($i in 1..9){ $arrayC[$i-1] = 0 ; $arrayP[$i-1] = 0 }
foreach ( $Co in 1..9 ) {
foreach ( $k in 1..9) {
if ( $ArrayMemo[$n - 1].Contains($k) ) { $ArrayC[$k - 1]++ ; $ArrayP[$k -1 ] = $n }
}
$n ++
}
foreach ( $p in 1..9 ) {
if ( $arrayC[$p - 1] -eq 1 ) {
$Pos = $ArrayP[$p - 1]
$ArraySingle[$Pos - 1] = $p }
}
}
PS >$ArraySingle[26,42,63,80]
6
5
9
2
$ArraySingle = 1..81
foreach ($i in 1..81 ) { $ArraySingle[$i -1] = 0 }
発見したシングルの位置に数字を格納するための配列 $ArraySingle[] を用意し、すべて0を入れて初期化します。
$n = 1
$ArrayC = 1..9
$ArrayP = 1..9
$n は、$ArrayMemo[]のインデックスとして使います。
$ArrayC[] を用意します。メモした数字が現れる回数をそれぞれの数字について数えます。 1の数を数えて$ArrayC[0]に以下2~9 も同様に入れて行きます。
$ArrayP[] には、その数字が現れた最後のポジションを入れます。
foreach ($Li in 1..9) { # 行 1~9で
foreach ($i in 1..9){ $arrayC[$i-1] = 0 ; $arrayP[$i-1] = 0 }
foreach ( $Co in 1..9 ) {
行 1~9で繰り返し、
$arrayC $arrayP を初期化します。
カラム 1~9で繰り返します。
foreach ( $k in 1..9) {
if ( $ArrayMemo[$n - 1].Contains($k) ) { $ArrayC[$k - 1]++ ; $ArrayP[$k -1 ] = $n }
}
$k は、チェックする数字1~9 となります。$ArrayMemo に チェックする数字が有れば $ArrayC[] をインクリメントします。そのポジションを $ArrayP に格納します。
foreach ( $p in 1..9 ) {
if ( $arrayC[$p - 1] -eq 1 ) {
$Pos = $ArrayP[$p - 1]
$ArraySingle[$Pos - 1] = $p }
}
横の一列をチェックした後、$arrayC のそれぞれのインデックスで 1 があるかチェックします。1が有ったら、そのポジションを $Pos に代入します。$ArraySingle[] の該当ポシションに数字を入れます。
縦方向のヒドゥンシングルのチェック
縦方向にチェックする場合、$ArrayMemo を参照する時のインデックスは、一つづつインクリメントする訳ではなくなります。よって、行、桁からマス目の位置を求める Function を作ります。
行、桁からマス目の番号を求める Function
Function MnFromLC($Li,$Co) {
if ($Co -eq 9 ) { $am = 9 }
else { $am = $Co % 9 }
$mn =( [math]::Floor(($Li-1)*9/9 )) * 9 + $am
return $mn
}
PS >MnFromLC 1 1
1
PS >MnFromLC 9 9
81
PS >MnFromLC 8 9
72
PS >MnFromLC 9 8
80
縦方向ヒドゥンシングルのチェック
#縦方向でのシングル(メモした数字が一つだけ)を探します
foreach ($Co in 1..9) {
Foreach ($i in 1..9){ $arrayC[$i-1] = 0 ; $arrayP[$i-1] = 0 }
Foreach ($Li in 1..9) {
$mn = MnFromCL $Li $Co
foreach ( $k in 1..9) {
if ( $ArrayMemo[$mn - 1].Contains($k) ) { $ArrayC[$k - 1]++ ; $ArrayP[$k -1 ] = $mn }
}
}
foreach ( $p in 1..9 ) {
if ( $arrayC[$p - 1] -eq 1 ) {
$Pos = $ArrayP[$p - 1]
$ArraySingle[$Pos - 1] = $p }
}
}
PS >$ArraySingle[26,42,63,80,28,54,77]
6
5
9
2
5
2
6
ブロックでヒドゥンシングルのチェック
#ブロックでのヒドゥンシングルを探します
foreach ( $block in 1,4,7,28,31,34,55,58,61 ) {
Foreach ($i in 1..9){ $arrayC[$i-1] = 0 ; $arrayP[$i-1] = 0 }
$Li,$Co = LiCol $block
$Li2 = $Li + 2
$Co2 = $Co + 2
Foreach ( $Gyo in $Li..$Li2 ) {
Foreach ($Keta in $Co..$Co2 ) {
$mn = MnFromLC $Gyo $Keta
foreach ( $k in 1..9) {
if ( $ArrayMemo[$mn - 1].Contains($k) ) { $ArrayC[$k - 1]++ ; $ArrayP[$k -1 ] = $mn }
}
}
}
foreach ( $p in 1..9 ) {
if ( $arrayC[$p - 1] -eq 1 ) {
$Pos = $ArrayP[$p - 1]
$ArraySingle[$Pos - 1] = $p }
}
}
マルチ・ディメンジョン・アレイ を使う
ここまで、ファイルを一行づつ読み込んで処理をしていましたが、9×9 の Multi Dimension Array を作って、そこに予め読み込んで処理すればもっと簡単に出来そうです。
マルチ・ディメンジョン・アレイの作成
次のコードで 9X9 の Multi Dimension Array を作成して、すべてのマスに0を入れて初期化します。
$mdarray = (1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9)
foreach ($Li in 1..9) {
foreach ($Co in 1..9) {
$mdarray[$Li-1][$Co-1] = 0
}
}
MD Array にデータを入れる
$mdarray = (1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9)
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
$Li = 1
foreach ( $line in $lines ) {
foreach ( $Co in 1..9 ) {
$mdarray[$Li - 1][$Co - 1] = $line.substring($Co - 1,1)
}
$Li++
}
PS >$mdarray[0][0]
PS >$mdarray[0][1]
6
PS >$mdarray[0][2]
5
PS >$mdarray[8][0]
5
PS >$mdarray[8][7]
7
PS >$mdarray[8][8]
横、縦、ブロックのデータを集める
$mdarray = (1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9)
$lines = get-content -Path "C:\Numpre\Numpre1.txt"
$Li = 1
foreach ( $line in $lines ) {
foreach ( $Co in 1..9 ) {
$mdarray[$Li - 1][$Co - 1] = $line.substring($Co - 1,1)
}
$Li++
}
# X Y----Y
# |
# |
# X
function BlockB($nn) {
If ( $nn -lt 4 ) { $Num = 1 }
If ( $nn -gt 3 -and $nn -lt 7 ) { $Num = 4 }
If ( $nn -gt 6 ) { $Num = 7 }
return $Num
}
$mdMemo = (1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9)
foreach ($x in 1..9){
foreach ($y in 1..9) { $mdMemo[$x-1][$y-1] = "" }
}
foreach ($x in 1..9) {
:label01 foreach ($y in 1..9 ) { #各マス毎に処理
if ( $mdarray[$x -1][$y -1] -match "[1-9]" ) { continue label01 } #マス目にすでに数字があるときは処理しない
$BData = ""
foreach ($yoko in 1..9 ) {
$Bdata = $Bdata + $mdarray[$x -1][$yoko - 1] #横データすべてが $Bdata に入ります
}
foreach ($Tate in 1..9) { #縦データを追加して行きます
$Bdata = $Bdata + $mdarray[$Tate - 1][$y - 1]
}
$xb = BlockB $x
$xbE = $xb + 2
$yb = BlockB $y
$ybE = $yb + 2
foreach ($Tate in $xb..$xbE) {
foreach ($Yoko in $yb..$ybE ) {
$BlockMemo = $mdarray[$Tate -1][$Yoko -1]
$Bdata = $Bdata + $BlockMemo
}
}
$mdMemo[$x-1][$y-1] = $Bdata
}
}
PS >$mdMemo[0][0]
65 87 3 5 65 2 3
PS >$mdMemo[8][8]
54 97 7 5 5 6 97
$mdMemo は 9x9の 配列です。インデックス[0][0] には以下の赤色のエリアの数字が、[8][8] には、青色のエリアの数字が入ります。
メモ数字に変換
$mdMemo の 9×9 配列に集めた数字より、そのマスに入る可能性の候補数字を求めます。
#候補数字に変換
Foreach ( $x in 1..9) {
:label02 Foreach ( $y in 1..9 ) {
if ( $mdMemo[$x -1][$y -1] -notmatch "[1-9]" ) { continue label02 }
$koho = ""
foreach ( $n in 1..9 ) {
if ( $mdMemo[$x -1][$y -1].contains("$n")) { }
else {
$Koho = $Koho + $n
}
}
$mdMemo[$x -1][$y -1] = $koho
}
}
$mdMemo の内容が、以下の 小さなメモ数字になっていれば成功です。
PS >$mdMemo[0][0]
149
PS >$mdMemo[8][8]
1238
シングルのチェック
$mdMemo に候補数字をメモしました。この時点で、マスに入る候補が一つだけのマスを探して、数字を$mdarray に入れて行きます。
以下の例では、赤丸の9はそのマスの候補で一つだけなので、これを探します。
#シングルのチェック
#全マス
For ( $x = 1; $x -lt 10 ; $x++ ) {
Foreach ( $y in 1..9 ) {
if ( $mdMemo[$x -1][$y -1].length -eq 1 ) {
$mdarray[$x -1][$y -1] = $mdMemo[$x -1][$y -1]
}
}
}
PS >$mdarray[0][2]
9
メモのアップデート
前項でシングルをチェックして、$mdarray に入れましたが、入れた数字は、現状のメモの状態に反映されていません。数字を入れた後は、入れたマスの箇所からみて、横列、縦列、ブロック内のメモから入れた数字を消す必要があります。縦順 X と横順 Y および入力数字 N から、$mdMemo をアップデートするルーティンを作ります。
#縦順 X と横順 Y および入力数字 N から、$mdMemo をアップデートするルーティン
param($X,$Y,$N)
$mdMemo[$X -1][$Y -1] = "" #mdarray に数字を入れたので、当該箇所のmemoは空白にします。
#横方向でのアップデート
Foreach ($C in 1..9) { #1カラムから 9カラムまで
$mdMemo[$x -1][$C -1] = $mdMemo[$x -1][$C -1].replace("$N","")
}
#縦方向でのチェック
Foreach ($L in 1..9 ) { #1行目から 9行目まで
$mdMemo[$L -1][$Y -1] = $mdMemo[$L -1][$Y -1].replace("$N","")
}
#ブロックでのmemoアップデート
$LiB = ([math]::Floor(($X -1)/3) + 1) #Block の行位置のはじめ
if ($LiB -eq 2) { $LiB = 4 }
if ($LiB -eq 3) { $LiB = 7 }
$CoB = ([math]::Floor(($Y -1)/3) + 1) #Block の桁位置のはじめ
if ($CoB -eq 2) { $CoB = 4 }
if ($CoB -eq 3) { $CoB = 7 }
$LiBe = $LiB + 2
$CoBe = $CoB + 2
Foreach ( $L in $LiB..$LiBe ) {
Foreach ( $C in $CoB..$CoBe ) {
$mdMemo[$L -1][$C -1] = $mdMemo[$L -1][$C -1].replace("$N","")
}
}
シングルチェック後 メモアップデート
シングルをチェックして、$mdarray に数字を入れて、メモをアップデートしたら、それまでチェックしてきたところより以前に、シングルが現れる可能性があります。ですので、そのような場合は、また最初からシングルをチェックする必要があります。UpdateMemo.ps1 をシングルチェックに組み込んで、SingleCheck.ps1 を以下のように書き換えます。簡単な問題は、ここまでのルーティンで回答出来てしまいます。
#シングルのチェック
#全マス
:Label01 For ( $x = 1; $x -lt 10 ; $x++ ) {
Foreach ( $y in 1..9 ) {
if ( $mdMemo[$x -1][$y -1].length -eq 1 ) {
$mdarray[$x -1][$y -1] = $mdMemo[$x -1][$y -1]
./UpdateMemo.ps1 $X $Y $mdarray[$x -1][$y -1]
$x = 0 ; continue Label01
}
}
}
ヒドゥン・シングルのチェック
前項では、マス目に一つだけの候補数字が存在するケースを処理しました。横方向、縦方向、ブロックで見た時に、一つだけ現れるケースがあります。これは、ヒドゥン・シングルと言って、そこには確実にその数字が入ると考えることが出来ます。$mdMemo をチェックして、このヒドゥンシングルが有るかどうかを探して、$mdarray に数字を入力して行きます。
以下の赤い数字がヒドゥンシングルです。緑の〇は、横方向のチェックで、青〇は、縦方向で、茶色の〇は、ブロックのチェックで見つかったものです。
横方向のヒドゥンシングルのチェック
以下のコードでは、横方向でヒドゥンシングルをチェックして、見つかったものは$mdarray に数字を入力しています。
#ヒドゥンシングルのチェック
#横方向でのチェック
#1行目から 9行目まで
Foreach ($L in 1..9) {
Foreach ($N in 1..9 ) { #数字 1から9の数をチェック
$count = 0
Foreach ($C in 1..9 ) { # 1から9カラム
if ( $mdMemo[$L -1][$C -1].contains("$N") ) { $count++ ; $pos = $C }
}
if ( $count -eq 1 ) {
$mdarray[$L -1][$pos -1] = $N
}
}
}
PS >$mdarray[2][8]
6
PS >$mdarray[4][6]
5
PS >$mdarray[7][0]
9
PS >$mdarray[8][8]
2
チェック後のメモアップデート
前述のシングルのチェック後と同じようにヒドゥンシングルをチェックして$mdarrayに数字入力した後も、当該箇所からみたメモをアップデートする必要があります。
#横方向でのチェック
:Label02 For ($L = 1; $L -lt 10 ; $L++ ) { #1行目から 9行目まで
Foreach ($N in 1..9 ) { #数字 1から9の数をチェック
$count = 0
Foreach ($C in 1..9 ) { # 1から9カラム
if ( $mdMemo[$L -1][$C -1].contains("$N") ) { $count++ ; $pos = $C }
}
if ( $count -eq 1 ) {
$mdarray[$L -1][$pos -1] = $N
./UpdateMemo.ps1 $L $pos $N
$AnyCh = 1; $L = 0 ; Continue Label02
}
}
}
縦方向のヒドゥンシングルのチェック
#縦方向でのチェック
Foreach ($C in 1..9) { # 1カラムから 9カラムまで
Foreach ($N in 1..9 ) { #数字 1から9の数をチェック
$count = 0
Foreach ($L in 1..9 ) { #1行目から 9行目まで
if ( $mdMemo[$L -1][$C -1].contains("$N") ) { $count++ ; $pos = $L }
}
if ( $count -eq 1 ) {
$mdarray[$pos -1][$C -1] = $N
}
}
}
PS >$mdarray[3][1]
5
PS >$mdarray[6][0]
2
PS >$mdarray[8][5]
6
ブロックでのヒドゥンシングルのチェック
#ブロックでのヒドゥンシングルのチェック
Foreach ( $BL in 1,4,7) { #ブロックの開始行
$BLe = $BL + 2
Foreach ( $BC in 1,4,7 ) { #ブロック開始カラム
$BCe = $BC + 2
Foreach ( $N in 1..9 ) { #数字 1から9の数をチェック
$count = 0
Foreach ( $LinB in $BL..$BLe ) { #ブロック内の1行目から 3行目
Foreach ( $CinB in $BC..$BCe ) { #ブロック内の1カラムから3カラム
if ( $mdMemo[$LinB -1][$CinB -1].contains("$N") ) { $count++ ; $posL = $LinB ; $posC = $CinB }
}
}
if ( $count -eq 1 ) {
$mdarray[$posL -1][$posC -1] = $N
}
}
}
}
PS >$mdarray[2][8]
6
PS >$mdarray[3][1]
5
PS >$mdarray[5][3]
9
PS >$mdarray[6][0]
2
PS >$mdarray[7][0]
9
PS >$mdarray[8][5]
6
ネイキッドペアのチェック
こちら プログラミングのすすめ 第十四歩 数独の解法プログラム Visual Studio(VB) の解き方 その3であります、ネイキッドペアをチェックして、処理します。横方向、縦方向、ブロックで見た時に、メモ数字が二つで同じマスがあるかどうかをチェックします。
上図は、ネイキッドペアを処理した後の模様です。4列目で 5,6 のペアがあります。この処理で、左図の赤丸の5は消すことが出来ます。その処理の結果、右図の5列目の赤の5は、縦列、ブロックでヒドゥンシングルとなります。4番目の縦列の4,3のペアは、他のマスが全て埋まっているので変化なしです。
7番目の横列の5,3のペアは、ブロックで見てもペアとなりますので、そのブロックの他の5,3は消えています。
横列でのネイキッドペアのチェックと処理
横列で見てネイキッドペアが有れば、ペアとなっているマス以外には、ペアとなっている数字が入る可能性はなくなるので、ペアとなっているマス以外のマスのメモ数字からペアになっている数字を消します。メモを消した後、シングル、ヒドゥンシングルが発生すれば、数字を$mdarrayに入れて他のメモをアップデートします。
以下のコードは、横方向で先ずネイキッドペアが有るかチェックして、あれば、横列の他のマスの該当の数字をメモから消すところまでです。上図の左の赤丸の5を消しています。
# ネイキッドペアのチェック
#横
for ( $L = 1 ; $L -lt 10 ; $L++ ) {
$P1 = 0 ; $P2 = 0
Foreach ( $C in 1..8 ) {
if ( $mdMemo[$L -1][$C -1].length -eq 2 ) {
$P1 = $C
$Cnext = $C + 1
$P2 = 0
foreach ( $CC in $Cnext..9 ) {
if ( $mdMemo[$L -1][$C -1] -eq $mdMemo[$L -1][$CC -1] ) {
$P2 = $CC
}
}
}
if ($P2 -ne 0 ) { #ネイキッドペアあり
$n1 = $mdMemo[$L -1][$P1 -1].substring(0,1)
$n2 = $mdMemo[$L -1][$P1 -1].substring(1,1)
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) ) {
$mdMemo[$L -1][$i -1] = $mdMemo[$L -1][$i -1].replace($n1,"")
$mdMemo[$L -1][$i -1] = $mdMemo[$L -1][$i -1].replace($n2,"")
}
}
}
}
}
縦列でのネイキッドペアのチェックと処理
前項のコードのLine とColumn を入れ替えて、縦列のネイキッドペアのチェックのコードを次のように記述します。こちらもメモのアップデートまでです。
#縦列でネイキッドペアのチェックとメモの処理
For ( $C = 1 ; $C -lt 10 ; $C++ ) {
$P1 = 0 ; $P2 = 0
Foreach ( $L in 1..8 ) {
$AnyCh = 0
if ( $mdMemo[$L -1][$C -1].length -eq 2 ) {
$P1 = $L
$Lnext = $L + 1
$P2 = 0
foreach ( $LC in $Lnext..9 ) {
if ( $mdMemo[$L -1][$C -1] -eq $mdMemo[$LC -1][$C -1] ) {
$P2 = $LC
}
}
}
if ($P2 -ne 0 ) { #ネイキッドペアあり
$n1 = $mdMemo[$P1 -1][$C -1].substring(0,1)
$n2 = $mdMemo[$P1 -1][$C -1].substring(1,1)
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) ) {
$mdMemo[$i -1][$C -1] = $mdMemo[$i -1][$C -1].replace($n1,"")
$mdMemo[$i -1][$C -1] = $mdMemo[$i -1][$C -1].replace($n2,"")
}
}
}
}
}
ブロックでのネイキッドペアのチェックと処理
ブロックで各マスを順番に見て行くことは少しややこしい作業になります。従って先ずブロックのデータを横列に並び変えてから作業して、結果を横列からブロックに戻すということを実施します。
123 456 ---> 123456789 このようにブロックから横列に並び変えて $TempArray に入れます。 789
#ブロックでのネイキッドペアのチェック
#
# 123
# 456 ---> 123456789 に並べ変える
# 789
#
#
$TempArray = (1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9),(1..9)
foreach ($x in 1..9){
foreach ($y in 1..9) { $TempArray[$x-1][$y-1] = "" }
}
$X = 1 ;
For ( $BL = 1; $BL -lt 8 ; $BL += 3) { #ブロックの開始行
$BLe = $BL + 2
Foreach ( $BC in 1,4,7 ) { #ブロック開始カラム
$BCe = $BC + 2
$Y = 1
Foreach ( $LinB in $BL..$BLe ) { #ブロック内の1行目から 3行目
Foreach ( $CinB in $BC..$BCe ) { #ブロック内の1カラムから3カラム
$TempArray[$X -1][$Y -1] = $mdMemo[$LinB -1][$CinB -1]
echo "X= $X Y= $Y"
$Y++
}
}
$X++
}
}
21行目を逆にすれば、元に戻すルーティンとなります。
#
# 123
# 123456789 -->456
# 789
#
$X = 1 ;
For ( $BL = 1; $BL -lt 8 ; $BL += 3) { #ブロックの開始行
$BLe = $BL + 2
Foreach ( $BC in 1,4,7 ) { #ブロック開始カラム
$BCe = $BC + 2
$Y = 1
Foreach ( $LinB in $BL..$BLe ) { #ブロック内の1行目から 3行目
Foreach ( $CinB in $BC..$BCe ) { #ブロック内の1カラムから3カラム
$mdMemo[$LinB -1][$CinB -1] = $TempArray[$X -1][$Y -1]
$Y++
}
}
$X++
}
}
ブロックを横並びにした$TempArray を横列でのNakedPairのチェックと同じように処理します。
# ネイキッドペアのチェック
#ブロックでのネイキッドペアのチェック
#ブロックを横列にした $TempArray でネイキッドペアをチェック メモの処理
For ( $L = 1 ; $L -lt 10 ; $L++ ) {
$P1 = 0 ; $P2 = 0
Foreach ( $C in 1..8 ) {
if ( $TempArray[$L -1][$C -1].length -eq 2 ) {
$P1 = $C
$Cnext = $C + 1
$P2 = 0
foreach ( $CC in $Cnext..9 ) {
if ( $TempArray[$L -1][$C -1] -eq $TempArray[$L -1][$CC -1] ) {
$P2 = $CC
}
}
}
if ($P2 -ne 0 ) { #ネイキッドペアあり
$n1 = $TempArray[$L -1][$P1 -1].substring(0,1)
$n2 = $TempArray[$L -1][$P1 -1].substring(1,1)
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) ) {
$TempArray[$L -1][$i -1] = $TempArray[$L -1][$i -1].replace($n1,"")
$TempArray[$L -1][$i -1] = $TempArray[$L -1][$i -1].replace($n2,"")
}
}
}
}
}
ネイキッドトリプルのチェック
下図は、6行目の横列でのネイキッドトリプルの処理の結果、ペア、シングルに派生した様子です。
横列の6行目、1カラム 19,4カラム 179,6カラム 179 でトリプルです。3カラムの 7 と7カラムの17が消えます。
3カラムの7が消えたことにより、ここは4が決定となり、その上の7も必然的に決定します。
7カラムの17が消えたことにより、縦列の7で、3,6行目の58のネイキッドペアとなり、1行目の5が消えます。従ってここは3が決定となり、
9行目の3が消えて、2が決定、2行目の2が消えて6が決定、その横の2が決定、同じカラムの9行目の3が決定となります。
ネイキッドトリプルのプログラミングでの見つけ方
ここで、ネイキッドトリプルをプログラミングでどのように見つけるかを整理しておきます。
上図の横列で1,4,6カラムの 19,179,179 でネイキッドトリプルが成立します。先ず、1カラム目から順に3桁以下かを調べます。3桁以下なら、そのマス目をネイキッドトリプルの一つ目の候補として、次のカラムのメモとマージします。1カラムの 19 と3カラムの47をマージすると 1479 となり 3桁以上になってしまうので、3カラム目は、1カラムとのトリプルの組み合わせにはなりません。
次の4カラムとマージすると、179 ですので、 1カラムと4カラムは、ネイキッドトリプルの第一候補と第二候補となります。次の6カラムとマージします。同じく179となりますので、6カラムは第三候補となり、この三つでネイキッドトリプル成立です。
同じように、上のブロックで考えると、赤枠でネイキッドトリプル成立と分かると思います。
横列のネイキッドトリプルのチェック
文字列をマージするFunctionを次のように作りました。
Function MergeStr ($Str1,$Str2) {
for ($i = 0 ; $i -lt $Str2.length ; $i++ ) {
if ( $Str1.contains($Str2.substring($i,1)) ) { }
else {
$Str1 = $Str1 + $Str2.substring($i,1)
}
}
return ($Str1)
}
次のコードで横方向でネイキッドトリプルを探します。
# ネイキッドトリプルのチェック
#横列でネイキッドトリプルをチェック メモの処理
For ( $L = 1 ; $L -lt 10 ; $L++ ) { #行1から9まで
$P1 = 0 ; $P2 = 0 ; $P3 = 0
#echo "L=$L P1=$P1 P2=$P2 P3=$P3"
:BP2 Foreach ( $C in 1..7 ) { #第一候補を カラム1-7 でトライ
if ( $mdMemo[$L -1][$C -1].length -gt 1 -and $mdMemo[$L -1][$C -1].length -lt 4 ) { # memo blank または 1桁 はスキップ
# 4桁以下 すなわち 3桁までなら実施
$P1 = $C ; $P2 = 0
$Cn = $C + 1
foreach ( $CC in $Cn..8 ) { #次のマスからチェック
if ( $mdMemo[$L -1][$CC -1].length -gt 1 -and $mdMemo[$L -1][$CC -1].length -lt 4 ) {
$MGSTR = MergeStr $mdMemo[$L -1][$C -1] $mdMemo[$L -1][$CC -1]
#echo "L=$L CC=$CC P1=$P1 P2=$P2 P3=$P3"
if ( $MGSTR.length -lt 4 ) { $P2 = $CC }
if ( $P2 -ne 0 ) { # 第二候補が見つかったら次から第三候補を探します
$P2n = $P2 + 1 ; $P3 = 0
foreach ( $ccc in $P2n..9 ) {
if ( $mdMemo[$L -1][$CCC -1].length -gt 1 -and $mdMemo[$L -1][$CCC -1].length -lt 4 ) {
$MGSTR2 = MergeStr $MGSTR $mdMemo[$L -1][$CCC -1]
if ( $MGSTR2.length -lt 4 ) { $P3 = $CCC ; break BP2 }
}
}
}
}
}
}
}
if ( $P3 -ne 0 ) { # ネイキッドトリプルあり
echo "$P1,$P2,$P3"
}
}
}
}
ネイキッドトリプルありの中のコードを次に代えてMEMOの処理をします。
$n1,$n2,$n3 = $MGSTR2.ToCharArray()
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) -and ($i -ne $P3) ) {
$mdMemo[$L -1][$i -1] = $mdMemo[$L -1][$i -1].replace("$n1","").replace("$n2","").replace("$n3","")
}
}
縦列のネイキッドトリプルのチェック
#縦列でネイキッドトリプルをチェック メモの処理
For ( $C = 1 ; $C -lt 10 ; $C++ ) { #カラム1から9まで
$P1 = 0 ; $P2 = 0 ; $P3 = 0
:BP3 Foreach ( $L in 1..7 ) { #第一候補を 行1-7 でトライ
if ( $mdMemo[$L -1][$C -1].length -gt 1 -and $mdMemo[$L -1][$C -1].length -lt 4 ) { # memo blank または 1桁 はスキップ
# 4桁以下 すなわち 3桁までなら実施
$P1 = $L ; $P2 = 0
$Ln = $L + 1
foreach ( $LL in $Ln..8 ) { #次のマスからチェック
if ( $mdMemo[$LL -1][$C -1].length -gt 1 -and $mdMemo[$LL -1][$C -1].length -lt 4 ) {
$MGSTR = MergeStr $mdMemo[$L -1][$C -1] $mdMemo[$LL -1][$C -1]
if ( $MGSTR.length -lt 4 ) { $P2 = $LL }
if ( $P2 -ne 0 ) { # 第二候補が見つかったら次から第三候補を探します
$P2n = $P2 + 1 ; $P3 = 0
foreach ( $LLL in $P2n..9 ) {
if ( $mdMemo[$LLL -1][$C -1].length -gt 1 -and $mdMemo[$LLL -1][$C -1].length -lt 4 ) {
$MGSTR2 = MergeStr $MGSTR $mdMemo[$LLL -1][$C -1]
if ( $MGSTR2.length -lt 4 ) { $P3 = $LLL ; break BP3 }
}
}
}
}
}
}
}
if ( $P3 -ne 0 ) { # ネイキッドトリプルあり
$n1,$n2,$n3 = $MGSTR2.ToCharArray()
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) -and ($i -ne $P3) ) {
$mdMemo[$i -1][$C -1] = $mdMemo[$i -1][$C -1].replace("$n1","").replace("$n2","").replace("$n3","")
}
}
}
}
ブロックでのネイキッドトリプルのチェック
ペアのチェックの時と同じように、チェック前に$mdMemo のブロックを横列に並び変えて、$TempArray に入れます。その後、$TempArray で横列のネイキッドトリプルのチェックと処理後に$mdMemo に戻します。
#ブロックでネイキッドトリプルをチェック メモの処理
#ブロックから横列へ
./BLtoSeq.ps1
For ( $L = 1 ; $L -lt 10 ; $L++ ) { #行1から9まで
$P1 = 0 ; $P2 = 0 ; $P3 = 0
#echo "L=$L P1=$P1 P2=$P2 P3=$P3"
:BP2 Foreach ( $C in 1..7 ) { #第一候補を カラム1-7 でトライ
if ( $TempArray[$L -1][$C -1].length -gt 1 -and $TempArray[$L -1][$C -1].length -lt 4 ) { # memo blank または 1桁 はスキップ
# 4桁以下 すなわち 3桁までなら実施
$P1 = $C ; $P2 = 0
$Cn = $C + 1
foreach ( $CC in $Cn..8 ) { #次のマスからチェック
if ( $TempArray[$L -1][$CC -1].length -gt 1 -and $TempArray[$L -1][$CC -1].length -lt 4 ) {
$MGSTR = MergeStr $TempArray[$L -1][$C -1] $TempArray[$L -1][$CC -1]
#echo "L=$L CC=$CC P1=$P1 P2=$P2 P3=$P3"
if ( $MGSTR.length -lt 4 ) { $P2 = $CC }
if ( $P2 -ne 0 ) { # 第二候補が見つかったら次から第三候補を探します
$P2n = $P2 + 1 ; $P3 = 0
foreach ( $ccc in $P2n..9 ) {
if ( $TempArray[$L -1][$CCC -1].length -gt 1 -and $TempArray[$L -1][$CCC -1].length -lt 4 ) {
$MGSTR2 = MergeStr $MGSTR $TempArray[$L -1][$CCC -1]
if ( $MGSTR2.length -lt 4 ) { $P3 = $CCC ; break BP2 }
}
}
}
}
}
}
}
if ( $P3 -ne 0 ) { # ネイキッドトリプルあり
$n1,$n2,$n3 = $MGSTR2.ToCharArray()
foreach ( $i in 1..9) {
if ( ($i -ne $P1) -and ($i -ne $P2) -and ($i -ne $P3) ) {
$TempArray[$L -1][$i -1] = $TempArray[$L -1][$i -1].replace("$n1","").replace("$n2","").replace("$n3","")
}
}
}
}
#横列からブロックへ
./SeqtoBl.ps1
ネイキッドクワッドのチェック
次は、四つのネイキッドの検索です。
上図は、2行目の横列は、赤枠の四つが 36,27,37,26 となっていますので、2367 のネイキッドクワッドが成立します。それによって、4カラムの236、5カラムの2が消えます。その結果、今度はブロックで青枠の四つが、12,89,189,28 となり、1289のネイキッドクワッドが成立します。1行目4カラムの2が消えて、1行目は5カラムの2が横列でみてヒドゥンシングルとなります。
横列のネイキッドクワッドのチェック
それでは、早速横列のネイキッドクワッドを見つけるプログラミングをして行きます。
トリプルのチェックと同じ要領で、項目をそれぞれ一つづつ増やしてネイキッドクワッドのチェックと処理をします。
# ネイキッドクワッドのチェック
#横列でネイキッドクワッドをチェック メモの処理
For ( $L = 1 ; $L -lt 10 ; $L++ ) { #行1から9まで
$P1 = 0 ; $P2 = 0 ; $P3 = 0 ; $P4 = 0
#echo "L=$L P1=$P1 P2=$P2 P3=$P3 P4=$P4"
:BP3 Foreach ( $C in 1..6 ) { #第一候補を カラム1-6 でトライ
if ( $mdMemo[$L -1][$C -1].length -gt 1 -and $mdMemo[$L -1][$C -1].length -lt 5 ) { # memo blank または 1桁 はスキップ
# 5桁以下 すなわち 4桁までなら実施
$P1 = $C
$Cn = $C + 1
foreach ( $CC in $Cn..7 ) { #次のマスからチェック
if ( $mdMemo[$L -1][$CC -1].length -gt 1 -and $mdMemo[$L -1][$CC -1].length -lt 5 ) {
$MGSTR = MergeStr $mdMemo[$L -1][$C -1] $mdMemo[$L -1][$CC -1]