15 puzzle solver: Difference between revisions

Content added Content deleted
(Fix C#. Not ideal, but fully correct answer. :D)
Line 2,661: Line 2,661:
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrrulddluuuldrurdddrullulurrrddldluurddlulurruldrdrd
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd }}
rrruldluuldrurdddluulurrrdlddruldluurddlulurruldrrdd }}
{{libheader|System.Windows.Forms"}}
{{libheader|System.Drawing}}
{{works with|C sharp|3+}}
{{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;
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Drawing;
using System.Text;
using System.Windows.Forms;


public static class Program
public static class Program
Line 2,675: Line 2,670:
public static void Main(string[] args)
public static void Main(string[] args)
{
{
FifteenPuzzle Game = new FifteenPuzzle();
byte[] t = new 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,
9, 11, 4, 12,
0, 10, 7, 3,
0, 10, 7, 3,
13, 8, 5, 2,
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, };


Moves = 0;
static Queue<bn> bbb = new Queue<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)
{
{
Button Bt1 = (Button)Sender;
public bool Equals(byte[] x, byte[] y)
Puzzle Pz1 = (Puzzle)Bt1.Tag;

Button Bt2 = Puzzles.Find(Bt => ((Puzzle)Bt.Tag).IsEmptyPuzzle);
Puzzle Pz2 = (Puzzle)Bt2.Tag;

if (Pz1.NearestWith(Pz2))
{
{
Swap(Bt1, Bt2);
if (x.Length != 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 i = 0; i < Puzzles.Count; i++)
int hc = a.Length;
for (int i = 0; i < a.Length; i++) hc = unchecked(hc * 314159 + a[i]);
{
Puzzles[i].Enabled = false;
return hc;
}

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;

Puzzle Pz1 = (Puzzle)Bt1.Tag;
public bool da(byte[] br)
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 j = i + 1; j < Puzzles.Count; j++)
for (int i = 0; i < t.Length; i++)
{
{
Puzzle Pz1 = (Puzzle)Puzzles[i].Tag;
if (br[i] == 99) continue;
if (Pz1.IsEmptyPuzzle) continue;
if (t[i] != br[i]) return 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)
{
{
bool HasDeadLock = true;
t = b; p = ' ';
for (int i = 0; i < BoardMask.Length; i++)
if (t != null)
{
{
if (BoardMask[i] < 0) continue;
for (int i = 0; i < t.Length; i++)
if (BoardMask[i] != Puzzles[i].CurrentNumber)
{
{
HasDeadLock = false;
if (br[i] == 99) continue;
break;
int 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[]
{
{
new Point(0, 0), new Point(0, 1), new Point(0, 2), new Point(0, 3), new Point(1, 3),
t = b; pa = pakk; st = pakk.st + 1; p = 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))
{
{
// unpin dest
if (br[i] == 99) continue;
Puzzle DestPz = Puzzles.Find(Pz => Pz.OrderedNumer == Lock.EntryOrderedNumber);
int add = (t[i] - br[i]);
DestPz.IsPined = false;
if (add < 0) add = -add;
gt += add;

PlanedPath(EmptyPz, DestPz);
PlanedPath(Lock.StepToSolve);
// do path!
if (PlanedMoves.Count > 0) return PlanedMoves.Dequeue();
}
}
}
}
// never throw on normal state
public bn mut(byte d, sbyte p, 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)
{
{
BestDistance = Distance;
z = i; if (t[i] == 0) break;
BestPz = NierPz;
}
continue;
bn r = ebn; byte[] 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;
}
}


if (Distance < BestDistance)
int exist = -1;
if (llll.ContainsKey(ghu))
{
{
BestDistance = Distance;
exist = llll[ghu];
BestPz = NierPz;
if (exist <= (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 (int i = 0; i < SolvingSecuence.Length; i++)
bbb.Clear(); llll.Clear();
bn hh = new bn(ooo, br); bbb.Enqueue(hh);
bn r; int las = 1;
while (true)
{
{
Puzzle SecPz = Puzzles.Find(Pz => Pz.CurrentNumber == SolvingSecuence[i]);
hh = bbb.Dequeue();
// first unpined in solving sec
if (hh.da(br)) { r = hh; break; }
if (!SecPz.IsPined) return SecPz;
if (hh.gt > 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)
{
{
AllPined = false;
las++; if (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.Clear();
bn 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
{
{
public Puzzle Puzzle;
DateTime Start = DateTime.Now;


public Point Location
bn K = chainI(t, tryesec1);
{
K = chainI(K.t, tryesec2);
get { return new Point(Puzzle.X, Puzzle.Y); }
K = chainI(K.t, tryesec3);
}
K = chainI(K.t, tryesec4);
public int X
K = chainI(K.t, tryesecA);
{
get { return Puzzle.X; }
}
public int Y
{
get { return Puzzle.Y; }
}
public bool IsWalkable
{
get { return !Puzzle.IsPined; }
}


public float G = 0f;
TimeSpan Elapsed = DateTime.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>
}</syntaxhighlight>
{{out}}
<pre>
Solved in 100 moves. Time: 00:00:33
Path: brttlbltrtlbltrbblbrrttrrrtlllbrbltrrrtlllbrttlbbrbltrtrbbrtllblbrtrrtlllbrbltrbltrbrrbllltrrbrtlbrt
</pre>


=={{header|C++}}==
=={{header|C++}}==
Retrieved from "https://rosettacode.org/wiki/15_puzzle_solver"