5

I've implemented the algorithms marked as the correct answer in this question: What to use for flow free-like game random level creation?

However, using that method will create boards that may have multiple solutions. I was wondering if there is any simple restrictions or modification that can be made to the algorithm to make sure that there is only one possible solution?

solutions

divibisan
  • 11,659
  • 11
  • 40
  • 58
Åke Gregertsen
  • 185
  • 2
  • 7
  • I was looking at Flow Free levels and none of them is solvable with paths containing U (path going through 2x2 cells). When path contains U, it can always be shortened by 2 cells, so it is not so interesting. – Ivan Kuckir Feb 06 '13 at 00:01

2 Answers2

1

Creating unique Numberlink/Flow Free is very difficult. If you look at my algorithm proposal in the mentioned thread, you'll find an algorithm that lets you create puzzles with the necessary condition that solutions must not have a 2x2 square of the same color. The discussion at http://forum.ukpuzzles.org/viewtopic.php?f=3&t=41, however, shows that this is insufficient, since there are also many non-trivial non-unique puzzles.

From my looking into this problem, it seems the only way to solve this problem is to have a separate algorithm for testing uniqueness, and discarding bad instances. One solver that's made precisely for uniqueness testing algorithm is Imo's solver. Another option is to use multiple different solvers and check that they come up with the same solution.

Thomas Ahle
  • 30,774
  • 21
  • 92
  • 114
0

I think you should implement the solver, which finds all the solutions for some level. The simplest way is backtracking.

When you have many levels, take one by one and look for solutions. As soon as you find the second solution for some level, throw that level away.

Ivan Kuckir
  • 2,327
  • 3
  • 27
  • 46