Resolver Nonograms

[DFPA46]

Boas,

tenho um projecto em mãos que consiste em resolver um nonogram 20x20 (para quem não sabe pode encontrar aqui informação e jogar tbm 😉 : http://pt.puzzle-nonograms.com/) a partir de um ficheiro .txt de entrada com o seguinte formato:

//dimensão da grelha

20

20

//entradas das linhas (o primeiro destes números corresponde à dimensão do vector de inteiros da

primeira linha do puzzle; os restantes números da sequência formam o vector.)

1 2

1 2

3 4 2 2

5 4 1 1 1 1

4 2 1 3 1

3 2 1 7

4 1 3 3 2

2 10 1

5 8 2 1 1 1

3 8 1 1

4 9 1 1 1

4 3 8 1 1

2 2 12

4 3 2 4 3

4 2 2 4 3

3 3 4 2

2 3 2

3 2 1 2

2 5 4

2 4 2

1 6

//entradas das colunas (o primeiro destes números corresponde à dimensão do vector de inteiros da

primeira coluna do puzzle; os restantes números da sequência formam o vector.)

1 9

2 9 3

4 4 4 1 1

3 1 2 8

3 4 9 1

4 2 7 1 1

2 7 1

3 1 5 1

3 8 5 1

4 1 3 7 1

5 1 2 2 3 1

5 2 1 2 2 1

3 2 4 1

4 2 1 4 1

6 1 1 1 1 2 1

4 1 2 1 2

3 8 1 2

1 4

1 2

Posto isto, não sei que estrutura de dados usar para guardar e manipular os dados, que seja, preferencialmente, fácil de programar, que não exija memória em excesso e que não influencie o tempo de execução em grande escala.

[HappyHippyHippo]

com uma simples matrix de 20 por 20 ... não será necessário mais do que isso

[DFPA46]

e já agora, alguém tem ideia de um algoritmo que se possa usar neste tipo de puzzles?

[HappyHippyHippo]

o primeiro de todos : brute force

[DFPA46]

como assim?

[HappyHippyHippo]

tentar todas as possibilidades

[DFPA46]

e isso não e ineficeinte e nao tem um tempo de execução enorme? e que num 20x20 temos inúmeras possibilidades...

Edited April 26, 2013 at 08:58 AM by DFPA46

[HappyHippyHippo]

o tempo de execução não deverá exceder os minutos, por isso não te preocupes com isso ...

[DFPA46]

e que algoritmo mais eficiente é que posso usar? e que tem de ser o mais eficiente possivel, e o brute force embora seja tentador de se usar é ineficiente..

[HappyHippyHippo]

existe alguma razão para que a eficiência seja para ter em conta ?

faz primeiro pro brute force e depois pensa em passos para simplificar o processo ...

[DFPA46]

sim a avaliação desse mesmo projecto... 😉

[HappyHippyHippo]

então aprende que não só a aprendizagem mas como o desenvolvimento em geral é um processo iterativo

- primeira iteração : brute force

[Jimbrix12345]

Estou a fazer algo semelhante...

Chegou agora a parte de guardar todas as possibilidades de uma linha num array. O problema é que nao faço ideia do nº que vai ter (depende de linha para linha, puzzle, nº peças, etc)).

Como posso fazer isso?

[HappyHippyHippo]

Estou a fazer algo semelhante...

Chegou agora a parte de guardar todas as possibilidades de uma linha num array. O problema é que nao faço ideia do nº que vai ter (depende de linha para linha, puzzle, nº peças, etc)).

Como posso fazer isso?

um problema correcto só tem uma solução

[Jimbrix12345]

Não é isso que quero dizer.

Quero parte de guardar todas as possibilidades de uma linha. Guardo onde? Além disso eu não sei o tamanho que vai ter.

[HappyHippyHippo]

Quero parte de guardar todas as possibilidades de uma linha.

sum solução = uma possibilidade

Guardo onde? Além disso eu não sei o tamanho que vai ter.

o tamanho está definido no problema