Help needed trying to write a program to solve a puzzle

[groston]

Just for fun, I have been trying, far less than successfully, to write a program to solve Einstein's Riddle Logic Puzzles, see https://play.google.com/store/apps/details?id=com.rottzgames.logic.

I code the board as layers, columns, and items. Each rule is them translated into two layer/item pairs; for example, a textual rule can become 1C-4B. The program I have written properly executes all of the games ‘rules’ and it also looks for a single item on a layer and recognizes that that must be the item in the column in which it appears. In fact, for one super simple game, my program actually came up with the correct answer. However, as I try the more reasonable puzzles, the answer is not correct. For example, in the game Hard:#1, there are five layers and six items. Thus, a proper result would have just six ‘columns’ of results. However, the best I have been able to do is 19 columns (and in these 19 solutions are the correct six).

I am clearly missing something to eliminate the extraneous 'solutions' (which are wrong!). I have looked over this particular game in great detail, but do not see any way to use an indirect approach to help eliminate some of the wrong answers.

So, please, if you have any insights, algorithms, etc., please share. Please.

[plasmid]

We'll have to see the algorithm and what it's doing in order to say much. Could you share it and walk through how it would handle an example Einstein puzzle that folks without the game could follow (say the one at https://web.stanford.edu/~laurik/fsmbook/examples/Einstein'sPuzzle.html)? If you solve the puzzle the old fashioned way and keep track of what you eliminate and why, is your algorithm able to recreate the path to the solution? If not, then what parts is it missing?

[groston]

Plasmid,

Thanks for the reply. Please note that, at best, I am a hobbyist, so I am not sure if my code meets your need for ‘an algorithm’.

I have attached my code – not too much of it. I have also attached the input file for a particular game. In this case, the game is from the cited app, difficulty ‘hard’, puzzle number 1.

Here are some more comments about the code:

• Structure AllSolutions – a large array with every possible solution
• Structure gboard – an array the size of the puzzle that shows what is still there

Description of code

• Lines 57-109: read in the input file, including the images and the rules
• Lines 111-152: configure both of the above arrays. Note that the arrows are for the display, nothing else
• Lines 155-285: execute a rule
•   Lines 158-165: clean up the gboard array
•   Lines 168-186: remove solutions that are not viable from the AllSolutions array
•   Lines 189-198: rebuild the gboard array
•   Lines 201-209: figure out how many viable solutions there are in each spot of the gboard array. Note that if there is a column with only one solution, that must be the solution in that column, so eliminate that item from other columns.
•   Lines 213-284: Do the above and keep repeating as long as any changes to the board are made
•   Lines 287-403: Display the board

The issue that I am having is trying to figure out what part of the algorithm I am missing! The above approach, for the above problem, should have exactly six answers – one for each column (and the number of columns is the same as the number of items). With the above, I get 19 answers – what am I missing???

fMain.vb Hard01_Input.txt

[plasmid]

The first thing that jumps out at me is that when I do Einstein puzzles by hand I usually need to do many iterations of going through the rules and filling out as much as I can, and then going through the rules again to narrow things down further based on what I’ve eliminated so far. In this case there’s a single loop of

For cr = 1 to cntRules

that gets executed once, as if a human were to just go through all the rules once instead of iteratively. If you as a human are able to solve the puzzle by going over each of the rules once in the order that they're presented, then the program should work. Otherwise maybe it would help if you wrap the for/next loop of cr in a loop similar to the one you currently have with bDoAgain checking for any changes since the last iteration before letting the program end.

If you can go through this particular Einstein puzzle by hand and complete it in a single iteration (so the above isn't applicable), then could it be an issue with how the rules are encoded? I'm afraid I can't get the app working, but I’m used to seeing things like “The plumber lives in a house to the left of the guy who goes birdwatching on Thursdays” which aren’t so easily encodable with a plus/minus system.

[groston]

plasmid - Your observation is correct, with the added issue of having to select the first row from which to solve the puzzle manually. However, I suspect that by creating the AllSolutions structure, that multiple iterations should not be needed. However, as stated previously, there is a step/process missing from my solution. Also note that if the main algorithm were to be repeated again, I seriously doubt that the answer would change...

Edited November 9, 2020 by groston