Algoritmo para representar un Sudoku

Inicio

Nos hemos tomado la libertad de publicar un código sin el consentimiento previo del autor, del cual desconocemos su procedencia. No tuvimos tiempo de contactarlo, debido a que esperamos hasta el último minuto a que los lectores de la revista nos enviaran su propio algoritmo, como habíamos sugerido en BlackHat 16. Pero no se preocupen, que avisaremos lo más pronto posible a dicho programador para que nos dé su consentimiento.

El hecho es que en la sección de Ocio de la edición #14 de BlackHat, comenzamos a hacer público un conjunto de tableros del Sudoku, generados por el GNU Sudoku Portable -y rediseñados por nustro equipo. En ese mismo número de la revista pensamos en tres reglas que pudieran ser aplicadas para la generación de un algoritmo eficiente que permitiera resolver todos los pasos iniciales de este juego matemático. Volvemos a repetir dichas propuestas y a continuación el código que permite resolver la primera de ellas:

Llenar de números una matriz 9×9 donde se cumplan las reglas del juego.
Hallar el máximo de números que se pueden ocultar para que no existan soluciones ambiguas.
Seleccionar arbitrariamente las posiciones de los números que se van a ocultar para que exista una sola solución.

#include <conio.h>
#include <time.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>

int a[9][9], b[9][9];

bool Verif_cuadros(int grupo){
  int posic, i;
  bool acepto;
  acepto= true;
  for (posic=1; posic<10; posic++) {
    for (i=1; i<posic; i++) {
      if (b[grupo][posic]==b[grupo][i]) {
        acepto=false;
        goto sali;
      }
    }
  }
  sali: return acepto;
}

void Mezclar(){
  int restoX, restoY;
  int subir, t, x, y;
  float X, Y;
  int grupo, posic;
  bool repet, acepta;
  srand((unsigned)time(NULL));
  for (y=1; y<10; y++) {
    for (x=1; x<10; x++) {
      a[y][x]= (rand()%9) + 1;
      for (t=1; t<x; t++) {
        if (a[y][x]==a[y][t]) repet=true;
      }
      if (repet==false) {
        for (t=1; t<y; t++) {
          if (a[y][x]==a[t][x]) repet=true;
        }
      }
      if (repet==true){
        repet=false;
        if (subir> 20){
          subir= 0;
          x= 0;
        }
        else {
          subir++;
          x--;
        }
      }
      else {
        restoY= y % 3;
        restoX= x % 3;
        if (restoX==0) restoX=3;
        if (restoY==0) restoY=3;
        Y= y; X= x;
        posic= 3*(restoY-1) + restoX;
        grupo= 3*(ceil(Y/3)-1) + ceil(X/3);
        b[grupo][posic]= a[y][x];
        subir= 0;
      }
    }
    if ((y%3)==0) {
      for (grupo=y-2; grupo<=y; grupo++){
        acepta= Verif_cuadros(grupo);
        if (acepta==false) {
          y= y-3;
          goto sali;
        }
      }
    }
    sali:;
  }
}

void Imprimir(){
  int y, x;
  for (y=1; y<10; y++) {
    for (x=1; x<10; x++) {
      cout << a[y][x] << " ";
    }
    cout << endl;
  }
}

void main(){
  Mezclar();
  Imprimir();
  getch();
}

Escrito por Ezequiel Hernandez

Codigos Proyecto BlackHat