###########################################################################################
# Solve-Sukoku.ps1 - script to solve sudoku puzzles
#	Usage: .\solve-sudoku.ps1 <puzzleFile>
#		puzzleFile - File to containing puzzle to solve (ignores non-numerics)
#
#	Origionaly derived from ps1.soapyfrog.com (http://ps1.soapyfrog.com/2007/01/05/sudoku/)
#	Solving strategies credited to http://www.scanraid.com/sudoku.htm
#
#	Script by Mark Sheppard http://mark-sheppard.spaces.live.com
###########################################################################################

###########################################################################################
# puzzleFile parameter
param($puzzleFile)

###########################################################################################
# Solving finctions

###########################################################################################
# Solve-Puzzle - Main puzzle loop
#
function Solve-Puzzle {	
	$pass = 0;
	$continue = $true;
	$solvedResult = 0;
	$result = $false;
	$timeTaken;
	while ($continue) {
		$pass++;
		write-host "Pass: $pass";
		#write-host "$(Format-PuzzleFull)";
		#Read-Host "Press return to complete pass $pass";

		$timeTaken = measure-command { $solvedResult = Check-Solved; }
		write-host "`tCheck-Solved: $solvedResult ($timeTaken)";
		if ($solvedResult -eq -1) { break; } # All done!
		
		$timeTaken = measure-command { $result = Calc-Possibles; }
		write-host "`tCalc-Possibles: $result ($timeTaken)";
		if ($result) { continue; }

		$timeTaken = measure-command { $result = Calc-SinglesInColRow; }
		write-host "`tCalc-SinglesInColRow: $result ($timeTaken)";
		if ($result) { continue; }

		$timeTaken = measure-command { $result = Calc-SinglesInBox; }
		write-host "`tCalc-SinglesInBox: $result ($timeTaken)";
		if ($result) { continue; }

		$timeTaken = measure-command { $result = Calc-NakedPairs; }
		write-host "`tCalc-NakedPairs: $result ($timeTaken)";
		if ($result) { continue; }

		$timeTaken = measure-command { $result = Calc-NakedTripples; }
		write-host "`tCalc-NakedTripples: $result ($timeTaken)";
		if ($result) { continue; }

		$timeTaken = measure-command { $result = Calc-HiddenPairs; }
		write-host "`tCalc-HiddenPairs: $result ($timeTaken)";
		if ($result) { continue; }

		$continue = $false;
	}
	Write-Host "Passes: $pass";
}

###########################################################################################
# Check-Solved - Loops through puzzle array and marks squares as solved that only
#	contain one possible value
#
function Check-Solved {
	[int]$solved = 0;
	[int]$totalSolved = 0;
	for ($i = 0; $i -lt 81; $i++) {
		if ($puzzle[$i][10]) { # Square already solved. force bitmask to 0
			$totalSolved++;
		}
		else {
			if ($puzzle[$i][12] -eq 1) {
				for ($num = 1; $num -lt 10; $num++) {
					if ($puzzle[$i][$num]) {
						$result = Solve-Square $i $num;
						$solved++;
						$totalSolved++;
						#Write-Debug "Solved: $i; Value=$num";
						break;
					}
				}
			}
		}
	}
	
	if ($totalSolved -eq 81) { # All done!
		return -1;
	}
	else {
		return $solved;
	}
}

###########################################################################################
# Calc-Possibles - Removes solved squares in col, row or box from each square
#
function Calc-Possibles {
	$change = $false;
	for ($x = 0; $x -lt 9; $x++) {
		$solvedInCol = 0;
		$solvedInRow = 0;
		$solvedInBox = 0;
		for ($y = 0; $y -lt 9; $y++) {
			# Check col
			$i = $x + ($y * 9);
			if ($puzzle[$i][10]) {
				$solvedInCol += [Math]::Pow(2, $puzzle[$i][0] - 1);
			}
			
			# Check row
			$i = $y + ($x * 9);
			if ($puzzle[$i][10]) {
				$solvedInRow += [Math]::Pow(2, $puzzle[$i][0] - 1);
			}
			
			# Check box
			$i = (($x - ($x % 3)) * 9) + (($x % 3) * 3) + ([Math]::Floor($y/3) * 9) + ($y % 3);
			if ($puzzle[$i][10]) {
				$solvedInBox += [Math]::Pow(2, $puzzle[$i][0] - 1);
			}
		}
		# Remove any solved values from possibles
		for ($y = 0; $y -lt 9; $y++) {
			# Remove solved from others in col
			if ($solvedInCol -ne 0) {
				$i = $x + ($y * 9);
				if (!$puzzle[$i][10]) {
					if ($puzzle[$i][11] -ne ($puzzle[$i][11] - ($puzzle[$i][11] -band $solvedInCol))) {
						$change = Remove-PossiblesBitMaskFromSquare $i $solvedInCol;
					}
					#Write-Debug "Possibles removed (col): $i; RemoveBitMask=$solvedInCol; change=$change";

				}
			}
			
			# Remove solved from others in row
			if ($solvedInRow -ne 0) {
				$i = $y + ($x * 9);
				if (!$puzzle[$i][10]) {
					if ($puzzle[$i][11] -ne ($puzzle[$i][11] - ($puzzle[$i][11] -band $solvedInRow))) {
						$change = Remove-PossiblesBitMaskFromSquare $i $solvedInRow;
					}
					#Write-Debug "Possibles removed (row): $i; RemoveBitMask=$solvedInRow; change=$change";
				}
			}
			
			# Remove solved from others in box
			if ($solvedInBox -ne 0) {
				$i = (($x - ($x % 3)) * 9) + (($x % 3) * 3) + ([Math]::Floor($y/3) * 9) + ($y % 3);
				if (!$puzzle[$i][10]) {
					if ($puzzle[$i][11] -ne ($puzzle[$i][11] - ($puzzle[$i][11] -band $solvedInBox))) {
						$change = Remove-PossiblesBitMaskFromSquare $i $solvedInBox;
					}
					#Write-Debug "Possibles removed (box): $i; RemoveBitMask=$solvedInBox; change=$change";
				}
			}
		}
	}
		
	return $change;
}

###########################################################################################
# Calc-SinglesInColRow - Looks for squares that contain the only instance of a possible
#	for each col or row and marks it solved
#
function Calc-SinglesInColRow {
	$change = $false;
	
	for ($x = 0; $x -lt 9; $x++) {
		for ($num = 1; $num -lt 10; $num++) {
			$countCol = 0;
			$posCol = 0;
			$countRow = 0;
			$posRow = 0;
			for ($y = 0; $y -lt 9; $y++) {
				# Check col
				$i = $x + ($y * 9);
				if ($countCol -lt 2 -and $puzzle[$i][$num] -and -not $puzzle[$i][10]) {
					$posCol = $i;
					$countCol++;
				}
				
				# Check row
				$i = $y + ($x * 9);
				if ($countRow -lt 2 -and $puzzle[$i][$num] -and -not $puzzle[$i][10]) {
					$posRow = $i;
					$countRow++;
				}
			}
			if ($countCol -eq 1) { # Found instance (col)
				$change = Solve-Square $posCol $num;
				#Write-Debug "Single (col): i=$posCol, value=$num :: Change=$change";
			}
			if ($countRow -eq 1) { # Found instance (row)
				$change = Solve-Square $posRow $num;
				#Write-Debug "Single (row): i=$posRow, value=$num :: Change=$change";
			}
		}
	}
	
	return $change;
}

###########################################################################################
# Calc-SinglesInBox - Looks for squares that contain the only instance of a possible
#	for each box and marks it solved
#
function Calc-SinglesInBox {
	$change = $false;
	
	for ($box = 0; $box -lt 9; $box++) {
		for ($num = 1; $num -lt 10; $num++) {
			$countBox = 0;
			$posBox = 0;
			for ($pos = 0; $pos -lt 9; $pos++) {
				$i = (($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($pos/3) * 9) + ($pos % 3);
				if ($puzzle[$i][$num] -and -not $puzzle[$i][10]) {
					$posBox = $i;
					$countBox++;
					if ($countBox -gt 1) { break; }
				}
			}
			if ($countBox -eq 1) { # Found instance (box)
				$change = Solve-Square $posBox $num;
				#Write-Debug "Single (box): i=$posBox, value=$num :: Change=$change";
			}
		}
	}

	return $change;
}

###########################################################################################
# Calc-NakedTripples - Looks for the pattern refered to as a Naked Tripple and removes
#	tripple values from other squares in the col, row or box that the tripple was found in.
#	http://www.scanraid.com/BasicStrategies.htm#NT
#
function Calc-NakedTripples {
	$change = $false;
	
	for ($x = 0; $x -lt 9; $x++) {
		for ($y1 = 0; $y1 -lt 7; $y1++) {
			$i1 = $x + ($y1 * 9);
			$j1 = $y1 + ($x * 9);
			$k1 = (($x - ($x % 3)) * 9) + (($x % 3) * 3) + ([Math]::Floor($y1/3) * 9) + ($y1 % 3);
			
			for ($y2 = ($y1 + 1); $y2 -lt 8; $y2++) {
				$i2 = $x + ($y2 * 9);
				$j2 = $y2 + ($x * 9);
				$k2 = (($x - ($x % 3)) * 9) + (($x % 3) * 3) + ([Math]::Floor($y2/3) * 9) + ($y2 % 3);
				
				for ($y3 = ($y2 + 1); $y3 -lt 9; $y3++) {
					$i3 = $x + ($y3 * 9);
					$j3 = $y3 + ($x * 9);
					$k3 = (($x - ($x % 3)) * 9) + (($x % 3) * 3) + ([Math]::Floor($y3/3) * 9) + ($y3 % 3);
				
					# Check col for naked-tripple
					if (!$puzzle[$i1][10] -and !$puzzle[$i2][10] -and !$puzzle[$i3][10]) { # Ensure values haven't already been solved
						$col = $x;
						$tValue = $puzzle[$i1][11] -bor $puzzle[$i2][11] -bor $puzzle[$i3][11];
						if ($(Count-Bits $tValue) -eq 3) { # A naked-tripple!
							# Get tripple values
							$n1 = 0;
							$n2 = 0;
							$n3 = 0;
							for ($n = 1; $n -lt 10; $n++) {
								if ($tValue -band [Math]::Pow(2, $n - 1)) {
									if ($n1 -eq 0) { $n1 = $n; }
									elseif ($n2 -eq 0) { $n2 = $n; }
									else { $n3 = $n; }
								}
							}
							
							# Remove $n1, $n2 or $n3 from other squares in column
							for ($row = 0; $row -lt 9; $row++) {
								if ($row -eq $y1 -or $row -eq $y2 -or $row -eq $y3) { continue; } # One of the tripple members, skip
								$pos = $col + ($row * 9);
								if ($puzzle[$pos][10]) { continue; } # Already solved, skip
								if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $tValue))) {
									$change = Remove-PossiblesBitMaskFromSquare $pos $tValue;
								}
							}
							#Write-Debug "Naked-tripple (col): $i1, $i2, $i3 ($n1, $n2, $n3) $change";
						}
					}
					
					# Check row for naked-tripple
					if (!$puzzle[$j1][10] -and !$puzzle[$j2][10] -and !$puzzle[$j3][10]) { # Ensure values haven't already been solved
						$row = $x;
						$tValue = $puzzle[$j1][11] -bor $puzzle[$j2][11] -bor $puzzle[$j3][11];
						if ($(Count-Bits $tValue) -eq 3) { # A naked-tripple!
							# Get tripple values
							$n1 = 0;
							$n2 = 0;
							$n3 = 0;
							for ($n = 1; $n -lt 10; $n++) {
								if ($tValue -band [Math]::Pow(2, $n - 1)) {
									if ($n1 -eq 0) { $n1 = $n; }
									elseif ($n2 -eq 0) { $n2 = $n; }
									else { $n3 = $n; }
								}
							}

							# Remove $n1, $n2 or $n3 from other squares in row
							for ($col = 0; $col -lt 9; $col++) {
								if ($col -eq $y1 -or $col -eq $y2 -or $col -eq $y3) { continue; } # One of the tripple members, skip
								$pos = $col + ($row * 9);
								if ($puzzle[$pos][10]) { continue; } # Already solved, skip
								if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $tValue))) {
									$change = Remove-PossiblesBitMaskFromSquare $pos $tValue;
								}
							}
							#Write-Debug "Naked-tripple (row): $j1, $j2, $j3 ($n1, $n2, $n3) $change";
						}
					}
					
					# Check box for naked-tripple
					if (!$puzzle[$k1][10] -and !$puzzle[$k2][10] -and !$puzzle[$k3][10]) { # Ensure values haven't already been solved
						$box = $x;
						$tValue = $puzzle[$k1][11] -bor $puzzle[$k2][11] -bor $puzzle[$k3][11];
						if ($(Count-Bits $tValue) -eq 3) { # A naked-tripple!
							# Get tripple values
							$n1 = 0;
							$n2 = 0;
							$n3 = 0;
							for ($n = 1; $n -lt 10; $n++) {
								if ($tValue -band [Math]::Pow(2, $n - 1)) {
									if ($n1 -eq 0) { $n1 = $n; }
									elseif ($n2 -eq 0) { $n2 = $n; }
									else { $n3 = $n; }
								}
							}

							# Remove $n1, $n2 or $n3 from other squares in box
							for ($i = 0; $i -lt 9; $i++) {
								if ($i -eq $y1 -or $i -eq $y2 -or $i -eq $y3) { continue; } # One of the tripple members, skip
								$pos = (($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($i/3) * 9) + ($i % 3);
								if ($puzzle[$pos][10]) { continue; } # Already solved, skip
								if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $tValue))) {
									$change = Remove-PossiblesBitMaskFromSquare $pos $tValue;
								}
							}
							#Write-Debug "Naked-tripple (box): $k1, $k2, $k3 ($n1, $n2, $n3) $change";
						}
					}
					
				}
			}
		}
	}
	
	return $change;
}

###########################################################################################
# Calc-NakedPairs - Looks for the pattern refered to as a Naked Pair and removes
#	pair values from other squares in the col, row or box that the pair was found in.
#	http://www.scanraid.com/BasicStrategies.htm#NP
#
function Calc-NakedPairs {
	$change = $false;
	for ($i = 0; $i -lt 81; $i++) {
		if ($puzzle[$i][10]) { continue; } # already solved
		if ($puzzle[$i][12] -eq 2) {
			# Look for item in col, row or box with same naked-pair
			$iCol = $i % 9;
			$iRow = [Math]::Floor($i/9);
			$iBox = [Math]::Floor($iCol/3) + (3 * [Math]::Floor($iRow/3))
			$colPos = 0;
			$rowPos = 0;
			$boxPos = 0;
			$colFoundPair = $false;
			$rowFoundPair = $false;
			$boxFoundPair = $false;

			for ($y = 0; $y -lt 9; $y++) {
				# Look in iCol
				$row = $y
				$pos = $iCol + ($row * 9);
				if (-not $colFoundPair -and $row -ne $iRow -and -not $puzzle[$pos][10]) {
					if ($puzzle[$pos][12] -eq 2 -and $puzzle[$pos][11] -eq $puzzle[$i][11]) {
						# Match with $pos
						$colPos = $pos;
						$colFoundPair = $true;
					}
				}
				
				# Look in iRow
				$col = $y;
				$pos = $col + ($iRow * 9);
				if (-not $rowFoundPair -and $col -ne $iCol -and -not $puzzle[$pos][10]) { 
					if ($puzzle[$pos][12] -eq 2 -and $puzzle[$pos][11] -eq $puzzle[$i][11]) {
						# Match with $pos
						$rowPos = $pos;
						$rowFoundPair = $true;
						break;
					}
				}

				# Look in i's box
				$foundPair = $false;
				$pos = (($iBox - ($iBox % 3)) * 9) + (($iBox % 3) * 3) + ([Math]::Floor($y/3) * 9) + ($y % 3);
				if (-not $boxFoundPair -and $i -ne $pos -and -not $puzzle[$pos][10]) {
					if ($puzzle[$pos][12] -eq 2 -and $puzzle[$pos][11] -eq $puzzle[$i][11]) {
						# Match with $pos
						$boxPos = $pos;
						$boxFoundPair = $true;
						break;
					}
				}
			}
			if ($colFoundPair) {
				for ($row = 0; $row -lt 9; $row++) {
					$pos = $iCol + ($row * 9);
					if ($pos -eq $i) { continue; } # i's row, ignore
					if ($pos -eq $colPos) { continue; } # i2's row, ignore
					if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $puzzle[$i][11]))) {
						$change = Remove-PossiblesBitMaskFromSquare $pos $puzzle[$i][11];
					}
				}
				#Write-Debug "Naked-Pair (col): $i and $colPos (bitmask: $($puzzle[$i][11])) $change";
			}

			if ($rowFoundPair) { # Remove $n1 and $n2 from all possibles for row
				for ($col = 0; $col -lt 9; $col++) {
					$pos = $col + ($iRow * 9);
					if ($pos -eq $i) { continue; } # i's col, ignore
					if ($pos -eq $rowPos) { continue; } # i2's col, ignore
					if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $puzzle[$i][11]))) {
						$change = Remove-PossiblesBitMaskFromSquare $pos $puzzle[$i][11];
					}
				}
				#Write-Debug "Naked-Pair (row): $i and $rowPos (bitmask: $($puzzle[$i][11])) $change";
			}
			
			if ($boxFoundPair) { # Remove $n1 and $n2 from all possibles for box
				for ($j = 0; $j -lt 9; $j++) {
					$pos = (($iBox - ($iBox % 3)) * 9) + (($iBox % 3) * 3) + ([Math]::Floor($j/3) * 9) + ($j % 3);
					if ($pos -eq $i) { continue; } # i's pos, ignore
					if ($pos -eq $boxPos) { continue; } # i2's pos, ignore
					if ($puzzle[$pos][11] -ne ($puzzle[$pos][11] - ($puzzle[$pos][11] -band $puzzle[$i][11]))) {
						$change = Remove-PossiblesBitMaskFromSquare $pos $puzzle[$i][11];
					}
				}
				#Write-Debug "Naked-Pair (box): $i and $boxPos (bitmask: $($puzzle[$i][11])) $change";
			}

		}
	}
	return $change;
}

###########################################################################################
# Calc-HiddenPairs - Looks for the pattern refered to as a Hidden Pair and removes
#	pair values from other squares in the col, row or box that the pair was found in.
#	http://www.scanraid.com/BasicStrategies.htm#HP
#
function Calc-HiddenPairs {
	$change = $false;

	for ($box = 0; $box -lt 9; $box++) {
		# Get position of each possible number
		[int[]]$positions = (0, 0, 0, 0, 0, 0, 0, 0, 0);
		for ($num = 1; $num -lt 10; $num++) {
			for ($pos = 0; $pos -lt 9; $pos++) {
				$i = (($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($pos/3) * 9) + ($pos % 3);
				if (-not $puzzle[$i][10]) {
					if ($puzzle[$i][11] -band [Math]::Pow(2, $num - 1)) {
						$positions[$num - 1] += [Math]::Pow(2, $pos);
					}
				}
			}
		}
		for ($num1 = 1; $num1 -lt 9; $num1++) {	
			for ($num2 = $num1 + 1; $num2 -lt 10; $num2++) {
				if (($positions[$num1 - 1] -eq $positions[$num2 - 1]) -and (Count-Bits $positions[$num1 - 1]) -eq 2) {
					# Get position of numbers in unit
					$i1 = -1;
					$i2 = -1;
					for ($pos = 0; $pos -lt 9; $pos++) {
						if ($positions[$num1 - 1] -band [Math]::Pow(2, $pos)) {
							if ($i1 -eq -1) { $i1 = ((($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($pos/3) * 9) + ($pos % 3)); }
							else { $i2 = ((($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($pos/3) * 9) + ($pos % 3)); }
						}
					}
					$removeBitmask = 0;
					for ($num = 1; $num -lt 10; $num++) {
						if (($num -ne $num1) -and ($num -ne $num2)) {
							$removeBitmask += [Math]::Pow(2, $num - 1);
						}
					}
					if ($puzzle[$i1][11] -ne ($puzzle[$i1][11] - ($puzzle[$i1][11] -band $removeBitmask))) {
						$change = Remove-PossiblesBitMaskFromSquare $i1 $removeBitmask;
					}
					if ($puzzle[$i2][11] -ne ($puzzle[$i2][11] - ($puzzle[$i2][11] -band $removeBitmask))) {
						$change = Remove-PossiblesBitMaskFromSquare $i2 $removeBitmask;
					}
					#Write-Debug "Hidden-Pair (box): $i1, $i2 ($num1, $num2) $change";
				}
			}
		}
	}
	
	for ($col = 0; $col -lt 9; $col++) {
		# Get position of each possible number
		[int[]]$positions = (0, 0, 0, 0, 0, 0, 0, 0, 0);
		for ($num = 1; $num -lt 10; $num++) {
			for ($row = 0; $row -lt 9; $row++) {
				$i = $col + ($row * 9);
				if (!$puzzle[$i][10]) {
					if ($puzzle[$i][11] -band [Math]::Pow(2, $num - 1)) {
						$positions[$num - 1] += [Math]::Pow(2, $row);
					}
				}
			}
		}
		for ($num1 = 1; $num1 -lt 9; $num1++) {	
			for ($num2 = $num1 + 1; $num2 -lt 10; $num2++) {
				if ($positions[$num1 - 1] -eq $positions[$num2 - 1] -and (Count-Bits $positions[$num1 - 1]) -eq 2) {
					# Get position of numbers in unit
					for ($row = 0; $row -lt 9; $row++) {
						$i1 = -1;
						$i2 = -1;
						if (($positions[$num1 - 1]) -band [Math]::Pow(2, $row)) {
							if ($i1 -lt 0) { $i1 = $col + ($row * 9); }
							else {$i2 = $col + ($row * 9); }
						}

						$removeBitmask = 0;
						for ($num = 1; $num -lt 10; $num++) {
							if (($num -ne $num1) -and ($num -ne $num2)) {
								$removeBitmask += [Math]::Pow(2, $num - 1);
							}
						}
						if ($puzzle[$i1][11] -ne ($puzzle[$i1][11] - ($puzzle[$i1][11] -band $removeBitmask))) {
							$change = Remove-PossiblesBitMaskFromSquare $i1 $removeBitmask;
						}
						if ($puzzle[$i2][11] -ne ($puzzle[$i2][11] - ($puzzle[$i2][11] -band $removeBitmask))) {
							$change = Remove-PossiblesBitMaskFromSquare $i2 $removeBitmask;
						}
						#Write-Debug "Hidden-Pair (col): $i1, $i2 ($num1, $num2) $change";
					}
				}
			}
		}
	}
	
	for ($row = 0; $row -lt 9; $row++) {
		# Get position of each possible number
		[int[]]$positions = (0, 0, 0, 0, 0, 0, 0, 0, 0);
		for ($num = 1; $num -lt 10; $num++) {
			for ($col = 0; $col -lt 9; $col++) {
				$i = $col + ($row * 9);
				if (!$puzzle[$i][10]) {
					if ($puzzle[$i][11] -band [Math]::Pow(2, $num - 1)) {
						$positions[$num - 1] += [Math]::Pow(2, $col);
					}
				}
			}
		}
		for ($num1 = 1; $num1 -lt 9; $num1++) {	
			for ($num2 = $num1 + 1; $num2 -lt 10; $num2++) {
				if ($positions[$num1 - 1] -eq $positions[$num2 - 1] -and (Count-Bits $positions[$num1 - 1]) -eq 2) {
					# Get position of numbers in unit
					for ($col = 0; $col -lt 9; $col++) {
						$i1 = -1;
						$i2 = -1;
						if (($positions[$num1 - 1]) -band [Math]::Pow(2, $col)) {
							if ($i1 -lt 0) { $i1 = $col + ($row * 9); }
							else {$i2 = $col + ($row * 9); }
						}

						$removeBitmask = 0;
						for ($num = 1; $num -lt 10; $num++) {
							if (($num -ne $num1) -and ($num -ne $num2)) {
								$removeBitmask += [Math]::Pow(2, $num - 1);
							}
						}
						if ($puzzle[$i1][11] -ne ($puzzle[$i1][11] - ($puzzle[$i1][11] -band $removeBitmask))) {
							$change = Remove-PossiblesBitMaskFromSquare $i1 $removeBitmask;
						}
						if ($puzzle[$i2][11] -ne ($puzzle[$i2][11] - ($puzzle[$i2][11] -band $removeBitmask))) {
							$change = Remove-PossiblesBitMaskFromSquare $i2 $removeBitmask;
						}
						#Write-Debug "Hidden-Pair (row): $i1, $i2 ($num1, $num2) $change";
					}
				}
			}
		}
	}

	return $change;
}
	
###########################################################################################
# Helper functions

###########################################################################################
# Get-Puzzle - reads the specified puzzle file into memory for solving
#
function Get-Puzzle {
	$i=0;
	get-content -erroraction "stop" $puzzleFile | foreach {  # for each line
		([char[]]$_) | foreach {  # for each character
			if ($_ -ge [char]"0" -and $_ -le [char]"9") {
				$num = [int][string]$_;
				$puzzle[$i][0] = $num;
				if ($num -gt 0) {
					Solve-Square $i $num;
				}
				$i++;
      }
    }
  }
  if ($i -ne 81) { throw "puzzle should have 81 numbers, found $i" }
}

###########################################################################################
# Format-Puzzle - Renders the current puzzle array to screen
#
function Format-Puzzle {
	[System.Text.StringBuilder]$sb = new-object System.Text.StringBuilder;
	[System.IO.StringWriter]$output = New-Object System.IO.StringWriter $sb
	for ($i=0; $i -lt 81; $i++) {
		$iCol = $i % 9;
		$iRow = [Math]::Floor($i/9);
		if ($puzzle[$i][10]) { # if solved
			$output.Write($puzzle[$i][0]);
		}
		else {
			$output.Write(".");
		}
			$output.Write(" ");
		if (2,5 -eq $iCol) { $output.Write(" "); }
		if ($iCol -eq 8) {
			$output.Write("`n");
			if (2,5 -eq $iRow) { $output.Write("`n"); }
		}
	}
	return $sb.ToString();
}

###########################################################################################
# Format-PuzzleFull - renders the puzzle grid, displaying only the possible values for each
#	square
#
function Format-PuzzleFull {
	[System.Text.StringBuilder]$sb = new-object System.Text.StringBuilder;
	[System.IO.StringWriter]$output = New-Object System.IO.StringWriter $sb
	
	for ($row = 0; $row -lt 9; $row++) {
		$pos = $row * 9;

		$output.Write("`n+---+---+---+`t+---+---+---+`t+---+---+---+`n");

		$output.Write("|");
		if ($puzzle[$pos + 0][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 1][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 2][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|`t|");									 
		if ($puzzle[$pos + 3][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 4][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 5][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|`t|");									 
		if ($puzzle[$pos + 6][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 7][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][3]) { $output.Write("3"); } else { $output.Write(" "); }
		$output.Write("|");										 
		if ($puzzle[$pos + 8][1]) { $output.Write("1"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][2]) { $output.Write("2"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][3]) { $output.Write("3"); } else { $output.Write(" "); }
		
		$output.Write("|`n|");

		if ($puzzle[$pos + 0][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 1][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 2][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|`t|");				  
		if ($puzzle[$pos + 3][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 4][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 5][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|`t|");				  
		if ($puzzle[$pos + 6][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 7][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][6]) { $output.Write("6"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 8][4]) { $output.Write("4"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][5]) { $output.Write("5"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][6]) { $output.Write("6"); } else { $output.Write(" "); }
		
		$output.Write("|`n|");

		if ($puzzle[$pos + 0][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 0][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 1][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 1][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 2][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 2][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|`t|");				  
		if ($puzzle[$pos + 3][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 3][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 4][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 4][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 5][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 5][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|`t|");				  
		if ($puzzle[$pos + 6][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 6][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 7][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 7][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");					  
		if ($puzzle[$pos + 8][7]) { $output.Write("7"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][8]) { $output.Write("8"); } else { $output.Write(" "); }
		if ($puzzle[$pos + 8][9]) { $output.Write("9"); } else { $output.Write(" "); }
		$output.Write("|");

		if ($row -eq 2 -or $row -eq 5 -or $row -eq 8) {
			$output.Write("`n+---+---+---+`t+---+---+---+`t+---+---+---+`n");
		}
		
	}
	
	return $sb.ToString();
}

###########################################################################################
# Count-Bits - Counts the number of bits set in the passsed int
#
function Count-Bits([int]$i) {
	$result = 0;

	if ($i -band 1) { $result++; }
	if ($i -band 2) { $result++; }
	if ($i -band 4) { $result++; }
	if ($i -band 8) { $result++; }
	if ($i -band 16) { $result++; }
	if ($i -band 32) { $result++; }
	if ($i -band 64) { $result++; }
	if ($i -band 128) { $result++; }
	if ($i -band 256) { $result++; }
	
	return $result;
}

###########################################################################################
# Solve-Square - Solves the specified square $i with the specified number $number
#
function Solve-Square([int]$i, [int]$number) {
	$script:puzzle[$i][0] = $number;
	$script:puzzle[$i][1] = $false;
	$script:puzzle[$i][2] = $false;
	$script:puzzle[$i][3] = $false;
	$script:puzzle[$i][4] = $false;
	$script:puzzle[$i][5] = $false;
	$script:puzzle[$i][6] = $false;
	$script:puzzle[$i][7] = $false;
	$script:puzzle[$i][8] = $false;
	$script:puzzle[$i][9] = $false;
	$script:puzzle[$i][10] = $true;
	$script:puzzle[$i][11] = 0;
	$script:puzzle[$i][12] = 0;
	
	return $true;
}

###########################################################################################
# Remove-PossiblesBitMaskFromSquare - Removes the specifed bitmask $possiblesBitMaskToRemove
#	from the specified square $i
#
function Remove-PossiblesBitMaskFromSquare([int]$i, [int]$possiblesBitMaskToRemove) {
	$initialBitMask = $script:puzzle[$i][11];
	$script:puzzle[$i][11] -= ($script:puzzle[$i][11] -band $possiblesBitMaskToRemove);
	$change = ($script:puzzle[$i][11] -ne $initialBitMask);

	if ($change) {
		if ($possiblesBitMaskToRemove -band 1) { $script:puzzle[$i][1] = $false; }
		if ($possiblesBitMaskToRemove -band 2) { $script:puzzle[$i][2] = $false; }
		if ($possiblesBitMaskToRemove -band 4) { $script:puzzle[$i][3] = $false; }
		if ($possiblesBitMaskToRemove -band 8) { $script:puzzle[$i][4] = $false; }
		if ($possiblesBitMaskToRemove -band 16) { $script:puzzle[$i][5] = $false; }
		if ($possiblesBitMaskToRemove -band 32) { $script:puzzle[$i][6] = $false; }
		if ($possiblesBitMaskToRemove -band 64) { $script:puzzle[$i][7] = $false; }
		if ($possiblesBitMaskToRemove -band 128) { $script:puzzle[$i][8] = $false; }
		if ($possiblesBitMaskToRemove -band 256) { $script:puzzle[$i][9] = $false; }
		$script:puzzle[$i][12] = Count-Bits $script:puzzle[$i][11];
	}
	
	return $change;
}

###########################################################################################
###########################################################################################

###########################################################################################
# $puzzle - main puzzle array.
#	[i][0]  = Solved number
#	[i][n]  = n(1-9) is possible in square? (all false for solved squares)
#	[i][10] = Square is solved
#	[i][11] = Puzzle mask (bit map of available numbers) (0 for solved squares)
#	[i][12] = Count of possibles (0 for solved squares)
$puzzle = (0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9),(0,$true,$true,$true,$true,$true,$true,$true,$true,$true,$false,511,9);

###########################################################################################
# Main code - starts the solving process off
$dur = measure-command {
	Get-Puzzle $puzzleFile;
	write-host "Puzzle start state:`n$(format-puzzle)";
	Solve-Puzzle;
	write-host "Solve lop complete.  End state:`n$(format-puzzle)";
}
write-host "Elapsed time $dur"

###########################################################################################
# Notes
#	$i = index of array (0-80)
#	$iCol = $i % 9
#	$iRow = [Math]::Floor($i/9)
#	$i = $iCol + ($iRow * 9)
#
#	$b = box number (0-8) = [Math]::Floor($iCol/3) + (3 * [Math]::Floor($iRow/3))
#	$bCol1 = 3 * [Math]::Floor($iCol/3)
#	$bRow1 = 3 * [Math]::Floor($iRow/3)
#	$bi = $bCol1 + ($bRow1 * 9)
#	$b1 = (($box - ($box % 3)) * 9) + (($box % 3) * 3)
#	$i = (($box - ($box % 3)) * 9) + (($box % 3) * 3) + ([Math]::Floor($pos/3) * 9) + ($pos % 3);