DAA Sudoku

By Sergio, ago, written in Java.
URL http://pastecode.org/index.php/view/49549578
Download Paste or View RawExpand paste to full width of browser | Change Viewing Options
  1. public class prac3 {
  2.    
  3.     public static class Tablero{
  4.         static int tabla[][] = {
  5.             {5, 3, 0, 0, 7, 0, 0, 0, 0},
  6.             {6, 0, 0, 1, 0, 5, 0, 0, 0},
  7.             {0, 9, 8, 0, 0, 0, 0, 6, 0},
  8.             {8, 0, 0, 0, 0, 0, 0, 0, 3},
  9.             {4, 0, 0, 8, 0, 3, 0, 0, 1},
  10.             {7, 0, 0, 0, 2, 0, 0, 0, 6},
  11.             {0, 6, 0, 0, 0, 0, 2, 8, 0},
  12.             {0, 0, 0, 4, 1, 9, 0, 0, 5},
  13.             {0, 0, 0, 0, 8, 0, 0, 7, 9},};
  14.     }
  15.    
  16.     public static class Celda{
  17.         int x, y, valor;
  18.         public Celda(int x, int y){
  19.             this.x = x;
  20.             this.y = y;
  21.             this.valor = Tablero.tabla[x][y];
  22.         }
  23.     }
  24.    
  25.     public static class Sudoku{
  26.         Tablero sudokuInicial = new Tablero();
  27.        
  28.         public void imprimirSudoku() {
  29.         System.out.println();
  30.         for (int i = 0; i < 9; ++i) {
  31.             for (int j = 0; j < 9; ++j) {
  32.                 System.out.print(Tablero.tabla[i][j] + " ");
  33.             }
  34.             System.out.println();
  35.         }
  36.         System.out.println();
  37.     }
  38.        
  39.         public boolean validoFila(Celda celda){
  40.             boolean valido = true;
  41.             for (int i=0; i<9; i++){
  42.                 if (celda.valor == Tablero.tabla[i][celda.y]){
  43.                     valido = false;
  44.                 }
  45.             }
  46.             return valido;
  47.         }
  48.        
  49.         public boolean validoColumna(Celda celda){
  50.             boolean valido = true;
  51.             for (int i=0; i<9; i++){
  52.                 if (celda.valor == Tablero.tabla[celda.x][i]){
  53.                     valido = false;
  54.                 }
  55.             }
  56.             return valido;
  57.         }
  58.        
  59.         public boolean validoCaja(Celda celda){
  60.             boolean valido = true;
  61.             int fila = (celda.x / 3) * 3;
  62.             int col = (celda.y / 3) * 3;
  63.             for (int f=0; f<3; f++){
  64.                 for (int c=0; c<3; c++){
  65.                     if (celda.valor == Tablero.tabla[fila+f][col+c]){
  66.                         valido = false;
  67.                     }
  68.                 }
  69.             }
  70.             return valido;
  71.         }
  72.        
  73.         public boolean yaEscrito(Celda celda){
  74.             return Tablero.tabla[celda.x][celda.y] != 0;
  75.         }
  76.        
  77.         public boolean comprobarCelda(Celda celda){
  78.             boolean valido = false;
  79.             if (validoFila(celda) && validoColumna(celda)
  80.                 && validoCaja(celda)){
  81.                 valido = true;                
  82.             }
  83.             return valido;
  84.         }
  85.        
  86.         public void colocar(Celda celda){
  87.             Tablero.tabla[celda.x][celda.y] = celda.valor;
  88.             System.out.println(celda.valor + " - Ha sido colocado en - " + celda.x + "," + celda.y);
  89.         }
  90.        
  91.         public void borrar(Celda celda){
  92.             Tablero.tabla[celda.x][celda.y] = 0;
  93.             celda.valor = 0;
  94.             System.out.println(celda.x + "," + celda.y + " - Reseteada a - " + celda.valor);
  95.         }
  96.        
  97.         public Celda siguienteCelda(Celda celdaAnterior){
  98.             Celda celda = new Celda(celdaAnterior.x, celdaAnterior.y);
  99.             if (celdaAnterior.x == 8){
  100.                 celda.x = 0;
  101.                 celda.y++;
  102.             }else{
  103.                 celda.x++;
  104.             }
  105.             return celda;
  106.         }
  107.        
  108.         public boolean resolver(Celda celda){
  109.             if (yaEscrito(celda)){
  110.                 if (celda.x == 8 && celda.y == 8){
  111.                     System.out.println("Ya ha terminado y este es el resultado"); //Haciendo una copia del tablero y metiendola en una lista hashset?
  112.                     imprimirSudoku();
  113.                     return true;
  114.                 }else{
  115.                     System.out.println(celda.x + "," + celda.y + " - Ya esta escrito, vamos a por la siguiente celda");
  116.                     return resolver(siguienteCelda(celda));
  117.                 }
  118.             }else{
  119.                 System.out.println(celda.x + "," + celda.y + " - No se ha escrito");
  120.                 for (int i=1; i<=9; i++){
  121.                     celda.valor = i;
  122.                     if (comprobarCelda(celda)){
  123.                         System.out.println(i + " - Es valido para la celda - " + celda.x + "," + celda.y);
  124.                         colocar(celda);
  125.                         if (resolver(celda)){
  126.                             return true;
  127.                         }
  128.                         borrar(celda);
  129.                     }else{
  130.                         System.out.println(i + " - No es valido para la celda - " + celda.x + "," + celda.y + " - Reseteamos la celda a 0");
  131.                         celda.valor = 0;
  132.                     }
  133.                 }
  134.             }
  135.             System.out.println("DEP");
  136.             return false; //Si se ejecuta esto es que ha fallado
  137.         }
  138.        
  139.     }
  140.    
  141.     public static void main(String[] args) {
  142.         Sudoku prac3 = new Sudoku();
  143.         if (prac3.resolver(new Celda(0,0))){
  144.             System.out.println("Sakabao");
  145.         }
  146.        
  147.     }
  148.    
  149.    
  150.    
  151. }

Here you can reply to the paste above

Make Private

   

Feeling clever? Set some advanced options.