真实算法 优化 求助

[zhaogaz]

https://item.taobao.com/item.htm?id=609807807418

这个拼图摆放方式如何用算法实现？

我真的买了，确实拼不出来。不是广告。

我尝试用写了个算法 试了下，能跑，很慢。希望大哥们能教教如何优化

package com.aliware.tianchi;

public class puzzle11j {
    public static int[][][] j_Offset = {
        {{0, 4}, {0, 3}, {0, 2}, {0, 1}, {0, 0}, {1, 0}, {2, 0}, {2, 1}},
        {{4, 2}, {3, 2}, {2, 2}, {1, 2}, {0, 2}, {0, 1}, {0, 0}, {1, 0}},
        {{2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {1, 4}, {0, 4}, {0, 3}},
        {{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {4, 1}, {4, 2}, {3, 2}},

        {{0, 1}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}},
        {{3, 0}, {4, 0}, {4, 1}, {4, 2}, {3, 2}, {2, 2}, {1, 2}, {0, 2}},
        {{2, 3}, {2, 4}, {1, 4}, {0, 4}, {0, 3}, {0, 2}, {0, 1}, {0, 0}},
        {{1, 2}, {0, 2}, {0, 1}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}}
    };
    public static int boardMaxLength = 10;
    public static void main(String[] args) {
        put(new int[boardMaxLength][boardMaxLength],0,0,11);
    }
//    public static int boardMaxLength = 6;
//    public static void main(String[] args) {
//        put(new int[boardMaxLength][boardMaxLength],0,0,4);
//    }

    public static boolean can_set(int[][] board, int x, int y, int offset_index) {
        for (final int[] offset : j_Offset[offset_index]) {
            int real_x_location = x + offset[0];
            int real_y_location = y + offset[1];
            //不出界
            if (real_x_location > boardMaxLength-1) return false;
            if (real_y_location > boardMaxLength-1) return false;
            //没重叠
            if (board[real_x_location][real_y_location] != 0) return false;
        }
        return true;
    }

    public static void put(int[][] board, int after_x,int after_y ,int left_j_num) {
        if (left_j_num == 0) {
            print_board(board);
            return;
        }
        if(after_x>(boardMaxLength-2) || after_y >(boardMaxLength-2)){
            return;
        }
        for (int x = after_x; x < boardMaxLength-2; x++) {
            for (int y = after_y; y < boardMaxLength-2; y++) {
                board = test_j(board, left_j_num, x, y);

            }
        }
        for (int x = 0; x < after_x; x++) {
            for (int y = after_y; y < boardMaxLength-2; y++) {
                board = test_j(board, left_j_num, x, y);
            }
        }
        for (int x = after_x; x < boardMaxLength-2; x++) {
            for (int y = 0; y < after_y; y++) {
                board = test_j(board, left_j_num, x, y);

            }
        }
    }

    private static int[][] test_j(int[][] board, final int left_j_num, final int x, final int y) {
        for (int j_index = 0; j_index < j_Offset.length; j_index++) {
            if (can_set(board, x, y, j_index)) {
                board = mark_board(board, x, y, j_index, left_j_num);
                put(board, x+1,y+1,left_j_num - 1);
                board = clean_board(board,x,y,j_index);
            }
        }
        return board;
    }

    public static int[][] mark_board(int[][] board, int x, int y, int offset_index, int left_j) {
        for (final int[] offset : j_Offset[offset_index]) {
            int real_x_location = x + offset[0];
            int real_y_location = y + offset[1];

            board[real_x_location][real_y_location] = left_j;
        }
        return board;
    }

    public static int[][] clean_board(int[][] board, int x, int y, int offset_index) {
        return mark_board(board, x, y, offset_index, 0);
    }

    public static void print_board(int[][] board) {
        for (int x = 0; x < boardMaxLength; x++) {
            for (int y = 0; y < boardMaxLength; y++) {
                System.err.print((char) (board[x][y]+64)+" ");
            }
            System.err.println("");
        }
        System.err.println("");
    }

}

把注释解开，即可测试，没毛病，就是慢。

算法逻辑是这样的：

• 把 j 的形状枚举出来，包含镜像，一共 8 个
• 一步一步试验，能不能放进去。
• j 的数量越来越少，0 的时候，直接输出对应的图象

可能算是广度优先算法，确实想不到其他的剪枝技巧

代码放着跑了 2 天多，终于跑出结果了,append 一下，其实不止这些，输出结果还有很多，但是都差不多。看来剪枝的方式也就是想办法去除重复数据可以考虑一下。其他的剪枝方式是明显有问题的都跳过一下。确实没啥好办法

```

K @ @ @ C C C C C G
K B B B B B E @ C G
K A A A @ B E C C G
K A K A B B E G @ G
K K K A E @ E G G G
J J J A E E E I I I
J @ J A @ D D I @ I
J F F F F F D H H I
J F D D D D D @ H I
J F F @ H H H H H I

K @ @ @ D D D D D G
K C C C C C B @ D G
K A A A @ C B D D G
K A K A C C B G @ G
K K K A B @ B G G G
J J J A B B B I I I
J @ J A @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

K @ @ @ D D D D D G
K C C C C C A @ D G
K B B B @ C A D D G
K B K B C C A G @ G
K K K B A @ A G G G
J J J B A A A I I I
J @ J B @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

K @ @ @ B B B B B G
K A A A A A D @ B G
K C C C @ A D B B G
K C K C A A D G @ G
K K K C D @ D G G G
J J J C D D D I I I
J @ J C @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

```

[Raven316]

帮顶

[zhaogaz]

自挽，真的没有人能救救老哥？

[nextFault]

变种八皇后，正常回溯复杂度常量级慢不了吧？

[Hyouka]

很多类型这样的 puzzle 拼图,是有一两块是打斜放的;
不过你的解开了...应该不是这类;

[zhaogaz]

@nextFault 上面的代码已经跑了超过 24h 了 还没有出结果