function for binary vector *puzzel solver*

1 次查看（过去 30 天）
eyal lampel
eyal lampel 2013-7-25
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);
%==================================================%
The problem is that brute force is only practical for rowLength < 16
and in a typical puzzel row length is 20-25 .
can someone plz guide me how can i solve this problem without
brute force the solution??
THANKS LAMPEL.

请先登录，再回答此问题。

回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Just for fun 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by