function queen(a,cur){ if(cur==a.length){console.log(a);return}; for(var i=0;i<a.length;i++){ a[cur]=i;flag=true; for(var j=0;j<cur;j++){ var ab=i-a[j]; if(a[j]==i||(ab>0?ab:-ab)==cur-j){flag=false;break}; }; if(flag){queen(a,cur+1)}; };};queen([1,1,1,1,1,1,1,1],0)
C++
#include<iostream>using namespace std;static int gEightQueen[8] = { 0 }, gCount = 0;void print()//輸出每一種情況下棋盤中皇后的擺放情況{ for (int i = 0; i < 8; i++) { int inner; for (inner = 0; inner < gEightQueen[i]; inner++) cout << "0"; cout <<"#"; for (inner = gEightQueen[i] + 1; inner < 8; inner++) cout << "0"; cout << endl; } cout << "==========================\n";}int check_pos_valid(int loop, int value)//檢查是否存在有多個皇后在同一行/列/對角線的情況{ int index; int data; for (index = 0; index < loop; index++) { data = gEightQueen[index]; if (value == data) return 0; if ((index + data) == (loop + value)) return 0; if ((index - data) == (loop - value)) return 0; } return 1;}void eight_queen(int index){ int loop; for (loop = 0; loop < 8; loop++) { if (check_pos_valid(index, loop)) { gEightQueen[index] = loop; if (7 == index) { gCount++, print(); gEightQueen[index] = 0; return; } eight_queen(index + 1); gEightQueen[index] = 0; } }}int main(int argc, char*argv[]){ eight_queen(0); cout << "total=" << gCount << endl; return 0;}
Pascal
program queen;vara:array[1..8]of longint;//記錄皇后的行坐標b,c,d:array[-7..16]of longint;//行，右上，右下斜線的占位標誌m,ans:longint;procedure queen(j:longint);vari:longint;begin if j>8 then begin inc(ans);//滿足條件，找到一種方案 exit; end; for i:=1 to 8 do//每個皇后位置有八種可能 if(b[i]=0)and(c[i+j]=0)and(d[j-i]=0)then//如果位置沒有被占則運行 begin a[j]:=i;//皇后放置在此行 b[i]:=1;//占領第i行 c[i+j]:=1;//占領右上 d[j-i]:=1;//占領右下 queen(j+1);//遞歸 b[i]:=0;//回溯，恢復行占位標誌 c[i+j]:=0;//回溯，恢復斜上方（右上）占位標誌 d[j-i]:=0;///回溯，恢復斜下方（右下）占位標誌 end;end;begin//主程式 for m:=-7 to 16 do//數據初始化為0 begin b[m]:=0;//行數據初始化為0 c[m]:=0;//右上數據初始化為0 d[m]:=0;//右下數據初始化為0 end; ans:=0; queen(1);//開始放置第一個皇后 writeln(ans);end.
Java
public class Queen { private int[] column; //同欄是否有皇后，1表示有 private int[] rup; //右上至左下是否有皇后 private int[] lup; //左上至右下是否有皇后 private int[] queen; //解答 private int num; //解答編號 public Queen() { column = new int[8+1]; rup = new int[(2*8)+1]; lup = new int[(2*8)+1]; for (int i = 1; i <= 8; i++) column[i] = 0; for (int i = 1; i <= (2*8); i++) rup[i] = lup[i] = 0; //初始定義全部無皇后 queen = new int[8+1]; } public void backtrack(int i) { if (i > 8) { showAnswer(); } else { for (int j = 1; j <= 8; j++) { if ((column[j] == 0) && (rup[i+j] == 0) && (lup[i-j+8] == 0)) { //若無皇后 queen[i] = j; //設定為占用 column[j] = rup[i+j] = lup[i-j+8] = 1; backtrack(i+1); //循環調用 column[j] = rup[i+j] = lup[i-j+8] = 0; } } } } protected void showAnswer() { num++; System.out.println("\n解答" + num); for (int y = 1; y <= 8; y++) { for (int x = 1; x <= 8; x++) { if(queen[y]==x) { System.out.print("Q"); } else { System.out.print("."); } } System.out.println(); } } public static void main(String[] args) { Queen queen = new Queen(); queen.backtrack(1); }}
def queen(A, cur=0): if cur == len(A): print(A) return 0 for col in range(len(A)): A[cur], flag = col, True for row in range(cur): if A[row] == col or abs(col - A[row]) == cur - row: flag = False break if flag: queen(A, cur+1)queen([None]*8)
C#
using System;using System.Collections.Generic;namespace EightQueens_CSharp{ public class EightQueens { private List<int[]> solutions; public List<int[]> GetSolutions(int queenCount) { solutions = new List<int[]>(); List<int> queenList = new List<int>(); for (int i = 0; i < queenCount; i++) { queenList.Add(0); } putQueen(queenCount, queenList, 0); printSolutions(solutions); return solutions; } private void putQueen(int queenCount, List<int> queenList, int nextY) { for (queenList[nextY] = 0; queenList[nextY] < queenCount; queenList[nextY]++) { if (checkConflict(queenList, nextY) == false) { nextY++; if (nextY < queenCount) { putQueen(queenCount, queenList, nextY); } else { solutions.Add(queenList.ToArray()); Console.WriteLine(string.Join(", ", queenList)); } nextY--; } } } private bool checkConflict(List<int> queenList, int nextY) { for (int positionY = 0; positionY < nextY; positionY++) { if (Math.Abs(queenList[positionY] - queenList[nextY]) == Math.Abs(positionY - nextY) || queenList[positionY] == queenList[nextY]) { return true; } } return false; } private void printSolutions(List<int[]> solutions) { int count = 0; foreach (var solution in solutions) { Console.WriteLine("Solution: {0}", count++); int queenCount = solution.Length; for (int i = 0; i < queenCount; i++) { printLine(solution[i], queenCount); } Console.WriteLine("------------------"); } } private void printLine(int pos, int width) { for (int i = 0; i < width; i++) { if (pos == i) { Console.Write(" x"); } else { Console.Write(" ."); } } Console.WriteLine(); } }}
10 I = 120 A(I) = 130 G = 140 FOR K = I - 1 TO 1 STEP -150 IF A(I) = A(K) THEN 7060 IF ABS(A(I) - A(K)) <> I - K THEN 9070 G = 080 GOTO 10090 NEXT K100 IF I <> 8 THEN 180110 IF G = 0 THEN 180120 FOR L = 1 TO 8130 PRINT USING “##”; A(L);140 NEXT L150 PRINT “*”;160 M = M + 1170 IF M MOD 3 = 0 THEN PRINT180 IF G = 0 THEN 230190 IF I = 8 THEN 230200 I = I + 1210 A(I) = 1220 GOTO 30230 IF A(I) < 8 THEN 270240 I = I - 1250 IF I = 0 THEN 290260 GOTO 230270 A(I) = A(I) + 1280 GOTO 30290 PRINT300 PRINT “SUM=”; USING “##”; M;310 PRINT320 END
// AppEntry.csusing System;namespace Chenglin{ class AppEntry { static void Main(string[] args) { int queenNumber = 8; QueenRowCollection q = new QueenRowCollection(queenNumber); bool flag; DateTime timeStarted = DateTime.Now; flag = q.PositionQueens(); TimeSpan ts = DateTime.Now.Subtract( timeStarted ); if( flag ) { Console.WriteLine( q.ToString() ); } else { Console.WriteLine( "Failed" ); } Console.WriteLine( " seconds has been elapsed.", ts.TotalSeconds ); } }}// QueenRowCollection.csusing System;using System.Text;namespace Chenglin{ public class QueenRowCollection { public QueenRowCollection( int numberOfQueens ) { this.numberOfQueens = numberOfQueens; this.rows = new QueenRow[ numberOfQueens ]; } } public bool PositionQueens() { return PositionQueen( 0 ); } private bool PositionQueen( int row ) { if( row>=this.numberOfQueens ) { return true; } QueenRow q = rows[row]; while(q.MoveNext()) { if( PositionAvailable( row, q.CurrentPosition ) ) { // An available position has been found for the current queen, // and try to find a proper position for the next queen. // // If no available position can be found for the next queen, // the current queen should move to the next position and try again. // if( PositionQueen( row+1 ) ) { // Both the current queen and the next queen // have found available positions. // return true; } } } // No position is available for the current queen, // return false; } private bool PositionAvailable( int row, int column ) { for( int i=row-1; i>=0; i-- ) { if( rows.PositionOccupied( column ) ) return false; if( rows.PositionOccupied( column-(i-row) ) ) return false; if( rows.PositionOccupied( column+(i-row) ) ) return false; } return true; } public override string ToString() { StringBuilder s = new StringBuilder(); foreach( QueenRow q in rows ) { s.AppendFormat( "", q, Environment.NewLine ); } return s.ToString(); } private int numberOfQueens; private QueenRow [] rows; }}
vari,k,n,h:longint;x:array[1..1000] of longint;function p1(k:longint):boolean;beginp1:=true;for i:=1 to (k-1) doif (x[i]=x[k]) or ((abs(x[i]-x[k]))=(abs(i-k))) then p1:=false;end;procedure p2;beginh:=h+1;end;procedure p3(k:longint);var i:integer;beginif (k=n+1) thenbeginp2;exit;end;for i:=1 to n dobeginx[k]:=i;if p1(k) then p3(k+1);end;end;beginreadln(n);p3(1);write(h);end.
*/public class Queen {int size;int resultCount;public void compute ( int size ) {this.size = size;resultCount = 0;int data[] = new int[size];intcount; // 所有可能的情況個數int i,j;// 計算所有可能的情況的個數count = 1;for ( i=0 ; i count = count * size;}// 對每一個可能的情況for ( i=0 ; i // 計算這種情況下的棋盤上皇后的擺放位置，用 8 進制數表示// 此處可最佳化inttemp= i;for ( j=0 ; j data [j] = temp % size;temp = temp / size;}// 測試這種情況是否可行，如果可以，輸出if (test(data) )output( data );}}/** 測試這種情況皇后的排列是否可行**/public boolean test( int[] data ) {int i,j;for ( i=0 ; i for ( j=i+1 ; j // 測試是否在同一排if ( data == data[j] )returnfalse;// 測試是否在一斜線if ( (data+i) == (data[j]+j) )return false;// 測試是否在一反斜線if ( (data-i) == (data[j]-j) )return false;}}returntrue;}/** 輸出某種情況下皇后的坐標**/public void output ( int[] data ) {int i;System.out.print ( ++resultCount + ": " );for ( i=0 ; i System.out.print ( "(" + i + "," + data + ") " );}System.out.println ();}public static void main(String args[]) {(new Queen()).compute( 8 );}}
