Hatena::Grouppython

Pythonで遊ぶよ

2011-01-20

リスト内包表記で数独

11:18

前回のような方法でリスト内包表記を使って数独を解くことができないかと思って試してみた。

数独の問題はだいぶ前にやったやつ。

    table = [
            [1,0,0,0,0,7,0,9,0],
            [0,3,0,0,2,0,0,0,8],
            [0,0,9,6,0,0,5,0,0],
            [0,0,5,3,0,0,9,0,0],
            [0,1,0,0,8,0,0,0,2],
            [6,0,0,0,0,4,0,0,0],
            [3,0,0,0,0,0,0,1,0],
            [0,4,0,0,0,0,0,0,7],
            [0,0,7,0,0,0,3,0,0]]

こんな感じ。

nums = set(range(1,10))
ans = [
        [
        [_00,_01,_02,_03,_04,_05,_06,_07,_08],
        [_10,_11,_12,_13,_14,_15,_16,_17,_18],
        [_20,_21,_22,_23,_24,_25,_26,_27,_28],
        [_30,_31,_32,_33,_34,_35,_36,_37,_38],
        [_40,_41,_42,_43,_44,_45,_46,_47,_48],
        [_50,_51,_52,_53,_54,_55,_56,_57,_58],
        [_60,_61,_62,_63,_64,_65,_66,_67,_68],
        [_70,_71,_72,_73,_74,_75,_76,_77,_78],
        [_80,_81,_82,_83,_84,_85,_86,_87,_88]
        ]
        for _00 in [1]
        for _05 in [7]
        for _07 in [9]
        for _11 in [3]
        for _14 in [2]
        for _18 in [8]
        for _22 in [9]
        for _23 in [6]
        for _26 in [5]
        for _32 in [5]
        for _33 in [3]
        for _36 in [9]
        for _41 in [1]
        for _44 in [8]
        for _48 in [2]
        for _50 in [6]
        for _55 in [4]
        for _60 in [3]
        for _67 in [1]
        for _71 in [4]
        for _78 in [7]
        for _82 in [7]
        for _86 in [3]
        for _01 in nums - set([_41,_71,_05,_07,_00,_11,_22])
        for _02 in nums - set([_05,_07,_00,_01,_11,_32,_22,_82])
        for _03 in nums - set([_05,_07,_00,_01,_02,_33,_23,_14])
        for _04 in nums - set([_44,_05,_07,_00,_01,_02,_03,_23,_14])
        for _06 in nums - set([_04,_05,_07,_00,_01,_02,_03,_26,_86,_18,_36])
        for _08 in nums - set([_48,_78,_04,_05,_06,_07,_00,_01,_02,_03,_26,_18])
        for _10 in nums - set([_02,_50,_60,_14,_00,_01,_11,_22,_18])
        for _12 in nums - set([_02,_14,_00,_01,_11,_10,_32,_22,_82,_18])
        for _13 in nums - set([_10,_04,_05,_14,_12,_11,_03,_33,_23,_18])
        for _15 in nums - set([_10,_55,_04,_05,_14,_13,_12,_11,_03,_23,_18])
        for _16 in nums - set([_06,_15,_07,_13,_12,_11,_10,_26,_86,_18,_08,_14,_36])
        for _17 in nums - set([_06,_16,_15,_07,_13,_12,_11,_10,_26,_18,_08,_14,_67])
        for _20 in nums - set([_02,_50,_60,_00,_12,_11,_10,_26,_22,_23,_01])
        for _21 in nums - set([_02,_41,_71,_00,_12,_11,_10,_26,_22,_23,_20,_01])
        for _24 in nums - set([_44,_04,_05,_15,_14,_13,_03,_26,_22,_23,_20,_21])
        for _25 in nums - set([_55,_04,_05,_15,_14,_13,_03,_26,_24,_22,_23,_20,_21])
        for _27 in nums - set([_18,_08,_17,_16,_06,_07,_67,_26,_24,_25,_22,_23,_20,_21])
        for _28 in nums - set([_48,_78,_18,_08,_17,_16,_06,_07,_26,_27,_24,_25,_22,_23,_20,_21])
        for _30 in nums - set([_41,_50,_60,_00,_10,_33,_32,_20,_36])
        for _31 in nums - set([_41,_50,_71,_21,_01,_11,_30,_33,_32,_36])
        for _34 in nums - set([_44,_55,_04,_14,_31,_30,_33,_32,_24,_36])
        for _35 in nums - set([_32,_44,_55,_05,_15,_31,_30,_33,_25,_34,_36])
        for _37 in nums - set([_48,_17,_07,_67,_27,_31,_30,_33,_32,_35,_34,_36])
        for _38 in nums - set([_48,_78,_18,_08,_28,_31,_30,_33,_32,_35,_34,_37,_36])
        for _40 in nums - set([_48,_41,_50,_44,_60,_00,_10,_31,_30,_32,_20])
        for _42 in nums - set([_48,_40,_41,_50,_44,_12,_02,_31,_30,_32,_22,_82])
        for _43 in nums - set([_48,_40,_41,_42,_44,_55,_23,_13,_03,_33,_35,_34])
        for _45 in nums - set([_48,_40,_41,_42,_43,_44,_55,_05,_15,_33,_25,_35,_34])
        for _46 in nums - set([_48,_38,_40,_41,_42,_43,_44,_45,_16,_06,_26,_86,_37,_36])
        for _47 in nums - set([_48,_40,_41,_42,_43,_44,_45,_46,_17,_38,_07,_67,_27,_37,_36])
        for _51 in nums - set([_40,_41,_42,_50,_71,_55,_01,_11,_31,_30,_32,_21])
        for _52 in nums - set([_40,_41,_51,_50,_55,_12,_02,_31,_30,_32,_22,_42,_82])
        for _53 in nums - set([_43,_52,_51,_50,_44,_45,_55,_23,_13,_03,_33,_35,_34])
        for _54 in nums - set([_43,_53,_52,_51,_50,_44,_45,_55,_04,_14,_33,_24,_35,_34])
        for _56 in nums - set([_48,_38,_53,_52,_51,_50,_55,_54,_16,_06,_46,_26,_86,_47,_37,_36])
        for _57 in nums - set([_48,_46,_53,_52,_51,_50,_56,_55,_54,_17,_38,_07,_67,_27,_47,_37,_36])
        for _58 in nums - set([_48,_78,_18,_53,_52,_51,_50,_57,_56,_55,_54,_38,_46,_28,_47,_08,_37,_36])
        for _61 in nums - set([_01,_41,_51,_71,_60,_67,_11,_31,_82,_21])
        for _62 in nums - set([_52,_42,_71,_60,_61,_12,_02,_32,_22,_82,_67])
        for _63 in nums - set([_53,_43,_62,_60,_61,_13,_67,_03,_33,_23])
        for _64 in nums - set([_61,_62,_44,_54,_04,_63,_60,_14,_67,_24,_34])
        for _65 in nums - set([_60,_05,_45,_55,_62,_63,_15,_61,_67,_64,_25,_35])
        for _66 in nums - set([_06,_78,_63,_56,_46,_62,_16,_60,_61,_67,_64,_65,_26,_86,_36])
        for _68 in nums - set([_48,_58,_64,_38,_78,_62,_63,_60,_61,_66,_67,_28,_65,_86,_08,_18])
        for _70 in nums - set([_78,_40,_50,_71,_62,_60,_61,_00,_82,_10,_30,_20])
        for _72 in nums - set([_78,_52,_42,_71,_70,_62,_60,_61,_12,_02,_32,_22,_82])
        for _73 in nums - set([_43,_78,_53,_65,_71,_70,_72,_63,_13,_64,_03,_33,_23])
        for _74 in nums - set([_78,_44,_71,_70,_73,_72,_04,_63,_14,_64,_65,_24,_54,_34])
        for _75 in nums - set([_78,_05,_74,_71,_45,_73,_72,_63,_15,_55,_64,_65,_70,_25,_35])
        for _76 in nums - set([_46,_78,_75,_74,_71,_56,_73,_72,_16,_06,_66,_67,_70,_26,_86,_68,_36])
        for _77 in nums - set([_78,_75,_74,_76,_71,_70,_73,_47,_17,_07,_66,_67,_57,_27,_86,_72,_68,_37])
        for _80 in nums - set([_40,_50,_71,_70,_72,_62,_60,_61,_00,_82,_10,_30,_86,_20])
        for _81 in nums - set([_41,_51,_71,_70,_72,_62,_60,_61,_01,_11,_31,_86,_80,_82,_21])
        for _83 in nums - set([_43,_86,_75,_74,_65,_73,_23,_63,_53,_13,_64,_03,_33,_80,_81,_82])
        for _84 in nums - set([_34,_75,_74,_44,_73,_54,_04,_63,_14,_64,_65,_86,_24,_80,_81,_82,_83])
        for _85 in nums - set([_35,_05,_75,_74,_45,_73,_63,_15,_55,_64,_65,_84,_86,_25,_80,_81,_82,_83])
        for _87 in nums - set([_81,_78,_77,_76,_57,_68,_47,_17,_07,_66,_82,_27,_84,_85,_86,_80,_67,_37,_83])
        for _88 in nums - set([_48,_58,_78,_18,_08,_77,_76,_38,_68,_66,_67,_28,_84,_85,_86,_87,_80,_81,_82,_83])
]
print(ans)

↑を出力するために書いたプログラム

#!/usr/bin/env python

'''
[
[_00,_01,_02,_03,_04,_05,_06,_07,_08],
[_10,_11,_12,_13,_14,_15,_16,_17,_18],
[_20,_21,_22,_23,_24,_25,_26,_27,_28],
...
]
'''

indices = range(9)
val = lambda row,col: '_' + str(row) + str(col)

table_rows = []

for row in indices:
    table_rows.append(
            '[' + ','.join(val(row,col) for col in indices) + ']')

table = '[\n' + ',\n'.join(table_rows) + '\n]'

program = table


fields = []
#problem set
problem = [
        [1,0,0,0,0,7,0,9,0],
        [0,3,0,0,2,0,0,0,8],
        [0,0,9,6,0,0,5,0,0],
        [0,0,5,3,0,0,9,0,0],
        [0,1,0,0,8,0,0,0,2],
        [6,0,0,0,0,4,0,0,0],
        [3,0,0,0,0,0,0,1,0],
        [0,4,0,0,0,0,0,0,7],
        [0,0,7,0,0,0,3,0,0]]

for row,rows in enumerate(problem):
    for col,num in enumerate(rows):
        if num: # != 0
            program += '\nfor ' + val(row,col) + ' in [' + str(num) + ']'
            fields.append((row,col))


# other conditions
for row in indices:
    for col in indices:
        if (row,col) not in fields:
            visited = set(fields)
            visited.update((r,c) for r in range(row) for c in indices)
            visited.update((row,c) for c in range(col))
            excl = set([val(r,c) for (r,c) in visited
                    if (r == row)
                    or (c == col)
                    or ((row / 3) * 3 <= r < (row / 3 + 1) * 3
                    and (col / 3) * 3 <= c < (col / 3 + 1) * 3)])
            program += '\nfor ' + val(row,col) + ' in nums - set([' + ','.join(excl) + '])'

program = '\t' + program.replace('\n', '\n\t')

program = 'nums = set(range(1,10))\nans = [\n' + program + '\n]\nprint(ans)'

print(program)


import profile
profile.run(program)

profile とったけど、リスト内包表記の中までは見てくれないらしくて参考にならなかった。0.7秒ぐらいで終わったらしい。

Haskell (GHC) だとコンパイルに0.6秒、実行に0.05秒ぐらいだった。そんなもんか。

トラックバック - http://python.g.hatena.ne.jp/edvakf/20110120