9
$\begingroup$

first of all this is my first time asking something here so please let me know if I am doing something wrong or asking it on the wrong place.

I have a custom puzzle model where I need to generate different puzzles difficulties, but I am having some problems making sure that the method that I use ensures that there is only one possible solution to solve it.

The puzzle is actually pretty simple, it consists in a board that can have any given size, but lets only consider a 4x4 so its easier to explain, the goal of the puzzle its to fill the entire board using only 'X' or 'O', and we can only have 2 symbols of the same type together in any direction, in other words you can´t have 3 or more equal symbols in the vertical, horizontal or diagonal, and there is also some locked squares, where you can´t play, they work as the ones in crosswoards.

Example of a well solved puzzle:

Well solved Puzzle

The puzzles are suposed to be generated with some clues and with all the blocked squares, and they are suposed to be generated with one of two difficulties, easy and hard. A easy puzzle can be solved only using logic, similar to a easy sudoku, wich means if you keep "blocking the sequences of two" you will end up solving the puzzle completly, meanwhile the hard ones they require more thinking, you need to make guesses to be able to solve them.

Examples of puzzles with different difficulties:

Easy Puzzle(Easy)

enter image description here(Hard)

At this point I can generate the two difficulties, the method that I use to generate the easy ones pretty much consist, after filling a board in a random way, recursively remove the 3rd element of the sequence, in other words the one that is diffrent, if I keep doing that untill its not possible anymore, I will end up with a puzzle that only has one way to be solved I believe, doing the same process, but backwards, even if you do it in a differente order there should only be one way to complete the board.

The problem starts when I try to generate the hard puzzles, I will now the explain the method that I use:

-Due to the fact that a given point a hard puzzle becomes a easy puzzle, I start for execuing the algorithm that generates the easy puzzle.

-Now that I have a board with a puzzle thats easy, I will try to remove some of the clues, so to test if I can remove it, what I do is to try to solve the puzzle with the opposite symbol on that position, if its not possible to solve it with the different symbol, that means I can remove that clue, because, that means that I will always need to have the same symbol in that postion, so I will always end up with the easy puzzle where I started. Once again I keep doing this same thinking for all the clues.

At this moment this seems to work very well, and at first sight the puzzles created seem to have actually a unique solution, but I am not entirely sure, so can anyone please help me to make sure if this works?

Thanks for the attention.

$\endgroup$
  • $\begingroup$ Welcome to puzzling! You can take a tour here to earn a badge, and learn more about the site. $\endgroup$ – CaptainPlanet May 31 '18 at 18:24
  • $\begingroup$ One thing I don't understand: You state that the board "can only have 2 symbols of the same type together in any direction", but the hard puzzle contains 3 similar symbols from the start!? Am I missing something? $\endgroup$ – Wolff Jun 1 '18 at 16:38
  • $\begingroup$ @Wolff Maybe I wasn´t very specific I am sorry. I meant to say that three equal symbols can´t occur all together, the sequence needs to be stoped. For example somethyng like: XXX is not valid, but something like XXOX is correct. $\endgroup$ – Sentry Jun 1 '18 at 23:42
  • 3
    $\begingroup$ @Wolff His puzzles are basically this with a modification. $\endgroup$ – dcfyj Jun 29 '18 at 12:44
  • $\begingroup$ How do you define an easy/hard puzzle? Is easy the sort where you can get the solution by applying the rule in only one line at a time and putting a suitable symbol and hard where you have to make more complex thought processes? E.g., in your easy example, first such step is: there are 2 O-s with a blank in between, so that can't be O, it's X. Then you have X_X and the blank has to be O. Then there is vertical OO_, so the blank has to be X etc. But your hard example doesn't have anything where you can make such step so you have to consider several directions and several blank squares together. $\endgroup$ – Heimdall Aug 24 '18 at 20:31
2
$\begingroup$

If it's not possible to solve with the other symbol, then you are basically doing the precise inverse of guess&check, which means that it will have a unique solution, since the other remaining symbols give enough information to guarantee that symbol that you have removed, so it does not remove required information. Does that explanation make sense?

$\endgroup$
  • $\begingroup$ Yep, I support this idea. If we change a symbol with its opposite and try to solve it and get some contradictions a.k.a unsolvable, then we can remove that symbol because puzzlers will learn that in that position there will be only a single symbol can be used which is the removed one. $\endgroup$ – athin May 29 at 3:30
1
$\begingroup$

Your logic is correct. The resulting puzzle can indeed be solved in a relatively straightforward way as you described.

First, assume that the red square shown is O (marked with a 1)
solution
Then the subsequent deductions can be made in numerical order, quickly leading to a contradiction.

Given this,

That square must be an X. And you can deduce your way to a unique finish from there.

Of course, this doesn't prove that it always works, but the logic is good and this example works.

$\endgroup$
  • $\begingroup$ Your second solution has triple X diagonal, R2C5 to R4C3 $\endgroup$ – athin May 29 at 2:16
  • $\begingroup$ Thanks. I've changed the solution. Shouldn't have rushed... $\endgroup$ – Dr Xorile May 29 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.