V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zhaogaz
V2EX  ›  算法

真实算法 优化 求助

  •  
  •   zhaogaz · 2020-09-21 01:12:50 +08:00 · 1559 次点击
    这是一个创建于 1284 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    第 1 条附言  ·  2020-09-23 21:21:58 +08:00
    代码放着跑了 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

    ```
    5 条回复    2020-09-22 13:11:32 +08:00
    Raven316
        1
    Raven316  
       2020-09-21 07:55:11 +08:00
    帮顶
    zhaogaz
        2
    zhaogaz  
    OP
       2020-09-21 13:18:49 +08:00
    自挽,真的没有人能救救老哥?
    nextFault
        3
    nextFault  
       2020-09-21 15:04:14 +08:00
    变种八皇后,正常回溯复杂度常量级慢不了吧?
    Hyouka
        4
    Hyouka  
       2020-09-21 15:58:41 +08:00
    很多类型这样的 puzzle 拼图,是有一两块是打斜放的;
    不过你的解开了...应该不是这类;
    zhaogaz
        5
    zhaogaz  
    OP
       2020-09-22 13:11:32 +08:00
    @nextFault 上面的代码已经跑了超过 24h 了 还没有出结果
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5290 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 09:32 · PVG 17:32 · LAX 02:32 · JFK 05:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.