9x9にトロミノを敷き詰めるやりかた

solution.txt

MMNNOPPQQ
JMKNOOPLQ
JJKKHHLLI
DDEEFHGII
ADBEFFGGC
AABB899CC
556688977
051623347
001122344

trominino-tiling.rb

#!/usr/bin/ruby
#
# 「アルゴリズムパズル」、
# Anany Levitin (著), Maria Levitin (著), 黒川 洋 (翻訳), 松崎 公紀 (翻訳) 、
# オライリー、2014
#
# p.41 トロミノによる敷き詰めより、9x9にトロミノを敷き詰めるやりかたを求めたい
#
# Copyright 2014 zunda <zunda at freeshell.org>
#
# Permission is granted for use, copying, modification,
# distribution, and distribution of modified versions of this
# work as long as the above copyright notice is included

# Tromino with the center (# below) at (x,y) and rotation:0, 1, 2, 3
# rot:0+  1: + 2:++ 3:++ 
#      #+   #+    #   #
# With x to the right, y to the top
class Tromino
	attr_reader :x, :y, :r, :label

	def initialize(x, y, r, label)
		@x, @y, @r, @label = x, y, r, label
	end

	def occupies
		case @r
		when 0
			return [[@x, @y], [@x+1, @y], [@x, @y+1]]
		when 1
			return [[@x, @y], [@x+1, @y], [@x+1, @y+1]]
		when 2
			return [[@x, @y], [@x-1, @y+1], [@x, @y+1]]
		when 3
			return [[@x, @y], [@x, @y+1], [@x+1, @y+1]]
		end
	end
end

class Board
	attr_reader :wx, :wy, :tromino

	def initialize(wx, wy)
		@wx, @wy = wx, wy
		@tromino = Hash.new

		# walls
		-1.upto(@wx) do |x|
			@tromino[[x, -1]] = :dummy
			@tromino[[x, @wy]] = :dummy
		end
		-1.upto(@wy) do |y|
			@tromino[[-1, y]] = :dummy
			@tromino[[@wx, y]] = :dummy
		end
	end

	# returns false if not placeable
	def place!(tromino)
		tromino.occupies.each do |tile|
			return false if @tromino[tile]
		end

		tromino.occupies.each do |tile|
			@tromino[tile] = tromino
		end
		return self
	end

	def next_empty_tile_from(x, y)
		while y < @wy
			while x < @wx
				return x, y unless @tromino[[x, y]]
				x += 1
			end
			x = 0
			y += 1
		end
		return nil
	end

	def remove!(tromino)
		tromino.occupies.each do |tile|
			@tromino[tile] = nil
		end
	end

	def to_s
		r = ''
		(@wy - 1).downto(0).each do |y|
			0.upto(@wx - 1).each do |x|
				t = @tromino[[x, y]]
				r += t ? t.label : '.'
			end
			r += "\n"
		end
		return r
	end
end

w = 9
b = Board.new(w, w)
trominos = Array.new
n = w*w / 3
labels = ('0'..'9').to_a + ('A'..'Z').to_a

# current location and direction of tromino
x = 0
y = 0
r = 0
while trominos.length < n
	# try placing a tromino
	t = Tromino.new(x, y, r, labels[trominos.length])
	if b.place!(t)
		# could be placed
		puts 
		puts b
		trominos.push(t)
		x, y = b.next_empty_tile_from(x, y)
		r = 0
	else
		# try another direction
		r += 1
		while r >= 3
			# backtrack
			t = trominos.pop
			if not t
				puts "No solution is found."
				exit
			end
			b.remove!(t)
			x = t.x
			y = t.y
			r = t.r + 1
		end
	end
end

方向2と方向3の形を逆にしないと解けないパターンがあるかもしれない。(左下には2は置けないが3は置ける。)