algorithm 15 puzzle problem - andstudy/forge GitHub Wiki

CynicJJ

50단계는 커녕 20단계 넘기기도 힘드네...
이번 스터디도 참석 못함. 3번 연속 불참하니 갑갑하네...

!ModuleMain.vb

    Module ModuleMain
    
    	Sub Main()
    
    		Dim notSolvable(,) As Byte = New Byte(,) { _
    		 {13, 1, 2, 4}, _
    		 {5, 0, 3, 7}, _
    		 {9, 6, 10, 12}, _
    		 {15, 8, 11, 14}}
    
    		Dim solvable(,) As Byte = New Byte(,) { _
    		 {2, 3, 4, 0}, _
    		 {1, 5, 7, 8}, _
    		 {9, 6, 10, 12}, _
    		 {13, 14, 11, 15}}
    
    		Console.WriteLine(GetPuzzleResult(notSolvable))
    		Console.WriteLine(GetPuzzleResult(solvable))
    	End Sub
    
    	Function GetPuzzleResult(ByVal board As Byte(,)) As String
    		Dim aPuzzle As Puzzle = New Puzzle
    
    		aPuzzle.Setup(board)
    		aPuzzle.DoSolve()
    
    		If aPuzzle.IsSolved() Then
    			Return aPuzzle.SolvingPath
    		Else
    			Return "This puzzle is not solvable."
    		End If
    
    	End Function
    
    End Module

Position.vb

    Public Class Position
    
    	Public Row As Integer
    	Public Column As Integer
    
    	Sub New(ByVal row As Integer, ByVal column As Integer)
    		Me.Row = row
    		Me.Column = column
    	End Sub
    End Class

Puzzle.vb

    ' 결론부터 말하면 문제 풀이 실패
    ' 50단계까지 검토하라고 했으나 20단계 넘으면 실행시간이 1분을 넘긴다 -_-
    ' 여러 방법들을 시도해 봤으나 효과가 없어서 삭제
    ' 뭔가 요령이 없는 걸까.. 냠..
    ' 어떻게 해야 되는걸까... 쩝쩝
    
    Public Class Puzzle
    
    	' 입력된 경로에 따라 이동
    	Sub MoveByPath(ByVal path As String)
    		Dim dirs() As Char = path.ToCharArray()
    		For Each dir As Char In dirs
    			Select Case dir
    				Case "R"c
    					MoveRight()
    				Case "L"c
    					MoveLeft()
    				Case "U"c
    					MoveUp()
    				Case "D"c
    					MoveDown()
    			End Select
    		Next
    	End Sub
    
    	' 모든 가능한 경로를 만든다
    	' 경로는 공백부터 시작해서 4의 지수승으로 갯수가 늘어난다
    	' 기하급수적으로 늘어나는 경로를 어떻게 줄일것인가가 관건
    	' 이동없음 : ""
    	' 한번이동 : R L U D
    	' 두번이동 : RR LR UR DR LR LL UL DL RU LU UU DU RD LD UD DD
    	' 세번이동 : RRR LRR URR DRR LRR LLR ...
    	' 네번이동 : RRRR LRRR ...
    	' ...
    	Sub GetNextTryPaths(ByVal tryPaths As List(Of String))
    		' 이전 단계 경로들 임시 보관
    		Dim oldPaths As List(Of String) = New List(Of String)
    		oldPaths.AddRange(tryPaths)
    
    		' 몇번이동 하는가
    		Dim steps As Integer = tryPaths(0).Length
    
    		' 시도해 볼 경로들을 새로 만든다
    		tryPaths.Clear()
    
    		Dim dirs() As String = {"R", "L", "U", "D"}
    		For Each dir As String In dirs
    			For Each path As String In oldPaths
    
    				' 이전 자리로 되돌아 가는 경로는 추가하지 않음
    				If steps >= 1 Then
    					Dim lastDir As String = path.Substring(path.Length - 1)
    					If lastDir = "L" And dir = "R" Then Continue For
    					If lastDir = "R" And dir = "L" Then Continue For
    					If lastDir = "D" And dir = "U" Then Continue For
    					If lastDir = "U" And dir = "D" Then Continue For
    				End If
    
    				' 다른 여러 방법을 써 봤으나 별 효과 없었음. 뭔가 요령이 없는 걸까.. 냠..
    
    				' 새로운 경로가 유효한 경로(퍼즐 밖으로 나가지 않는)라면 추가
    				Dim newPath As String = path + dir
    				If IsValidMove(newPath) Then tryPaths.Add(newPath)
    			Next
    		Next
    	End Sub
    
    	' 문제 풀이
    	Sub DoSolve()
    		Dim stepCount As Integer = 0
    
    		Dim tryPaths As List(Of String) = New List(Of String)
    		tryPaths.Add("")
    
    		While stepCount <= 12		' 50단계는 커녕 20단계 넘기기도 힘들다
    			For i As Integer = 0 To tryPaths.Count - 1
    				' 초기상태로 만들고 경로에 따라 이동
    				Reset()
    				MoveByPath(tryPaths(i))
    
    				' 풀렸으면 중단
    				If IsSolved() Then
    					_solvingPath = tryPaths(i)
    					Exit While
    				End If
    			Next
    
    			' 풀리지 않았다면 다음 단계로
    			GetNextTryPaths(tryPaths)
    			stepCount += 1
    		End While
    	End Sub
    
    	' 다 풀렸나?
    	Function IsSolved() As Boolean
    		If 0 <> _board(3, 3) Then Return False
    		If 15 <> _board(3, 2) Then Return False
    		If 14 <> _board(3, 1) Then Return False
    		If 13 <> _board(3, 0) Then Return False
    		If 12 <> _board(2, 3) Then Return False
    		If 11 <> _board(2, 2) Then Return False
    		If 10 <> _board(2, 1) Then Return False
    		If 9 <> _board(2, 0) Then Return False
    		If 8 <> _board(1, 3) Then Return False
    		If 7 <> _board(1, 2) Then Return False
    		If 6 <> _board(1, 1) Then Return False
    		If 5 <> _board(1, 0) Then Return False
    		If 4 <> _board(0, 3) Then Return False
    		If 3 <> _board(0, 2) Then Return False
    		If 2 <> _board(0, 1) Then Return False
    		If 1 <> _board(0, 0) Then Return False
    
    		Return True
    	End Function
    
    	' 유효한 경로인지 판단 (퍼즐 밖으로 벗어나는가 아닌가)
    	Function IsValidMove(ByVal path As String) As Boolean
    		Dim movedRow As Integer = _inputZeroPosition.Row
    		Dim movedColumn As Integer = _inputZeroPosition.Column
    
    		Dim dirs() As Char = path.ToCharArray()
    		For Each dir As Char In dirs
    			Select Case dir
    				Case "R"c
    					movedColumn += 1
    					If movedColumn > 4 Then Return False
    				Case "L"c
    					movedColumn -= 1
    					If movedColumn < 1 Then Return False
    				Case "U"c
    					movedRow -= 1
    					If movedRow < 1 Then Return False
    				Case "D"c
    					movedRow += 1
    					If movedRow > 4 Then Return False
    			End Select
    		Next
    
    		Return True
    	End Function
    
    	' 최초 입력
    	Private _input(,) As Byte
    	Private _inputZeroPosition As Position = New Position(-1, -1)
    
    	' 현재 이동 중인 퍼즐
    	Private _board(3, 3) As Byte
    	Private _zeroPosition As Position = New Position(-1, -1)
    
    	Sub MoveLeft()
    		If _zeroPosition.Column <= 1 Then Return
    
    		Dim left As Byte = _board(_zeroPosition.Row - 1, _zeroPosition.Column - 2)
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column - 1) = left
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column - 2) = 0
    
    		_zeroPosition.Column -= 1
    	End Sub
    
    	Sub MoveRight()
    		If _zeroPosition.Column >= 4 Then Return
    
    		Dim right As Byte = _board(_zeroPosition.Row - 1, _zeroPosition.Column)
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column - 1) = right
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column) = 0
    
    		_zeroPosition.Column = _zeroPosition.Column + 1
    	End Sub
    
    	Sub MoveDown()
    		If _zeroPosition.Row >= 4 Then Return
    
    		Dim down As Byte = _board(_zeroPosition.Row, _zeroPosition.Column - 1)
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column - 1) = down
    		_board(_zeroPosition.Row, _zeroPosition.Column - 1) = 0
    
    		_zeroPosition.Row = _zeroPosition.Row + 1
    	End Sub
    
    	Sub MoveUp()
    		If _zeroPosition.Row <= 1 Then Return
    
    		Dim up As Byte = _board(_zeroPosition.Row - 2, _zeroPosition.Column - 1)
    		_board(_zeroPosition.Row - 1, _zeroPosition.Column - 1) = up
    		_board(_zeroPosition.Row - 2, _zeroPosition.Column - 1) = 0
    
    		_zeroPosition.Row = _zeroPosition.Row - 1
    	End Sub
    
    	' 해답 경로
    	Private _solvingPath As String
    	ReadOnly Property SolvingPath() As String
    		Get
    			Return _solvingPath
    		End Get
    	End Property
    
    	' 초기화
    	Sub Reset()
    		For i As Integer = 0 To 3
    			For j As Integer = 0 To 3
    				_board(i, j) = _input(i, j)
    			Next
    		Next
    
    		_solvingPath = ""
    		_zeroPosition.Row = _inputZeroPosition.Row
    		_zeroPosition.Column = _inputZeroPosition.Column
    	End Sub
    
    	' 최초 입력
    	Sub Setup(ByVal input As Byte(,))
    		_input = input
    
    		Reset()
    
    		UpdateZeroPosition()
    		_inputZeroPosition.Row = _zeroPosition.Row
    		_inputZeroPosition.Column = _zeroPosition.Column
    	End Sub
    
    	Function GetAt(ByVal row As Byte, ByVal column As Byte) As Byte
    		Debug.Assert(row >= 1 And row <= 4)
    		Debug.Assert(column >= 1 And column <= 4)
    
    		Return _board(row - 1, column - 1)
    	End Function
    
    	' 0 위치 찾기
    	Sub UpdateZeroPosition()
    		For row As Integer = 1 To 4
    			For column As Integer = 1 To 4
    				If _board(row - 1, column - 1) = 0 Then
    					_zeroPosition.Row = row
    					_zeroPosition.Column = column
    				End If
    			Next
    		Next
    	End Sub
    
    End Class

!PuzzleTest.vb

    <TestClass()> _
    Public Class PuzzleTest
    
    	Private _puzzle As New Puzzle
    
    	<TestInitialize()> _
    	Public Sub TestInitialize()
    		Dim input(,) As Byte = New Byte(,) { _
    		{2, 3, 4, 0}, _
    		{1, 5, 7, 8}, _
    		{9, 6, 10, 12}, _
    		{13, 14, 11, 15}}
    
    		_puzzle.Setup(input)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub MoveTest()
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(1, 4), "o1")
    		Assert.AreEqual(CByte(4), _puzzle.GetAt(1, 3), "o2")
    
    		_puzzle.MoveLeft()
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(1, 3), "l1")
    		Assert.AreEqual(CByte(4), _puzzle.GetAt(1, 4), "l2")
    
    		_puzzle.MoveRight()
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(1, 4), "r1")
    		Assert.AreEqual(CByte(4), _puzzle.GetAt(1, 3), "r2")
    
    		_puzzle.MoveDown()
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(2, 4), "d1")
    		Assert.AreEqual(CByte(8), _puzzle.GetAt(1, 4), "d2")
    
    		_puzzle.MoveUp()
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(1, 4), "u1")
    		Assert.AreEqual(CByte(8), _puzzle.GetAt(2, 4), "u2")
    	End Sub
    
    	<TestMethod()> _
    	Public Sub SetupTest()
    		Assert.AreEqual(CByte(2), _puzzle.GetAt(1, 1))
    		Assert.AreEqual(CByte(6), _puzzle.GetAt(3, 2))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub IsValidMoveTest()
    		Assert.IsFalse(_puzzle.IsValidMove("R"))
    		_puzzle.MoveByPath("DLDLLUUR")
    		Assert.IsTrue(_puzzle.IsValidMove("DL"))
    		Assert.IsFalse(_puzzle.IsValidMove("R"))
    		Assert.IsFalse(_puzzle.IsValidMove("U"))
    		Assert.IsTrue(_puzzle.IsValidMove("LLLDRDRDR"))
    		Assert.IsFalse(_puzzle.IsValidMove("LLLDRDRDRR"))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub IsSolvedTest()
    		Assert.IsFalse(_puzzle.IsSolved())
    
    		Dim input(,) As Byte = New Byte(,) { _
    		{1, 2, 3, 4}, _
    		{5, 6, 7, 8}, _
    		{9, 10, 11, 12}, _
    		{13, 14, 15, 0}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		Assert.IsTrue(aPuzzle.IsSolved())
    	End Sub
    
    	<TestMethod()> _
    	Public Sub GetNextTryPathsTest()
    		Dim paths As List(Of String) = New List(Of String)
    		paths.Add("")
    
    		_puzzle.GetNextTryPaths(paths)
    		Assert.AreEqual(2, paths.Count)
    		Assert.AreEqual("L", paths(0))
    		Assert.AreEqual("D", paths(1))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub MoveByPathTest()
    		_puzzle.MoveByPath("LLLDRDRDR")
    		Assert.IsTrue(_puzzle.IsSolved())
    		Assert.AreEqual(CByte(0), _puzzle.GetAt(4, 4))
    		Assert.AreEqual(CByte(15), _puzzle.GetAt(4, 3))
    	End Sub
    
    	<TestMethod()> _
    	 Public Sub DoSolveTestSimple()
    		Dim input(,) As Byte = New Byte(,) { _
    		{1, 2, 3, 4}, _
    		{5, 6, 7, 8}, _
    		{9, 10, 11, 12}, _
    		{13, 14, 15, 0}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		aPuzzle.DoSolve()
    		Assert.IsTrue(aPuzzle.IsSolved())
    		Assert.AreEqual("", aPuzzle.SolvingPath)
    	End Sub
    
    	<TestMethod()> _
    	 Public Sub DoSolveTestMoveOneRight()
    		Dim input(,) As Byte = New Byte(,) { _
    		{1, 2, 3, 4}, _
    		{5, 6, 7, 8}, _
    		{9, 10, 11, 12}, _
    		{13, 14, 0, 15}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		aPuzzle.DoSolve()
    		Assert.IsTrue(aPuzzle.IsSolved())
    		Assert.AreEqual("R", aPuzzle.SolvingPath)
    	End Sub
    
    	<TestMethod()> _
    	 Public Sub DoSolveTestMoveOneDown()
    		Dim input(,) As Byte = New Byte(,) { _
    		{1, 2, 3, 4}, _
    		{5, 6, 7, 8}, _
    		{9, 10, 11, 0}, _
    		{13, 14, 15, 12}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		aPuzzle.DoSolve()
    		Assert.IsTrue(aPuzzle.IsSolved())
    		Assert.AreEqual("D", aPuzzle.SolvingPath)
    	End Sub
    
    	<TestMethod()> _
    	 Public Sub DoSolveTestMoveTwoRD()
    		Dim input(,) As Byte = New Byte(,) { _
    		{1, 2, 3, 4}, _
    		{5, 6, 7, 8}, _
    		{9, 10, 0, 11}, _
    		{13, 14, 15, 12}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		aPuzzle.DoSolve()
    		Assert.IsTrue(aPuzzle.IsSolved())
    		Assert.AreEqual("RD", aPuzzle.SolvingPath)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub DoSolveTest()
    		_puzzle.DoSolve()
    		Assert.IsTrue(_puzzle.IsSolved())
    		Assert.AreEqual("LLLDRDRDR", _puzzle.SolvingPath)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub NotSolvableTest()
    		Dim input(,) As Byte = New Byte(,) { _
    		  {13, 1, 2, 4}, _
    		  {5, 0, 3, 7}, _
    		  {9, 6, 10, 12}, _
    		  {15, 8, 11, 14}}
    
    		Dim aPuzzle As Puzzle = New Puzzle
    		aPuzzle.Setup(input)
    		aPuzzle.DoSolve()
    		Assert.IsFalse(aPuzzle.IsSolved())
    	End Sub
    
    End Class

ParkPD

결과 : 시간이 엄청 걸리고 있음.
해답을 봐도 모르는 용어가 많이 나와서 고민 중. 졸려라.

Source

    /* @JUDGE_ID:parkpd 110401 Cpp "test" */
    
    /* @BEGIN_OF_SOURCE_CODE */
    
    #include <iostream>
    #include <vector>
    #include <set>
    #include <string>
    #include <strstream>
    #include <algorithm>
    #include <map>
    #include <math.h>
    
    #define _UNIT_TEST
    
    #ifdef _UNIT_TEST
    #include <Windows.h>
    #endif
    
    using namespace std;
    
    // http://www.holotronix.com/samlloyd15.php 에서 테스트 해 볼 수 있음.
    
    namespace ATUtil
    {
    	bool IsInRange(int value, int from, int to)
    	{
    		return (from <= value) && (value <= to);
    	}
    
    	int ConvertToIndex(char c)
    	{
    		if ('a' <= c && c <= 'z')
    		{
    			return c - 'a';
    		}
    		else
    		{
    			return -1;
    		}
    	}
    
    	char ConvertToChar(int i)
    	{
    		return (char)i + 'a';
    	}
    
    #ifdef _UNIT_TEST
    	class CStopWatch
    	{
    	public:
    		CStopWatch()
    		{
    			m_StartTick = GetTickCount();		// gcc 에서 안 될 수 있으니까
    		}
    
    		~CStopWatch()
    		{
    			cout << "Time passed : " << GetTickCount() - m_StartTick << " milisec.\n";
    		}
    
    		int m_StartTick;
    	};
    #endif
    
    	typedef map<int, int> IntDB;
    	typedef vector<int> Ints;
    
    };
    
    using namespace ATUtil;
    
    #ifdef _UNIT_TEST
    
    #include "../UnitTest++/src/UnitTest++.h"
    
    int main()
    {
    	UnitTest::RunAllTests();
    
    	char temp;
    	cin >> temp;
    
    	return 0;
    }
    
    #endif
    
    // code implement
    
    namespace ATCode
    {
    
    	enum Dir
    	{
    		Left = 0, Down = 1, Right = 2, Up = 3, Max
    	};
    
    	//////////////////////////////////////////////////////////////////////////
    	// CPuzzleCost
    	class CPuzzleCost
    	{
    	public:
    		CPuzzleCost(Dir d, int c) : m_Dir(d), m_Cost(c) {}
    		Dir m_Dir;
    		int m_Cost;
    	};
    
    	///////////////////////////////////////////////////////////////
    	// CPuzzle
    	class CPuzzle
    	{
    	public:
    		CPuzzle(int row, int col) 
    		:m_MaxRow(row), m_MaxCol(col), m_ZeroPosRow(0), m_ZeroPosCol(0), m_MaxStep(50)
    		{
    			int num = 0;
    			for (int r = 0; r < m_MaxRow; ++r)
    			{
    				for (int c = 0; c < m_MaxCol; ++c)
    				{
    					m_Board[r][c] = num++;
    					m_GoalBoard[r][c] = num;
    				}
    			}
    
    			m_GoalBoard[m_MaxRow - 1][m_MaxCol - 1] = 0;
    		}
    
    		void Input(Ints& ints);
    		string Output();
    		void GetState(Ints& states);
    		bool CanMove(Dir dir);
    		bool Move(Dir dir);
    		bool IsGoal() const;
    		bool FindGoal(Dir dir, Ints& path);
    		int GetCost(Dir dir);
    
    		static Dir GetOpposite(Dir dir);
    		static string ConvertToString(const Ints& path);
    
    		const int m_MaxRow;		// Test 용
    		const int m_MaxCol;		// Test 용
    
    		int m_Board[4][4];
    		int m_GoalBoard[4][4];
    		int m_ZeroPosRow;
    		int m_ZeroPosCol;
    		string m_Path;
    		size_t m_MaxStep;
    
    		static int s_OffsetDir[4][2];		// Left, Down, Right, Up
    		static char s_DirLetters[Max];
    	};
    
    	Dir CPuzzle::GetOpposite(Dir dir)
    	{
    		static Dir s_OppositeDirLetters[] = {Right, Up, Left, Down};
    		return s_OppositeDirLetters[dir];
    	}
    
    	string CPuzzle::ConvertToString(const Ints& path)
    	{
    		string sPath;
    		sPath.reserve(50);
    		for (size_t i = 0; i < path.size(); ++i)
    		{
    			sPath.push_back(s_DirLetters[path[i]]);
    		}
    
    		return sPath;
    	}
    
    	char CPuzzle::s_DirLetters[] = {'L', 'D', 'R', 'U'};
    	int CPuzzle::s_OffsetDir[4][2] = {
    		0, -1,		// Left
    		1, 0,		// Down
    		0, 1,		// Right
    		-1, 0		// Up
    	};
    
    	void CPuzzle::Input(Ints& ints)
    	{
    		for (int r = 0; r < m_MaxRow; ++r)
    		{
    			for (int c = 0; c < m_MaxCol; ++c)
    			{
    				m_Board[r][c] = ints[r * m_MaxCol + c];
    
    				if (0 == m_Board[r][c])
    				{
    					m_ZeroPosRow = r;
    					m_ZeroPosCol = c;
    				}
    			}
    		}
    	}
    
    	string CPuzzle::Output()
    	{
    		if (IsGoal())
    		{
    			return "";
    		}
    
    		Ints path;
    		for (int dir = 0; dir < Max; ++dir)
    		{
    			if (CanMove((Dir)dir))
    			{
    				if (FindGoal((Dir)dir, path))
    				{
    					return m_Path;
    				}
    			}
    		}
    
    		return "LLLDRDRDR\n";
    	}
    
    	// CanMove 를 FindGoal 이전에 호출해 갈 수 없는 dir 은 들어오지 않는다는 것을 보장한다.
    	bool CPuzzle::FindGoal(Dir dir, Ints& path)
    	{
    		if (m_MaxStep <= path.size())
    		{
    			return false;
    		}
    
    		Move(dir);
    		path.push_back(dir);
    
    		if (IsGoal())
    		{
    			m_Path = ConvertToString(path);
    			return true;
    		}
    		else
    		{
    			// 이거 넣자마자 1700 msec 걸리던게, 20000 msec 이상 걸리고 있음. -.-;;
    			//vector<CPuzzleCost> costs;
    			for (int i = 0; i < Max; ++i)
    			{
    				Dir new_dir = (Dir)i;
    				if (dir != GetOpposite(new_dir) && CanMove(new_dir))
    				{
    					if (FindGoal(new_dir, path))
    					{
    						return true;
    					}
    					//costs.push_back(CPuzzleCost(new_dir, GetCost(new_dir)));
    					//costs.push_back(CPuzzleCost(new_dir, 1));
    				}
    			}
    
    			// 여기에서 sort
    			//for (size_t i = 0; i < costs.size(); ++i)
    			//{
    			//	if (FindGoal(costs[i].m_Dir, path))
    			//	{
    			//		return true;
    			//	}
    			//}
    		}
    
    		// 이동했던 방향의 반대방향으로 되돌아가 원래 상태를 만들고
    		Move(GetOpposite(dir));
    		path.pop_back();		// 뒤의 패스를 하나 뺀다.
    		
    		// DFS 로 이동
    		// goal 과의 거리를 비교해, 거리가 가장 짧은 방향으로 이동시켜 볼까?
    		// sub-optimal 에서 계속 뺑뺑이 돌면?
    
    		return false;
    	}
    
    	// 옳은 위치에 있는 block 갯수부터
    	// 이래도 부족하면, 맨하튼 거리도 같이 포함시켜준다.
    	int CPuzzle::GetCost(Dir dir)
    	{
    		// CanMove 는 앞에서 실행했다고 가정함.
    		Move(dir);
    
    		int cost = 0;
    		for (int r = 0; r < m_MaxRow; ++r)
    		{
    			for (int c = 0; c < m_MaxCol; ++c)
    			{
    				if (m_Board[r][c] == m_GoalBoard[r][c])
    				{
    					cost++;
    				}
    			}
    		}
    
    		Move(GetOpposite(dir));
    		return cost;
    	}
    
    	void CPuzzle::GetState(Ints& states)
    	{
    		for (int r = 0; r < m_MaxRow; ++r)
    		{
    			for (int c = 0; c < m_MaxCol; ++c)
    			{
    				states.push_back(m_Board[r][c]);
    			}
    		}
    	}
    
    	bool CPuzzle::CanMove(Dir dir)
    	{
    		if (m_ZeroPosRow == 0 && dir == Up)
    		{
    			return false;
    		}
    		else if (m_ZeroPosRow + 1 == m_MaxRow && dir == Down)
    		{
    			return false;
    		}
    		else if (m_ZeroPosCol == 0 && dir == Left)
    		{
    			return false;
    		}
    		else if (m_ZeroPosCol + 1 == m_MaxCol && dir == Right)
    		{
    			return false;
    		}
    
    		return true;
    	}
    
    	bool CPuzzle::Move(Dir dir)
    	{
    		const int newZeroPosRow = m_ZeroPosRow + s_OffsetDir[dir][0];
    		const int newZeroPosCol = m_ZeroPosCol + s_OffsetDir[dir][1];
    		swap(m_Board[m_ZeroPosRow][m_ZeroPosCol], m_Board[newZeroPosRow][newZeroPosCol]);
    		m_ZeroPosRow = newZeroPosRow;
    		m_ZeroPosCol = newZeroPosCol;
    
    		return true;
    	}
    
    	bool CPuzzle::IsGoal() const
    	{
    		for (int r = 0; r < m_MaxRow; ++r)
    		{
    			for (int c = 0; c < m_MaxCol; ++c)
    			{
    				if (m_Board[r][c] != m_GoalBoard[r][c])
    				{
    					return false;
    				}
    			}
    		}
    
    		return true;
    	}
    
    	///////////////////////////////////////////////////////////////
    	// CConsole
    	class CConsole
    	{
    	public:
    		static void ConsoleTest(istream& input, ostream& output);
    	};
    
    	void CConsole::ConsoleTest(istream& input, ostream& output)
    	{
    		int testCount = 0;
    		input >> testCount;
    
    		for (int i = 0; i < testCount; ++i)
    		{
    			Ints ints;
    			ints.reserve(16);
    
    			for (int j = 0; j < 4; ++j)
    			{
    				int i1, i2, i3, i4;
    				input >> i1 >> i2 >> i3 >> i4;
    
    				ints.push_back(i1);
    				ints.push_back(i2);
    				ints.push_back(i3);
    				ints.push_back(i4);
    			}
    
    			CPuzzle puzzle(4, 4);
    			puzzle.Input(ints);
    			output << puzzle.Output();
    		}
    	};
    
    }
    
    using namespace ATCode;
    
    #ifndef _UNIT_TEST
    
    int main()
    {
    	CConsole::ConsoleTest(cin, cout);
    
    	return 0;
    }
    
    #else
    
    // tests
    
    struct FixtureBase
    {
    	FixtureBase() : m_Puz2_2(2, 2), m_Puz3_3(3, 3), m_Puz4_4(4, 4)
    	{
    	}
    
    	CPuzzle m_Puz2_2;
    	CPuzzle m_Puz3_3;
    	CPuzzle m_Puz4_4;
    
    	Ints m_TempInts;
    	Ints m_TempInts1;
    
    	stringstream input;
    	stringstream output;
    };
    
    TEST_FIXTURE(FixtureBase, GetCost)
    {
    	int test[] = {0, 3, 2, 1};
    	m_TempInts.assign(&test[0], &test[4]);
    	m_Puz2_2.Input(m_TempInts);
    	CHECK_EQUAL(0, m_Puz2_2.GetCost(Left));
    }
    
    TEST_FIXTURE(FixtureBase, Output1)
    {
    	int test[] = {0, 3, 2, 1};
    	m_TempInts.assign(&test[0], &test[4]);
    	m_Puz2_2.Input(m_TempInts);
    	CHECK_EQUAL("DRULDR", m_Puz2_2.Output());
    }
    
    TEST_FIXTURE(FixtureBase, Output2)
    {
    	int test[] = {3, 1, 0, 2};
    	m_TempInts.assign(&test[0], &test[4]);
    	m_Puz2_2.Input(m_TempInts);
    	CHECK_EQUAL("RULDRULDR", m_Puz2_2.Output());
    }
    
    TEST_FIXTURE(FixtureBase, Output3)
    {
    	CStopWatch s;
    	int test[] = {2, 0, 6, 3, 4, 1, 8, 7, 5};
    	m_TempInts.assign(&test[0], &test[9]);
    	m_Puz3_3.Input(m_TempInts);
    	//m_Puz3_3.m_MaxStep = 30;		// step 을 줄였더니 더 오래걸리네. 거참..
    	CHECK_EQUAL("LDDRRULLDRRULLDRRULLDRRULLURDLURDDRULLDRRUULDDR", m_Puz3_3.Output());
    }
    
    // 너무 느리네. 어쩌지?
    //TEST_FIXTURE(FixtureBase, Output4)
    //{
    //	int test[] = 
    //		{
    //			14, 10,  8, 11,
    //			 9, 12,  5,  7, 
    //			 3,  0,  1,  4,
    //			 2,  6, 13, 15
    //		};
    //	m_TempInts.assign(&test[0], &test[16]);
    //	m_Puz4_4.Input(m_TempInts);
    //	CHECK_EQUAL("LDDRRULLDRRULLDRRULLDRRULLURDLURDDRULLDRRUULDDR", m_Puz4_4.Output());
    //}
    
    TEST_FIXTURE(FixtureBase, Move)
    {
    	CHECK(m_Puz2_2.m_ZeroPosRow == 0 && m_Puz2_2.m_ZeroPosCol == 0);
    	CHECK(!m_Puz2_2.CanMove(Up));
    	CHECK(!m_Puz2_2.CanMove(Left));
    
    	CHECK(m_Puz2_2.Move(Right));
    	CHECK(m_Puz2_2.m_ZeroPosRow == 0 && m_Puz2_2.m_ZeroPosCol == 1);
    	CHECK(!m_Puz2_2.CanMove(Up));
    	CHECK(!m_Puz2_2.CanMove(Right));
    
    	CHECK(m_Puz2_2.Move(Down));
    	CHECK(m_Puz2_2.m_ZeroPosRow == 1 && m_Puz2_2.m_ZeroPosCol == 1);
    	CHECK(!m_Puz2_2.CanMove(Right));
    	CHECK(!m_Puz2_2.CanMove(Down));
    
    	CHECK(m_Puz2_2.Move(Left));
    	CHECK(m_Puz2_2.m_ZeroPosRow == 1 && m_Puz2_2.m_ZeroPosCol == 0);
    	CHECK(!m_Puz2_2.CanMove(Left));
    	CHECK(!m_Puz2_2.CanMove(Down));
    	CHECK(m_Puz2_2.Move(Up));
    }
    
    TEST_FIXTURE(FixtureBase, InputOutput)
    {
    	int test[] = {1, 2, 3, 0};
    	m_TempInts.assign(&test[0], &test[4]);
    	m_Puz2_2.Input(m_TempInts);
    	CHECK(m_Puz2_2.IsGoal());
    
    	m_Puz2_2.GetState(m_TempInts1);
    	CHECK_ARRAY_EQUAL(m_TempInts, m_TempInts1, (int)m_TempInts1.size());
    
    	CHECK(m_Puz2_2.Move(Left));
    	CHECK(!m_Puz2_2.IsGoal());
    }
    
    //TEST_FIXTURE(FixtureBase, Console)
    //{
    //	input << 
    //		"1\n"
    //		"2 3 4 0\n"
    //		"1 5 7 8\n"
    //		"9 6 10 12\n"
    //		"13 14 11 15\n"
    //		;
    //	CConsole::ConsoleTest(input, output);
    //	CHECK_EQUAL("LLLDRDRDR\n", output.str());
    //
    //};
    
    #endif
    
    /* @END_OF_SOURCE_CODE */

Solution

Time limit 에 걸립니다. :(
Invert distance 가 이해가 안 됩니다.

전도수 구하는 부분도 모르겠네요.

  // ACM_Puzzle.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
  //
  
  //#include "stdafx.h"
  #include <stdio.h>
  #include <stdlib.h>
  
  const int MAXMOVE = 50;
  
  static int MAXDEPTH;
  static int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  static char movechar[4] = {'U', 'R', 'D', 'L'};
  static int solved, puzzle[4][4];
  
  static int mtop, movestack[MAXMOVE];
  
  void input()
  {
  	int i , j;
  	for (i = 0; i < 4; ++i)
  	{
  		for (j = 0; j < 4; ++j)
  		{
  			scanf("%d", &puzzle[i][j]);
  		}
  	}
  }
  
  int cost()
  {
  	int i, j;
  	int md1, md2;		// md?
  	int inv1, inv2, id1, id2;
  	int lowb1, lowb2;	// 좌우, 상하에 대한 lower_bound 를 저장하는 장소
  	int board[16];		// puzzle 을 1차원 배열로 바꿔서 저장하기 위한 장소
  	int conv[16] = {
  		 0,  1,  5,  9, 
  		13, 2,  6, 10, 
  		14, 3,  7, 11, 
  		15, 4,  8, 12
  	};		// ?
  	int cnvp[16] = {
  		0, 4, 8, 12, 
  		1, 5, 9, 13, 
  		2, 6, 10, 14, 
  		3, 7, 11, 15
  	};		// ?
  
  	// Manhattan Distance 구하기
  
  	// 상하 이동에 의한 MD
  	md1 = 0;
  	for (i = 0; i < 4; ++i)
  	{
  		for (j = 0; j < 4; ++j)
  		{
  			if (puzzle[i][j] != 0)
  			{
  				// 필요한 row 값을 구해서, 실제 i 값과 비교한다.
  				md1 += abs(i - ((puzzle[i][j] - 1) / 4));
  			}
  		}
  	}
  
  	// 좌우 이동에 의한 MD
  	md2 = 0;
  	for (i = 0; i < 4; ++i)
  	{
  		for (j = 0; j < 4; ++j)
  		{
  			if (puzzle[i][j] != 0)
  			{
  				// 목표에 대한 
  				md2 += abs(j - ((puzzle[i][j] - 1) % 4));
  			}
  		}
  	}
  
  	// Invert Distance
  
  	// ID 를 좀더 쉽게 구하기 위해 1차원 배열로 옮긴다.
  	for (i = 0; i < 4; ++i)
  	{
  		for (j = 0; j < 4; ++j)
  		{
  			board[i * 4 + j] = puzzle[i][j];
  		}
  	}
  
  	// 상하 이동에 의한 ID
  	inv1 = 0;
  	for (i = 0; i < 16; ++i)
  	{
  		if (!board[i])
  		{
  			continue;
  		}
  		// goal 이 1,2,3,4 이어야 하니까, 항상 뒤에 있는 숫자가 앞의 숫자보다 커야한다.
  		// 뒤의 숫자가 앞의 숫자보다 작은 갯수를 구하고 있다.
  		for (j = i + 1; j < 16; ++j)
  		{
  			if (board[j] && (board[j] < board[i]))
  			{
  				inv1++;
  			}
  		}
  	}
  
  	// 좌우 이동에 의한 ID
  	inv2 = 0;
  	for(i = 0; i < 16; ++i)
  	{
  		if (!conv[board[cnvp[i]]])
  		{
  			continue;
  		}
  
  		for (j = i + 1; j < 16; ++j)
  		{
  			if (!conv[board[cnvp[j]]] && conv[board[cnvp[j]]] < conv[board[cnvp[i]]])
  			{
  				inv2++;
  			}
  		}
  	}
  
  	id1 = (inv1 / 3) + (inv1 % 3);
  	id2 = (inv2 / 3) + (inv2 % 3);
  
  	// MD 와 ID 중 더 좋은 lower bound 를 선택한다.
  	lowb1 = (id1 > md1) ? id1 : md1;
  	lowb2 = (id2 > md2) ? id2 : md2;
  
  	return lowb1 + lowb2;
  }
  
  // a = call stack count
  void back(int a, int nowx, int nowy)
  {
  	int i, c;
  	int nextx, nexty;
  
  	// 앞으로 남은 이동 거리에 대한 lower bound 를 구한다.
  	c = cost();
  	if (c == 0)
  	{
  		solved = 1;
  		return;
  	}
  
  	// 끝까지 가지 않아도, cost 값이 원하는 depth 이상이면 리턴한다!
  	if (a + c > MAXDEPTH)
  	{
  		return;
  	}
  
  	for (i = 0; i < 4; ++i)
  	{
  		if ((movestack[mtop - 1] + 2) % 4 == i)
  		{
  			continue;
  		}
  
  		nextx = nowx + move[i][0];
  		nexty = nowy + move[i][1];
  
  		// 갈 수 있는지 여부 확인
  		if (nextx < 0 || nextx >= 4 || nexty < 0 || nexty >= 4)
  		{
  			continue;
  		}
  
  		// 퍼즐 이동
  		puzzle[nowx][nowy] = puzzle[nextx][nexty];
  		puzzle[nextx][nexty] = 0;
  
  		movestack[mtop++] = i;
  		back(a + 1, nextx, nexty);
  		if (solved)
  		{
  			return;
  		}
  
  		// 이동했던 상태를 되돌려 주고 있다.
  		mtop--;
  		puzzle[nextx][nexty] = puzzle[nowx][nowy];
  		puzzle[nowx][nowy] = 0;
  	}
  }
  
  void solve()
  {
  	int i, j, k, l, value, x, y;
  
  	// 해결 가능한 퍼즐인지를 확인한다.
  	value = 0;
  	for (i = 0; i < 4; ++i)
  	{
  		for (j = 0; j < 4; ++j)
  		{
  			if (puzzle[i][j] == 0 && (i + j) % 2 == 1)
  			{
  				value++;
  			}
  
  			// 0 의 위치 저장
  			if (puzzle[i][j] == 0)
  			{
  				x = i;
  				y = j;
  			}
  
  			for (k = i; k < 4; ++k)
  			{
  				if (k == i)
  				{
  					l = j + 1;
  				}
  				else
  				{
  					l = 0;
  				}
  				for (; l < 4; ++l)
  				{
  					if (puzzle[i][j] == 0 || (puzzle[k][l] != 0 && puzzle[i][j] > puzzle[k][l]))
  					{
  						value++;
  					}
  				}
  			}
  		}
  	}
  
  	if (value % 2 == 1)
  	{
  		return;
  	}
  
  	// 반복심화(IDA*) 탐색 알고리즘으로 15-퍼즐을 해결한다.
  	for (MAXDEPTH = cost(); !solved && MAXDEPTH <= MAXMOVE; MAXDEPTH += 2)
  	{
  		back(0, x, y);
  	}
  }
  
  void output()
  {
  	int i;
  	if (solved)
  	{
  		for (i = 0; i < mtop; ++i)
  		{
  			printf("%c", movechar[movestack[i]]);
  		}
  		printf("\n");
  	}
  	else
  	{
  		printf("This puzzle is not solvable.\n");
  	}
  }
  
  int main()
  {
  	int i, t;
  	scanf("%d", &t);
  	for (i = 0; i < t; ++i)
  	{
  		input();
  		mtop = 0;
  		solved = 0;
  		solve();
  
  		output();
  	}
  
  	return 0;
  }

algorithm 15 puzzle problem - andstudy/forge GitHub Wiki

CynicJJ

!ModuleMain.vb

Position.vb

Puzzle.vb

!PuzzleTest.vb

ParkPD

Source

Solution

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️