Nクイーン問題を解決するさまざまなアプローチのパフォーマンス比較を評価したいと考えました。主にAIメタヒューリスティクスベースのアルゴリズムは、シミュレーテッドアニーリング、タブー検索、遺伝的アルゴリズムなど、正確な方法（バックトラッキングなど）と比較しています。学習に利用できるコードはありますか？そのような実際の最適化問題の多くは、正確な方法とメタヒューリスティクスの間の協調スキームを考慮しています。Nクイーン問題に対するアルゴリズムアプローチの比較
私は数年前に大学でn-queensソルバーをJavaのクラスに書く必要がありました。あなたが探しているソースコードのタイプがわからないのですが、ここで助けが必要な場合は、そのプログラムのコードです。どのような方法でも最適化されているわけではなく、非常に単純な再帰アルゴリズムです。私はこれを最初の学期に書きましたので、初心者の間違いを許してください:-)私はブロックコメントのほとんどを取りましたが、残念ながらそれを理解することができます。多分Googleの検索を行うのだろうか？私はWikipediaにはまともな記事と疑似コードがあることを知っています。お役に立てれば！
import java.util.Scanner;
public class QueensSolver
{
public static void main(String args[])
{
System.out.println("Please enter the size of the chessboard: ");
Scanner stdin = new Scanner(System.in);
int sizeOfBoard = stdin.nextInt();
//Create the board to the given size.
char[][] board = new char[sizeOfBoard][sizeOfBoard];
//fill board with hyphens
for(int row=0; row<sizeOfBoard; row++)
{
for(int col=0; col<sizeOfBoard; col++)
{
board[row][col] = '-';
}
}
//Call the method which attempts to solve the problem
if(solve(sizeOfBoard, board, 0))
{ //if true, we know that the board array contains a solution
printBoard(sizeOfBoard, board);
}
else
{ //if false, we know that no solutions exist on this size of board
System.out.println("No solutions are possible with this board size.");
}
}
public static boolean solve(int sizeOfBoard, char[][] board, int row)
{
//If all rows have been filled, we have a solution
if(row>=sizeOfBoard)
{
return true;
}
//For each column(space) on the given row
for(int col=0; col<sizeOfBoard; col++)
{
//If placing a queen in this column(space) does not cause a conflict
if(!checkConflict(sizeOfBoard, board, row, col))
{
//place a queen here
board[row][col]='Q';
//then call this same function on the next row
boolean success = solve(sizeOfBoard, board, row+1);
//if every function in this recursive path returns true
if(success)
{
//then we return true also
return true;
}
//If there is no possible solution with this queen placement,
//then we replace the queen with an empty and attempt
//to place a queen in the next column(space).
else
{
board[row][col]='-';
}
}
}
return false;
}
public static boolean checkConflict(int sizeOfBoard, char[][] board, int rowCheck, int colCheck)
{
//Check for queens placed directly above this position
for(int row = rowCheck-1; row>=0; row--)
{
if(board[row][colCheck]=='Q')
{
return true;
}
}
//Check for queens placed on the diagonal
//above and to the right of this position
int col = colCheck+1;
for(int row = rowCheck-1; row>=0; row--)
{
if(col>=sizeOfBoard)
{
break;
}
if(board[row][col]=='Q')
{
return true;
}
col++;
}
//Check for queens placed on the diagonal
//above and to the left of this position
col = colCheck-1;
for(int row = rowCheck-1; row>=0; row--)
{
if(col<0)
{
break;
}
if(board[row][col]=='Q')
{
return true;
}
col--;
}
//We know that no conflicts are caused by this position, so return false
return false;
}
public static void printBoard(int sizeOfBoard, char[][] board)
{
for(int row=0; row<sizeOfBoard; row++)
{
for(int col=0; col<sizeOfBoard; col++)
{
System.out.print(board[row][col]);
}
System.out.print("\n");
}
}
}
私は本当に（あなたがアルゴリズムの理論を知りたいですか？だから、コードを見たいですか？）あなたの質問を得ることはありませんが、私は野生から適応コードを共有して喜んでいます。それはPythonで、それはかなりクールです。イテレータを使用するように変更しました。奇跡的にも、イテレータは動作します。
# I can't really claim much credit for this implementation.
# I found this on the web and I converted it to use python generators.
# Adapted from:
# http://en.wikibooks.org/wiki/Algorithm_implementation/Miscellaneous/N-Queens
def queensproblem(solution, rows, columns):
def add_one_queen(new_row, columns, solution):
for new_column in range(columns):
if not conflict(new_row, new_column, solution):
yield new_column
def conflict(new_row, new_column, solution):
return any(solution[row] == new_column or
solution[row] + row == new_column + new_row or
solution[row] - row == new_column - new_row
for row in range(new_row))
if len(solution) == rows:
yield solution
else :
for row in range(len(solution), rows):
for col in add_one_queen(row, columns, solution):
for x in queensproblem(solution + [col], rows, columns):
yield x
else:
break
if __name__ == '__main__':
for i,solution in enumerate(queensproblem([], 8, 8)):
print i, solution
Python標準ライブラリのファイルtest/test_generators.pyには良いアプローチがあります。 Queensクラスをチェックしてください。
コンピュータにPythonがインストールされていない場合は、オンラインでファイルhereを参照できます。
Droolsソルバが面白いかもしれません。特にchapter 1 of the documentation。
これは可能な限り速いスキームの実装ではありませんが、かなり簡潔です。私はそれを独立して作り出しましたが、それは独特だとは思わない。これはPLT Schemeにありますので、R6RSで実行するにはいくつかの関数名を変更する必要があります。ソリューションと各ソリューションのリストは短所で構築されているため、逆になっています。最後に反転してマップすると、すべてが並べ替えられ、かなりの出力が得られるように行が追加されます。ほとんどの言語は、折り畳み式の機能を持って、次を参照してください。
http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29
#lang scheme/base
(define (N-Queens N)
(define (attacks? delta-row column solution)
(and (not (null? solution))
(or (= delta-row (abs (- column (car solution))))
(attacks? (add1 delta-row) column (cdr solution)))))
(define (next-queen safe-columns solution solutions)
(if (null? safe-columns)
(cons solution solutions)
(let move-queen ((columns safe-columns) (new-solutions solutions))
(if (null? columns) new-solutions
(move-queen
(cdr columns)
(if (attacks? 1 (car columns) solution) new-solutions
(next-queen (remq (car columns) safe-columns)
(cons (car columns) solution)
new-solutions)))))))
(unless (exact-positive-integer? N)
(raise-type-error 'N-Queens "exact-positive-integer" N))
(let ((rows (build-list N (λ (row) (add1 row)))))
(reverse (map (λ (columns) (map cons rows (reverse columns)))
(next-queen (build-list N (λ (i) (add1 i))) null null)))))