Pythonを使ってN-queensを解く（コードの代替案）：

Question

私は次のコードを試しました。コードの複雑さを減らすために何か修正が加えられたら、私はboardというネストされた辞書を使用しました。

def initialize(board,n): 
    for key in ['queen','row','col','nwtose','swtone']: 
    board[key] = {} 
    for i in range(n): 
    board['queen'][i] = -1 
    board['row'][i] = 0 
    board['col'][i] = 0 
    for i in range(-(n-1),n): 
    board['nwtose'][i] = 0 
    for i in range(2*n-1): 
    board['swtone'][i] = 0 

def printboard(board): 
    for row in sorted(board['queen'].keys()): 
    print((row,board['queen'][row])) 

def free(i,j,board): 
    return(board['queen'][i] == 0 and board['row'][i] == 0 and board['col'][j] == 0 and board['nwtose'][j-i] == 0 and board['swtone'][j+i] == 0) 

def addqueen(i,j,board): 
    board['queen'][i] = j 
    board['row'][i] = 1 
    board['col'][j] = 1 
    board['nwtose'][j-i] = 1 
    board['swtone'][j+i] = 1 

def undoqueen(i,j,board): 
    board['queen'][i] = -1 
    board['row'][i] = 0 
    board['col'][j] = 0 
    board['nwtose'][j-i] = 0 
    board['swtone'][j+i] = 0 


def placequeen(i,board): 
    n = len(board['queen'].keys()) 
    for j in range(n): 
     if free(i,j,board): 
     addqueen(i,j,board) 
     if i == n-1: 
      return(True) 
     else : 
      extendsoln = placequeen(i+1,board) 
     if extendsoln: 
      return(True) 
     else: 
      undoqueen(i,j,board) 
    else: 
     return(False) 


board = {} 
n = int(input("How many Queens? ")) 
initialize(board,n) 
if placequeen(0,board): 
    printboard(board) 

私はこのコードを試してみましたが、入力を4にしても出力は得られません。 私は間違っていますか？

おかげ

Answer 1

あなたはinitialize()でボードを初期化するときは、すべての値board['queen'][i]-1に設定します。あなたのメインプログラムは、jの各値に対して、board['queen'][i] == 0をチェックするif free(i,j,board):を呼び出すif placequeen(0,board):を呼び出します。最後のチェックはすべてjで失敗します。したがってfree()はFalseを返し、placequeenは返すことがないので、Falseを返します。メインプログラムはボードを印刷しようとしません。

あなたのプログラムは、必要以上に複雑です。あなたの辞書は全く必要ないと思っています。さまざまな配列を別々の変数として使うことができます。しかし、実際にコードの簡素化を求めることはありませんでした。この印刷されていないバグをどのように取り除くかはわかりませんが、-1ではなくboard['queen'][i]を0に設定することを検討してください。

@RandomDavisには、デバッガの使い方を学ぶ必要があることに同意します。私はあなたが述べたバグの原因を見つけるために1つを使用しましたが、他のバグが残っている可能