Jump to content
DFPA46

Resolver Nonograms

Recommended Posts

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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
DFPA46

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

Share this post


Link to post
Share on other sites
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 by DFPA46

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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..

Share this post


Link to post
Share on other sites
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 ...


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

- primeira iteração : brute force


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.