Program to Find All paths in a Matrix of 2D array.

Problem : Find all possible paths through the array.

It is only allowed to go diagonally up or down, or go to the right. An example 4x4 matrix

3  5  7  9
2  4  6  8
9  3  7  5
6  8  2  4

The numbers in the matrix can be any arbitrary value. I would like to generate all possible routes through the matrix, starting in one of the four numbers in the first column. It is only allowed to move Northeast, East, and Southeast. An example route:

3-5 7 9
   \
2 4 6-8
9 3 7 5
6 8 2 4

Solution

import java.util.*;

class Paths{

  static int arr[][] = {{3,5,7,9},{2,4,6,8},{9,3,7,5},{6,8,2,4}};
    
  public static void main(String args[]){

   for(int itr=0; itr<arr.length; itr++){
      for(String path : new Paths().findPaths(itr, 0)){
        if(path.split("->").length == 4)
           System.out.println(path); 
      }
   }
  }

  public ArrayList<String> findPaths(int row, int col){
  ArrayList<String> paths = new ArrayList<String>();
  if(goNorthEast(row,col)){
    paths.add(arr[row][col]+"->"+arr[row-1][col+1]);
    for(String path :  findPaths(row-1,col+1)){
      paths.add(arr[row][col]+"->" + path);
    }
  }
  if(goEast(row,col)){
    paths.add(arr[row][col]+"->"+arr[row][col+1]);
    for(String path :  findPaths(row,col+1)){
      paths.add(arr[row][col]+"->" + path);
    }
  }
  if(goSouthEast(row,col)){
    paths.add(arr[row][col]+"->"+arr[row+1][col+1]);
    for(String path :  findPaths(row+1,col+1)){
      paths.add(arr[row][col]+"->" + path);
    }
  }
  return paths;
 }

 public boolean goNorthEast(int row, int col){
   if(row-1<0 || col+1 >= arr.length)
     return false;
   return true;
 }

 public boolean goEast(int row, int col){
   if(col+1 >= arr.length)
     return false;
   return true;
 }

 public boolean goSouthEast(int row, int col){
   if(row+1 >=arr.length || col+1 >= arr.length)
     return false;
   return true;
 }


}

3->5->7->9
3->5->7->8
3->5->6->9
3->5->6->8
3->5->6->5
3->4->7->9
3->4->7->8
3->4->6->9
3->4->6->8
3->4->6->5
3->4->7->8
3->4->7->5
3->4->7->4
2->5->7->9
2->5->7->8
2->5->6->9
2->5->6->8
2->5->6->5
2->4->7->9
2->4->7->8
2->4->6->9
2->4->6->8
2->4->6->5
2->4->7->8
2->4->7->5
2->4->7->4
2->3->6->9
2->3->6->8
2->3->6->5
2->3->7->8
2->3->7->5
2->3->7->4
2->3->2->5
2->3->2->4
9->4->7->9
9->4->7->8
9->4->6->9
9->4->6->8
9->4->6->5
9->4->7->8
9->4->7->5
9->4->7->4
9->3->6->9
9->3->6->8
9->3->6->5
9->3->7->8
9->3->7->5
9->3->7->4
9->3->2->5
9->3->2->4
9->8->7->8
9->8->7->5
9->8->7->4
9->8->2->5
9->8->2->4
6->3->6->9
6->3->6->8
6->3->6->5
6->3->7->8
6->3->7->5
6->3->7->4
6->3->2->5
6->3->2->4
6->8->7->8
6->8->7->5
6->8->7->4
6->8->2->5
6->8->2->4