6/7/2023 0 Comments Hexcells toucharcade![]() Initially I was suprised how fast it was (even though it's just brute-forcing all the possibilities of some sub-sets of all cells) Yeah :D I wouldn't want to do that either And it's really awesome that your implementation allows to convert levels into. OCR is a pain, I remember doing that for some programming project a few years ago. Still, your implementation is really impressive considering you did everything by hand (and did it from a screenshot instead of an abstract representation!). So in practice it seems to be feasible with the right tools. The hardest levels I came across could still be solved in a second or so. Solving Hexcells is NP-hard but there are pretty good MILP solvers out there (the sixcells implementation uses glpsol by default). I'm pretty sure writing a complete solver would be NP-complete I assume the “examples”-folder shows cases that you cannot solve, right? In case there is a cell that is blue or black in every valid assignment, then this cell can be revealed.Īs an optimisation you also generate some redundant hints that are implied by other hints (but potentially more handy sometimes). those that do not conflict with any hint. Then you go through all assignments of blue and black to cells in D (those are 2 |D| possibilities) and filter for valid assignments, i.e. You consider every set D of cells that is the domain of a hint, for example one column or one ball of radius 2 around a labeled blue cell. Ok, let me say it in my own words, to check if I understand this correctly (I'm a bit too lazy to go through all the source code): I need to wait 2 seconds before grabbing a new screenshot (so these annoying particles are gone, they confuse my OCR) and the TSP calculations for the execution path are also not really fast (and to be fair not really optimized ^^) I really optimized the iterating through all possibilities, If you think the program is slow thats not because of the solving (the solving takes most of the time around 500ms).the levels are designed for humans to solve, and this aproach is similiar to a human one (or at last to mine).I think the main thing that makes this work is: I start with the small sets (quicker to calculate) and continue with the bigger ones. ![]() If for all combinations a cell is either active or inactive this is a solution :) No I went through the hints and tested all possible (and valid) combinations of active/inactive cells.Then I try to combine them together (in this set A are 4 active cells and in set B are 10.First I collect all the "Hints", eg "in this set of cells are n active ones and they are non consecutive".So I tried to orient my solver at a kinda human aproach: I'm pretty sure writing a complete solver would be NP-complete, and so not really feasible. I fucking needed to write my own OCR algorithm to get these stupid little numbers from the screenshots.Ī few images of the analyze process: (more on github) But the real thing that took almost two weeks to get right is the character recognition. Oh and if someone tries to do something similiar in the future: I initially thought the problem would be solving the puzzles. If someone is interested in the code is on github and while not really documented, I tried to not write a complete mess :) Find the optimal path to execute the solution (wit the shortest mouse path).Show the next calculated solutions (if you only need a hint).The result is a program which solves Hexcells levels completely autonom ( see this screen-recording) in about one minute each. Then it tries to find solutions with the avaiable hints and if needed it can also execute them. My program is capable of automatically take a screenshot of an puzzle and extract the current gamestate out of it (No cheat-y RAM-reading or similar). Over the last few weeks I coded an Hexcells solver (I complete under-estimated the time this would take): > Download
0 Comments
Leave a Reply. |