【LeetCode】51. N-Queens 解答・解説【Python】

はじめに
1. ポイント
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, backtrack
  2. 解答2：Python, backtrack
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- backtrack

詳細

問題

原文

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4 Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

1
2
3

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1 Output: [["Q"]]

1
2

Input: n = 1
Output: [["Q"]]

Constraints:

1 <= n <= 9

内容(和訳)

n-queensパズルは、n x nのチェス盤上にn個のクイーンを配置する際に、2つのクイーンが互いに攻撃しないようにする問題です。

整数nが与えられた場合、n-queensパズルのすべての異なる解を返します。解答の順序は任意です。

各解は、n-queensの配置における異なる盤面の構成を含みます。ここで、’Q’と’.’はそれぞれクイーンと空白を表します。

※trancelated by ChatGPT

解答

解答1：Python, backtrack

"""
When backtrack method is called, row is incremented.
And each column is cheacked whether queen can be located in each call of the backtrack method.
"""


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        #make a chessboard.
        state= [["."] * n for _ in range(n)] 
        #variable which is answer of this problem
        res=[]
        
        #
        visited_cols=set()
        visited_diagonals=set()
        visited_antidiagonals=set()
        
        #define backtrack method
        def backtrack(r):
            #If all queens are located on the chessboard, keep current state.
            if r==n:                
                #state is chessboard that display how queens are located.
                #state has n rows and n columns as 2D list.
                #each row has to be changed to str
                res.append(["".join(row) for row in state])
                print(res,"res")
                return
            
            #c is each column.
            for c in range(n):
                #When another queen is located, its difference between row and column is same as one of current location.
                diff=r-c
                #When another queen is located in anti-diagonal, its sum of row and column is same as one of current location.
                _sum=r+c
                #print(r,"r")
                #print(c,"c")
                #print(diff,"diff")
                #print("---------")
                
                #if there is not queen of current row, column and diagonals,
                #keep current row,column,diagonals and locate queen and call this method.
                if not (c in visited_cols or diff in visited_diagonals or _sum in visited_antidiagonals):
                    #keep column range of queen
                    visited_cols.add(c)
                    #keep diagonal range of queen
                    visited_diagonals.add(diff)
                    #keep antiiagonals range of queen
                    visited_antidiagonals.add(_sum)
                    #locate Queen on row=r, column=c
                    state[r][c]='Q' 
                    #call this method recursively with next row
                    #print("located")
                    #print(state,"state1",r,c)
                    #Continue to call backtrack with incremenation of row until queen cannot be located.
                    backtrack(r+1) 

                    #"Q" is replaced to "." and remove sign from column,diagonals for the first time when queens cannot be located.
                    visited_cols.remove(c)
                    visited_diagonals.remove(diff)
                    visited_antidiagonals.remove(_sum)
                    state[r][c]='.'      
                    print("removed")
                    print(state,"state2",r,c)                          
        
        #start from row=1,column=1
        backtrack(0)
        return res

"""

When backtrack method is called, row is incremented.

And each column is cheacked whether queen can be located in each call of the backtrack method.

"""

class Solution:

def solveNQueens(self, n: int) -> List[List[str]]:

#make a chessboard.

state= [["."] * n for _ in range(n)]

#variable which is answer of this problem

res=[]

visited_cols=set()

visited_diagonals=set()

visited_antidiagonals=set()

#define backtrack method

def backtrack(r):

#If all queens are located on the chessboard, keep current state.

if r==n:

#state is chessboard that display how queens are located.

#state has n rows and n columns as 2D list.

#each row has to be changed to str

res.append(["".join(row) for row in state])

print(res,"res")

return

#c is each column.

for c in range(n):

#When another queen is located, its difference between row and column is same as one of current location.

diff=r-c

#When another queen is located in anti-diagonal, its sum of row and column is same as one of current location.

_sum=r+c

#print(r,"r")

#print(c,"c")

#print(diff,"diff")

#print("---------")

#if there is not queen of current row, column and diagonals,

#keep current row,column,diagonals and locate queen and call this method.

if not (c in visited_cols or diff in visited_diagonals or _sum in visited_antidiagonals):

#keep column range of queen

visited_cols.add(c)

#keep diagonal range of queen

visited_diagonals.add(diff)

#keep antiiagonals range of queen

visited_antidiagonals.add(_sum)

#locate Queen on row=r, column=c

state[r][c]='Q'

#call this method recursively with next row

#print("located")

#print(state,"state1",r,c)

#Continue to call backtrack with incremenation of row until queen cannot be located.

backtrack(r+1)

#"Q" is replaced to "." and remove sign from column,diagonals for the first time when queens cannot be located.

visited_cols.remove(c)

visited_diagonals.remove(diff)

visited_antidiagonals.remove(_sum)

state[r][c]='.'

print("removed")

print(state,"state2",r,c)

#start from row=1,column=1

backtrack(0)

return res

有名なNクイーン問題。nxnマスの盤面にn個のクイーンの置き方は何通りあるかを調べる。

クイーンを置くとき、お互いの移動範囲にクイーンが居ないことが条件。

条件を満たす組み合わせ(クイーンを試しにおいていく)を調べていき、当てはまらない場合は前に置いたクイーンを取り除いてまた別の条件を満たす場所にクイーンをおいていくことを繰り返す。

なるべく英語でコメントを付けるようにしたい。実際の面接は英語なので。

解答2：Python, backtrack

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        state = [["."]*n for i in range(n)]
        answer = []

        reach_of_column = set()
        reach_of_diagonal = set()
        reach_of_anti_diagonal = set()
        
        self. backtrack(0, n, state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal)
        return answer

    def backtrack(self, row, n, state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal):
        if row == n:
            _ = ["".join(i) for i in state]
            answer.append(_)
            return
        
        for column in range(n):
            diff = row - column
            sum_ = row + column
            
            if not (column in reach_of_column or diff in reach_of_diagonal or sum_ in reach_of_anti_diagonal):
                reach_of_column.add(column)
                reach_of_diagonal.add(diff)
                reach_of_anti_diagonal.add(sum_)
                state[row][column] = "Q"
                self. backtrack(row+1, n , state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal)
                
                reach_of_column.remove(column)
                reach_of_diagonal.remove(diff)
                reach_of_anti_diagonal.remove(sum_)
                state[row][column] = "."

class Solution:

def solveNQueens(self, n: int) -> List[List[str]]:

state = [["."]*n for i in range(n)]

answer = []

reach_of_column = set()

reach_of_diagonal = set()

reach_of_anti_diagonal = set()

self. backtrack(0, n, state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal)

return answer

def backtrack(self, row, n, state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal):

if row == n:

_ = ["".join(i) for i in state]

answer.append(_)

return

for column in range(n):

diff = row - column

sum_ = row + column

if not (column in reach_of_column or diff in reach_of_diagonal or sum_ in reach_of_anti_diagonal):

reach_of_column.add(column)

reach_of_diagonal.add(diff)

reach_of_anti_diagonal.add(sum_)

state[row][column] = "Q"

self. backtrack(row+1, n , state, answer, reach_of_column, reach_of_diagonal, reach_of_anti_diagonal)

reach_of_column.remove(column)

reach_of_diagonal.remove(diff)

reach_of_anti_diagonal.remove(sum_)

state[row][column] = "."

ほぼ同じコード。解答1とは違い、関数内に関数を置くのではなく独立させた。

書き換えが自由にできるようになりたい。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：216. Combination Sum III

次：

LeetCode 解答・解説記事一覧