1

Please help me by refering the Algorithm Name or if you have any good source code to solve the problem

To understand the problem,

Here's some input in JSON Format Correspond with Their Initial Map Picture

{"wallX":[0,2],"wallY":[0,2],"startX":0,"startY":1,"maxX":3,"maxY":3}

enter image description here

{"wallX":[],"wallY":[],"startX":1,"startY":4,"maxX":6,"maxY":6}

enter image description here

The Rules

  1. 99 represent the wall. X&Y of wall[index] is represent by wallX[index] and wallY[index].
  2. 01 represent the starting point of the Snake. X&Y of 01 is represent by startX and startY
  3. maxX represent the column of the 2D array while maxY represent the row of the 2d array. Both maxX and maxY <= 9
  4. On The initial 2-D Array / Map, any tile which is not 01 or 99 will be Tile 00.
  5. Snake can only Move to 00
  6. Snake move 4 ways[left,top,right,bottom]

The input of the program is those JSON format.

The output of the program should be :

  1. 2-Dimension Array consist of 99 and/or (01 to 0X) with no 00 Tiles left which represent the map is solved
  2. Initial 2-D Array which represent there is no more possible move left but there is at least 1 of 00

Here's Some other Input Correspond with Their output's 2D Array picture

{"wallX":[0,0,1,2,3,4,5],"wallY":[0,4,5,1,1,1,4],"startX":0,"startY":3,"maxX":6,"maxY":8}

{"wallX":[0,1],"wallY":[0,1],"startX":0,"startY":1,"maxX":2,"maxY":2}

""

{"wallX":[0,2],"wallY":[0,2],"startX":1,"startY":1,"maxX":3,"maxY":3}

enter image description here

I have made my own source code to solve this problem, but i want to find the algorithm so i can study more on how to actually deal with this/related algorithm/problem.

  1. I tried to search on google, with keyword such as "Fill" but most result showing me [Flood-Fill-Algorithm]. Most Flood Fill that i read, can't be applied here since The Snake or [LastNumber] have to be Adjacent to [LastNumber+1].

  2. I also tried to find about Pathing, but it seems PathFinding works if there is Start and Destination, but this problem doesn't seem have any clear Destination.

Please correct me if im wrong about these ^

Thank you in advance for your help

c0der
  • 18,467
  • 6
  • 33
  • 65
Yogie Soesanto
  • 172
  • 1
  • 3
  • 13
  • This is a hard problem. It's equivalent to finding a Hamiltonian cycle in a graph (cells are vertices; adjacent cells have an edge). https://en.wikipedia.org/wiki/Hamiltonian_path_problem – Dave Mar 04 '20 at 19:43
  • @Dave The fact that problem X can be specified as a special case of NP-complete problem Y does not mean that X is NP-complete. So the problem of finding Hamiltonian cycles in rectangular grids with some omitted nodes might be polynomial even though the same problem for general graphs is NP-complete. – btilly Mar 05 '20 at 00:32
  • For this case, see https://www.hindawi.com/journals/jam/2012/475087/ showing some success for solving this kind of problem for some rectangular shapes. Given that that is published research and a simple version of the general problem, it suggests that the problem is hard. But it may still be possible. At the least, the necessary test "even number of black/white squares on a checkerboard pattern" can let many arrangement of walls be recognized quickly as impossible. – btilly Mar 05 '20 at 00:37
  • I suspect Hamilton path in arbitrarily walled grid graphs is hard, but Angluin--Valiant may be a decent heuristic in practice: https://stackoverflow.com/questions/15898884/fill-2d-grid-with-single-path/15904295#15904295 – David Eisenstat Mar 05 '20 at 03:09
  • NB: it is strange to see a property named "maxX" when it does not provide the maximum value for X, but one more -- since your examples show a coordinate system is zero-based. Better names would be "sizeX" or "endX". – trincot Mar 05 '20 at 14:13
  • @btilly It's NP for subgraphs of a lattice or square grid graph (according to the wikipedia article) – Dave Mar 06 '20 at 11:33

0 Answers0