真实算法优化求助

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 的时候，直接输出对应的图象

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

真实算法 优化 求助

真实算法优化求助