Pythonで数独を解くプログラムの書き方

数独を解くプログラムを、指針に従って書いたのですが、答えが出せません。
何かアドバイスいただけると幸いです。
grid_prib1、２は既に定義してあります。
nan = 0です。

nan=0
def input_helper(str_lines):
    lines=str_lines.split()
    #print(lines)
    grid=[]
    for line in lines:
        grid.append([ int(c) if int(c)>0 else nan for c in list(line)])
    return grid

def print_grid(grid):
    str_grid = [ [ ' '+str(e) if e !=nan else '  ' for e in row ] for row in grid ]
    for nth,row in enumerate(str_grid):
        sub_str_list=['[']
        for col in [0,3]:
            sub_str_list.append( ','.join(row[col:col+3])+' | ' )
        sub_str_list.append(','.join(row[6:9])+']')
        line_str = ''.join(sub_str_list)
        print(line_str)
        if nth in [2,5]:
            print('-----------'*3)
    print() 
    
#
grid_str1='''
517600034 089004000 306205090
600000010 030006047 000000000
090000078 703400560 000000000
'''
grid_prob1=input_helper(grid_str1)
print("数独問題1： grid_prob1")
print_grid(grid_prob1)

# 
grid_str2='''
530070000 600195000 098000060
800060003 400803001 700020006
060000280 000419005 000080079
'''
grid_prob2=input_helper(grid_str2)
print("数独問題2： grid_prob2")
print_grid(grid_prob2)



import copy 


def find_next(grid):
    '''
    INPUT:
        grid: マス目情報
    OUTPUT:
        左上隅(0行0列）から順にスキャンして、
        初めてマス目の値が nan となる、行と列の番号(i,j)を返す
        値が nan となるマス目がない場合： -1, -1 を返す
    '''
    pass
    # 以下にコードを書く

    for j in range(9):
        for i in range(9):
            if grid[j][i] == nan:
                return j, i
    
    return -1,-1
    
def isValidInRowCol(grid, i,j,e):
    '''
    INPUT: 
    grid: マス目情報
    i : 行番号
    j : 列番号
    e : 1から9のどれかの数字
    OUTPUT:
        i行の数字にeがなく、 j列の数字にeがない -> True   
        False 上記以外
    '''
    pass
    # 以下にコードを書く
    
    if e in grid[j]:
        return False
    if e in [v[i] for v in grid]:
        return False
    

def isValidInBlock(grid, i,j,e):
    '''
    INPUT: 
    grid: マス目情報
    i : 行番号
    j : 列番号
    e : 1から9のどれかの数字
    OUTPUT:
        True if i行j列が属するブロックに値e を置くことができる
        False 上記以外
    '''
    pass
    # 以下にコードを書く
    block_row=(i//3)
    block_col=(j//3)
    for i in range(block_row*3, block_row*3+3):
        for j in range(block_col*3, block_col*3+3):
            if e == grid[i][j]:
                return True
    return False
    
    
    

#  判定関数   isValid(grid,i,j,e)  を isValidInRowCol() と isValidInBlock() で構成
    
def isValid(grid, i,j,e):
    return isValidInRowCol(grid,i,j,e) and isValidInBlock(grid,i,j,e)

#-------------------------------
# テストしてみる
print_grid(grid_prob1)
if find_next(grid_prob1)  == (0,4):#  (0,4) が出力されればよい！
    print('find_next() works well')   
else:
    print('[BAD] find_next() does not work')
    
print_grid(grid_prob2)
if find_next(grid_prob2)  == (0,2):#  (0,2) が出力されればよい！
    print('find_next() works well')
else:
    print('[BAD] find_next() does not work')

backtrack=0
def solve(grid):
    global backtrack
    i,j = find_next(grid)
    if i<0:
        return True 
    for e in range(1,10):
        if isValid(grid,i,j,e):
            grid[i][j]=e
            if solve(grid):
                return True
            backtrack += 1
            grid[i][j]=nan
    return False

#---------------

def call_solve(grid):
    grid_copy=copy.deepcopy(grid)
    if solve(grid_copy):
        print(f'succeeded in solving [backtrack={backtrack}]')
        print_grid(grid_copy)
    else:
        print('FAIL in solving')

# ------
#  問題を解く
#
print('grid_prob1 を解く')
print_grid(grid_prob1)
call_solve(grid_prob1)

print('grid_prob2 を解く')
print_grid(grid_prob2)
call_solve(grid_prob2)

追記
間違えて追加修正依頼のところに書いてしまいました。
すいません。

turkey1212

2022/06/25 22:33

「nan = 0です」は、別途定義してあるという意味でしょうか？ Pythonではnanは非数（数値ではない）を意味してnp.nan、math.nanとして定義されています。独自に別のものに定義し直すことは避けた方が無難ですよ。 nanが独自に定義した0ではなく本来のnanであれば、 0 == nan はFalseと判定されます。あるいは、nan（という名の変数）は0と評価されているけど、データの中に0ではなく本来のnanが入っているのかもしれません。 grid_prob1やgrid_prob2をどう与えていますか？ nanはどう定義していますか？

melian

2022/06/25 23:10

isValidInRowCol 関数ですが、return True が書かれていません。例えば適当に、 print(isValidInRowCol([[*range(1, 10)]]*9, 3, 4, 11)) とすると、None が返ります(False として扱われてしまいます)。

TakaiY

2022/06/26 05:29

「指針に従って書いたのですが、答えが出せません。」とありますが、具体的にはどのような結果になるのですか。また、他の方の質問にもありますが、grid_prob1やgrid_prob2の定義を教えてください。

hagi

2022/06/26 09:40

nan=0 def input_helper(str_lines): lines=str_lines.split() #print(lines) grid=[] for line in lines: grid.append([ int(c) if int(c)>0 else nan for c in list(line)]) return grid def print_grid(grid): str_grid = [ [ ' '+str(e) if e !=nan else ' ' for e in row ] for row in grid ] for nth,row in enumerate(str_grid): sub_str_list=['['] for col in [0,3]: sub_str_list.append( ','.join(row[col:col+3])+' | ' ) sub_str_list.append(','.join(row[6:9])+']') line_str = ''.join(sub_str_list) print(line_str) if nth in [2,5]: print('-----------'*3) print() # grid_str1=''' 517600034 089004000 306205090 600000010 030006047 000000000 090000078 703400560 000000000 ''' grid_prob1=input_helper(grid_str1) print("数独問題1： grid_prob1") print_grid(grid_prob1) # grid_str2=''' 530070000 600195000 098000060 800060003 400803001 700020006 060000280 000419005 000080079 ''' grid_prob2=input_helper(grid_str2) print("数独問題2： grid_prob2") print_grid(grid_prob2) 質問以前のプログラムです。 nan=0とここで定義されています。 backtrack=0 def solve(grid): global backtrack i,j = find_next(grid) if i<0: return True for e in range(1,10): if isValid(grid,i,j,e): grid[i][j]=e if solve(grid): return True backtrack += 1 grid[i][j]=nan return False #--------------- def call_solve(grid): grid_copy=copy.deepcopy(grid) if solve(grid_copy): print(f'succeeded in solving [backtrack={backtrack}]') print_grid(grid_copy) else: print('FAIL in solving') # ------ # 問題を解く # print('grid_prob1 を解く') print_grid(grid_prob1) call_solve(grid_prob1) print('grid_prob2 を解く') print_grid(grid_prob2) call_solve(grid_prob2) そのあと、こちらのプログラムを実行して数独を解く問題です。エラーはないのですが、答えが出せず、どこが違うのかが分からない状況です。 isValidInRowCol関数のif文の後にそれぞれ else: return True を書いたのですが、問題は解けなかったです…

行動規範の内容に同意します

回答1件

ベストアンサー

以下の問題があります。

すでに指摘されていますが、isValidInRowCol関数のTrueの時の返り値がありません。 if - elif -else で場合分けするのがいいのではないかと思います。

isValidInBlock関数の判定が逆です。ブロック内に対象の数が入っていたらFalseを返さなければなりません。

iとjが逆になってしまっている箇所がいくつかあります。iは行でjは列です。ただ、ちゃんと逆になっているところもあったりしますが、混乱するので、全て統一すべきです。

これらを直せば動くと思います。

text
1succeeded in solving [backtrack=6372]
2[ 5, 1, 7 |  6, 9, 8 |  2, 3, 4]
3[ 2, 8, 9 |  1, 3, 4 |  7, 5, 6]
4[ 3, 4, 6 |  2, 7, 5 |  8, 9, 1]
5---------------------------------
6[ 6, 7, 2 |  8, 4, 9 |  3, 1, 5]
7[ 1, 3, 8 |  5, 2, 6 |  9, 4, 7]
8[ 9, 5, 4 |  7, 1, 3 |  6, 8, 2]
9---------------------------------
10[ 4, 9, 5 |  3, 6, 2 |  1, 7, 8]
11[ 7, 2, 3 |  4, 8, 1 |  5, 6, 9]
12[ 8, 6, 1 |  9, 5, 7 |  4, 2, 3]