- 2

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!

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.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

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?

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.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

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.

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

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.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]

The complexity of this puzzle is much less than that of a sudoku, so I would not compare it to a sudoku puzzle

`enum`elements and display them in the squares.

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.

Practice mindfully by doing the right things and doing things right.

[How to Ask Questions] [How to Answer Questions]