Example10.1

「Example10.1」の編集履歴（バックアップ）一覧はこちら

Example10.1 - (2011/02/24 (木) 08:49:00) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

#co(){
10.1 The N-Queens Problem 

For-comprehensions are especially useful for solving combinatorial puzzles. An example of such a puzzle is the 8-queens problem: Given a standard chess-board, place 8 queens such that no queen is in check from any other (a queen can check another piece if they are on the same column, row, or diagonal). We will now develop a solution to this problem, generalizing it to chess-boards of arbitrary size. Hence, the problem is to place n queens on a chess-board of size n × n. 
}

** 10.1 N クィーン問題 (The N-Queens Problem)

for 内包表記は組み合わせパズルを解くのに特に役立ちます。そのようなパズルの一つの例が８クイーン問題 : 標準的なチェス盤に、８個のクイーンをお互いにチェックしない (クイーンは他の駒が同じ行、列、斜めにある時にチェックできます) ように置け、です。この問題の解法を考えますが、一般化してチェス盤を任意の大きさにします。したがって問題は、n個のクイーンを n x n の大きさのチェス盤に置け、となります。

#co(){
To solve this problem, note that we need to place a queen in each row. So we could place queens in successive rows, each time checking that a newly placed queen is not in check from any other queens that have already been placed. In the course of this search, it might arrive that a queen to be placed in row k would be in check in all fields of that row from queens in row 1 to k − 1. In that case, we need to abort that part of the search in order to continue with a different configuration of queens in columns 1 to k − 1. 
}

問題を解くには、クイーンは各行に置かなくてはならないことに注意しましょう。ですから、クイーンを各行に置き、その度に新しく置いたクイーンが、すでに置かれた他のクイーンからチェックされないことを確認します。探索の過程において、行 k 
のどの場所にクイーンを置いても、それが行 1 から行 k-1 までのどれかのクイーンによってチェックされるかもしれません。そのような場合にはその部分の探索を止め、列 1 から列 k-1 のクイーンの異なる配置で探索を続けます。

#co(){
This suggests a recursive algorithm. Assume that we have already generated all solutions of placing k − 1 queens on a board of size n × n. We can represent each such solution by a list of length k − 1 of column numbers (which can range from 1 to n). We treat these partial solution lists as stacks, where the column number of the queen in row k − 1 comes first in the list, followed by the column number of the queen in row k − 2, etc. The bottom of the stack is the column number of the queen placed in the first row of the board. All solutions together are then represented as a list of lists, with one element for each solution. 
}

以上から、再帰的なアルゴリズムが示唆されます。サイズ n x n の盤に k-1 個のクイーンを置いた解がすでにあるとしましょう。そのような解は、長さ k-1 の列番号のリスト (1 から n の範囲の値) として表現できます。この部分解リストをスタックのように扱います。リストの最初は k-1 行のクイーンの列番号、二番目は k-2 行のクイーンの列番号です。スタックの底は、盤の最初の行のクイーンの列番号です。すべての解はリストのリストとして表現され、各要素が個々の解です。

#co(){
Now, to place the k 'the queen, we generate all possible extensions of each previous solution by one more queen. This yields another list of solution lists, this time of length k . We continue the process until we have reached solutions of the size of the chess-board n. This algorithmic idea is embodied in function placeQueens below:
}

さて、k 番目のクイーンを置くために、前の解にクイーンを一つ追加し、可能なすべての拡張を作ります。これは長さ k の次の解のリストとなります。このプロセスをチェス盤のサイズ n に達するまで繰り返します。このアルゴリズムは次の関数 placeQueens に表されます。

 def queens(n: Int): List[List[Int]] = { 
   def placeQueens(k: Int): List[List[Int]] = 
     if (k == 0) List(List()) 
     else for { queens <- placeQueens(k - 1) 
                   column <- List.range(1, n + 1) 
                   if isSafe(column, queens, 1) } yield column :: queens 
   placeQueens(n) 
 }

#co(){
Exercise 10.1.1 Write the function 
}

&b(){演習 10.1.1　} 次の関数を書きなさい。

 def isSafe(col: Int, queens: List[Int], delta: Int): Boolean 

#co(){
which tests whether a queen in the given column col is safe with respect to the queens already placed. Here, delta is the difference between the row of the queen to be placed and the row of the first queen in the list. 
}

この関数は与えられた列 col に置くクイーンが、すでに置かれているクイーンに対して安全か否かを判定します。ここで delta は、クイーンを置く行と、リスト中の最初のクイーンの行との差です。

#center(){[[前ページ>Chapter 10 For-Comprehensions]]　[[ 10 章>Chapter 10 For-Comprehensions]]　[[目次>ScalaByExample和訳]]　[[次ページ>Example10.2]]}

----
#comment

#co(){
10.1 The N-Queens Problem 

For-comprehensions are especially useful for solving combinatorial puzzles. An example of such a puzzle is the 8-queens problem: Given a standard chess-board, place 8 queens such that no queen is in check from any other (a queen can check another piece if they are on the same column, row, or diagonal). We will now develop a solution to this problem, generalizing it to chess-boards of arbitrary size. Hence, the problem is to place n queens on a chess-board of size n × n. 
}


#setmenu2(ex-r-menu)
** 10.1 N クィーン問題 (The N-Queens Problem)

for 内包表記は組み合わせパズルを解くのに特に役立ちます。そのようなパズルの一つの例が８クイーン問題 : 標準的なチェス盤に、８個のクイーンをお互いにチェックしない (クイーンは他の駒が同じ行、列、斜めにある時にチェックできます) ように置け、です。この問題の解法を考えますが、一般化してチェス盤を任意の大きさにします。したがって問題は、n個のクイーンを n x n の大きさのチェス盤に置け、となります。

#co(){
To solve this problem, note that we need to place a queen in each row. So we could place queens in successive rows, each time checking that a newly placed queen is not in check from any other queens that have already been placed. In the course of this search, it might arrive that a queen to be placed in row k would be in check in all fields of that row from queens in row 1 to k − 1. In that case, we need to abort that part of the search in order to continue with a different configuration of queens in columns 1 to k − 1. 
}

問題を解くには、クイーンは各行に置かなくてはならないことに注意しましょう。ですから、クイーンを各行に置き、その度に新しく置いたクイーンが、すでに置かれた他のクイーンからチェックされないことを確認します。探索の過程において、行 k 
のどの場所にクイーンを置いても、それが行 1 から行 k-1 までのどれかのクイーンによってチェックされるかもしれません。そのような場合にはその部分の探索を止め、列 1 から列 k-1 のクイーンの異なる配置で探索を続けます。

#co(){
This suggests a recursive algorithm. Assume that we have already generated all solutions of placing k − 1 queens on a board of size n × n. We can represent each such solution by a list of length k − 1 of column numbers (which can range from 1 to n). We treat these partial solution lists as stacks, where the column number of the queen in row k − 1 comes first in the list, followed by the column number of the queen in row k − 2, etc. The bottom of the stack is the column number of the queen placed in the first row of the board. All solutions together are then represented as a list of lists, with one element for each solution. 
}

以上から、再帰的なアルゴリズムが示唆されます。サイズ n x n の盤に k-1 個のクイーンを置いた解がすでにあるとしましょう。そのような解は、長さ k-1 の列番号のリスト (1 から n の範囲の値) として表現できます。この部分解リストをスタックのように扱います。リストの最初は k-1 行のクイーンの列番号、二番目は k-2 行のクイーンの列番号です。スタックの底は、盤の最初の行のクイーンの列番号です。すべての解はリストのリストとして表現され、各要素が個々の解です。

#co(){
Now, to place the k 'the queen, we generate all possible extensions of each previous solution by one more queen. This yields another list of solution lists, this time of length k . We continue the process until we have reached solutions of the size of the chess-board n. This algorithmic idea is embodied in function placeQueens below:
}

さて、k 番目のクイーンを置くために、前の解にクイーンを一つ追加し、可能なすべての拡張を作ります。これは長さ k の次の解のリストとなります。このプロセスをチェス盤のサイズ n に達するまで繰り返します。このアルゴリズムは次の関数 placeQueens に表されます。

 def queens(n: Int): List[List[Int]] = { 
   def placeQueens(k: Int): List[List[Int]] = 
     if (k == 0) List(List()) 
     else for { queens <- placeQueens(k - 1) 
                   column <- List.range(1, n + 1) 
                   if isSafe(column, queens, 1) } yield column :: queens 
   placeQueens(n) 
 }

#co(){
Exercise 10.1.1 Write the function 
}

&b(){演習 10.1.1　} 次の関数を書きなさい。

 def isSafe(col: Int, queens: List[Int], delta: Int): Boolean 

#co(){
which tests whether a queen in the given column col is safe with respect to the queens already placed. Here, delta is the difference between the row of the queen to be placed and the row of the first queen in the list. 
}

この関数は与えられた列 col に置くクイーンが、すでに置かれているクイーンに対して安全か否かを判定します。ここで delta は、クイーンを置く行と、リスト中の最初のクイーンの行との差です。

#center(){[[前ページ>Chapter 10 For-Comprehensions]]　[[ 10 章>Chapter 10 For-Comprehensions]]　[[目次>ScalaByExample和訳]]　[[次ページ>Example10.2]]}

----
#comment