关于8皇后问题,这里为了简便就是4个皇后在排列,问题出在我每次把程序里的Net数组加到net set里面以后,就发生了改变,这就导致后续的重复方式被加入net set
(HashSet类型)里面,求问为什么会出现加入之后数组会发生改变?
下面是代码:
package chessloc;
import java.util.ArrayList;
import java.util.HashSet;
//net_set???????
class point {
int x;
int y;
point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Chessloc {
static int n = 4;
//net_set is for storing all of the possible way.
static HashSet<int[][]> net_set = new HashSet();
//remove is for recording the impossible place after one queen place.
static ArrayList<point> remove[][] = new ArrayList[n][n];
//Net is for recording the possible way for placing queen, each time finish it will be added into net_set.
static int[][] Net = new int[n][n];
public static void main(String[] args) {
for (int p = 0; p < n; p++) {
for (int m = 0; m < n; m++) {
//here is for initialize reomve[][].
for (int p_t = 0; p_t < n; p_t++) {
for (int m_t = 0; m_t < n; m_t++) {
remove[p_t][m_t] = new ArrayList();
}
}
Net = re();
backtrace(p, m);
}
}
System.out.println("final:");
print();
System.out.print(net_set.size());
}
static void backtrace(int index_x, int index_y) {
Net[index_x][index_y] = 6;
for (int i = 0; i < n; i++) {
for (int m = 0; m < n; m++) {
if (Net[i][m] == 0 && (Math.abs(index_x - i) == Math.abs(index_y - m) || i == index_x || m == index_y)) {
point p = new point(i, m);
remove[index_x][index_y].add(p);
Net[i][m] = 1;
}
}
}
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
//a second point.
if (Net[x][y] == 0) {
backtrace(x, y);
Net[x][y] = 0;
remove(remove[x][y]);
remove[x][y].clear();
}
}
}
if (isDone()) {
System.out.println("correct case_Net:");
Print();
net_set.add(Net);
System.out.println("After add in__Net:");
Print();
System.out.println("add inside_net_set:");
print();
}
}
//judge whether get the correct way.
public static boolean isDone() {
int x = 0;
for (int p = 0; p < n; p++) {
for (int m = 0; m < n; m++) {
x = (Net[p][m] == 6) ? x + 1 : x;
if (Net[p][m] == 0) {
return false;
}
}
}
return (x == n);
}
//here is for making the impossible place(under a way to place queen) become possible.
public static void remove(ArrayList<point> x) {
for (point temp : x) {
if (Net[temp.x][temp.y] == 1) {
Net[temp.x][temp.y] = 0;
}
}
}
public static int[][] re() {
int[][] N = new int[n][n];
for (int p = 0; p < n; p++) {
for (int m = 0; m < n; m++) {
N[p][m] = 0;
}
}
return N;
}
//here is for printing Net array.
public static void Print() {
for (int p = 0; p < n; p++) {
for (int m = 0; m < n; m++) {
System.out.print(Net[p][m] + " ");
}
System.out.println("");
}
}
//here is for printing net_set.
public static void print() {
for (int[][] temp : net_set) {
for (int p = 0; p < n; p++) {
for (int m = 0; m < n; m++) {
System.out.print(temp[p][m] + " ");
}
System.out.println("");
}
System.out.println();
}
}
}
下面运行截图:
出现第一种case的时候运行运行正常
但是出现第二种case后,加入net set之后一种case就发生了改变。。。。。。、
求问如何修改?
对了,这个方法不是很好,效率很低,但是只是想修复它。。
谢谢了。