public final class puzzle15{
int maxLevel = 30; //高さ制限
class StackDataDef {
int Level = 0;
String Log = "";
String priMove;
int[][] ValList = {{ 1, 2, 3, 4,}, //1
{ 0, 5, 6, 7,}, //2
{ 9,10,11, 8,}, //3
{13,14,15,12,}}; //4;
}
//スタック
class StackClass {
int stackP;
StackDataDef stackData[];
StackClass(){
stackP = 0;
stackData = new StackDataDef[99999];
}
private void push(StackDataDef pushData,String addLog){
stackData[stackP] = new StackDataDef();
stackData[stackP].Level = pushData.Level+1;
stackData[stackP].Log = pushData.Log+addLog;
stackData[stackP].priMove = addLog;
for(int Y=0;Y<=3;Y++)
for(int X=0;X<=3;X++)
stackData[stackP].ValList[X][Y] = pushData.ValList[X][Y];
stackP++;
}
private StackDataDef pop(){
return stackData[--stackP];
}
boolean isEmpty(){ return stackP == 0; }
}
public static void main(String[] args) {
puzzle15 mi = new puzzle15();
mi.main();
}
void main() {
StackClass st = new StackClass();
StackDataDef willPush = new StackDataDef();
int X=0; int Y=0;
while(willPush.ValList[X][Y] !=0){
if (++Y == 4){
X++;Y=0;
}
}
int saveVal;
//左の数字を移動
if (X!=0){
saveVal = willPush.ValList[X-1][Y];
willPush.ValList[X-1][Y] = 0;
willPush.ValList[X][Y] = saveVal;
st.push(willPush,"→");
willPush.ValList[X-1][Y] = saveVal;
willPush.ValList[X][Y] = 0;
}
//右の数字を移動
if (X!=3){
saveVal = willPush.ValList[X+1][Y];
willPush.ValList[X+1][Y] = 0;
willPush.ValList[X][Y] = saveVal;
st.push(willPush,"←");
willPush.ValList[X+1][Y] = saveVal;
willPush.ValList[X][Y] = 0;
}
//上の数字を移動
if (Y!=0){
saveVal = willPush.ValList[X][Y-1];
willPush.ValList[X][Y-1] = 0;
willPush.ValList[X][Y] = saveVal;
st.push(willPush,"↓");
willPush.ValList[X][Y-1] = saveVal;
willPush.ValList[X][Y] = 0;
}
//下の数字を移動
if (Y!=3){
saveVal = willPush.ValList[X][Y+1];
willPush.ValList[X][Y+1] = 0;
willPush.ValList[X][Y] = saveVal;
st.push(willPush,"↑");
willPush.ValList[X][Y+1] = saveVal;
willPush.ValList[X][Y] = 0;
}
int ansCnt=0;
while (st.isEmpty() == false){
StackDataDef priInfo = st.pop();
boolean isOK = true;
int mustNumber=0;
//合格経路なら表示
for (X=0;X<=3;X++)
for (Y=0;Y<=3;Y++){
++mustNumber;
if (mustNumber!=16 && priInfo.ValList[X][Y] != mustNumber) isOK = false;
}
if (isOK){
System.out.println("解" + Integer.toString(++ansCnt));
priInfo.Log = priInfo.Log.replaceAll("←","上");
priInfo.Log = priInfo.Log.replaceAll("→","下");
priInfo.Log = priInfo.Log.replaceAll("↑","左");
priInfo.Log = priInfo.Log.replaceAll("↓","右");
System.out.println(priInfo.Log);
if (maxLevel > priInfo.Level) maxLevel = priInfo.Level; //高さ制限値を更新
}
if (priInfo.Level >=maxLevel) continue; //高さ制限
X=Y=0;
while(priInfo.ValList[X][Y] !=0){
if (++Y == 4){
X++;Y=0;
}
}
//左の数字を移動
if (X!=0 && !priInfo.priMove.equals("←")){
saveVal = priInfo.ValList[X-1][Y];
priInfo.ValList[X-1][Y] = 0;
priInfo.ValList[X][Y] = saveVal;
st.push(priInfo,"→");
priInfo.ValList[X-1][Y] = saveVal;
priInfo.ValList[X][Y] = 0;
}
//右の数字を移動
if (X!=3 && !priInfo.priMove.equals("→")){
saveVal = priInfo.ValList[X+1][Y];
priInfo.ValList[X+1][Y] = 0;
priInfo.ValList[X][Y] = saveVal;
st.push(priInfo,"←");
priInfo.ValList[X+1][Y] = saveVal;
priInfo.ValList[X][Y] = 0;
}
//上の数字を移動
if (Y!=0 && !priInfo.priMove.equals("↑")){
saveVal = priInfo.ValList[X][Y-1];
priInfo.ValList[X][Y-1] = 0;
priInfo.ValList[X][Y] = saveVal;
st.push(priInfo,"↓");
priInfo.ValList[X][Y-1] = saveVal;
priInfo.ValList[X][Y] = 0;
}
//下の数字を移動
if (Y!=3 && !priInfo.priMove.equals("↓")){
saveVal = priInfo.ValList[X][Y+1];
priInfo.ValList[X][Y+1] = 0;
priInfo.ValList[X][Y] = saveVal;
st.push(priInfo,"↑");
priInfo.ValList[X][Y+1] = saveVal;
priInfo.ValList[X][Y] = 0;
}
}
}
}