F#(FSharp)用三种方法解N皇后问题，剖析F#之美
由于论坛不易于排版，所以具体内容请看这里，欢迎转载、拍砖！
http://blog.csdn.net/aimeast/archive/2010/04/25/5527749.aspx
代码先贴出：
let NQueens n = let a = [|for i in 0..n -> true|] //某列是否使用的标志 let b = [|for i in 0..(2 * n - 1) -> true|] //斜负方向上是否使用的标志 let c = [|for i in 0..(2 * n - 1) -> true|] //斜正方向上是否使用的标志 let path = [|for i in 0..n -> 0|] //记录当前路径 //Solve n j 求解规模为n，第j行的解 let rec Solve n j = if j > n then //已经把当前状态的n行都求解完毕，可打印当前路径 printfn "%A" path.[1..] //打印当前结果 else //否则，要继续向下求解 for i in 1..n do //枚举当前行的所有列 //如果当前位置的列、斜正、斜负方向都可用，则使用 if (a.[i] && b.[i + j - 1] && c.[n - i + j]) then //标记状态 a.[i] <- false b.[i + j - 1] <- false c.[n - i + j] <- false path.[j] <- i //记录当前路径 do Solve n (j + 1) //求解下一行 //还原状态 a.[i] <- true b.[i + j - 1] <- true c.[n - i + j] <- true do Solve n 1 //从第一行开始求解 printfn "" List.iter NQueens [1..10] //求1到10皇后的所有解 System.Console.ReadKey()|>ignore
//自定义数据类型 type Queen = struct val x: int val y: int //构造函数 new(x: int, y: int) = { x = x; y = y } //重载Object.ToString() override this.ToString() = //字符串打印函数 sprintf "(%d,%d)" this.x this.y end let NQueens n = //对子问题求解 let rec Solve = function //第一行每一个位置都可以放置 | x when x = 1 -> [for y in 1..n -> [new Queen(1,y)]] //其他情况 | x -> //构造一个临时存放结果的变量 let mutable t = [[new Queen(0,0)]].Tail //枚举当前子问题的解 for i in Solve (x - 1) do //逐一尝试是否可以放置 for y in 1..n do if not((List.exists (fun (elem: Queen) -> elem.y = y ) i) //列可放置 ||(List.exists (fun elem -> elem = x + y) (List.map (fun (elem: Queen) -> elem.x + elem.y) i)) //斜负方向可放置 ||(List.exists (fun elem -> elem = x - y) (List.map (fun (elem: Queen) -> elem.x - elem.y) i))) //斜正方向可放置 then //把当前可行解放入临时空间 t <- t @ ([i @ [new Queen(x, y)]]) //返回当前可行解 t //求解并返回 Solve n //打印结果 NQueens 8 |> List.iteri (fun i elem -> printfn "%d:\t%A" (i + 1) elem) System.Console.ReadKey()|>ignore type Queen =
struct
val x: int
val y: int
new(x: int, y: int) = { x = x; y = y }
override this.ToString() =
sprintf "(%d,%d)" this.x this.y
end
let NQueens n =
let rec Solve = function
| x when x = 1 ->
[for y in 1..n -> [new Queen(1,y)]]
| x ->
//求出当前子问题解集与要测试是否能放置的点的空间
[for sub in Solve (x - 1) do
for y in 1..n -> (sub, y)]
//将此空间传递给选择器选择哪些是有效的
|> List.choose (fun (sub, y) ->
if not(sub |> List.exists (fun (elem: Queen) -> elem.y = y ) //列有效
||(List.map (fun (elem: Queen) -> elem.x + elem.y) sub)
|> List.exists (fun elem -> elem = x + y) //斜负方向有效
||(List.map (fun (elem: Queen) -> elem.x - elem.y) sub)
|> List.exists (fun elem -> elem = x - y)) //斜正方向有效
then Some(sub @ [new Queen(x, y)]) //标记有效值
else None) //不作处理
//求解并返回结果
Solve n
//求解并打印结果
NQueens 8 |> List.iteri (fun i elem -> printfn "%d:\t%A" (i + 1) elem)
System.Console.ReadKey()|>ignore
using System;namespace CSharpTest{ class Program { static int[] Place; static int QueenCount; static void Main(string[] args) { Solve(10); Console.ReadKey(); } static void Solve(int length) { QueenCount = length; Place = new int[length]; SearchQueens(0, 0, 0, 0); } static void SearchQueens(int currentColumn, int columnCheck, int slashCheck1, int slashCheck2) { if (currentColumn == QueenCount) { PrintResult(); return; } slashCheck1 <<= 1; slashCheck2 >>= 1; for (int i = 0; i < QueenCount; i++) { int sign = 1 << i; if ((sign & columnCheck) == 0 && (slashCheck1 & sign) == 0 && (slashCheck2 & sign) == 0) { Place[currentColumn] = i + 1; SearchQueens(currentColumn + 1, columnCheck | sign, slashCheck1 | sign, slashCheck2 | sign); } } } static void PrintResult() { for (int i = 0; i < QueenCount; i++) Console.Write("{0} ", Place[i]); Console.WriteLine(); } }}
[解决办法]
學了物件導向的程式語言後再看F#的code真的有點難吸收呀!
[解决办法]
大家都那么积极 我也分享一下以前写的代码吧。还没完善
using System;
using System.Collections.Generic;
using System.Text;
namespace BreaveBoy.ConsoleApplication_Test.Logic
{
class EightQueen
{
private char other ;
private char queen ;
private char split ;
private int maxResult;
private int random;
private bool isLoop;
private bool isPrint = false;
private bool isRandom;
private int flag;
private bool graphPrint;
/// <summary>
/// 默认图形输出
/// GraphPrint=false为坐标打印
/// </summary>
public bool GraphPrint
{
get { return graphPrint; }
set { graphPrint = value; }
}
Point[] QueenPosition = new Point[8];
/// <summary>
/// 是否打印
/// </summary>
public bool IsPrint
{
get { return isPrint; }
set { isPrint = value; }
}
/// <summary>
/// 是否循环求解
/// </summary>
public bool IsLoop
{
get { return isLoop; }
set { isLoop = value; }
}
/// <summary>
/// 是否随机求解
/// </summary>
public bool IsRandom
{
get { return isRandom; }
set { isRandom = value; }
}
/// <summary>
/// 求解方式（1:遍历求解，2:删选求解）
/// </summary>
public int Flag
{
get { return flag; }
set { flag = value; }
}
/// <summary>
/// 皇后位置默认为8皇后
/// </summary>
public EightQueen()
{
other = '*';
queen = 'Q';
split = '\t';
random = 0;
graphPrint = true;
maxResult = FindResult(2, 0);
}
/// <summary>
/// n皇后求解
/// </summary>
/// <param name="flag">求解方式（1:遍历求解，2:删选求解） </param>
/// <param name="x">求第x种解 </param>
/// <returns> </returns>
public int FindResult(int flag,int x)
{
int ret=0;
int all = 0;
x = (x == 0 ? 0 : (x % maxResult));
if (flag % 2 == 1)
{
for (int i = 0; i < 8; i++)
{
QueenPosition[0] = new Point(i, 0);
for (int j = 0; j < 8; j++)
{
QueenPosition[1] = new Point(j, 1);
for (int k = 0; k < 8; k++)
{
QueenPosition[2] = new Point(k, 2);
for (int l = 0; l < 8; l++)
{
QueenPosition[3] = new Point(l, 3);
for (int m = 0; m < 8; m++)
{
QueenPosition[4] = new Point(m, 4);
for (int n = 0; n < 8; n++)
{
QueenPosition[5] = new Point(n, 5);
for (int o = 0; o < 8; o++)
{
QueenPosition[6] = new Point(o, 6);
for (int p = 0; p < 8; p++)
{
QueenPosition[7] = new Point(p, 7);
if (CheckConflict(QueenPosition, 7))
{
all++;
continue;
}
else
{
all++;
ret++;
if (x == ret && isPrint)
Print(QueenPosition);
}
}
}
}
}
}
}
}
}
}
else
{
for (int i = 0; i < 8; i++)
{
QueenPosition[0] = new Point(i, 0);
for (int j = 0; j < 8; j++)
{
QueenPosition[1] = new Point(j, 1);
if (CheckConflict(QueenPosition, 1))
{ all++; continue; }
for (int k = 0; k < 8; k++)
{
QueenPosition[2] = new Point(k, 2);
if (CheckConflict(QueenPosition, 2))
{ all++; continue; }
for (int l = 0; l < 8; l++)
{
QueenPosition[3] = new Point(l, 3);
if (CheckConflict(QueenPosition, 3))
{ all++; continue; }
for (int m = 0; m < 8; m++)
{
QueenPosition[4] = new Point(m, 4);
if (CheckConflict(QueenPosition, 4))
{ all++; continue; }
for (int n = 0; n < 8; n++)
{
QueenPosition[5] = new Point(n, 5);
if (CheckConflict(QueenPosition, 5))
{ all++; continue; }
for (int o = 0; o < 8; o++)
{
QueenPosition[6] = new Point(o, 6);
if (CheckConflict(QueenPosition, 6))
{ all++; continue; }
for (int p = 0; p < 8; p++)
{
QueenPosition[7] = new Point(p, 7);
if (CheckConflict(QueenPosition, 7))
{
all++;
continue;
}
else
{
all++;
ret++;
if (x == ret && isPrint)
Print(QueenPosition);
}
}
}
}
}
}
}
}
}
}
Console.WriteLine("\n总共遍历{0}次：成功{1}", all, ret);
return ret;
}
/// <summary> /// 检查水平线 private bool CheckHorizontal(Point a, Point b) { if (a.Y == b.Y) return true; else return false; } /// <summary> /// 检查竖线 /// </summary> private bool CheckVertical(Point a, Point b) { if (a.X== b.X) return true; else return false; } /// <summary> /// 检查斜线 /// </summary> private bool CheckOblique(Point a, Point b) { if (a.X - b.X == 0) return false; if (Math.Abs((float)(a.Y - b.Y) / (a.X - b.X)) == 1) return true; else return false; } /// <summary> /// 检查数组中皇后的位置是否有冲突 /// </summary> /// <param name="QueenPosition"></param> /// <param name="to">0<to<8 </param> /// <returns></returns> private bool CheckConflict(Point[] QueenPosition,int to) { for (int i = 0; i <to; i++) { for (int j = i + 1; j <=to; j++) { if (CheckHorizontal(QueenPosition[i], QueenPosition[j]) ||CheckVertical(QueenPosition[i], QueenPosition[j]) || CheckOblique(QueenPosition[i], QueenPosition[j])) return true; } } return false; } /// <summary> /// 打印一行皇后的位置 /// </summary> /// <param name="loac">换后所在位置</param> /// <param name="n">可扩展为n皇后问题</param> private String PrintOneLine(Point loac,int n) { StringBuilder tem = new StringBuilder() ; for (int i = 0; i < n; i++) { tem.Append(split); if (i == loac.X) { if (graphPrint) tem.Append(queen); else tem.Append(loac.PrintString()); } else tem.Append(other); } return tem.Append("\n\n").ToString(); } /// <summary> /// 控制台打印皇后 /// *可打印n皇后 /// </summary> /// <param name="QueenPosition">皇后位置数组</param> private void Print(Point[] QueenPosition) { StringBuilder tem = new StringBuilder(); for (int i = 0; i < QueenPosition.Length; i++) { tem.Append(PrintOneLine(QueenPosition[i], QueenPosition.Length)); } Console.WriteLine(tem.ToString()); }
[解决办法]
/// <summary> /// 测试用例一 /// </summary> public void Test1() { DateTime beginTime = DateTime.Now; Console.WriteLine("（方法一）\n\tbegin time :" + beginTime); Console.WriteLine(FindResult(1,0)); DateTime endTime = DateTime.Now; Console.WriteLine("\tend time :" + endTime); Console.WriteLine("算法所用时间（单位：毫秒）" + (endTime - beginTime).TotalMilliseconds); } /// <summary> /// 测试用例二 /// </summary> public void Test2() { DateTime beginTime = DateTime.Now; Console.WriteLine("（方法二）\n\tbegin time :" + beginTime); Console.WriteLine(FindResult(2, 0)); DateTime endTime = DateTime.Now; Console.WriteLine("\tend time :" + endTime); Console.WriteLine("算法所用时间（单位：毫秒）" + (endTime - beginTime).TotalMilliseconds); } /// <summary> /// 测试用例三 /// </summary> public void Test3() { Point[] p = new Point[] { new Point(0, 0), new Point(1, 2), new Point(2, 4), new Point(3, 1), new Point(4, 5), new Point(5, 7), new Point(6, 3), new Point(7, 6) }; Console.WriteLine(CheckConflict(p, 7)); Console.ReadLine(); } /// <summary> /// 测试用例一和二 /// </summary> public void Test() { Test1(); Test2(); Console.ReadLine(); } /// <summary> /// 定制测试用例 /// </summary> /// <param name="Flag">1:q</param> public void Run(int Flag) { String input=""; while (true) { if (IsRandom) { Random rd = new Random(); random = rd.Next(maxResult); } FindResult(Flag, random); if (!IsLoop) break; Console.WriteLine("退出/继续（q/g）！"); input = Console.ReadLine(); if (input.Equals("q")) break; } } class Point { int _x, _y; public int Y { get { return _y; } set { _y = value; } } public int X { get { return _x; } set { _x = value; } } public Point(int x, int y) { X = x; Y = y; } public String PrintString() { return String.Format("({0},{1})", X, Y); } public void Print() { Console.WriteLine(PrintString()); } } }}