Advertisement
Guest User

sdf

a guest
Jan 28th, 2020
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.32 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. //         http://i.imgur.com/xk5XCCl.png
  6.  
  7. typedef vector<vector<int> > sudoku;
  8.  
  9.  
  10. /*
  11. bool evaluar(sudoku &matriz){
  12.    
  13.   for(int s=0;s<9;s++){
  14.       int a=0,b=0;
  15.       for(int z=0;z<9;z++){
  16.           a+=matriz[s][z];
  17.           b+=matriz[z][s];
  18.         }
  19.        
  20.         if (a!=45) return false ;
  21.         if (b!=45) return false ;}
  22.      
  23.       return true;
  24. }
  25. */
  26.  
  27. bool posVacia(sudoku &s, int &fila, int &col)
  28. {
  29.     for (fila = 0; fila < 9; fila++)
  30.         for (col = 0; col < 9; col++)
  31.             if (s[fila][col] == 0)
  32.                 return true;
  33.     return false;
  34. }
  35.  
  36. bool estaEnFila(sudoku &s, int fila, int num)
  37. {
  38.     for (int col = 0; col < 9; col++)
  39.         if (s[fila][col] == num)
  40.             return true;
  41.     return false;
  42. }
  43.  
  44. bool estaEnCol(sudoku &s, int col, int num)
  45. {
  46.     for (int fila = 0; fila < 9; fila++)
  47.         if (s[fila][col] == num)
  48.             return true;
  49.     return false;
  50. }
  51.  
  52.  
  53. bool estaEnBox(sudoku &s, int empiezaFila, int empiezaCol, int num)
  54. {
  55.     for (int fila = 0; fila < 3; fila++)
  56.         for (int col = 0; col < 3; col++)
  57.             if (s[fila+empiezaFila][col+empiezaCol] == num)
  58.                 return true;
  59.     return false;
  60. }
  61.  
  62. bool valido(sudoku &s, int fila, int col, int num)
  63. {
  64.    
  65.     return !estaEnFila(s, fila, num) &&
  66.            !estaEnCol(s, col, num) &&
  67.            !estaEnBox(s, fila - fila%3 , col - col%3, num)&&
  68.             s[fila][col]==0;
  69. }
  70.  
  71. bool resolver(sudoku &s){
  72.     int fila, col;
  73.  
  74.    
  75.     if (!posVacia(s, fila, col))
  76.        return true;
  77.  
  78.     for (int num = 1; num <= 9; num++)
  79.     {
  80.         if (valido(s, fila, col, num))
  81.         {
  82.             s[fila][col] = num;
  83.  
  84.             if (resolver(s))
  85.                 return true;
  86.  
  87.             s[fila][col] = 0;
  88.         }
  89.     }
  90.     return false;
  91.  
  92.  
  93. }
  94.  
  95. sudoku leer(){
  96.   sudoku s (9, vector<int> (9));
  97.  
  98.   for(int i = 0; i<9;++i){
  99.     for(int j = 0; j<9; ++j){
  100.       scanf("%d", &s[i][j]);
  101.     }
  102.   }
  103.  
  104.   return s;
  105. }
  106.  
  107. void escribir(sudoku &s){
  108.  
  109.   for(int i = 0; i<9;++i){
  110.     for(int j = 0; j<9; ++j){
  111.       printf("%d ", s[i][j]);
  112.     }
  113.     printf("\n");
  114.   }
  115.  
  116. }
  117.  
  118.  
  119. int main(){
  120.  
  121.   sudoku s = leer();
  122.  
  123.   if(resolver(s)) escribir(s);
  124.  
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement