MLaskun

Sudoku Solver

May 17th, 2021
581
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //plik SudokuSolver.java
  2.  
  3. import java.util.*;
  4.  
  5. public class SudokuSolver{
  6.     private int[][] board;
  7.    
  8.     private List<Set<Integer>> row = new ArrayList<>();
  9.     private List<Set<Integer>> col = new ArrayList<>();
  10.     private List<Set<Integer>> square = new ArrayList<>();
  11.  
  12.    
  13.     public SudokuSolver(int[][] board){
  14.         this.board = board;
  15.         for(int i=0;i<9;i++){
  16.             row.add(new HashSet<>());
  17.             col.add(new HashSet<>());
  18.             square.add(new HashSet<>());
  19.         }
  20.         for(int i=0;i<9;i++){
  21.             for(int j=0;j<9;j++){
  22.                 if(board[i][j]==0) continue;
  23.                 int sqIx = (i/3)*3 + (j/3);
  24.                 square.get(sqIx).add(board[i][j]);
  25.                 row.get(i).add(board[i][j]);
  26.                 col.get(j).add(board[i][j]);
  27.             }
  28.         }
  29.     }
  30.    
  31.     public boolean solveSudoku(int y, int x){
  32.         if(y==9) return true;
  33.         int nx = (x+1)%9;
  34.         int ny = (nx==0)? (y+1):y;
  35.         if(board[y][x]!=0) return solveSudoku(ny,nx);
  36.         int sqIx = (y/3)*3+(x/3);
  37.         for(int i=1;i<10;i++){
  38.             if(row.get(y).contains(i) || col.get(x).contains(i) || square.get(sqIx).contains(i)) continue;
  39.             square.get(sqIx).add(i);
  40.             row.get(y).add(i);
  41.             col.get(x).add(i);
  42.             board[y][x] = i;
  43.             if(solveSudoku(ny,nx)) return true;
  44.             board[y][x] = 0;
  45.             square.get(sqIx).remove(i);
  46.             row.get(y).remove(i);
  47.             col.get(x).remove(i);
  48.         }
  49.         return false;
  50.     }
  51.    
  52.     public void getBoard(){
  53.         for(int i=0;i<board.length;i++){
  54.             for(int j=0;j<board[i].length;j++){
  55.                 System.out.println(board[i][j] + " ");
  56.             }
  57.             System.out.println();
  58.         }
  59.     }
  60. }
  61.  
  62.  
  63. /**********************************************************************/
  64. //plik Main.java
  65.  
  66. public class Main
  67. {
  68.     public static void main(String[] args) {
  69.         SudokuSolver solver = new SudokuSolver(new int[][] {{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}});
  70.         solver.solveSudoku(0,0);
  71.         solver.getBoard();
  72.     }
  73. }
RAW Paste Data