RobotColoringProblem.java

import java.util.HashMap;
import java.util.Map;

public class RobotColoringProblem {

    public boolean isPossible(int row, int col, int [][] input){
        if(row>=0 && col>=0 && col<input.length && row<input[0].length)
            return true;
        return false;
    }

    public int[] move(char direction){
        if(direction == 'N')
            return new int[]{-1, 0};
        if(direction == 'E')
            return new int[]{0,1};
        if(direction == 'S')
            return new int[]{1,0};
        else //west
            return new int[]{0,-1};
    }

    public void assign(int [][] input, Map<Integer, Character> colors){
        boolean [][] visited = new boolean[input.length][input[0].length];

        if (assignUtil(0, 0, input, colors, visited)){
            for(Integer key: colors.keySet()){
                System.out.println(key + "  " + colors.get(key));
            }
        }else {
            System.out.println("No Path possible");
        }

    }

    public boolean assignUtil(int row, int col, int [][] input, Map<Integer, Character> colors, boolean [][] visited){

        if(!isPossible(row, col, input) || visited[row][col])
            return false;

        if(input[row][col]==-1)
            return true;

        //mark visited
        visited[row][col] = true;

        int val = input[row][col];
        if(colors.containsKey(val)) { //check if color is already assigned
            char direction = colors.get(val);
            int [] add = move(direction);
            return assignUtil(row + add[0], col + add[1], input, colors, visited);
        }else {
            //try 4 directions
            char[] dir = {'N', 'E', 'S', 'W'};
            for (char direction : dir) {
                colors.put(input[row][col], direction);
                int[] add = move(direction);
                if (assignUtil(row + add[0], col + add[1], input, colors, visited)) {
                    return true;
                }
                colors.remove(input[row][col]); //backtrack
            }
        }
            return false;
    }

    public static void main(String[] args) {
        int [][] a = {{0,1,0,0},
                {0,1,-1,4},
                {0,1,0,3},
                {0,2,0,3}};
        RobotColoringProblem r = new RobotColoringProblem();
        Map<Integer, Character> colors = new HashMap<>();
        r.assign(a, colors);
    }
}