[Powershell] 用powershell算9X9数独.

浏览数：53 / 时间：2015年06月20日

This arctical will also be published in English at http://www.cnblogs.com/LarryAtCNBlog/p/4307965.html

数独是一个填字游戏，广为人知的是9X9类型的，下面是一个算法，也就是由每次从可确定的数中推算同行或同列的可能值，如果可能值只为1个，那就可以直接确定该单元格的值，如果可能的值的数量大于或等于2，则做循环和单元格值的假设，推算出答案。由于数独答案不唯一，因此加了一个参数定义返回的答案数量。

技术分享

param(
    # 返回几个答案
    [int]$HowManyAnswersYouWanttoGet = 1
)

$SudokuMatrix = @(
    @(0,0,0, 0,0,0, 0,0,3),
    @(0,0,0, 0,0,0, 0,4,0),
    @(0,5,1, 6,0,0, 0,0,0),
    
    @(0,3,0, 0,0,8, 0,0,2),
    @(9,0,0, 1,6,0, 0,0,0),
    @(0,6,0, 0,5,4, 0,0,0),
    
    @(5,4,0, 0,0,0, 0,2,0),
    @(0,0,3, 4,0,2, 0,0,0),
    @(0,0,8, 3,0,0, 7,1,0)
)
# 循环每个元素，给没有值的元素加上 1-9 的数组。
for($i = 0; $i -lt 9; $i++){
    for($j = 0; $j -lt 9; $j++){
        if(!$SudokuMatrix[$i][$j]){
            $SudokuMatrix[$i][$j] = 1..9
        }else{
            $SudokuMatrix[$i][$j] = @($SudokuMatrix[$i][$j])
        }
    }
}

# 循环每个元素，比较横向和纵向数据，从除去所有可能的值。
function GoLoop($arr){
    $NewArr = @($null) * 9
    for($i = 0; $i -lt 9; $i++){
        $NewArr[$i] = $arr[$i].PSObject.Copy()
    }
    for($i = 0; $i -lt 9; $i++){
        for($j = 0; $j -lt 9; $j++){
            if($NewArr[$i][$j].Count -ne 1){
                for($k = 0; $k -lt 9; $k++){
                    if($NewArr[$i][$k].Count -eq 1 -and $NewArr[$i][$j].Count -ne 1){
                        $NewArr[$i][$j] = @($NewArr[$i][$j] | ?{$_ -ne $NewArr[$i][$k][0]})
                    }
                    if($NewArr[$k][$j].Count -eq 1 -and $NewArr[$i][$j].Count -ne 1){
                        $NewArr[$i][$j] = @($NewArr[$i][$j] | ?{$_ -ne $NewArr[$k][$j][0]})
                    }
                }
            }
        }
    }
    return $NewArr
}

# 循环每个元素，如果可能的值数量变为0，返回true，说明计算错误。
function VerifyZero($arr){
    for($i = 0; $i -lt 9; $i++){
        for($j = 0; $j -lt 9; $j++){
            if($arr[$i][$j].Count -eq 0){
                return $i, $j, $true
            }
        }
    }
    return $i, $j, $false
}

# 找到元素中可能的值数量最小的那个，返回该元素的位置。
function FindSmallest($arr){
    foreach($k in 2..9){
        for($i = 0; $i -lt 9; $i++){
            for($j = 0; $j -lt 9; $j++){
                if($arr[$i][$j].Count -eq $k){
                    return $i, $j, $k
                }
            }
        }
    }
}

# 计算数组中有多少个元素已经被确认了值。
function CountConfirmedNumber($arr){
    $NumberConfirmed = 0
    for($i = 0; $i -lt 9; $i++){
        for($j = 0; $j -lt 9; $j++){
            if($arr[$i][$j].Count -eq 1){
                $NumberConfirmed++
            }
        }
    }
    return $NumberConfirmed
}

$AnswerCount = 0
$Results = @()

function GoCalculate($arr){
    $NewArray = GoLoop($arr)
    # verify no zero option!
    $ZeroPosition = VerifyZero($NewArray)
    if($ZeroPosition[2]){
        # Write-Host "0 option found: [$($ZeroPosition[0])][$($ZeroPosition[1])]"
        return
    }
    # confirm current numbers
    if((CountConfirmedNumber($NewArray)) -eq 81){
        $Script:AnswerCount++
        Write-Host "An answer captured, ID: $AnswerCount" -ForegroundColor Green
        # Write-Host "81 numbers confirmed."
        $Script:Results += $null
        $Script:Results[-1] = $NewArray
        return
    }
    # find the nearest(to [0][0]) and smallest(2 to 9) option element.
    $Smallest = FindSmallest($NewArray)
    $OptionsStack = @($NewArray[$Smallest[0]][$Smallest[1]])
    # Write-Host "Row: $($Smallest[0]); Col: $($Smallest[1]); Option: $($OptionsStack -join ‘ ‘)"
    foreach($Option in $OptionsStack){
        # Write-Host "Set [$($Smallest[0])][$($Smallest[1])] to: $Option"
        $NewArray[$Smallest[0]][$Smallest[1]] = @($Option)
        if($AnswerCount -lt $HowManyAnswersYouWanttoGet){
            GoCalculate($NewArray)
        }
    }
}
# 触发
GoCalculate($SudokuMatrix)

# 输出结果
$Results | %{
    if($_ -eq $null){return}
    Write-Host "Answer:" -ForegroundColor Yellow
    for($i = 0; $i -lt 9; $i++){
        for($j = 0; $j -lt 9; $j++){
            Write-Host "$($_[$i][$j][0]) " -NoNewline -ForegroundColor yellow
        }
        Write-Host "`n"
    }
}