Rosetta Code

15 puzzle solver: Difference between revisions

Page Discussion

15 puzzle solver (view source)

Revision as of 08:38, 13 January 2023

14,598 bytes removed ,  1 year ago
Fix C#. Not ideal, but fully correct answer. :D
(Fix C#. Not ideal, but fully correct answer. :D)
Line 2,661:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd }}
{{libheader|System.Windows.Forms"}}
{{libheader|System.Drawing}}
{{works with|C sharp|3+}}
Note 1: The program does not output a text solution. It's solvig step by step in grafical interface.<br>
Note 2: Rosetta task avaiable from UI. Click "Task" button and run slover. The solution is obtained for 164 moves.
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.DrawingText;
using System.Windows.Forms;
 
public static class Program
Line 2,675 ⟶ 2,670:
public static void Main(string[] args)
{
FifteenPuzzlebyte[] Gamet = new FifteenPuzzle();byte[]
Application.Run(Game.Form);{
15, 14, 1, 6,
}
}
 
public class Puzzle
{
private int mOrderedNumer;
public int OrderedNumer
{
get { return mOrderedNumer; }
}
 
public int CurrentNumber;
 
public bool IsPined = false;
 
public int X;
public int Y;
 
public int InvX
{
get { return (FifteenPuzzle.GridSize - 1) - X; }
}
public int InvY
{
get { return (FifteenPuzzle.GridSize - 1) - Y; }
}
 
public Puzzle(int OrderedNumer)
{
mOrderedNumer = OrderedNumer;
CurrentNumber = OrderedNumer;
 
X = OrderedNumer % FifteenPuzzle.GridSize;
Y = OrderedNumer / FifteenPuzzle.GridSize;
}
 
public bool IsEmptyPuzzle
{
get { return CurrentNumber >= (FifteenPuzzle.BlockCount - 1); }
}
public bool IsTruePlace
{
get { return (CurrentNumber == mOrderedNumer); }
}
public bool NearestWith(Puzzle OtherPz)
{
int dx = (X - OtherPz.X);
int dy = (Y - OtherPz.Y);
 
if ((dx == 0) && (dy <= 1) && (dy >= -1)) return true;
if ((dy == 0) && (dx <= 1) && (dx >= -1)) return true;
 
return false;
}
public int MHDistance(Puzzle OtherPz)
{
int dx = (X - OtherPz.X);
int dy = (Y - OtherPz.Y);
 
if (dx < 0) dx = -dx;
if (dy < 0) dy = -dy;
 
return dx + dy;
}
 
public override string ToString()
{
return (CurrentNumber + 1).ToString();
}
public void UpdateView(Button V)
{
V.Visible = true;
V.Text = ToString();
if (IsEmptyPuzzle) V.Visible = false;
}
}
 
public class FifteenPuzzle
{
public const int GridSize = 4; //Standard 15 puzzle is 4x4
public const int BlockCount = 16;
 
static readonly Random R = new Random();
 
private Form mForm;
public Form Form
{
get { return mForm; }
}
 
private List<Button> Puzzles = new List<Button>();
private int Moves = 0;
private DateTime Start;
 
private SolverPuzzle Solver;
private Button SolverButton;
private Timer SolverClock;
 
public FifteenPuzzle()
{
this.mForm = CreateForm();
this.Solver = new SolverPuzzle(Puzzles.ConvertAll<Puzzle>(Bt => (Puzzle)Bt.Tag));
}
 
private Form CreateForm()
{
int ButtonSize = 50;
int ButtonMargin = 3;
int FormEdge = 9;
 
Font ButtonFont = new Font("Arial", 15.75F, FontStyle.Regular);
 
Button StartButton = CreateButton("New Game", NewGameWithRandomBoard);
StartButton.Location = new Point(FormEdge, (GridSize * (ButtonMargin + ButtonSize)) + FormEdge);
 
int FormWidth = (GridSize * ButtonSize) + ((GridSize - 1) * ButtonMargin) + (FormEdge * 2);
int FormHeigth = FormWidth + StartButton.Height;
 
Form Form = new Form();
Form.Text = "Fifteen";
Form.ClientSize = new Size(FormWidth, FormHeigth);
Form.FormBorderStyle = FormBorderStyle.FixedSingle;
Form.MaximizeBox = false;
Form.SuspendLayout();
 
for (int i = 0; i < BlockCount; i++)
{
Button Bt = new Button();
Puzzle Pz = new Puzzle(i);
 
int PosX = FormEdge + (Pz.X) * (ButtonSize + ButtonMargin);
int PosY = FormEdge + (Pz.Y) * (ButtonSize + ButtonMargin);
Bt.Location = new Point(PosX, PosY);
 
Bt.Size = new Size(ButtonSize, ButtonSize);
Bt.Font = ButtonFont;
 
Bt.Tag = Pz;
Bt.UseVisualStyleBackColor = true;
Bt.TabStop = false;
Bt.Enabled = false;
 
Pz.UpdateView(Bt);
Bt.Click += new EventHandler(MovePuzzle);
 
Puzzles.Add(Bt);
Form.Controls.Add(Bt);
}
 
// solver controls
SolverClock = new Timer();
SolverClock.Interval = 300;
SolverClock.Tick += new EventHandler(SolverStep);
 
SolverButton = CreateButton("Run Solver", RunOrStopSolver);
SolverButton.Location = new Point(FormWidth - FormEdge - SolverButton.Width, StartButton.Location.Y);
SolverButton.Enabled = false;
 
Button TaskButton = CreateButton("Task", NewGameWithTask);
TaskButton.Location = new Point(StartButton.Location.X + StartButton.Width + ButtonMargin, StartButton.Location.Y);
TaskButton.Size = new Size((SolverButton.Location.X - ButtonMargin) - TaskButton.Location.X, 23);
 
Form.Controls.Add(StartButton);
Form.Controls.Add(TaskButton);
Form.Controls.Add(SolverButton);
Form.ResumeLayout();
 
return Form;
}
private Button CreateButton(string Text, EventHandler ClickHandler)
{
Button Bt = new Button();
 
Bt.Size = new Size(80, 23);
Bt.Text = Text;
Bt.Font = new Font("Arial", 9.75F, FontStyle.Regular);
Bt.UseVisualStyleBackColor = true;
Bt.TabStop = false;
 
Bt.Click += ClickHandler;
 
return Bt;
}
 
private void NewGameWithRandomBoard(object Sender, EventArgs E)
{
do
{
for (int i = 0; i < Puzzles.Count; i++)
{
Button Bt1 = Puzzles[R.Next(i, Puzzles.Count)];
Button Bt2 = Puzzles[i];
Swap(Bt1, Bt2);
}
}
while (!IsSolvable());
 
NewGameBase();
}
private void NewGameWithTask(object Sender, EventArgs E)
{
int[] RosettaTask = new int[]
{
15, 14, 1, 6,
9, 11, 4, 12,
0, 10, 7, 3,
13, 8, 5, 2,
};
SolutionForCodersParaolympiad.sp15(t);
 
for (int i = 0; i < Puzzles.Count; i++)
{
Button Bt = Puzzles[i];
Puzzle Pz = (Puzzle)Bt.Tag;
 
Pz.CurrentNumber = RosettaTask[i] - 1;
if (Pz.CurrentNumber < 0) Pz.CurrentNumber = BlockCount - 1;
 
Pz.UpdateView(Bt);
}
 
NewGameBase();
}
}
private void NewGameBase()
{
Solver.Clear();
 
public static class SolutionForCodersParaolympiad
for (int i = 0; i < Puzzles.Count; i++)
{
{
static byte[] tryesecA = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, };
Puzzles[i].Enabled = true;
static byte[] tryesec1 = new byte[] { 1, 2, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, };
}
static byte[] tryesec2 = new byte[] { 1, 2, 3, 4, 5, 6, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, };
SolverButton.Enabled = true;
static byte[] tryesec3 = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 99, 99, 99, 99, 99, 99, };
static byte[] tryesec4 = new byte[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 99, 99, 13, 14, 99, 99, };
 
static Queue<bn> bbb = Moves =new 0Queue<bn>();
static Dictionary<byte[], int> llll = new Dictionary<byte[], int>(new com());
Start = DateTime.Now;
static int ms = 0; static string pth = "";
}
private class com : IEqualityComparer<byte[]>
 
private void MovePuzzle(object Sender, EventArgs E)
{
Buttonpublic Bt1 =bool Equals(Buttonbyte[] x, byte[] y)Sender;
Puzzle Pz1 = (Puzzle)Bt1.Tag;
 
Button Bt2 = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle);
Puzzle Pz2 = (Puzzle)Bt2.Tag;
 
if (Pz1.NearestWith(Pz2))
{
Swapif (Bt1,x.Length Bt2!= y.Length) return false;
for (int i = 0; i < x.Length; i++) if (x[i] != y[i]) return false;
Moves++;
return true;
}
public int GetHashCode(byte[] a)
 
CheckWin();
}
 
private void CheckWin()
{
Button WrongPuzzle = Puzzles.Find(Bt => !((Puzzle)Bt.Tag).IsTruePlace);
bool UWin = (WrongPuzzle == null);
 
if (UWin)
{
for (int ihc = 0; i < Puzzlesa.CountLength; i++)
for (int i = 0; i < a.Length; i++) hc = unchecked(hc * 314159 + a[i]);
{
return Puzzles[i].Enabled = falsehc;
}
 
SolverClock.Enabled = false;
SolverButton.Enabled = false;
SolverButton.Text = "Run Solver";
 
TimeSpan Elapsed = DateTime.Now - Start;
Elapsed = TimeSpan.FromSeconds(Math.Round(Elapsed.TotalSeconds, 0));
MessageBox.Show(String.Format("Solved in {0} moves. Time: {1}", Moves, Elapsed));
}
}
private class bn
 
private void Swap(Button Bt1, Button Bt2)
{
public static bn ebn = new bn(null, null); public static byte s = 4;
if (Bt1 == Bt2) return;
public byte[] t; public char p; public int st; public bn pa; public int gt = 1;
 
Puzzlepublic Pz1 =bool da(Puzzlebyte[] br)Bt1.Tag;
Puzzle Pz2 = (Puzzle)Bt2.Tag;
 
int g = Pz1.CurrentNumber;
Pz1.CurrentNumber = Pz2.CurrentNumber;
Pz2.CurrentNumber = g;
 
Pz1.UpdateView(Bt1);
Pz2.UpdateView(Bt2);
}
 
private bool IsSolvable()
{
// WARNING: size of puzzle board MUST be even(like 4)!
// For explain see: https://www.geeksforgeeks.org/check-instance-15-puzzle-solvable/
 
int InvCount = 0;
for (int i = 0; i < Puzzles.Count - 1; i++)
{
for (int ji = i + 10; ji < Puzzlest.CountLength; ji++)
{
Puzzle Pz1 =if (Puzzle)Puzzlesbr[i].Tag == 99) continue;
if (Pz1.IsEmptyPuzzlet[i] != br[i]) continuereturn false;
 
Puzzle Pz2 = (Puzzle)Puzzles[j].Tag;
if (Pz2.IsEmptyPuzzle) continue;
 
if (Pz1.CurrentNumber > Pz2.CurrentNumber) InvCount++;
}
return true;
}
public bn(byte[] b, byte[] br)
 
Button EmptyBt = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle);
Puzzle EmptyPz = (Puzzle)EmptyBt.Tag;
 
bool Result = false;
// even + odd
if (((EmptyPz.InvY + 1) % 2 == 0) && (InvCount % 2 != 0)) Result = true;
// odd + even
if (((EmptyPz.InvY + 1) % 2 != 0) && (InvCount % 2 == 0)) Result = true;
 
return Result;
}
 
private void RunOrStopSolver(object Sender, EventArgs E)
{
SolverClock.Enabled = !SolverClock.Enabled;
 
if (SolverClock.Enabled)
{
SolverButton.Text = "Stop Solver";
}
else
{
SolverButton.Text = "Run Solver";
Solver.Clear();
}
}
 
private void SolverStep(object Sender, EventArgs E)
{
Point NextMove = Solver.AnalysisPosition();
Button NextBt = Puzzles.Find(Bt => (((Puzzle)Bt.Tag).X == NextMove.X && ((Puzzle)Bt.Tag).Y == NextMove.Y));
 
if (NextBt != null) MovePuzzle(NextBt, EventArgs.Empty);
}
}
 
public class SolverPuzzle
{
static readonly int[] SolvingSecuence = new int[] { 0, 1, 2, 3, 4, 8, 12, 5, 6, 7, 9, 13, 10, 11, 14 };
static readonly Point[] GameSteps = new Point[] { new Point(0, 1), new Point(1, 0), new Point(-1, 0), new Point(0, -1) };
 
private List<Puzzle> Puzzles;
private PathSearch Navigator;
private Queue<Point> PlanedMoves = new Queue<Point>();
 
private class DeadLock
{
public int[] BoardMask;
 
public int EntryOrderedNumber;
public Point[] StepToSolve;
 
public bool InBoard(List<Puzzle> Puzzles)
{
boolt HasDeadLock= b; p = true' ';
forif (int it != 0; i < BoardMask.Length; i++null)
{
iffor (BoardMask[int i] <= 0); continuei < t.Length; i++)
if (BoardMask[i] != Puzzles[i].CurrentNumber)
{
HasDeadLockif (br[i] == 99) falsecontinue;
breakint add = (t[i] - br[i]);
if (add < 0) add = -add;
gt += add;
}
}
return HasDeadLock;
}
public bn(byte[] b, bn pakk, char ddd, byte[] br)
}
private static List<DeadLock> DeadLocks = new List<DeadLock>();
 
static SolverPuzzle()
{
// create deadlocks
DeadLock D;
 
// top line
D = new DeadLock();
D.EntryOrderedNumber = 0;
D.BoardMask = new int[] { 0, 1, 2, -1, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, };
D.StepToSolve = new Point[]
{
new Point(1, 0), new Point(2, 0), new Point(3, 0), new Point(3, 1), new Point(2, 1),
new Point(2, 0), new Point(1, 0), new Point(0, 0), new Point(0, 1),
};
DeadLocks.Add(D);
 
// left line
D = new DeadLock();
D.EntryOrderedNumber = 1;
D.BoardMask = new int[] { 0, -1, -1, -1, 4, -1, -1, -1, 8, -1, -1, -1, -1, 12, -1, -1, };
D.StepToSolve = new Point[]
{
newt Point(0,= 0),b; newpa Point(0,= 1),pakk; newst Point(0,= 2),pakk.st new+ Point(0,1; 3),p new Point(1,= 3),ddd;
new Point(1, 2), new Point(0, 2), new Point(0, 1), new Point(0, 0), new Point(1, 0),
new Point(1, 1),
};
DeadLocks.Add(D);
 
for (int i = 0; i < t.Length; i++)
// second from top line
D = new DeadLock();
D.EntryOrderedNumber = 5;
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, 6, -1, -1, -1, -1, 7, -1, -1, -1, -1, };
D.StepToSolve = new Point[]
{
new Point(2, 1), new Point(3, 1), new Point(3, 2), new Point(2, 2), new Point(2, 1),
new Point(1, 1), new Point(1, 2),
};
DeadLocks.Add(D);
 
// second from left line
D = new DeadLock();
D.EntryOrderedNumber = 7;
D.BoardMask = new int[] { -1, -1, -1, -1, -1, 5, -1, -1, -1, 9, -1, -1, -1, -1, 13, -1, };
D.StepToSolve = new Point[]
{
new Point(2, 1), new Point(1, 1), new Point(1, 2), new Point(1, 3), new Point(2, 3),
new Point(2, 2), new Point(1, 2), new Point(1, 1), new Point(2, 1), new Point(3, 1),
new Point(3, 2),
};
DeadLocks.Add(D);
}
 
public SolverPuzzle(List<Puzzle> Puzzles)
{
this.Puzzles = Puzzles;
Navigator = new PathSearch(Puzzles, GameSteps);
}
 
public Point AnalysisPosition()
{
// just do exist plan
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
 
bool AllPined = PinTruePuzzles();
// already solved
if (AllPined) return new Point(-1, -1);
 
Puzzle EmptyPz = Puzzles.Find(Pz => Pz.IsEmptyPuzzle);
Puzzle WrongPz = FindWrongPuzzle();
 
// get path (empty puzzle => wrong puzle) if a far!
if (EmptyPz.MHDistance(WrongPz) > 1)
{
PlanedPath(EmptyPz, WrongPz);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
else // empty puzzle near
{
// move empty puzzle around!
WrongPz.IsPined = true;
Puzzle BestPz = FindBestPuzzleToSwap(WrongPz);
 
// if already in place - click on target
if (BestPz == EmptyPz) return new Point(WrongPz.X, WrongPz.Y);
 
PlanedPath(EmptyPz, BestPz);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
 
// if we are here SPEC CASE AHEAD
for (int i = 0; i < DeadLocks.Count; i++)
{
DeadLock Lock = DeadLocks[i];
if (Lock.InBoard(Puzzles))
{
//if unpin(br[i] dest== 99) continue;
Puzzleint DestPzadd = Puzzles.Find(Pzt[i] => Pz.OrderedNumer ==- Lock.EntryOrderedNumberbr[i]);
DestPz.IsPinedif (add < 0) add = false-add;
gt += add;
 
PlanedPath(EmptyPz, DestPz);
PlanedPath(Lock.StepToSolve);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
}
//public neverbn throwmut(byte ond, normalsbyte statep, char jjj , byte[] br)
throw{ new Exception("Wtf?");
int z = 0;
}
for (int i = 0; i < t.Length; i++)
 
private void PlanedPath(Point[] Steps)
{
// add to plan
for (int i = 0; i < Steps.Length; i++)
{
PlanedMoves.Enqueue(Steps[i]);
}
}
private void PlanedPath(Puzzle StartPz, Puzzle TargetPz)
{
List<Point> Path = Navigator.FindPath(StartPz, TargetPz);
// add to plan
for (int i = 0; i < Path.Count; i++)
{
PlanedMoves.Enqueue(Path[i]);
}
}
 
private Puzzle FindBestPuzzleToSwap(Puzzle CentrPz)
{
Puzzle TruePlacePz = Puzzles.Find(Pz => Pz.OrderedNumer == CentrPz.CurrentNumber);
 
Puzzle BestPz = null;
int BestDistance = 0;
 
for (int i = 0; i < GameSteps.Length; i++)
{
Puzzle NierPz = Puzzles.Find(Pz => ((Pz.X == CentrPz.X + GameSteps[i].X) && (Pz.Y == CentrPz.Y + GameSteps[i].Y)));
if (NierPz == null) continue;
if (NierPz.IsPined) continue;
 
int Distance = TruePlacePz.MHDistance(NierPz);
 
if (BestPz == null)
{
BestDistancez = Distancei; if (t[i] == 0) break;
BestPz = NierPz;}
bn r = ebn; continuebyte[] ghu = null;
if (d == 0)
{
int x = z % s; if (((x + p) >= s) || ((x + p) < 0)) return ebn;
ghu = new byte[t.Length]; Array.Copy(t, ghu, t.Length);
byte gg = ghu[z + p];
ghu[z + p] = ghu[z];
ghu[z] = gg;
}
if (d == 1)
{
int y = z / s; if (((y + p) >= s) || ((y + p) < 0)) return ebn;
ghu = new byte[t.Length]; Array.Copy(t, ghu, t.Length);
byte gg = ghu[z + (p * s)];
ghu[z + (p * s)] = ghu[z];
ghu[z] = gg;
}
 
ifint (Distanceexist <= BestDistance)-1;
if (llll.ContainsKey(ghu))
{
BestDistanceexist = Distancellll[ghu];
BestPzif (exist <= NierPz(this.st + 1)) return ebn;
else
{
bn aaaa = new bn(ghu, this, jjj, br);
llll[ghu] = aaaa.st;
return aaaa;
}
}
bn aaaab = new bn(ghu, this, jjj, br);
r = aaaab; llll.Add(aaaab.t, aaaab.st);
return r;
}
return BestPz;
}
private static void s(byte[] ooo, byte[] br, out bn rrrrr, out string strrr)
private Puzzle FindWrongPuzzle()
{
for bbb.Clear(int i = 0); i < SolvingSecuencellll.LengthClear(); i++)
bn hh = new bn(ooo, br); bbb.Enqueue(hh);
bn r; int las = 1;
while (true)
{
Puzzle SecPzhh = Puzzlesbbb.FindDequeue(Pz => Pz.CurrentNumber == SolvingSecuence[i]);
//if first(hh.da(br)) unpined{ inr solving= sechh; break; }
if (!SecPzhh.IsPined)gt return> SecPz;las)
}
return null;
}
private bool PinTruePuzzles()
{
// unpin all
for (int i = 0; i < Puzzles.Count; i++)
{
Puzzles[i].IsPined = false;
}
// pin
bool AllPined = true;
for (int i = 0; i < SolvingSecuence.Length; i++)
{
Puzzle SecPz = Puzzles.Find(Pz => Pz.OrderedNumer == SolvingSecuence[i]);
// stop pining on first wrong puzzle
if (!SecPz.IsTruePlace)
{
AllPinedlas++; =if false(bbb.Count < 1000000) bbb.Enqueue(hh); continue;
break;
}
else las--;
 
SecPz.IsPined// = true;mut
bn n = hh.mut((byte)0, (sbyte)1, 'r', br); if (n != bn.ebn) bbb.Enqueue(n);
n = hh.mut((byte)0, (sbyte)-1, 'l', br); if (n != bn.ebn) bbb.Enqueue(n);
n = hh.mut((byte)1, (sbyte)1, 'b', br); if (n != bn.ebn) bbb.Enqueue(n);
n = hh.mut((byte)1, (sbyte)-1, 't', br); if (n != bn.ebn) bbb.Enqueue(n);
}
bn u = r; StringBuilder rrr = new StringBuilder();
return AllPined;
while (u != null) { rrr.Append(u.p); u = u.pa; }
rrrrr = r; strrr = rrr.ToString().Trim();
}
private static bn chainI(byte[] t, byte[] h)
 
public void Clear()
{
PlanedMoves.Clearbn r; string sr; s(t, h, out r, out sr);
if (r != null) { ms += sr.Length; pth += sr; }
return r;
}
public static void sp15(byte[] t)
}
 
public class PathSearch
{
// AStar path search. Extremely naive realization for one task.
 
private Stack<NodeSearch> OpenedNodes = new Stack<NodeSearch>();
private List<NodeSearch> Nodes = new List<NodeSearch>();
 
private Point[] Steps;
private const float StepCost = 1f;
 
private enum NodeState { Unknown, Open, Closed }
private class NodeSearch
{
publicDateTime PuzzleStart Puzzle= DateTime.Now;
 
publicbn PointK Location= chainI(t, tryesec1);
{K = chainI(K.t, tryesec2);
K = get { return new PointchainI(PuzzleK.Xt, Puzzle.Ytryesec3); }
}K = chainI(K.t, tryesec4);
publicK int= XchainI(K.t, tryesecA);
{
get { return Puzzle.X; }
}
public int Y
{
get { return Puzzle.Y; }
}
public bool IsWalkable
{
get { return !Puzzle.IsPined; }
}
 
publicTimeSpan float GElapsed = 0fDateTime.Now - Start;
Elapsed = TimeSpan.FromSeconds(Math.Round(Elapsed.TotalSeconds, 0));
public NodeState State = NodeState.Unknown;
public NodeSearch ParentNode;
 
public NodeSearch(Puzzle Puzzle)
{
this.Puzzle = Puzzle;
}
 
public void Clear()
{
G = 0f;
State = NodeState.Unknown;
ParentNode = null;
}
}
 
public PathSearch(List<Puzzle> Puzzles, Point[] GameSteps)
{
this.Steps = GameSteps;
// bind puzzles to search nodes
for (int i = 0; i < Puzzles.Count; i++)
{
Nodes.Add(new NodeSearch(Puzzles[i]));
}
}
 
public List<Point> FindPath(Puzzle StartPz, Puzzle TargetPz)
{
List<Point> Path = new List<Point>();
 
NodeSearch Start = Nodes.Find(Ns => (Ns.Puzzle == StartPz));
if (Start == null) return Path;
 
NodeSearch Target = Nodes.Find(Ns => (Ns.Puzzle == TargetPz));
if (Target == null) return Path;
 
Start.State = NodeState.Open;
OpenedNodes.Push(Start);
 
bool PathFound = false;
 
while (OpenedNodes.Count > 0)
{
NodeSearch CurrentNode = OpenedNodes.Pop();
 
if (CurrentNode == Target)
{
PathFound = true;
break;
}
 
for (int i = 0; i < Steps.Length; i++)
{
NodeSearch NextNode = Nodes.Find(Ns => ((Ns.X == CurrentNode.X + Steps[i].X) && (Ns.Y == CurrentNode.Y + Steps[i].Y)));
if (NextNode == null) continue;
 
if (!NextNode.IsWalkable) continue;
 
if (NextNode.State == NodeState.Closed) continue;
 
if (NextNode.State == NodeState.Open)
{
float NewG = CurrentNode.G + StepCost;
if (NewG < NextNode.G)
{
NextNode.ParentNode = CurrentNode;
NextNode.G = NewG;
OpenedNodes.Push(NextNode);
}
}
else
{
// unknow node
NextNode.State = NodeState.Open;
NextNode.ParentNode = CurrentNode;
NextNode.G = CurrentNode.G + StepCost;
OpenedNodes.Push(NextNode);
}
}
 
CurrentNode.State = NodeState.Closed;
}
 
// restore path
if (PathFound)
{
NodeSearch CurentNode = Target;
while (CurentNode != Start)
{
Path.Add(CurentNode.Location);
CurentNode = CurentNode.ParentNode;
}
Path.Reverse();
}
 
// clear state
OpenedNodes.Clear();
for (int i = 0; i < Nodes.Count; i++)
{
Nodes[i].Clear();
}
 
Console.WriteLine(String.Format("Solved in {0} moves. Time: {1}", ms, Elapsed));
return Path;
Console.WriteLine(String.Format("Path: {0}", pth));
Console.ReadKey();
}
}</syntaxhighlight>
{{out}}
<pre>
Solved in 100 moves. Time: 00:00:33
Path: brttlbltrtlbltrbblbrrttrrrtlllbrbltrrrtlllbrttlbbrbltrtrbbrtllblbrtrrtlllbrbltrbltrbrrbllltrrbrtlbrt
</pre>
 
=={{header|C++}}==
Fig
7

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335463"