[Community Puzzle] Nurikabe

https://www.codingame.com/training/expert/nurikabe

Send your feedback or ask for help here!

Created by @Djoums,validated by @Q12,@Madina_T and @PaarthThePro.
If you have any issues, feel free to ping them.

Hello,
All tests work fine, but Validator 1, 6, 10 and 11 are KO.
I’m working with python.
Do you have any suggestion to help me ?
Thank you

To miss validator 1, you probably incorrectly handled a basic case (area of ​​islands is its clue, islands don’t touch each other, no 2x2 sea square, ocean is continuous).

To pass tests 10 and 11, being more subtle than brute force is required.

1 Like

Has validation 11 something special ? Bigger complexity than tests 5, 10 or 11 ?
All my tests are green, tests 5 and 10 take a bit more than a second to execute… could it be a timeout ?

Is there a time out? I have all solutions in less than 6 seconds

Hi, all mine are green too, I have a 0,7s time for case 11, all others below 0.5s, and I tested a time.sleep(4.2) for the easiest cases which means they don’t time out before at least 4s.
I don’t get it I can’t make the validator number 11 (all others pass), since for very hard puzzles I find on the my program solves them. Could the creator @Djoums help on this issue? Thanks

I sent it via pm to both of you.
If you notice something peculiar about it please tell, it is not meant to be special.

Hi, I received your message thanks. Finally made it, my code is probably still quite messy but it was fun and interesting. All the best

Hello,
First of all - thank you for creating this awesome puzzle!
Tests are very nice and helpful, there’s quite a lot of them.

Some tips for future solvers:

I tried to solve in C#, but make sure that you know what’s the time limit for the exercise - for me it seems to be about 1.9-2s. If all your test cases pass but you’re failing on some validators - you’re most likely timing out. Make sure to improve and optimize your solution so that all of them will pass under the time limit (I’m not sure if time limits are different for various languages - be sure to check yours!)

As long as you implement most logical steps and pass all test cases - you should be able to eventually overcome the challange. Well worth it!

Good luck everyone :slight_smile:

1 Like

Hi,
This puzzle is great but difficult for me. I implemented an optimized dfs with few pruning techniches introduced in paper[1] in C++. It passed test 1,2,3 and validator 1,2,4, timing out on other testcases.
I feel surprised that this puzzle can be solved by Ant Colony Optimization[2]. I’ll come back later and try to solve this puzzle in this way.

Reference:
[1] Chen, Shi-Jim Yen Jr-Chang, Tzu-Der Chuang, and Shih-Yuan Chiu. “Nurikabe, heuristic search, puzzle.” Game Programming Workshop. 2009.
[2] Amos, Martyn, Matthew Crossley, and Huw Lloyd. “Solving nurikabe with ant colony optimization.” Proceedings of the Genetic and Evolutionary Computation Conference Companion. 2019.

Hi,
I found it difficult too. Solved passing through a loop that consecutively implements basic Nirukabe solving technics as described on https://www.conceptispuzzles.com/index.aspx?uri=puzzle/nurikabe/techniques. If this can help, python is fast enough.