function for binary vector puzzel solver

Question

eyal lampel 2013-7-25

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/83128-function-for-binary-vector-puzzel-solver

hello all,

i am tring to make a nonogram/gridller solver using matlab , for this task i need to create a function that takes a "clue" vector and a row length and return a matrix with all possible solutions for the given clue .

see exampls below.

Input: clue , rowLength

Output : possibleMatrix

*************************

examples

Input: -----------------------------------------> Output

3 one's followed by 1 one in a vector length 5, there is 1 solution

clue=[3,1] rowLength=5 -----------> possibleMatrix=[1,1,1,0,1]

**********************************************

clue=[1,3] rowLength=5 -----------> possibleMatrix=[1,0,1,1,1]

**********************************************

clue=[1,2] rowLength=5 ----------->possibleMatrix=[1,0,1,1,0];[0,1,0,1,1];[1,0,0,1,1]

**********************************************

clue=[1] rowLength=5 ----------->possibleMatrix=[1,0,0,0,0];[0,1,0,0,0];[0,0,1,0,0];[0,0,0,1,0];[0,0,0,0,1]

**********************************************

clue=[1,1,1] rowLength=5 ----------->possibleMatrix=[1,0,1,0,1]

**********************************************

clue=[4] rowLength=5 ----------->possibleMatrix=[1,1,1,1,0];[0,1,1,1,1]

**********************************************

clue=[1,1] rowLength=5-->possibleMatrix=[1,0,1,0,0];[0,1,0,1,0];[0,0,1,0,1];[1,0,0,1,0];[0,1,0,0,1];[1,0,0,0,1]

**********************************************

clue=[9] rowLength=10 ---->possibleMatrix=[1,1,1,1,1,1,1,1,1,0];[0,1,1,1,1,1,1,1,1,1]

**********************************************

my solution :

I take the clue and create a basicVector

for clue=[1,2] rowLength=7 ---> basicVector=[1,0,1,1,0,0,0] I then brute force all possible permutation of basicVector , and remove all wrong rows using "RemoveIncorrectRows" function

Code:

    %%%%%%%%%%%%%%
    clue=[1,1];
    rowLength=5;
    %%%%%%%%%%%%%%
    %===create a basic vector from clue================%
    createVector=[];
    for i=1:length(clue)
    createVector=[createVector ones(1,clue(i)) 0];
    end
    if rowLength>length(createVector)
    createVector=[createVector zeros(1,rowLength-length(createVector))];
    end
    %==================================================%
    %====all possible permutation of basic vector=====%
    a=createVector;
    n=size(a,2);
    k=sum(a==1);
    c=nchoosek(1:n,k);
    m=size(c,1);
    b=zeros(m,n);
    b(repmat((1-m:0)',1,k)+m*c)=1;
    possibleMatrix=b
    %==================================================%
    %====remove incorrect rows from possibleMatrix=====%
    possibleMatrix=unique(possibleMatrix,'rows');
    %a function that remove incorrect rows from possibleMatrix%
    possibleMatrix=RemoveIncorrectRows(possibleMatrix,clue);
    %==================================================%