プログラム解説：CodeIQ「ナンプレを解くプログラム」

問題の概要

問題を引用します。

【概要】
簡単なナンプレの問題を解くプログラムを書いてみましょう。

【問題】
次のようなナンプレがあります。
・2x2のマス（Box）が縦横ふたつずつ並んだ4x4のマスがある
・それぞれのマスには1~4の数字が入り、それらは行／列の4つのマスに同じ数字がくることはない（行／列の合計は10となる）

・2x2のマス（Box）にも同じ数字がくることはなく、合計は10となる
・最初に1~4の数字がランダムにひとつずつ設定されている（同じ行／列／Boxに複数の数字が設定されることは無い）
初期状態の例（-は数字の入っていない状態を表します）

1 - - -

- - 3 -

- - - 4

- 2 - -

【入出力】
CSV形式のテストデータを標準入力で受け取る想定で、結果を標準出力するプログラムを作ってください。
上図のナンプレでは、以下のようなCSVファイルが入力されます。

1,0,0,0
0,0,3,0
0,0,0,4
0,2,0,0

これに対して、以下のようなデータを標準出力から出力してください。

1,3,4,2
2,4,3,1
3,1,2,4
4,2,1,3

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby
def makeList(board)
	ret = []
	for r in 0...4
		for c in 0...4
			ret << [r,c] if board[r][c] == 0
		end
	end
	return ret
end

def checkRow(board, n, r)
	for i in 0...4
		return false if board[r][i] == n
	end
	return true
end

def checkCol(board, n, c)
	for i in 0...4
		return false if board[i][c] == n
	end
	return true
end

def checkBox(board, n, r, c)
	pr = r%2
	pc = c%2

	if pr == 0 && pc == 0 then
		return false if (board[r][c+1] == n) || (board[r+1][c] == n) || (board[r+1][c+1] == n)
	elsif pr == 1 && pc == 0 then
		return false if (board[r][c+1] == n) || (board[r-1][c] == n) || (board[r-1][c+1] == n)
	elsif pr == 0 && pc == 1 then
		return false if (board[r][c-1] == n) || (board[r+1][c-1] == n) || (board[r+1][c] == n)
	elsif pr == 1 && pc == 1 then
		return false if (board[r-1][c] == n) || (board[r-1][c-1] == n) || (board[r][c-1] == n)
	end

	return true
end

def setCand(board, list)
#	printf("%s, %s\n", board, list)
	return true if list.empty?
	pos = list.shift

	for i in 1..4
#		printf("n=%d, %s, %s, %s\n", i, checkRow(board, i, pos[0]), checkCol(board, i, pos[1]), checkBox(board, i, pos[0], pos[1]))
		if checkRow(board, i, pos[0]) && checkCol(board, i, pos[1]) && checkBox(board, i, pos[0], pos[1]) then
			board[pos[0]][pos[1]] = i
			ret = setCand(board, list)
			if ret == false then
				board[pos[0]][pos[1]] = 0
			else
				return ret
			end
		end
	end

	if board[pos[0]][pos[1]] == 0
		list.unshift(pos)
		return false
	end
end

def solve(board)
	list = makeList(board)
	setCand(board, list)

	return board.map{|a| a.join(",")}.join("\n")
end

# main
board = []
while line = gets
	line.strip!
	next if line.empty?

	board << line.split(",").map{|v| v.to_i}
end

puts solve(board)

解説

ナンプレを解くプログラムはたくさん見つかりそうなので少し調べて見ましたが、実際人間がやるように解いているプログラムばかりでした。
多少効率が悪いかもしれないけれどバックトラック法で簡単に実装できるんじゃないのかと思ってやったのが私のプログラムです。

考え方

考え方はすごく単純です。
左上から順に空いているマスに任意の数字を入れます。
条件に合致していたら次のマスに進みます。
条件に合致しなかったら次の数字を試します。
全ての数字で条件を満たせなかったら1マス戻って、次の数字を試します。
という操作を最後まで繰り返すだけです。
これは再帰で単純に実装できます。

main

入力値を数値の二次元配列にし、solve()に渡します。
戻り値を印字します。

solve(board)

makeList()で空いているマスのリストを作ります。
setCand()で空いているマスを埋めます。
boardが埋められて来るのでそれを文字列にして返します。

makeList(board)

数字が入っていないマス目の座標リストを作成して返します。

setCand(board, list)

boardは現在の盤面、listは空きマスのリストです。
listが空ならboardが埋まっているのでtrueを返して終わります。
listから空きマスを1つ取り出します。

空きマスに1〜4の数字を配置します。
checkRow()、checkCol()、checkBox()が全部trueならその数字は配置可能なのでboardの当該マスに値を設定します。
そして次のマスを処理するためsetCand()を再帰呼び出しします。

setCand()がfalseを返した場合、そのマス目をやり直すためboardの当該位置を0にしてループを繰り返します。
trueが帰ってきたらret=trueを返します。

ループを抜けた時にboardの当該位置が0、つまり置ける数字がなかった時はlistに処理中の座標を戻してfalseを返します。
これによって一つ前のマスをやり直せます。

最終的に戻ってきたらboardが埋まっています。

checkRow(board, n, r), checkCol(board, n, c), checkBox(board, n, c)

縦横BOX内に同じ数字が無いかをチェックします。
同じ数字があったらfalse、なかったらtrueを返します。

雑感

解けることが決まっているならこの単純な方法でいけると思います。
4×4だったのでボックスのチェック方法が頭悪い感じですが、そこさえきちんとやれば9×9でも問題ないと思います。

CodeIQ：ナンプレを解くプログラム