2

I'm reviewing a programming problem from a local programming contest.

You can download the problem http://www.vlaamseprogrammeerwedstrijd.be/2011/opgaves/cat2-2011/loodgieter.pdf. It's in dutch but the pictures will help to understand it.

You receive a m*m grid as input with some pipes and some missing spots (the questionmarks). The remaining pipes have to be placed in the grid so that they connect with the others.

Each pipe is represented as a letter (see picture on page 2). The letter 'A' has value 1, 'B' has value 2,..

Does someone knows how to solve this problem by backtracking in Java?

Luc Peetersen
  • 133
  • 1
  • 9
  • will clojure do? see the 5 articles at http://isti.bitbucket.org/ ; there's also some discussion at http://stackoverflow.com/questions/9689436/backtracking-solution-for-programming-exercise-fitting-pipes – andrew cooke Apr 08 '12 at 22:36

1 Answers1

0

i would suggest to collect all your knowledge about the game:

  • boundaries are newer connected
  • the pipes are connected to eachother
  • ? i don't really understand dutch ;)

select a representation which describes the puzzle's at every cell there are required connections (which are implied by the already placed pieces) and can be some optionals which may or may not be connections

write the placing handler which updates these attributes when a piece is placed into the board

create the logic which decides if a part can be placed at a specific position or not.

at this point start with an empty board and place the parts you know

start a recursion which does the following:

  • selects the first empty cell
    • if there is none copy current board to output (solution)
  • for every availibe piece it trys it if it would fit
    • if it does, places it and recalls itself

i hope you put it together, this is a nice puzzle, note i play every day with: daily expert netwalk, it's a kind of similar to this, the heuristics there can be used, can be applied on this too problem as well.

Zoltán Haindrich
  • 1,788
  • 11
  • 20