ngridgame.java

经典8数码问题扩展为N数码问题

import java.util.ArrayList;

public class NGridGame {
	public int N;

	public Nod[] nods;

	public Blank blank;

	public NGridGame(int n) {
		N = n;
		int f = N * N;
		nods = new Nod[f];
		for (int i = 0; i < f; i++) {
			nods[i] = new Nod(i, N);
		}
		blank = new Blank();
	}

	public NGridGame(NGridGame game) {
		this.N=game.N;
		this.nods=new Nod[N*N];
		for(int i=0;i<N*N;i++){
			nods[i]=new Nod(i,N);
			nods[i].x=game.nods[i].x;
			nods[i].y=game.nods[i].y;
		}
		blank=new Blank();
		blank.x=game.blank.x;
		blank.y=game.blank.y;
	}

	public int getNod(int x, int y) {
		boolean f = false;
		int i = 1;
		int r = 0;
		if (x < 0 || x >= N || y < 0 || y >= N)
			return 0;
		while (!f && i < nods.length) {
			if ((nods[i].x == x) && (nods[i].y == y)) {
				r = i;
				f = true;
			}
			i++;
		}
		return r;
	}

	public int getDNod(int d) {// 1 up 2 down 3 right 4 left
		int nod = 0;
		switch (d) {
		case 1:
			if (blank.x == 0)
				break;
			else {
				nod = getNod(blank.x - 1, blank.y);
				break;
			}
		case 2:
			if (blank.x == N - 1)
				break;
			else {
				nod = getNod(blank.x + 1, blank.y);
				break;
			}
		case 3:
			if (blank.y == N - 1)
				break;
			else {
				nod = getNod(blank.x, blank.y + 1);
				break;
			}
		case 4:
			if (blank.y == 0)
				break;
			else {
				nod = getNod(blank.x, blank.y - 1);
				break;
			}
		default:
			nod = 0;
		}
		return nod;
	}

	public boolean move(int i) {
		if (getDNod(i) != 0) {
			blank.exchange(nods[getDNod(i)]);
			return true;
		} else
			return false;
	}

	public boolean moveNod(int i) {
		boolean f = false;
		if (i == getNod(blank.x - 1, blank.y)) {
			move(1);
			return true;
		}
		if (i == getNod(blank.x + 1, blank.y)) {
			move(2);
			return true;
		}
		if (i == getNod(blank.x, blank.y + 1)) {
			move(3);
			return true;
		}
		if (i == getNod(blank.x, blank.y - 1)) {
			move(4);
			return true;
		}
		return f;
	}

	public void moveTo(int[] ds) {
		for (int i = 0; i < ds.length; i++)
			move(ds[i]);
	}

	public int[] moveBack() {
		ArrayList al = new ArrayList();
		boolean f = false;
		int i = 0;
		boolean[] ff = { false, false, false, false, false, false };
		int[] fn = { 0, 0, 0, 0, 0 };
		blank.setf(ff, N);
		do {
			for (int j = 1; j < 5; j++)
				if (ff[j]) {
					fn[j] = getDNod(j);
					ff[j] = nods[fn[j]].testD(blank.x, blank.y, N);
					if (ff[j])
						fn[j] = nods[fn[j]].getD(nods[fn[j]].x, nods[fn[j]].y,
								N);
					else
						fn[j] = 0;
				}
			int s = 0, max = 0;
			for (int j = 1; j < 5; j++)
				if (fn[j] > max) {
					max = fn[j];
					s = j;
				}
			if (max == 0)
				f = true;
			if (!f) {
				al.add(i++, Integer.valueOf(s));
				move(s);
			}
			blank.setf(ff, N);
			switch (s) {
			case 1:
				s = 2;
				break;
			case 2:
				s = 1;
				break;
			case 3:
				s = 4;
				break;
			case 4:
				s = 3;
				break;
			}
			ff[s] = false;
		} while (!f);
		int[] r = new int[al.size()];
		for (int j = 0; j < r.length; j++) {
			r[j] = ((Integer) al.get(j)).intValue();
		}
		return r;
	}

	public void display() {
		System.out.println();
		int n, i, j;
		String s;
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {

				n = getNod(i, j);
				if (n == 0) {
					if (blank.x == i && blank.y == j)
						s = "*";
					else
						return;

				} else
					s = String.valueOf(n);
				System.out.print(s + "\t");
			}
			System.out.println();
		}
	}

	public static void main(String[] ar) {
		NGridGame game = new NGridGame(5);
		int[] begin = { 3, 3, 3, 3, 2, 2, 2, 2, 4, 4, 4, 4, 1, 1, 1 };
		game.display();
		game.moveTo(begin);
		game.display();
		int[] back = game.moveBack();

		for (int i = 0; i < back.length; i++) {
			System.out.print(back[i] + "\t");
		}
	}
}