Sobre backtracking

Parece que el problema comienza a complicarse :P La verdad es que no tengo experiencia práctica con problemas de ramificación y acotación, pero quizá pueda explicártelo con palabras.
Tu algoritmo trabaja sobre un árbol cuyas hojas son las soluciones del problema. Empieza desde la raíz, que es el primer estado (la matriz vacía, en tu caso), y en cada iteración tiene que ir bajando a un nivel inferior por una de las ramas (es decir, debe elegir al nodo hijo más "prometedor", o a través del cual pueda llegar a la mejor solución). Por tanto, para saber qué nodo hijo elegir, lo primero que tienes que hacer es fijar un criterio de valoración para los nodos, de manera que puedas establecer un orden de preferencias.
En tu caso, veo que estás trabajando en un programa relacionado con los nanogramas, así que supongo que las matrices toman valores binarios que pueden ser correctos o erróneos. Por tanto, un posible criterio de valoración podría ser el número de aciertos posibles (es decir, el número de elementos de la matriz, M por N) menos el número de errores de la matriz actual, o, lo que es lo mismo, el número de elementos erróneos. El valor resultante no sería el valor final, sino una cota superior. Es decir, a cuánto puedes aspirar como máximo si sigues por esa rama.
Imagina que tienes una matriz 2 x 2 con la primera fila a cero, y uno de esos elementos es erróneo. En tal caso, el valor de ese nodo es 4 - 1 = 3 (número de posibles aciertos, 2 x 2, menos errores). Otro nodo podría tener un 1 y un 0 en la primera fila, siendo ambos elementos erróneos, de manera que el valor del nodo correspondiente fuese 4 - 2 = 2. Por tanto, tu algoritmo exploraría el subárbol cuya raíz es el primer nodo, el valorado en 3 unidades, que es una cota superior.
Tu programa seguiría bajando por el árbol hasta llegar a los nodos hoja (es decir, los que no tienen descendientes o ramificaciones) y de esos elegiría el mejor, siguiendo el mismo criterio de valoración que el utilizado en la exploración del resto del árbol. El mejor nodo sería la solución final.
Es complicado de implementar y me falta tiempo para escribirte el código, pero en resumen lo primero que tienes que hacer es fijar un criterio de valoración como el que te he dicho.
Empieza por crear una función que te devuelva el número de errores de una matriz, y otra que se sirva de la primera para determinar el valor de esa matriz (es decir, el número de aciertos posibles, M x N, menos el número de errores) y yo intentaré buscar un hueco cuando pueda para ayudarte con el algoritmo, ¿ok?
¡Mucha suerte! ;-)

No te preocupes, veré si puedo arreglarlo...
Yo tengo hecho ya el programa que lee los que serian las matrices solución del nonograma y me genera el tablero original, lo hago por vuelta atrás así que hasta tableros 5x5 la cosa va bien, pero a partir de ahí tarda mucho, de ahí que quiera acotarlo. He seguido los pasos como me indicó mi tutor, que me dijo que cuando tuviera esto le hiciera una poda, por ejemplo: cuando tengo la 1ª fila del posible tablero, si veo que no coincide, en cuanto a unos, con la solución que yo tenga pues que no siga generando esa matriz. Muy bonito en la teoría pero en la práctica no hay quien lo haga, yo al menos no lo veo. Tendría que haberlo pensado cuando hice el backtracking, y hacer lo que tu dices... pero me dijo que era muy fácil así y piqué.
Voy a ver que me dice ahora el tutor.
Gracias.

Okey, en cuanto sepas algo me dices. Suerte ;-)

Bueno ya me he enterado, entre que él no se había explicado muy bien la otra vez y yo no había entendido pues así estábamos. Te explico lo que voy a hacer por si te puedo preguntar las dudillas que tendré. Se podrá hacer de forma más fina pero la que me ha dicho no es muy complicada (en teoría). Como te veo familiarizado con los nonogramas te explico por encima: una vez puesto la primera casilla (0,0) tengo que llamar a una función "poda", en ella tendré que generar desde 0 a n cuadrado -1 dígitos binarios (son las posibles combinaciones que hay en una fila) y ver las que cumplen los requisitos de la matriz que tengo con las pistas para resolver el nonograma, de las que los cumplan tendré que ver si alguno empieza por 0 si es así no puedo podar y sigo al nivel 2 (casilla (0,1) y repito el proceso, cuando pueda podar pues podo y retrocedo y etc... de la función "poda" supongo que devolveré un booleano que me diga si podo o no. Lo entiendo pero no se yo... la verdad es que me cuesta trabajo ver la recursividad y como sube y baja a través de los niveles...
Evidentemente mis funciones para generar las filas y columnas me sirven.
Pues no es "nada más" que esto ;) allá voy!. Cualquier ayuda o sugerencia será bienvendia je je.
Gracias por leer esta chapa.

Veo que en cada nivel del árbol quieres rellenar una fila completa. Yo había pensado en rellenar un elemento en cada nivel, de manera que no tuvieras que explorar tantas posibilidades. Pero supongo que también se puede hacer así.
De todas maneras, el número de "combinaciones" posibles para una fila de dígitos binarios sería 2 elevado a n, donde n es el número de columnas (variaciones con repetición de 2 elementos en grupos de n).
En cada nivel tendrás varias opciones posibles (es decir, igualmente válidas en apariencia), así que tendrás que explorarlas todas. Esto puedes hacerlo mediante un bucle que explore recursivamente todos los nodos de valor igual al valor máximo encontrado.
La recursividad es difícil de entender al principio, sobre todo si intentas hacer "trazas" del funcionamiento del sistema. Yo te recomiendo que no te compliques tanto: no te preocupes de lo que hace el sistema, tú simplemente dale las órdenes y asegúrate de que las funciones recursivas tengan una condición de parada. Así es muchísimo más fácil.
Otro consejo que te puedo dar es que, en estas funciones, primero escribas las condiciones de parada ordenadas de la más sencilla a la más compleja, y finalmente la llamada recursiva.
En fin, no quiero complicarte más. No me hagas demasiado caso, intenta hacerlo a tu manera, tal como pensabas hacerlo antes de leer mi comentario. Si tienes alguna dificultad pues intentaré ayudarte encantado.
Y no te preocupes, me gusta leer tus "chapas", al menos haces preguntas interesantes. ;-) Suerte.

Me entendiste mal, en cada nivel genero una casilla, así en el nivel 1 genera la casilla (0,0) y en el nivel 2 la casilla (0,1) etc. Llamo "nivel" al entero que pasó en mi llamada a backtracking del programa del primer comentario.Y lo de los dígitos binarios, yo creo que si tengo una matriz de 4x4, en una fila tengo las combinaciones 0 0 0 0, 0 0 0 1, 0 0 1 0 etc, que me viene dado por los i desde 0 (0 0 0 0) hasta n elevado 2 menos 1 que es 15 (1111). Es que no me explico muy bien...
Y en eso estoy; generando los números binarios...
Gracias por todo

Ah, vale, ahora sí te entendí.
Pues eso, a ver si sale bien y si hay dudas pues ya sabes ;-)

Hola!, bueno estoy atascada en una tontería, creo yo. Genero los binarios, sin problema, luego los meto en un vector, o eso intento usando:
char[] generador = binario.toCharArray();
Pero a la hora de acceder a los elementos, sólo me deja al primero, si intento acceder al segundo me salta la excepción java.lang.ArrayIndexOutOfBoundsException: 1
¿Qué esta mal?
Gracias

Creo que ya se porque salta, al generar los binarios el cero es un 0 en lugar del 0 0 0 que debiera ser y lo mismo con el 1,2 y 3 que no completan los dígitos por la izquierda. Yo tengo esto
String sBinario = Integer.toBinaryString(miNumero); y he visto por ahi algo de añadir substring(1) al final pero tampoco me funciona...

No sé si conoces los operadores bit a bit de lenguajes como Java o C/C++, pero por si acaso te los explico un poco.
Cada número en base decimal se almacena en la memoria del ordenador como una secuencia de bits que puede ser explorada utilizando estos operadores. Para la solución que te voy a proponer, es necesario que conozcas los operadores << y &.
El operador << en la expresión (a << b) desplaza a la izquierda los bits del número "a" tantas posiciones como indique el número "b". Es lo mismo que multiplicar "a" por 2 elevado a "b". Un ejemplo:
3 << 2 = 12
La representación binaria de 3 es 11, así que desplazado a la izquierda 2 posiciones queda 1100, que es 12.
Otro operador es &, "and bit-a-bit", que hace la operación lógica AND entre los bits de dos números. Con un ejemplo lo verás más claro:
14 & 7 = 6
La representación binaria de 14 es 00001110, y la de 7 es 00000111. Si haces un AND bit a bit:
00001110
00000111
--------
00000110
Es decir, que en cada posición del resultado sólo hay un 1 si en los dos operandos también hay un 1 en esa posición.
Por eso se nos puede ocurrir la idea de utilizar un mecanismo para ir explorando los bits del número e ir añadiéndolos a un String. Así, para saber si la posición "i" de ese número contiene un 1, sólo hay que hacer un AND bit a bit entre ese número y (1 << i). Si el resultado es cero, en esa posición hay un cero. De lo contrario, hay un 1.
De esto se puede sacar una bonita función como la siguiente:
// bin
/**
* Devuelve la representación binaria de un número
* en forma de String.
* @param num Número en base decimal
* @param bits Número de bits del resultado
* @return String con la representación binaria del número
*/
static String bin(int num, int bits) {
String res = ""; // Resultado
// El resultado se configura a través de la exploración
// del número utilizando los operadores bit a bit.
for (int i = 0; i < bits; ++i)
// Si el número no contiene un 1 en la posición "i",
// se añade un cero al resultado.
if ((num & (1 << i)) == 0)
res = "0" + res;
// En caso contrario, se añade un 1.
else
res = "1" + res;
return res;
}
Espero haberme explicado más o menos bien. De todas maneras, si tienes alguna duda ya sabes. Suerte.

Gracias por la explicación, desde luego tu función es más eficaz pero demasiado para mi nivel ;) me ha costado entenderla. Pero ya la he incrustado en mi programa y a seguir!. Gracias.

Me alegro de que te sirviera. Es que con las prisas me explico bastante mal, perdona.

Ya no me queda nada, pero llevo 2 días dándole vueltas a lo mismo, no entiendo porque no entra en un bucle... lo estoy haciendo para un ejemplo concreto y no podo todo, de momento sólo quería que pusiera la primera casilla bien, no pedía gran cosa, pero cuando compara, aunque los valores coinciden, no hace lo que le pido... Si se te ocurre algo que pueda ser... Gracias.
import junit.framework.*;
import java.util.*;
import java.math.*;
public class nanograma {
static int filas[][]={{3,0},{1,1},{1,0}};
static int columnas[][]={{3,1,2},{0,0,0}};
int TOPE=filas.length;
static int TOPE = 3;
static String binario;
static int t ;
static int p ;
static boolean b;                  
    static int conta=0;
    static int nivel;
static int fila,columna;
  static  int mat[][];
    int solH[][];
    int solV[][];
    int contador;
    static int devolver;
    public nanograma() {
        mat=new int[TOPE][TOPE];
//      mostrarMatriz();
       bactracking(1);
       System.out.println("matrices generadas son "+conta);
    }
    public void bactracking(int nivel)
    {
                if (nivel>TOPE*TOPE)
              {
                System.out.println("Matriz solucion  ");
                mostrarMatriz(); 
              }
  else
            for(int i=0;i 0)            
                   p++;
                   t = 0; }
                }
                  //si coincide las sumas de unos con las que tengo en filas
                  //Miro si lo que llevo puesto en la matriz coincide con el vector de binarios que genero esa suma
                   for(int i=0;i<1;i++){
                       System.out.println("s "+s);
                       System.out.println("filas"+filas[0]);
                       if (s==filas[0]){
                        System.out.println("mat "+mat[0][0]);
                           System.out.println("vector "+vector[0]);
                       if (mat[0][0]==vector[0]) {        //AQUI NO ENTRA NUNCA!!
                           System.out.println("hola");
//                        devolver++;
  //                      System.out.println("dev "+devolver);
                        return devolver;
                    }
                }
            }
                    return devolver;
    }
        public void mostrarMatriz(){
        for(int i=0;i<TOPE;i++)
        { for(int j=0;j<TOPE;j++)
             System.out.print(mat[j]+" ");
          System.out.println();
        }
//         System.out.println();
  //        System.out.println();
    //       System.out.println();
           conta++;
           System.exit(0);
            }
    public static void main(String[] args) {
        nanograma x=new nanograma();
    }
}

Ya se porque no me entra, es que esoy intentando comparar un char con un int...
¿Puedo solucionarlo de alguna forma?

Prueba con:
if (mat[0][0].toString().equals(vector[0].toString()))
No lo he probado pero inténtalo y me cuentas, ¿vale? Suerte.

Me dice "char cannot be dereferended"... vaya!nah! No te preocupes.

Perdón, me equivoqué. La condición sería:
Integer.toString(mat[0][0]).equals(Character.toString(vector[0]))
[url|http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Integer.html#toString(int)]Documentación sobre Integer.toString(int)[/url]
[url|http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Character.html#toString(char)]Documentación sobre Character.toString(char)
Documentación sobre String.equals(java.lang.Object)[/url]

Esta cosa juntó dos enlaces en uno. Aquí está el tercero:
[url|http://java.sun.com/j2se/1.4.2/docs/api/java/lang/String.html#equals(java.lang.Object)]Documentación sobre String.equals(java.lang.Object)[/url]
A ver si ahora...