ペグソリティア

今更気になってしまって、しかし中々解けずに悔しくて、つい思わずカッとなって全探索プログラムを書いて先週から流してしまっているのだけれど、、、、、

#!/usr/bin/env python

import copy

valid = (
	(0, 0, 1, 1, 1, 0, 0, ),
	(0, 0, 1, 1, 1, 0, 0, ),
	(1, 1, 1, 1, 1, 1, 1, ),
	(1, 1, 1, 1, 1, 1, 1, ),
	(1, 1, 1, 1, 1, 1, 1, ),
	(0, 0, 1, 1, 1, 0, 0, ),
	(0, 0, 1, 1, 1, 0, 0, ),
	)

board = [
	[0, 0, 1, 1, 1, 0, 0, ],
	[0, 0, 1, 1, 1, 0, 0, ],
	[1, 1, 1, 1, 1, 1, 1, ],
	[1, 1, 1, 0, 1, 1, 1, ],
	[1, 1, 1, 1, 1, 1, 1, ],
	[0, 0, 1, 1, 1, 0, 0, ],
	[0, 0, 1, 1, 1, 0, 0, ],
	]

def deepsum(seq):
    sum = 0
    for i in seq:
	if type(i) is tuple or type(i) is list:
	    i = deepsum(i)
	sum += i
    return sum

def changeit(x, y, d, board):
    (xx,yy) = (x+d[0], y+d[1])
    (xxx,yyy) = (xx+d[0], yy+d[1])
    board[y][x] = 1
    board[yy][xx] = 0
    board[yyy][xxx] = 0

print "\x1b[2J"
def disp(board, msg = "   "):
    print "\x1b[1;1H===%s===" % msg
    for i in board:
	print i

def search(i, board):
    if i == 0:
	print "found"
	return (0, 0, 0)
    disp(board)
    for y in xrange(len(board)):
	for x in xrange(len(board[0])):
	    disp(board)
	    print i, x, y
	    if valid[y][x] == 1 and board[y][x] == 0:
		dir = ( (0,-1), (-1, 0), (0, 1), (1, 0))
		for d in dir:
		    try:
			(xx,yy) = (x+d[0], y+d[1])
			(xxx,yyy) = (xx+d[0], yy+d[1])
			if xx < 0 or xxx < 0 or yy < 0 or yyy < 0: continue
			if board[yy][xx] == 1 and board[yyy][xxx] == 1:
			    work = copy.deepcopy(board)
			    changeit(x,y,d, work)
			    disp(work)
			    sol = search(i-1, work)
			    if sol: return (x,y,d)+sol
			    disp(work, "OUT")
		    except:
			continue
    return None

print search(deepsum(board)-1, board)

考えるまでも無く、これってとんでもないステップがかかるわけで、仮に非常にゆるい予測として書く局面で平均１０分岐すると仮定して、秒間 1M局面とけるとしても秒かかるということか。ムチャすぎる。んだけど、実は頭のほうに解があったりしたらもうあと少しで答えが出るかもとか思って、なかなかCntl-Cできない自分がいる。馬鹿すぎ。