Win a copy of Java 9 Revealed this week in the Features new in Java 9 forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Tents and Trees puzzle  RSS feed

 
Alex Bru
Greenhorn
Posts: 11
1
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi guys,

I am trying to understand the tents and trees puzzle (maybe you have heard of it, maybe not) in terms of arrays.

This is how a version of the game looks like:

Image



Goal

The goal of the game is to place a tent ("near") a tree such that there are exactly as many tents as indicated by the row and column numbers that you see on the sides of the grid.

My approach

I am not near having a workable solution. As a start, I am denoting my trees in a 2D-array as a "1" and the tents as a "2".
So far so good, I place X amount of "1"s in random locations of the array.

What should come next? Logically, I would think that a tent can only be [X+1][Y], [X-1][Y], [X][Y+1], and [X][Y-1] from the tree, right?

This is what I have so far, although I am getting an IndexOutOfBounds Exception (why?).



Exception:


Do I need a break statement at all?

I know I would still have to figure out how to determine the number of tents in the rows and columns, and so if you have any suggestions, improvements and on how to approach this problem, let them be heard!
 
Paul Clapham
Sheriff
Posts: 22203
38
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alex Bru wrote:Logically, I would think that a tent can only be [X+1][Y], [X-1][Y], [X][Y+1], and [X][Y-1] from the tree, right?


Well, yes, but not quite. If the tree is at the edge of the grid then one or more of those expressions would point to something outside the grid. I haven't looked at your code but the fact that you're getting an IndexOutOfBounds exception suggests very strongly to me that you haven't accounted for that issue.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What I don't understand is how you can place trees and tents at random. You'd think that if this were a puzzle, there would be a specific configuration and a corresponding unique solution.  If you just put trees in the grid at random, wouldn't it be possible to have a configuration that has no solution?
 
Alex Bru
Greenhorn
Posts: 11
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:What I don't understand is how you can place trees and tents at random. You'd think that if this were a puzzle, there would be a specific configuration and a corresponding unique solution.  If you just put trees in the grid at random, wouldn't it be possible to have a configuration that has no solution?


I'm not sure - do you have another method in mind?
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alex Bru wrote:I'm not sure - do you have another method in mind?

Well, I once wrote a Sudoku puzzle solver where I had to give the program the puzzle to solve and then have it go through all the logic to solve the puzzle. I would think that if you were to write a Trees and Tents puzzle solver, you'd have to take the same approach: Give the puzzle with the tents already in place and the hints for each row and column also indicated. The program would then apply logic rules to "deduce" where the tents are supposed to be placed.

On the flipside, you could also write a program that creates the puzzle. I got my Sudoku puzzle solver pretty good that it could solve any beginner to intermediate puzzle I threw at it; however, there were some situations where it, too, was stumped by some advance/intermediate to difficult puzzles. I never did get around to writing a program that could generate a Sudoku puzzle. I guess what I'm trying to get at is that while they are both based on the same set of rules, I think the puzzle creator program is more difficult to write than a puzzle solver program. I think it's a little more difficult because you have to make sure that you end up with something that's solvable.

Since you're not even sure how to approach this, I would suggest you start with a puzzle solver before you try to go for a puzzle creator.  Find pre-defined puzzles that you can use as input to see if your solver can at least handle those properly.

You can probably mine this site: https://www.mathsisfun.com/games/tents-puzzle.html for some basic Trees and Tents puzzles.
 
Campbell Ritchie
Sheriff
Posts: 54033
130
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a reversible Sudoku solver, which I wrote to use a naïve algorithm to show backtracking the best. It took approx. 50 min for one puzzle, which I managed to solve by hand in under 10 min. I can give links to a database of Sudoku puzzles if anybody wants it.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'll have to dig up my Sudoku solver, if I can still find it. That was at least a couple of years ago so it's probably on a backup disk somewhere since I get a laptop refresh every three years and I'm due for another one early next year. I remember I combined a number of different strategies for deducing the solutions, starting with the more common ones that I used to solve puzzles manually then progressing incrementally to include more advance strategies that I learned about through searches on the Internet. I still remember clipping dozens of puzzles from newspapers and magazines, using them as test input for my program.

Anyway, I would think that the Trees and Tents problem has to use a similar approach of deduction, eliminating possibilities based on the hints on each row and column and the rule that no two tents can be "near" each other.
 
Winston Gutkowski
Bartender
Posts: 10573
65
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alex Bru wrote:I am trying to understand the tents and trees puzzle (maybe you have heard of it, maybe not) in terms of arrays.

OK, well first off: Do you want to write a "solver" for the problem, or simply a "checker" or "referee"?
The latter is likely to be simpler, and actually using it to play the game yourself may give you some ideas about how to write a "solver".

My approach
I am not near having a workable solution. As a start, I am denoting my trees in a 2D-array as a "1" and the tents as a "2".

You can do it that way, but it's not very "Objective". One alternative might be to have a Board made up of "Squares", eg:

What should come next? Logically, I would think that a tent can only be [X+1][Y], [X-1][Y], [X][Y+1], and [X][Y-1] from the tree, right?

Seems right, but only you can really know what "near" means in the context of the game. For example, is an adjacent diagonal square "near"?
And as others have said, there are also the "edges" of the Board to consider.

Also: are there any other rules? For example, can two tents be next to each other?

I think if I was doing this, rather than trying to write a "solver", I'd now concentrate on the mechanics of the game.

First: It would appear that you need to come up with a number of Tents to be placed on each row and column, so your program needs to understand every square that it's possible to put a Tent. For example, in your example - and assuming that diagonals aren't "near" - you could put a Tent in any empty square except row 1, column 2 and row 3, column 5.

So my approach - again from your example, which has 7 tents - would be to:
1. Fill the board with every possible Tent (16 total).
2. Remove 9 of them randomly.
3. Calculate the number of Tents in each row and column.

And then of course, there's the issue of checking the result of a player's "solution" ... but hopefully you have a bit to work with.

Winston
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, Winston, in this puzzle, "near" includes diagonals. So, just as in Conway's Game of Life, there are normally eight neighbors for each cell that's not on the edge of the board.

A method that checks for a neighboring cell can adjust for too large or too small of a coordinate by returning EMPTY, if your suggestion to use an enum, which I think is a good idea, were to be followed by OP.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Although the name "Square" for that enum isn't really a good expression of the idea behind the values. The TENT, TREE, and EMPTY values do not represent "squares" but rather what could be in them.
 
Piet Souris
Rancher
Posts: 1828
61
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Suppose you have a method that is able to draw every set of M out of a collection of N (a nice recursion would do), then I would simply start with column 1, generate all possible set ups given the number of tents, and while doing so for every column, check if the number in each row is okay. If not, then reject and go on.

The complexity of this puzzle is much less than that of a sudoku, so I would not compare it to a sudoku puzzle
 
Campbell Ritchie
Sheriff
Posts: 54033
130
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Somebody please remind me how to use Unicode numbers > 0xffff. This Unicode sheet has trees in, e.g. 1f332‑4 and 1f384, and ⛺ is U+26fa. Then you can add those symbols to the enum elements and display them in the squares.
 
Junilu Lacar
Sheriff
Posts: 10884
158
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:The complexity of this puzzle is much less than that of a sudoku, so I would not compare it to a sudoku puzzle

Overall, yes, Sudoku is more complex, but the deductive process you follow is pretty much the same: you have a set of constraints that define what can be placed in each row or column and you have to find an arrangement that fits those rules by eliminating options that do not adhere to the constraints.
 
Liutauras Vilda
Marshal
Posts: 3961
214
BSD
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

Have a cow for the nicely indented code, good formatting, added error message and after all for used code tags.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!