View difference between Paste ID: 2FR50GYr and h40qCYfd
SHOW: | | - or go back to the newest paste.
1
package com.company;
2
3
import java.util.*;
4
5
public class Sudoku {
6
    public static int[][] sudokuInDigits = new int[9][9]; //matricata kydeto se pazi sudokuto
7
    private static boolean solved = false;//uslovie za izlizane ot rekursiqta
8
    public static void main(String[] args) {
9
        Scanner in = new Scanner(System.in);
10
        String[][] sudoku = new String[9][9];
11
        int placesToFill = 0;
12
        for (int i = 0; i < sudoku.length; i++) {
13
            for (int j = 0; j < 1; j++) {
14
                sudoku[i][j] = in.next();
15
                    for (int k = 0; k < 9; k++) {
16
                        //prevryshtane ot String kym int na vxoda
17
                        if (sudoku[i][k] != "-") {
18
                            int digit = sudoku[i][j].charAt(k) - '0';
19
                            if (digit > 0) {
20
                                sudokuInDigits[i][k] = digit;
21
                            }
22
                            else {
23
                                //dynoto na rekursiqta
24
                                placesToFill++;
25
                            }
26
                        }
27
                    }
28
            }
29
        }
30
        solveSudoku(placesToFill, 0);
31
        //printirane na gotovoto sudoku
32
        for (int i = 0; i < sudokuInDigits.length; i++) {
33
            for (int j = 0; j < sudokuInDigits[i].length; j++) {
34
                System.out.print(sudokuInDigits[i][j]);
35
            }
36
            System.out.println();
37
        }
38
    }
39
40
    private static void solveSudoku(int squaresLeft, int nextNumber) {
41
        if (squaresLeft == 0 || solved) {
42
            solved = true;
43
            return;
44
        }
45
        for (int i = 0; i < sudokuInDigits.length; i++) {
46
            for (int j = 0; j < sudokuInDigits[i].length; j++) {
47
                //obxojdane na matricata za da vidim kyde lipsvat chisla
48
                if (sudokuInDigits[i][j] == 0) {
49
                    for (int k = 1; k < 10; k++) {
50
                        //proverki za tova koe chislo lipsva i koe se sydyrja na syotvetniq red/kolona
51
                        //ili kvadratche
52
                        if (checkRow(k,i) == true && checkColumn(j,k) == true
53
                                && checkSquare(i,k,j) == true) {
54
                            sudokuInDigits[i][j] = k;
55
                            squaresLeft--;
56
                            solveSudoku(squaresLeft,k + 1);
57
                            //neobxodimo za da moje da kato se vryshta rekursiqta
58
                            //da ne promenq tekushtoto systoqnie
59
                            if(solved)
60
                                return;
61
                            //pri otkriti konflikti vyzstanovqvame predishnoto systoqnie
62
                            //na matricata
63
                            sudokuInDigits[i][j] = 0;
64
                            squaresLeft++;
65
                        }
66
                    }
67
                    return;
68
                }
69
            }
70
        }
71
        return;
72
    }
73
74
    private static boolean checkRow(int candidate, int row) {
75
        //proverka za reda dali sydyrjda chisloto
76
        for (int col = 0; col < 9; col++ ) {
77
            if (sudokuInDigits[row][col] == candidate)
78
                return false;
79
        }
80
        return true;
81
    }
82
83
    private static boolean checkColumn(int column, int candidate) {
84
        //proverka za kolonata dali sydyrja chisloto
85
        for (int row = 0; row < 9; row++ ) {
86
            if (sudokuInDigits[row][column] == candidate)
87
                return false;
88
        }
89
        return true;
90
    }
91
92
    private static boolean checkSquare(int row, int candidate, int column) {
93
        //izchisleniq za tova kakvo e razstoqnieto ot [0,0] do [row,column]
94
        int colMultiplier = column / 3;
95
        int rowMultiplier = row / 3;
96
        int cellsInASquareSide = 3;
97
        //proverka na kvadratcheto
98
        for (int i = 0; i < 9; i++) {
99
            if (sudokuInDigits[i % 3 + rowMultiplier * cellsInASquareSide][i / 3 +
100
                        colMultiplier * cellsInASquareSide] == candidate) {
101
                return false;
102
            }
103
        }
104
        return true;
105
    }
106
}