Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
5.0 kB
4
Indexable
Never
import java.util.*;
import java.io.*;
public class Main{
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br=new BufferedReader(new InputStreamReader(System.in));
        }
        String next(){
            while(st==null || !st.hasMoreTokens()){
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        String nextLine(){
            String str="";
            try {
                str=br.readLine().trim();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    static class FastWriter {
		private final BufferedWriter bw;
		public FastWriter() {
			this.bw = new BufferedWriter(new OutputStreamWriter(System.out));
		}
		public void print(Object object) throws IOException {
			bw.append("" + object);
		}
		public void println(Object object) throws IOException {
			print(object);
			bw.append("\n");
		}
		public void close() throws IOException {
			bw.close();
		}
	}
	
	public static boolean verify(int [][]arr){
	    int n = 9;
	   // for rows
	    for(int i = 0;i<n;i++){
	        HashMap<Integer, Integer> map = new HashMap<>();
	        for(int j = 0;j<n;j++){
	            if(map.containsKey(arr[i][j])) return false;
	            map.put(arr[i][j], 0);
	        }
	    }
	   // for colm
	    for(int i = 0;i<n;i++){
	        HashMap<Integer, Integer> map1 = new HashMap<>();
	        for(int j = 0;j<n;j++){
	            if(map1.containsKey(arr[j][i])) return false;
	            map1.put(arr[j][i], 0);
	        }
	    }
	   // for 3x3
	   int x1 = 0, x2 = 3;
        while(x1 < 9){
            int y1 = 0, y2 = 3;
           while(y1 < 9){
                HashMap<Integer, Integer> map = new HashMap<>();
                for(int i = x1;i<x2;i++){
                    for(int j = y1;j<y2;j++){
                        // System.out.print(i+","+j+" ");
                        if(map.containsKey(arr[i][j])) return false;
                        map.put(arr[i][j], 0);
                    }
                    // System.out.println();
    	        }
    	       // System.out.println();
                // System.out.println(map);
    	        y1 = y2;
    	        y2 += 3; 
            }
            // System.out.println();
            x1 = x2;
            x2 += 3;
        }
	    
	    return true;
	}
	
	public static boolean isEmpty(int[][]arr){
	    for(int i = 0;i<9;i++){
	        for(int j = 0;j<9;j++){
	            if(arr[i][j] == 0) return true;
	        }
	    }
	    return false;
	}
	
	public static int[][] deepCopy(int[][] arr){
	    int[][] temp =  new int[9][9];
	    for(int i = 0;i<9;i++){
	        for(int j = 0;j<9;j++){
	            temp[i][j] = arr[i][j];
	        }
	    }
	    return temp;
	}
	
	static boolean solved = false;
	public static void solveSudoku(int x, int y, int[][]arr){
	   // if sudoku is full and solution is valid then print
	    if(!isEmpty(arr) && verify(arr)){
	        for(int i = 0;i<9;i++){
	            for(int j = 0;j<9;j++){
	                System.out.print(arr[i][j]+" ");
	            }
	            System.out.println();
	        }
	        solved = true;
	        return;
	    }
	   // if it is solved but invalid or there is another value exist inn place of xy
	    else if(!isEmpty(arr) || arr[x][y] != 0) return;
	    else{
	        
	        for(int a = 1; a<10; a++){
	            arr[x][y] = a;
    	        for(int i = x+1;i<9;i++){
    	            for(int j = y+1;j<9;j++){
    	                int [][]temp = deepCopy(arr);
    	                solveSudoku(i,j,arr);
    	            }    
    	        }
	        }
	    }
	}
	
    public static void main(String[] args) {
        try {
            FastReader sc=new FastReader();
            FastWriter out = new FastWriter();
            
            //write code here
    	    int n = 9;
            int[][] arr = new int[n][n];
            for(int i = 0; i<n;i++){
                for(int j = 0; j<n;j++){
                    
                    arr[i][j] = sc.nextInt();
                }
            }
            solveSudoku(0,0,arr);
            if(!solved) System.out.println(-1);
            // System.out.println(verify(arr));
            // System.out.println(isEmpty(arr));
            out.close();
        
        }
        catch (Exception e) {
            e.printStackTrace() ;
            return;
        }
    }
    
}
Leave a Comment