# 数独解法 Sudoku Solver
# 引数 問題 (\@Problem)
# 戻り値 答え (@SudokuSolver)
sub SUDOKUSOLVER{
	my ($Problem) = @_;
	my @SudokuSolver = @$Problem;
	my @Move = ();
	my @CheckBlock = ();
	my @CheckNumber = ();
	my $GetNumber = 0;
	my $Column = 0;
	my $Row = 0;
	my $BlockPosition = 0;
	my $IsBack = 0;
	my $Count = 0;
	
	# 重複の確認 Check Repetition
	&CheckRepetition(\@Problem);
	
	# (0, 0) から (8, 8) 移動ルート Move
	@Move = &Move(\@SudokuSolver);
	$Count = @Move;
	
	# ブロック内(3 * 3)で使用できる数字列 Check Block
	@CheckBlock = &CheckBlock(\@SudokuSolver);
	
	for(my $i = 0; $i < $Count; $i++){
		# 縦 横 ブロックの番号
		$Column = $Move[$i][0];
		$Row = $Move[$i][1];
		$BlockPosition = $Move[$i][2];
	
		# 使用可能な数字列を取り出す Check Number
		$CheckNumber[$i] = &CheckNumber($Column, $Row, $CheckBlock[$BlockPosition], \@SudokuSolver) if($IsBack == 0);
		# 数字を一つ取り出す Get Number
		$GetNumber = &GetNumber(\$CheckNumber[$i]);
		# フラグ
		$IsBack = 0;
	
		if($GetNumber eq ""){
			# 一つ後ろ
			$i--;
	
			# 失敗
			if($i == -1){
				print "Failure";
				exit();
			}
	
			# 縦 横 ブロックの番号
			$Column = $Move[$i][0];
			$Row = $Move[$i][1];
			$BlockPosition = $Move[$i][2];
			# 使用した数字を戻す
			$CheckBlock[$BlockPosition] = $CheckBlock[$BlockPosition] . $SudokuSolver[$Column][$Row];
			# 使用した数字を削除
			$SudokuSolver[$Column][$Row] = 0;
			# フラグ
			$IsBack = 1;
	
			# forの$i++があるので
			$i--;
		}else {
			# 数独解法 Sudoku SudokuSolver
			$SudokuSolver[$Column][$Row] = $GetNumber;
			# 使用した数字を取り除く
			substr($CheckBlock[$BlockPosition], index($CheckBlock[$BlockPosition], $SudokuSolver[$Column][$Row]), 1) = "";
		}
	}
	
	return @SudokuSolver;
}
	
# 数字を一つ取り出す Get Number
# 引数 値 (\$Number)
# 戻り値 数字 ($GetNumber)
sub GetNumber{
	my ($Number) = @_;
	my $GetNumber = substr($$Number, 0, 1);
	
	# 使用した値を削除
	substr($$Number, 0, 1) = "";
	
	return $GetNumber;
}
	
# ブロック内(3 * 3)で使用できる数字列 Check Block
# 引数 数独 (\@Sudoku)
# 戻り値 使用できる数字列 ($CheckBlock)
sub CheckBlock{
	my ($Sudoku) = @_;
	my @CheckBlock = ();
	my $Number = 0;
	my $Column = 0;
	my $Row = 0;
	my $BeginColumn = 0;
	my $EndColumn = 0;
	my $BeginRow = 0;
	my $EndRow = 0;
	my $Position = 0;
	
	for(my $i = 0; $i < 9; $i++){
		$Column = $i;
		$Row = ($i % 3) * 3;
	
		# 初期化
		$Number = "123456789";
		$BeginColumn = $Column - ($Column % 3);
		$EndColumn = $BeginColumn + 3;
		$BeginRow = $Row - ($Row % 3);
		$EndRow = $BeginRow + 3;
	
		for(my $j = $BeginColumn; $j < $EndColumn; $j++){
			for(my $k = $BeginRow; $k < $EndRow; $k++){
				# 数字の位置を取得
				$Position = index($Number, $$Sudoku[$j][$k]);
				# 使用済みの数字があるなら削除
				substr($Number, $Position, 1) = "" if($Position != -1);
			}
		}
	
		$CheckBlock[$i] = $Number;
	}
	
	return @CheckBlock;
}
	
# 使用可能な数字列を取り出す Check Number
# 引数 縦 横 数字 数独 ($Column, $Row, $Number, \@Sudoku)
# 戻り値 使用可能な数字列 ($CheckNumber)
sub CheckNumber{
	my ($Column, $Row, $CheckBlock, $Sudoku) = @_;
	my $CheckNumber = $CheckBlock;
	my $Position = 0;
	
	# 空白
	if($CheckNumber eq ""){
		return $CheckNumber;
	}
	
	for(my $i = 0; $i < 9; $i++){
		# 縦
		if($i != $Column){
			# 数字の位置を取得
			$Position = index($CheckNumber, $$Sudoku[$i][$Row]);
			# 使用済みの数字があるなら削除
			substr($CheckNumber, $Position, 1) = "" if($Position != -1);
		}
	
		# 横
		if($i != $Row){
			# 数字の位置を取得
			$Position = index($CheckNumber, $$Sudoku[$Column][$i]);
			# 使用済みの数字があるなら削除
			substr($CheckNumber, $Position, 1) = "" if($Position != -1);
		}
	}
	
	return $CheckNumber;
}
	
# 重複の確認 Check Repetition
# 引数 数独 (\@Sudoku)
# 戻り値 なし ()
sub CheckRepetition{
	my ($Sudoku) = @_;
	my $NumberColumn = 0;
	my $NumberRow = 0;
	my $NumberBlock = 0;
	my $BlockColumn = 0;
	my $BlockRow = 0;
	my $PositionColumn = 0;
	my $PositionRow = 0;
	my $PositionBlock = 0;
	
	for(my $i = 0; $i < 9; $i++){
		# 初期化
		$NumberColumn = "123456789";
		$NumberRow = "123456789";
		$NumberBlock = "123456789";
		$BlockColumn = int($i / 3) * 3;
		$BlockRow = ($i % 3) * 3;
	
		for(my $j = 0; $j < 9; $j++){
			my $BlcCol = $BlockColumn + int($j / 3);
			my $BlcRow = $BlockRow + ($j % 3);
	
			$PositionColumn = index($NumberColumn, $$Sudoku[$j][$i]);
			$PositionRow = index($NumberRow, $$Sudoku[$i][$j]);
			$PositionBlock = index($NumberBlock, $$Sudoku[$BlcCol][$BlcRow]);
	
			if((($PositionColumn == -1) && ($$Sudoku[$j][$i] != 0)) ||
			  (($PositionRow == -1)  && ($$Sudoku[$i][$j] != 0)) ||
			  (($PositionBlock == -1) && ($$Sudoku[$BlcCol][$BlcRow] != 0))){
				print "Repetition";
				exit();
			}else {
				# 値を削除
				substr($NumberColumn, $PositionColumn, 1) = "" if($$Sudoku[$j][$i] != 0);
				substr($NumberRow, $PositionRow, 1) = "" if($$Sudoku[$i][$j] != 0);
				substr($NumberBlock, $PositionBlock, 1) = "" if($$Sudoku[$BlcCol][$BlcRow] != 0);
			}
		}
	}
	
	return ;
}
	
# (0, 0) から (8, 8) 移動ルート Move
# 引数 数独 (\@Sudoku)
# 戻り値 移動ルート (@Move)
sub Move{
	my ($Sudoku) = @_;
	my @Move = ();
	my $Position = 0;
	
	for(my $i = 0; $i < 9; $i++){
		for(my $j = 0; $j < 9; $j++){
			if($$Sudoku[$i][$j] == 0){
				# 移動する [0] 縦 [1] 横 [2] ブロックの番号
				$Move[$Position][0] = $i;
				$Move[$Position][1] = $j;
				$Move[$Position][2] = &BlockPosition($i, $j);
	
				# 配列の位置
				$Position++;
			}
		}
	}
	
	return @Move;
}
	
# ブロックの番号 Block Position
# 引数 縦 横 ($Column, $Row)
# 戻り値 ブロックの番号 ($CheckBlock)
sub BlockPosition{
	my ($Column, $Row) = @_;
	my $BlockPosition = (int($Column / 3) * 3) + int($Row / 3);
	
	return $BlockPosition;
}