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

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