AnyOne Knows how to???
- To: mathgroup at smc.vnet.net
- Subject: [mg88212] AnyOne Knows how to???
- From: AnnaSJ <anna_112006 at yahoo.com>
- Date: Mon, 28 Apr 2008 04:40:40 -0400 (EDT)
Hello Group,
This Program is the knight's tour, however if someone could help me
knightJumps = {{2, -1}, {1, -2}, {-1, -2}, {-2, -1}, {-2, 1}, {-1,
2}, {1, 2}, {2, 1}};
successors[s_, n_, position_] :=
Block[{moves, onBoard},
moves = Map[position + # &,
knightJumps];(*moves over the edge of the chessboard \
are*)(*invalid*)
onBoard = Select[moves, And @@ Thread[{0, 0} < # <= {n, n}] &];
Select[onBoard, s[[Sequence @@ #]] == 0 &]]
numberOfSuccessors[s_, n_, position_] :=
Length[successors[s, n, position]]
mina[s_, n_, position_] :=
(*successor(s) with least number of successors*)
Block[{localSuccessors, localNumbersOfSuccessors, minimum},
localSuccessors = successors[s, n, position];
localNumbersOfSuccessors =
Map[numberOfSuccessors[s, n, #] &, localSuccessors];
minimum = Min[localNumbersOfSuccessors];
localSuccessors[[
Flatten[Position[localNumbersOfSuccessors, minimum]]]]]
mabst[destination_, successorlist_] :=
(*successor(s) with greatest distance from*)(*destination*)
Block[{vectors, distances, maximum},
vectors = Map[destination - # &, successorlist];
distances = Map[#.# &, vectors];
maximum = Max[distances];
successorlist[[Flatten[Position[distances, maximum]]]]]
improvedWarnsdorff[n_] :=(*main program*)
Block[{s, destination, position,
localMina},(*initialize chessboard s*)(*s[[x,y]]==0==>square (x,
y) is*)(*untouched.*)(*in the end,
s contains the step numbers*)(*at which every square was visited*)
s = Table[0, {n}, {n}];(*path should end near the following*)
destination = {Round[n/2] - 1/2,
Round[n/2] - 1/2};(*starting point in the corner of the board*)
position = {1, 1}; s[[1, 1]] = 1;
Do[localMina = mina[s, n, position];
If[Length[localMina] == 0, Print["Blind alley"];(*algorithm failed*)
Break[]];
position =
If[Length[localMina] == 1, First[localMina],
First[mabst[destination, localMina]]];
s[[First[position], Last[position]]] = stepNumber, {stepNumber, 2,
n n}]; s]
knight = improvedWarnsdorff[6]; MatrixForm[knight]
This Program is the knight's tour, however if someone could help me to use a doubly subscripted array, accessibility, with numbers indicating from how many squares each particular square is accessible. On a blank chessboard, each center square is rated as 8, each corner square is rated as 2, and the other squares have accessibility numbers of 3, 4, or 6 as follows:
2 3 4 4 3 2
3 4 6 6 4 3
4 6 8 8 6 4
4 6 8 8 6 4
3 4 6 6 4 3
2 3 4 4 3 2
Is some one could help me to use the Knight's Tour program by using this heuristic. At any time, the knight "SHOULD MOVE TO THE SQUARE WITH THE LOWEST ACCESSIBILITY NUMBER". If the square have the same "value" (6,6) (tie), the knight may move to any of the same square, so the tour may begin in any of the four corners.
As the knight moves around the chessboard, THE program should reduce the accessibility numbers as more and more squares become occupied. In this way, at any given time during the tour, each available square's accessibility number will remain equal to precisely the number of squares from which that square may be reached.
Thank you All,
Anna SJ