fork(23) download 
  1. import java.io.InputStreamReader;
  2. import java.util.ArrayDeque;
  3. import java.util.PriorityQueue;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6. import java.util.Stack;
  7.  
  8. class Solver{
  9.     private int N ; 
  10.     private int minMoves ;
  11.     public static int[] correctRow;
  12.     public static int[] correctCol;
  13.  
  14.     private class Node implements Comparable<Node>{
  15.         private Board board ; 
  16.         private int moves ; 
  17.         private Node prevNode ; 
  18.         public Node(Board board,int moves,Node prev){
  19.             this.board = board ; 
  20.             this.moves = moves ; 
  21.             this.prevNode = prev ; 
  22.         }
  23.         public int compareTo(Node that){
  24.             int thisPriority = this.moves+this.board.manhattan() ; 
  25.             int thatPriority = that.moves+that.board.manhattan() ; 
  26.             if(thisPriority<thatPriority){
  27.                 return -1 ; 
  28.             }else if(thisPriority>thatPriority){
  29.                 return 1 ; 
  30.             }else{
  31.                 return 0 ; 
  32.             }
  33.         }
  34.     }
  35.  
  36.     private Node lastNode ; 
  37.     private boolean solvable ; 
  38.  
  39.     public Solver(Board initial){
  40.         N = initial.dimension() ; 
  41.         PriorityQueue<Node> pq = new PriorityQueue<Node>() ; 
  42.         PriorityQueue<Node> pq2 = new PriorityQueue<Node>() ; 
  43.         pq.add(new Node(initial,0,null)) ; 
  44.         pq2.add(new Node(initial.twin(),0,null)) ; 
  45.         while(true){
  46.             Node removed = pq.poll();
  47.             Node removed2 = pq2.poll();
  48.             if(removed.board.isGoal()){
  49.                 minMoves = removed.moves ; 
  50.                 lastNode = removed ; 
  51.                 solvable = true ; 
  52.                 break ; 
  53.             }
  54.             if(removed2.board.isGoal()){
  55.                 minMoves = -1 ; 
  56.                 solvable = false ; 
  57.                 break ; 
  58.             }
  59.  
  60.             Iterable<Board> neighbors = removed.board.neighbors() ; 
  61.             Iterable<Board> neighbors2 = removed2.board.neighbors() ; 
  62.             for(Board board : neighbors){
  63.                 if(removed.prevNode != null && removed.prevNode.board.equals(board) ){
  64.                     continue ; 
  65.                 }
  66.                 pq.add(new Node(board,removed.moves+1,removed)) ; 
  67.             }
  68.             for(Board board : neighbors2){
  69.                 if(removed2.prevNode != null && removed2.prevNode.board.equals(board) ){
  70.                     continue ; 
  71.                 }
  72.                 pq2.add(new Node(board,removed2.moves+1,removed2)) ; 
  73.             }
  74.         }
  75.     }
  76.  
  77.     public boolean isSolvable(){
  78.         return solvable ; 
  79.     }
  80.  
  81.     public int moves(){
  82.         return minMoves ; 
  83.     }
  84.  
  85.     public Iterable<Board> solution(){
  86.         if(!isSolvable()){
  87.             return null ;
  88.         }
  89.         Stack<Board> stack = new Stack<Board>() ; 
  90.         Node node = lastNode ; 
  91.         while(true){
  92.             if(node == null) break ; 
  93.             Board board = node.board ; 
  94.             node = node.prevNode ; 
  95.             stack.push(board) ; 
  96.         }
  97.         return stack ; 
  98.     }
  99.  
  100.     static void initCorrectRowsCols(int N){
  101.     	correctRow = new int[N*N] ; 
  102.         int z = 0 ; 
  103.         for(int i = 0 ; i < N ; i++ ){
  104.             for(int j = 0 ; j < N ; j++ ){
  105.                 correctRow[z++] = i ; 
  106.             }
  107.         }
  108.         z = 0 ; 
  109.         correctCol = new int[N*N] ; 
  110.         for(int i = 0 ; i < N ; i++ ){
  111.             for(int j = 0 ; j < N ; j++ ){
  112.                 correctCol[z++] = j ; 
  113.             }
  114.         }
  115.     }
  116.  
  117.     public static void main(String[] args) {
  118.     	long start = System.currentTimeMillis();
  119.         // create initial board from file
  120.         Scanner in = new Scanner(new InputStreamReader(System.in));
  121.         int N = in.nextInt();
  122.         initCorrectRowsCols(N);
  123.         int[][] blocks = new int[N][N];
  124.         for (int i = 0; i < N; i++)
  125.             for (int j = 0; j < N; j++)
  126.             blocks[i][j] = in.nextInt();
  127.  
  128.         Board initial = new Board(blocks);
  129.  
  130.         // solve the puzzle
  131.         Solver solver = new Solver(initial);
  132.  
  133.         long end = System.currentTimeMillis();
  134.         System.out.println("time taken " + (end-start) + " milli seconds");
  135.  
  136.         // print solution to standard output
  137.         if (!solver.isSolvable())
  138.             System.out.println("No solution possible");
  139.         else {
  140.             System.out.println("Minimum number of moves = " + solver.moves());
  141.             Stack<Board> stack = new Stack<Board>();
  142.             for (Board board : solver.solution())
  143.             	stack.push(board);
  144.             while(!stack.isEmpty()){
  145.             	System.out.println(stack.pop());
  146.             }
  147.         }
  148.     }
  149. }
  150.  
  151. class Board{
  152.     private int[][] array ; 
  153.     private int N ;
  154.     int emptyRow;
  155.     int emptyCol;
  156.     boolean reached;
  157.     int manhattan = 0;
  158.  
  159.     public Board(int[][] blocks){
  160.         N = blocks.length ; 
  161.         array = new int[N][N] ;
  162.         reached = true;
  163.         for(int i = 0 ; i < N ; i++ ){
  164.             for(int j = 0 ; j < N ; j++ ) {
  165.                 array[i][j] = blocks[i][j] ;
  166.                 if(array[i][j] == 0){
  167.                 	emptyRow = i;
  168.                 	emptyCol = j;
  169.                 }
  170.                 if(array[i][j] != N*i + j+1){
  171.                     if(!(i==N-1 && j==N-1)){
  172.                     	reached = false;
  173.                     }
  174.                 }
  175.                 int num = array[i][j] ; 
  176.                 if(num==0){
  177.                     continue ; 
  178.                 }
  179.                 int indManhattan = Math.abs(Solver.correctRow[num-1] - i) 
  180.                 		+ Math.abs(Solver.correctCol[num-1]-j) ; 
  181.                 manhattan += indManhattan ;
  182.             }
  183.         }
  184.     }
  185.  
  186.     public int dimension(){
  187.         return N ; 
  188.     }
  189.  
  190.     public int hamming(){
  191.         int outOfPlace = 0 ; 
  192.         for(int i = 0 ; i < N ; i++ ) {
  193.             for(int j = 0 ; j < N ; j++ ){
  194.                 if(i==N-1 && j==N-1) {
  195.                     break ; 
  196.                 }
  197.                 if(array[i][j] != i*N+j+1){
  198.                     outOfPlace++ ; 
  199.                 }
  200.             }
  201.         }
  202.         return outOfPlace ; 
  203.     }
  204.  
  205.     public int manhattan(){
  206.         return manhattan ; 
  207.     }
  208.  
  209.     public boolean isGoal(){
  210.         return reached ; 
  211.     }
  212.  
  213.     public Board twin(){
  214.         int[][] newArray = new int[N][N] ; 
  215.         for(int i = 0 ; i < N ; i++ ){
  216.             for(int j = 0 ; j < N ; j++ ){
  217.                 newArray[i][j] = array[i][j] ; 
  218.             }
  219.         }
  220.         for(int i = 0 ; i < 2 ; i++ ) {
  221.             if(newArray[i][0]==0 || newArray[i][1]==0){
  222.                 continue ; 
  223.             }
  224.                 int temp = newArray[i][0] ; 
  225.                 newArray[i][0] = newArray[i][1] ; 
  226.                 newArray[i][1] = temp ; 
  227.                 break ; 
  228.  
  229.         }
  230.         return new Board(newArray) ; 
  231.     }
  232.  
  233.     public boolean equals(Object y){
  234.         if(y==this){
  235.             return true ; 
  236.         }
  237.         if(y == null){
  238.             return false ; 
  239.         }
  240.         if(y.getClass() != this.getClass()){
  241.             return false ; 
  242.         }
  243.         Board that = (Board)y ; 
  244.         if(that.array.length != this.array.length){
  245.             return false ;
  246.         }
  247.         for(int i = 0 ; i < N ; i++ ) {
  248.             for(int j =  0 ; j < N ; j++ ) {
  249.                 if(that.array[i][j] != this.array[i][j] ){
  250.                     return false ; 
  251.                 }
  252.             }
  253.         }
  254.         return true ; 
  255.     }
  256.  
  257.     public Iterable<Board> neighbors(){
  258.         Queue<Board> q = new ArrayDeque<Board>() ; 
  259.         int firstIndex0 = 0 ; 
  260.         int secondIndex0 = 0 ; 
  261.         for(int i = 0 ; i < N ; i++ ){
  262.             for(int j = 0 ; j < N ; j++ ) {
  263.                 if(array[i][j] == 0){
  264.                     firstIndex0 = i ; 
  265.                     secondIndex0 = j ; 
  266.                     break ; 
  267.                 }
  268.             }
  269.         }
  270.         if(secondIndex0-1>-1){
  271.             int[][] newArr = getCopy() ; 
  272.             exch(newArr,firstIndex0,secondIndex0,firstIndex0,secondIndex0-1) ; 
  273.             q.add(new Board(newArr)) ; 
  274.         }
  275.         if(secondIndex0+1<N){
  276.             int[][] newArr = getCopy() ; 
  277.             exch(newArr,firstIndex0,secondIndex0,firstIndex0,secondIndex0+1) ; 
  278.             q.add(new Board(newArr)) ; 
  279.         }
  280.         if(firstIndex0-1>-1){
  281.             int[][] newArr = getCopy() ; 
  282.             exch(newArr,firstIndex0,secondIndex0,firstIndex0-1,secondIndex0) ;     
  283.             q.add(new Board(newArr)) ; 
  284.         }
  285.         if(firstIndex0+1<N){
  286.             int[][] newArr = getCopy() ; 
  287.             exch(newArr,firstIndex0,secondIndex0,firstIndex0+1,secondIndex0) ; 
  288.             q.add(new Board(newArr)) ; 
  289.         }
  290.         return q ; 
  291.     }
  292.  
  293.     private int[][] getCopy(){
  294.         int[][] copy = new int[N][N] ; 
  295.         for(int i = 0 ; i < N ; i++ ) {
  296.             for(int j = 0 ; j < N ; j++ ){
  297.                 copy[i][j] = array[i][j] ; 
  298.             }
  299.         }
  300.         return copy ; 
  301.     }
  302.  
  303.     private void exch(int[][] arr, int firstIndex,int secIndex,int firstIndex2,int secIndex2){
  304.         int temp = arr[firstIndex][secIndex] ; 
  305.         arr[firstIndex][secIndex] = arr[firstIndex2][secIndex2] ;  
  306.         arr[firstIndex2][secIndex2] = temp ; 
  307.     }
  308.  
  309.     public String toString(){
  310.         StringBuilder s = new StringBuilder() ; 
  311.         s.append(N + "\n") ; 
  312.         for(int i = 0 ; i < N ; i++ ){
  313.             for(int j = 0 ; j  < N ; j++ ) {
  314.                 s.append(String.format("%4d",array[i][j])) ; 
  315.             }
  316.             s.append("\n") ; 
  317.         }
  318.         return s.toString() ; 
  319.     }
  320. }
Success #stdin #stdout 4.53s 381696KB
comments (?)
stdin 
4
 6  5 11  4 
10 13  2  1 
 9 15  7  3 
14 12  8  0
stdout 
time taken 4406 milli seconds
Minimum number of moves = 40
4
   6   5  11   4
  10  13   2   1
   9  15   7   3
  14  12   8   0

4
   6   5  11   4
  10  13   2   1
   9  15   7   3
  14  12   0   8

4
   6   5  11   4
  10  13   2   1
   9  15   7   3
  14   0  12   8

4
   6   5  11   4
  10  13   2   1
   9   0   7   3
  14  15  12   8

4
   6   5  11   4
  10  13   2   1
   0   9   7   3
  14  15  12   8

4
   6   5  11   4
   0  13   2   1
  10   9   7   3
  14  15  12   8

4
   6   5  11   4
  13   0   2   1
  10   9   7   3
  14  15  12   8

4
   6   5  11   4
  13   2   0   1
  10   9   7   3
  14  15  12   8

4
   6   5  11   4
  13   2   1   0
  10   9   7   3
  14  15  12   8

4
   6   5  11   4
  13   2   1   3
  10   9   7   0
  14  15  12   8

4
   6   5  11   4
  13   2   1   3
  10   9   0   7
  14  15  12   8

4
   6   5  11   4
  13   2   1   3
  10   0   9   7
  14  15  12   8

4
   6   5  11   4
  13   2   1   3
   0  10   9   7
  14  15  12   8

4
   6   5  11   4
   0   2   1   3
  13  10   9   7
  14  15  12   8

4
   0   5  11   4
   6   2   1   3
  13  10   9   7
  14  15  12   8

4
   5   0  11   4
   6   2   1   3
  13  10   9   7
  14  15  12   8

4
   5   2  11   4
   6   0   1   3
  13  10   9   7
  14  15  12   8

4
   5   2  11   4
   6   1   0   3
  13  10   9   7
  14  15  12   8

4
   5   2   0   4
   6   1  11   3
  13  10   9   7
  14  15  12   8

4
   5   0   2   4
   6   1  11   3
  13  10   9   7
  14  15  12   8

4
   5   1   2   4
   6   0  11   3
  13  10   9   7
  14  15  12   8

4
   5   1   2   4
   6  10  11   3
  13   0   9   7
  14  15  12   8

4
   5   1   2   4
   6  10  11   3
  13   9   0   7
  14  15  12   8

4
   5   1   2   4
   6  10   0   3
  13   9  11   7
  14  15  12   8

4
   5   1   2   4
   6  10   3   0
  13   9  11   7
  14  15  12   8

4
   5   1   2   4
   6  10   3   7
  13   9  11   0
  14  15  12   8

4
   5   1   2   4
   6  10   3   7
  13   9  11   8
  14  15  12   0

4
   5   1   2   4
   6  10   3   7
  13   9  11   8
  14  15   0  12

4
   5   1   2   4
   6  10   3   7
  13   9  11   8
  14   0  15  12

4
   5   1   2   4
   6  10   3   7
  13   9  11   8
   0  14  15  12

4
   5   1   2   4
   6  10   3   7
   0   9  11   8
  13  14  15  12

4
   5   1   2   4
   6  10   3   7
   9   0  11   8
  13  14  15  12

4
   5   1   2   4
   6   0   3   7
   9  10  11   8
  13  14  15  12

4
   5   1   2   4
   0   6   3   7
   9  10  11   8
  13  14  15  12

4
   0   1   2   4
   5   6   3   7
   9  10  11   8
  13  14  15  12

4
   1   0   2   4
   5   6   3   7
   9  10  11   8
  13  14  15  12

4
   1   2   0   4
   5   6   3   7
   9  10  11   8
  13  14  15  12

4
   1   2   3   4
   5   6   0   7
   9  10  11   8
  13  14  15  12

4
   1   2   3   4
   5   6   7   0
   9  10  11   8
  13  14  15  12

4
   1   2   3   4
   5   6   7   8
   9  10  11   0
  13  14  15  12

4
   1   2   3   4
   5   6   7   8
   9  10  11  12
  13  14  15   0
https://ideone.com/DCirVQ
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!