# 数独自動生成 Sudoku Generator
# 引数 なし ()
# 戻り値 数独自動生成 (@SudokuProblem)
sub SUDOKUGENERATOR{
	my @SudokuSolver = ();
	my @SudokuProblem = ();
	my @Move = ();
	my @CheckBlock = ();
	my @CheckNumber = ();
	my $GetNumber = 0;
	my $Column = 0;
	my $Row = 0;
	my $BlockPosition = 0;
	my $IsBack = 0;
	my $Count = 81;
	
	# 初期化 Initialization
	&Initialization(\@Move, \@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) = "";
		}
	}
	
	# 初期化 Deep Copy
	for(my $i = 8; $i >= 0; $i--){
		for(my $j = 8; $j >= 0; $j--){
			$SudokuProblem[$i][$j] = $SudokuSolver[$i][$j];
		}
	}
	
	# ランダムに問題から数字を取り除く
	&RandomDeleteNumber(\@SudokuProblem);
	
	return @SudokuProblem;
}
	
# 初期化 Initialization
# 引数 移動 ブロック 数独解法 (\@Move, \@CheckBlock, \@SudokuSolver)
# 戻り値 なし ()
sub Initialization{
	my ($Move, $CheckBlock, $SudokuSolver) = @_;
	my $Number = "123456789";
	my $Position = 0;
	my $Count = 9;
	
	for(my $i = 0; $i < $Count; $i++){
		for(my $j = 0; $j < $Count; $j++){
			$$SudokuSolver[$i][$j] = 0;
	
			# 移動する [0] 縦 [1] 横 [2] ブロックの番号
			$$Move[$Position][0] = $i;
			$$Move[$Position][1] = $j;
			$$Move[$Position][2] = &BlockPosition($i, $j);
	
			# 配列の位置
			$Position++;
		}
	
		# 乱数列を作成 Rand Number
		&RandNumber(\$Number);
	
		# ブロック内(3 * 3)で使用できる数字列 Check Block
		$$CheckBlock[$i] = $Number;
	}
}
	
# 数字を一つ取り出す Get Number
# 引数 値 (\$Number)
# 戻り値 数字 ($GetNumber)
sub GetNumber{
	my ($Number) = @_;
	my $Rand = int(rand(length($$Number)));
	my $GetNumber = substr($$Number, $Rand, 1);
	
	# 使用した値を削除
	substr($$Number, $Rand, 1) = "";
	
	return $GetNumber;
}
	
# 乱数列を作成 Rand Number
# 引数 値 (\$Number)
# 戻り値 なし ()
sub RandNumber{
	my ($Number) = @_;
	my $RandNumber = "";
	
	for(my $i = length($$Number); $i > 0; $i--){
		$RandNumber = $RandNumber . &GetNumber($Number, $i);
	}
	
	# 乱数列を作成 Rand Number
	$$Number = $RandNumber;
	
	return ;
}
	
# 使用可能な数字列を取り出す Check Number
# 引数 縦 横 数字 数独 ($Column, $Row, $CheckNumber, \@SudokuSolver)
# 戻り値 使用可能な数字列 ($CheckNumber)
sub CheckNumber{
	my ($Column, $Row, $CheckNumber, $SudokuSolver) = @_;
	my $Position = 0;
	
	# 空白
	if($CheckNumber eq ""){
		return $CheckNumber;
	}
	
	# 縦
	for(my $i = $Column - ($Column % 3) - 1; $i >= 0; $i--){
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuSolver[$i][$Row]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	}
	
	# 横
	for(my $i = $Row - ($Row % 3) - 1; $i >= 0; $i--){
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuSolver[$Column][$i]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	}
	
	return $CheckNumber;
}
	
# ブロックの番号 Block Position
# 引数 縦 横 ($Column, $Row)
# 戻り値 ブロックの番号 ($CheckBlock)
sub BlockPosition{
	my ($Column, $Row) = @_;
	my $BlockPosition = (int($Column / 3) * 3) + int($Row / 3);
	
	return $BlockPosition;
}
	
# (0, 0) から (8, 8) ランダム移動ルート Move
# 引数 数独問題 ($SudokuProblem)
# 戻り値 ランダム移動ルート (@RandomMove)
sub RandomMove{
	my ($SudokuProblem) = @_;
	my @RandomMove = ();
	my $Number = "012345678";
	my $GetColumn = 0;
	my $Position = 0;
	my $RandomPosition = 0;
	my $Count = 9;
	
	for(my $i = 0; $i < $Count; $i++){
		# 乱数列を作成 Rand Number
		&RandNumber(\$Number);
		# 数字を一つ取り出す Get Number
		$GetColumn = &GetNumber(\$Number);
	
		for(my $j = 0; $j < $Count; $j++){
			# すでに数字が取り除かれているなら
			next if($$SudokuProblem[$GetColumn][$j] == 0);
	
			# 移動する [0] 縦 [1] 横 [2] ブロックの番号
			$RandomMove[$Position][0] = $GetColumn;
			$RandomMove[$Position][1] = $j;
			$RandomMove[$Position][2] = &BlockPosition($GetColumn, $j);
	
			# ランダム移動ルート
			$RandomPosition = int(rand($Position));
	
			# 移動ルートの変更
			($RandomMove[$Position][0], $RandomMove[$RandomPosition][0]) = ($RandomMove[$RandomPosition][0], $RandomMove[$Position][0]);
			($RandomMove[$Position][1], $RandomMove[$RandomPosition][1]) = ($RandomMove[$RandomPosition][1], $RandomMove[$Position][1]);
			($RandomMove[$Position][2], $RandomMove[$RandomPosition][2]) = ($RandomMove[$RandomPosition][2], $RandomMove[$Position][2]);
	
			# 配列の位置
			$Position++;
		}
	}
	
	return @RandomMove;
}
	
# ランダムに問題から数字を取り除く Random Delete Number
# 引数 数独問題 (\@SudokuProblem)
# 戻り値 なし ()
sub RandomDeleteNumber{
	my ($SudokuProblem) = @_;
	my @RandomMove = ();
	my @CheckBlock = ();
	my $Column = 0;
	my $Row = 0;
	my $BlockPosition = 0;
	my $Number = 0;
	my $IsDelete = 0;
	my $Limit = 3;
	my $Count = 9;
	
	# 初期化
	for(my $i = 0; $i < $Count; $i++){
		# ブロック内で使用可能な数字
		$CheckBlock[$i] = "123456789";
	}
	
	# (0, 0) から (8, 8) ランダム移動ルート Move
	@RandomMove = &RandomMove($SudokuProblem);
	$Count = @RandomMove - 1;
	
	for(my $i = $Count; $i >= 0; $i--){
		# 縦 横 ブロックの番号
		$Column = $RandomMove[$i][0];
		$Row = $RandomMove[$i][1];
		$BlockPosition = $RandomMove[$i][2];
		# 数字
		$Number = $$SudokuProblem[$Column][$Row];
	
		# 選択した行・列を中心に数字列(1-9)が揃っているか調べる
		$IsDelete = &IsDeleteLevel1($Column, $Row, $SudokuProblem);
	
		if($IsDelete == 0){
			# 選択した行・列以外のブロックを埋められるか
			$IsDelete = &IsDeleteLevel2($Column, $Row, $SudokuProblem);
		}
		if($IsDelete == 0){
			# ブロック内と選択した行・列の数字で数字列(1-9)が揃っているか調べる Is Delete Level3
			$IsDelete = &IsDeleteLevel3($Column, $Row, $CheckBlock[$BlockPosition], $SudokuProblem);
		}
		if($IsDelete == 0){
			# 片方の行・列が埋まっていて、もう片方のブロック内と選択した行・列の数字があるか調べる Is Delete Level4
			$IsDelete = &IsDeleteLevel4($Column, $Row, \@CheckBlock, $SudokuProblem);
		}
	
		if($IsDelete == 1){
			# 数字を取り除く
			$$SudokuProblem[$Column][$Row] = 0;
			# ブロック内の数字を取り除く
			substr($CheckBlock[$BlockPosition], index($CheckBlock[$BlockPosition], $Number), 1) = "";
		}
	}
	
	return ;
}
	
# 選択した行・列を中心に数字列(1-9)が揃っているか調べる Is Delete Level1
# 引数 縦 横 数独 ($Column, $Row, \@SudokuProblem)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel1{
	my ($Column, $Row, $SudokuProblem) = @_;
	my $IsDelete = 0;
	my $CheckNumber = "123456789";
	my $Position = 0;
	my $Count = 9;
	
	for(my $i = 0; $i < $Count; $i++){
		# 縦
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuProblem[$i][$Row]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	
		# 横
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuProblem[$Column][$i]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	}
	
	# 数字列(1-9)が揃うなら
	$IsDelete = 1 if($CheckNumber eq "");
	
	return $IsDelete;
}
	
# 選択した行・列以外のブロックを埋められるか Is Delete Level2
# 引数 縦 横 数独 ($Column, $Row, \@SudokuProblem)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel2{
	my ($Column, $Row, $SudokuProblem) = @_;
	my $IsDelete = 0;
	my $BlockColumn = $Column - ($Column % 3);
	my $BlockRow = $Row - ($Row % 3);
	my $BlCol = 0;
	my $BlRow = 0;
	my $Position = 0;
	my $Count = 9;
	
	for(my $i = 0; $i < $Count; $i++){
		# 初期化
		$BlCol = $BlockColumn + int($i / 3);
		$BlRow = $BlockRow + ($i % 3);
		$IsDelete = 0;
	
		# 0以外 選択した行・列
		if(($$SudokuProblem[$BlCol][$BlRow] != 0) || ($$SudokuProblem[$BlCol][$BlRow] == $$SudokuProblem[$Column][$Row])){
			$IsDelete = 1;
			next;
		}
	
		for(my $j = 0; $j < $Count; $j++){
			# 縦
			if(($j != $Column) && ($$SudokuProblem[$j][$BlRow] == $$SudokuProblem[$Column][$Row])){
				$IsDelete = 1;
			
				last;
			}
			# 横
			if(($j != $Row) && ($$SudokuProblem[$BlCol][$j] == $$SudokuProblem[$Column][$Row])){
				$IsDelete = 1;
			
				last;
			}
		}
	
		# 埋められないなら
		last if($IsDelete == 0);
	}
	
	return $IsDelete;
}
	
# ブロック内と選択した行・列の数字で数字列(1-9)が揃っているか調べる Is Delete Level3
# 引数 縦 横 数字 ブロック内にある数字 数独 ($Column, $Row, $CheckBlock[$BlockPosition], \@SudokuProblem)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel3{
	my ($Column, $Row, $CheckBlock, $SudokuProblem) = @_;
	my $IsDelete = 0;
	my $CheckNumber = "123456789";
	my $Number = 0;
	my $Position = 0;
	my $Count = 9;
	
	# ブロック内に残っている数字を取り除く
	for(my $i = length($CheckBlock) - 1; $i >= 0; $i--){
		$Number = substr($CheckBlock, $i, 1);
		substr($CheckNumber, index($CheckNumber, $Number), 1) = "";
	}
	
	for(my $i = 0; $i < $Count; $i++){
		# 縦
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuProblem[$i][$Row]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	
		# 横
		# 数字の位置を取得
		$Position = index($CheckNumber, $$SudokuProblem[$Column][$i]);
		# 使用済みの数字があるなら削除
		substr($CheckNumber, $Position, 1) = "" if($Position != -1);
	}
	
	# 数字列(1-9)が揃うなら
	$IsDelete = 1 if($CheckNumber eq "");
	
	return $IsDelete;
}
	
# 片方の行・列が埋まっていて、もう片方のブロック内と選択した行・列の数字があるか調べる Is Delete Level4
# 引数 縦 横 ブロック内にある数字 数独 ($Column, $Row, \@CheckBlock, \@SudokuProblem)
# 戻り値 フラグ ($IsDelete)
sub IsDeleteLevel4{
	my ($Column, $Row, $CheckBlock, $SudokuProblem) = @_;
	my $IsDelete = 0;
	my $Position = 0;
	my $BlockPosition = 0;
	my $CountNumCol = 0;
	my $CountNumRow = 0;
	my $IsAlignmentCol = 0;
	my $IsAlignmentRow = 0;
	my $IsSameNumberCol = 0;
	my $IsSameNumberRow = 0;
	
	for(my $i = 0; $i < 3; $i++){
		# 初期化
		$CountNumCol = 0;
		$CountNumRow = 0;
	
		# 縦
		if(($Column % 3) == $i){
			for(my $j = 0; $j < 3; $j++){
				if($$SudokuProblem[($i * 3) + $j][$Row] != 0){
					$CountNumCol++;
				}
			}
	
			$BlockPosition = &BlockPosition($Row, ($i * 3));
			$Position = index($$CheckBlock[$BlockPosition], $$SudokuProblem[$Column][$Row]);
	
			if($CountNumCol == 3){
				# 列が埋まっている
				$IsAlignmentCol = 1;
			}
			elsif(($CountNumCol != 0) & ($Position != -1)){
				# ブロック内に同じ数字がある
				$IsSameNumberCol = 1;
			}
		}
	
		# 横
		if(($Row % 3) != $i){
			for(my $j = 0; $j < 3; $j++){
				if($$SudokuProblem[$Column][($i * 3) + $j] != 0){
					$CountNumRow++;
				}
			}
	
			$BlockPosition = &BlockPosition($Column, ($i * 3));
			$Position = index($$CheckBlock[$BlockPosition], $$SudokuProblem[$Column][$Row]);
	
			if($CountNumRow == 3){
				# 列が埋まっている
				$IsAlignmentRow = 1;
			}
			elsif(($CountNumRow != 0) & ($Position != -1)){
				# ブロック内に同じ数字がある
				$IsSameNumberRow = 1;
			}
		}
	}
	
	$IsDelete = 1 if((($IsAlignmentCol == 1) && ($IsSameNumberCol == 1)) || (($IsAlignmentRow == 1) && ($IsSameNumberRow == 1)));
	
	return $IsDelete;
}