本履歴

購入した古本の履歴と時々プログラミング

数学パズル本に敢てプログラムで挑戦(5)

チェス盤のタイリング問題に挑戦。この問題はALGORITHMIC PUZZLESではチュートリアルの例題として載っていた。 まあ有名ですからね。

Domino Tiling of Deficient Chessboards

8x8のチェス盤をドミノ(1*2)で隙間なく埋めることを考える。a)左上が欠けているチェス盤で可能か? b)左上、右下が欠けている場合は?

a)は偶奇性が異なる(空きは偶数である必要がある)からNGは明らか。b)はちょっとトリッキーだが、チェス盤が市松模様なのとドミノをどう置いても2色をカバーする必要があることからチェス盤の2色は同じセル数ある必要があるからNG。 念のため、深さ優先でプログラムを組んでドミノを置いてみたが、理屈通りできませんでした(笑) まあ、ロジックで出来ないを判定できるのはすごいことだ。

#domino tiling on N*N board

N = 8
board = Array.new(N + 1){Array.new(N + 1, false)}
(N + 1).times{|j|board[N][j] = true} #sentinel
(N + 1).times{|i|board[i][N] = true}
board[0][0] = true #deficient cell
board[N - 1][N - 1] = true

def find_next(b, x, y, n)
    x.upto(N){|i|return [i, y] unless b[i][y]}
    (y + 1).upto(n - 1){|j|N.times{|i|return [i, j] unless b[i][j]}}
    nil
end

def f(b)
    def dfs(b, x, y, rest, n)
        ret = 0

        #horizontal
        if b[x][y + 1] == false
            return 1 if rest == 2
            b[x][y] = b[x][y + 1] = true
            nx, ny = find_next(b, x, y, n)
            if nx
                ret += dfs(b, nx, ny,rest - 2, n)
            end
            b[x][y] = b[x][y + 1] = false
        end

        #vertical
        if b[x + 1][y] == false
            return 1 if rest == 2
            b[x][y] = b[x + 1][y] = true
            nx, ny = find_next(b, x, y, n)
            if nx
                ret += dfs(b, nx, ny, rest - 2, n)
            end
            b[x][y] = b[x + 1][y] = false
        end
        ret
    end

    #body
    n = b.size - 1
    rest = 0
    n.times{|i|n.times{|j|rest += 1 unless b[i][j]}}
    x,y = find_next(b, 0, 0, n)
    dfs(b, x, y, rest, n)
end

p f(board) # => 0