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 | } |