Javaban;
//#######################################################
// File : Queen.java
// Writer : dants, mosheb
//#######################################################
//#######################################################
// Class description:
//#######################################################
/** *****************************************************
* Slove the N by N Queens Problem using backtracking.<br>
* see: <href=http://www.math.utah.edu/~alfeld/queens/queens.html>
* http://www.math.utah.edu/~alfeld/queens/queens.html</a>
* <br><br>
* @author dants, mosheb
********************************************************/
public class Queen {
//@@bfg:t@ solve
/** *************************************************
* In chess, a queen can move as far as she pleases,
* horizontally, vertically, or diagonally. A chess
* board has 8 rows and 8 columns (n=8). The standard
* 8 by 8 Queen's problem asks how to place 8 queens
* on an ordinary chess board so that none of them
* can attack any other in one move.
*
* This is one solution to the problem:
* <img src="../../fig/8-queen.gif">
*
* This method prints all the solutions possible
* for an <i>n X n</i> board.
****************************************************/
public static void solve(int n) {
boolean[][] board = new boolean[n][n];
solve(board, 0);
}
//@@efg@
//@@bfg:t@ backtracking
/** *************************************************
* This is the recursive function per se.
* - Each instance of the method is responsible for
* positioning one queen in row `row' (in all
* possible columns).
* - If a position in this `row' is legal with respect
* to the queens positioned in previous rows, then
* this method will call itself recursively to
* position the queens in the next rows.
****************************************************/
private static void solve(boolean[][] board, int row){
final int N = board.length;
for(int col=0; col < N; col++) {
// <b>1- position queen in [row][col]</b>
board[row][col] = true;
// <b>2- if it's a legal position ...</b>
if( checkPosition(board,row,col) ) {
if( row < N-1 )
solve(board, row+1);
else
print(board);
}
// <b>3- remove queen from [row][col]</b>
board[row][col] = false;
}
}
//@@efg@
//@@bfg:t@ checkPosition
/** *************************************************
* Return true iff positioning a queen in [row][col]
* doesn't conflict with the queens already
* positioned in previous rows.
* This can be done using a linear pass over the
* board using <i>k = 1..row</i> as follows:
*
* |-- col-k --| |---- col+k ----|
*
* - +---+---+---+---+---+---+---+---+
* | | | | | x | | | | x |
* | |---|---|---|---|---|---|---|---|
* | | x | | | x | | | x | |
* row-k |---|---|---|---|---|---|---|---|
* | | | x | | x | | x | | |
* | |---|---|---|---|---|---|---|---|
* | | | | x | x | x | | | |
* - |---|---|---|---|---|---|---|---|
* | | | | Q | | | | |row
* |---|---|---|---|---|---|---|---|
* col
*
****************************************************/
private static boolean
checkPosition(boolean[][] board, int row, int col)
{
final int N = board.length;
for(int k=1; k <= row; k++) {
if( board[row-k][col] ||
((col-k >= 0) && board[row-k][col-k]) ||
((col+k < N) && board[row-k][col+k]) )
return false;
}
return true;
}
//@@efg@
//@@bfg:t@ print
/** *************************************************
* Print the given board to the standard output.
****************************************************/
private static void print(boolean[][] board) {
final int N = board.length;
// <b>each line in the board will be separated using
// the following string:</b>
String sepLine = "+";
for(int i=0; i < N; i++)
sepLine += "---+";
// <b>print the board:</b>
for(int r=0; r < N; r++) {
System.out.println(sepLine);
System.out.print("|");
for(int c=0; c < N; c++) {
String q = board[r][c] ? "Q" : " ";
System.out.print( " " + q + " |" );
}
System.out.println();
}
System.out.println(sepLine + "\n\n");
}
//@@efg@
//@@bfg:t@ test
/** *************************************************
* Test Queen.solve():
* The first board that will be printed is:
*
* +---+---+---+---+---+---+---+---+
* | Q | | | | | | | |
* +---+---+---+---+---+---+---+---+
* | | | | | Q | | | |
* +---+---+---+---+---+---+---+---+
* | | | | | | | | Q |
* +---+---+---+---+---+---+---+---+
* | | | | | | Q | | |
* +---+---+---+---+---+---+---+---+
* | | | Q | | | | | |
* +---+---+---+---+---+---+---+---+
* | | | | | | | Q | |
* +---+---+---+---+---+---+---+---+
* | | Q | | | | | | |
* +---+---+---+---+---+---+---+---+
* | | | | Q | | | | |
* +---+---+---+---+---+---+---+---+
*
****************************************************/
public static void main(String argv[]) {
solve(8);
}
//@@efg@
}
//#######################################################
// EOF
//#######################################################
Nézzük meg pascalban;
Function Jo(i:integer):boolean; {T[i] üti-e az elõzõeket} var j:integer;
Begin
j:=1;
while (not uti(i,j)) and (j<i) do j:=j+1;
Jo:=(j=i); {végigmentünk ütés nélkül az elõzõeken} End;
var i:integer;
BEGIN
for i:=1 to 8 do T[i]:=0;
i:=1; {az i. bábut vizsgáljuk} while (i>0) and (i<9) do begin
T[i]:=T[i]+1; {eggyel elõretoljuk az i. bábut} if T[i]>8 then begin
T[i]:=0; {ha nincs több lehetõség, visszalépés} i:=i-1;
end else
if Jo(i) then i:=i+1; {továbblépés a következõre} end;
if i>8 then for i:=1 to 8 do writeln(T[i])
else writeln('Nincs megoldás.');
END.
Nincsenek megjegyzések:
Megjegyzés küldése