本履歴

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

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

今日も今日とて、マーチン・ガードナーのMy Best Mathematical and Logic Puzzlesを眺めていたら見つけた問題。

39. The Game of Hip

6x6のチェッカーボードに先手後手が黒石、白石を置いていく。自分の石で正方形(斜めも可)を作ったら負け。この時、引き分けになる置き方は存在するか?

このゲーム何処かで見かけたことあるな・・・。いずれにせよ本によると、マーチン・ガードナーは当初存在しない、勝ちか負けになると予想していたらしいが、どこかの大学の数学科の生徒が引き分けになる最終図を見つけたとのこと。つまり、6x6が黒石18個、白石18個で埋められていて且つそれぞれの色で正方形が作られないパターンだ。36箇所から18箇所選ぶ組み合わせの数は90億なので、それぞれが正方形を含まない(6x6上の正方形のパターンは105通り)をチェックすると相当無理、ここでは小さい場合について解き、その結果からn=6を構築した。

まず、6x6の正解のパターンがあるとすると、その左上、4x4の部分チェッカーボードも正方形を含まない。同様に、右上、左下、右下も4x4の正方形ができないパターンになっている。そこでまず、4x4の正方形が出来ないパターンを全て求める。これは5,006通りあった。その中から一つ左上の候補を固定する。右上の部分の4x4だが重なっている部分は左上と同じパターンにならないといけないので5,006からかなり少なくなる。20通りくらい。同様に左下の候補も20通りほど。右下は右上と左下の4x4と重なっているので更に候補が絞れる、高々数通りだ。このようにして候補の6x6パターンを作る。当然黒石が18個のチェックも忘れずに。

次に、そのパターンが正方形を含むかどうかだが、正方形を含まない4x4から作ってあるので6x6上でも幾つかの正方形構成条件は満たさないことが分かっている。結局チェックする条件は105から減って36通り。ここまでやってあとはプログラムをぶん回した。結果、数十分かかった・・・。最終結果は本に載っていた解答も出てきたので問題なさそうだ。それにしても、回転、反転、bit反転含めてで24通りしかないんだから、マーチン・ガードナーが見つけられなくてもしようがない。目視で確認してみたけど人間は斜めの正方形見つけるのは不可能だね(笑)

プログラムを改良して速くしたいんだけど3x3に分割して合成するくらいしか思いつかない。それも速いかどうか定かでないし。結局これって36変数の210節の4-SATを解いているわけだし、構造になんか良い性質ないと難しそう。

#generate square position on nxn board
def gene_square_pos(n)
    ret=[]
    r=0...n
    n.times{|x|1.upto(n-1){|y|
        ul=[x,0]
        ur=[0,y]
        next unless r===x+y
        dl=[x+y,x]
        dr=[y,x+y]
        v=[ul,ur,dl,dr]
        d=n-x-y
        d.times{|dx|d.times{|dy|ret << v.map{|_x,_y|[_x+dx,_y+dy]}}}
    }}
    ret
end

def anti_pos(pos)
    pos.map{|p4|p4.map{|p|!p}}
end

def move_square_pos(pos,dx,dy)
    pos.map{|p4|p4.map{|x,y|[x+dx,y+dy]}}
end

#turn some portion of position into code
def code(pos,xrange,yrange)
    ret=0
    xrange.each{|x|yrange.each{|y|ret=2*ret+(pos[x][y] ? 1 : 0)}}
    ret
end

def lcode(pos)
    n=pos.size
    code(pos,0...n,0...n/2)
end

def rcode(pos)
    n=pos.size
    code(pos,0...n,n/2...n)
end

def ucode(pos)
    n=pos.size
    code(pos,0...n/2,0...n)
end

def dcode(pos)
    n=pos.size
    code(pos,n/2...n,0...n)
end

#check whether the given position make a square?
def pos_make_square?(pos,sq_pos)
    sq_pos.any?{|pts|
        pts.all?{|p|pos.dig(*p)}||pts.all?{|p|!pos.dig(*p)}
    }
end

def display(pos)
    pos.each{|ary|puts ary.map{|v|v ? ?# : ?.}*""}
end

#doable up to 4
def gene_nxn_pos(n)
    ret=[]
    sq_pos=gene_square_pos(n)
    1.upto(n*n/2){|k|
        (n*n).times.map{|i|i.divmod n}.combination(k){|ary|
            pos=Array.new(n){Array.new(n,false)}
            ary.each{|x,y|pos[x][y]=true}
            next if pos_make_square?(pos,sq_pos)
            ret << pos
            ret << anti_pos(pos) unless 2*k==n*n
        }
    }
    ret
end

pos4x4=gene_nxn_pos(4)
sq_pos4x4=gene_square_pos(4)
sq_pos6x6=gene_square_pos(6)
pos6x6=[]
u={}
l={}
pos4x4.each{|pos|
    uc,lc=ucode(pos),lcode(pos)
    [[u,uc],[l,lc]].each{|h,c|
        if h[c]
            h[c] << pos
        else
            h[c]=[pos]
        end
    }
}

#eliminate the condition already examined
sq_pos6x6-=sq_pos4x4
sq_pos6x6-=move_square_pos(sq_pos4x4,0,2)
sq_pos6x6-=move_square_pos(sq_pos4x4,2,0)
sq_pos6x6-=move_square_pos(sq_pos4x4,2,2)

pos4x4.each_with_index{|ulpos,idx|
    p idx
    rc=rcode(ulpos)
    dc=dcode(ulpos)
    l[rc].each{|urpos|u[dc].each{|dlpos|
        dl_cand1=l[rcode(dlpos)]
        next unless dl_cand1
        dl_cand2=u[dcode(urpos)]
        next unless dl_cand2
        dl_cand=dl_cand1&dl_cand2
        next if dl_cand.empty?
        dl_cand.each{|drpos|
            pos=Array.new(6){Array.new(6,false)}
            #copy
            num=0
            4.times{|x|4.times{|y|
                if ulpos[x][y]
                    pos[x][y]=true
                    num+=1
                end
            }}
            4.times{|x|4.upto(5){|y|
                if urpos[x][y-2]
                    pos[x][y]=true
                    num+=1
                end
            }}
            4.times{|y|4.upto(5){|x|
                if dlpos[x-2][y]
                    pos[x][y]=true
                    num+=1
                end
            }}
            4.upto(5){|x|4.upto(5){|y|
                if drpos[x-2][y-2]
                    pos[x][y]=true
                    num+=1
                end
            }}
            next unless num==18
            #square check
            unless pos_make_square?(pos,sq_pos6x6)
                pos6x6 << pos
                display(pos)
                puts
            end
        }
    }}
}

puts pos6x6.size # => 24

My Best Mathematical and Logic Puzzles (Dover Recreational Math)

My Best Mathematical and Logic Puzzles (Dover Recreational Math)

#.#.#.
....##
.#.##.
.##.##
##....
.###.#

.#.#.#
####..
#.#..#
#..#..
..####
#...#.

#...#.
..####
#..#.#
..#..#
####..
.#.#.#

.###.#
##....
.##.#.
##.##.
....##
#.#.#.

#.###.
....##
.#.##.
.##.##
##....
.#.#.#

#.###.
....##
.#.##.
.##.#.
##....
.###.#

.#...#
####..
#.#..#
#..#..
..####
#.#.#.

.#...#
####..
#.#..#
#..#.#
..####
#...#.

#.#.#.
..####
#..#.#
..#..#
####..
.#...#

#.#.#.
..####
#..#..
..#..#
####..
.#.#.#

.#.#.#
##....
.##.#.
##.##.
....##
#.###.

.#.#.#
##....
.##.##
##.##.
....##
#.#.#.

#.#.#.
....##
##.##.
.##.##
##....
.#.#.#

#.#.#.
....##
##.##.
.##.#.
##....
.###.#

.#.#.#
####..
..#..#
#..#..
..####
#.#.#.

.#.#.#
####..
..#..#
#..#.#
..####
#...#.

#...#.
..####
#..#.#
#.#..#
####..
.#...#

#...#.
..####
#..#..
#.#..#
####..
.#.#.#

.###.#
##....
.##.#.
.#.##.
....##
#.###.

.###.#
##....
.##.##
.#.##.
....##
#.#.#.

#.###.
....##
##.##.
.##.#.
##....
.#.#.#

#.#.#.
..####
#..#..
#.#..#
####..
.#...#

.#.#.#
##....
.##.##
.#.##.
....##
#.###.

.#...#
####..
..#..#
#..#.#
..####
#.#.#.