Witchess Puzzle Solving: Discussion

There are a finite number of valid witchess paths for an empty board of any fixed size, so at the very least, witchess solutions can be calculated in finite time with brute force. In order to do this, the following needs to happen:
  • visit_url( ) to the page, and parsing
  • creation of a model
  • generation of solutions
  • testing of solutions (many may be possible)
  • inputting the solutions into the page (probably with a POST visit_url( ))
Now, how to do this?
 
There are a finite number of valid witchess paths for an empty board of any fixed size, so at the very least, witchess solutions can be calculated in finite time with brute force.

It sounds like you're seriously underestimating the increase in possible paths as grid size increases.

This link shows the number of valid 'self-avoiding walks' (e.g. valid witchess paths) for some grids of various size: http://www.ms.unimelb.edu.au/~ij@unimelb/saw/series/saw_cross.ser

Note that, for example, an 8x8 witchess grid has 3,266,598,486,981,642 valid paths. And that there are witchess grids in game significantly larger than 8x8.

EDIT: This isn't to say that an automated solver is unfeasible, but you'd need to dramatically cut down the problem space and use some heuristics. The mechanics of witch pieces would really screw with that too.
 
Last edited:
I imagine you would very quickly get your account banned for this style of brute forcing, considering the number of server hits involved.
 
I know, don't actually use brute force. Even if that is necessary, it's always possible to test the solutions locally before submitting them. I just used that to say that there has to be a finite number of possibilities, so it has to be possible to solve in finite time; any smarter algorithm is guaranteed not to run infinitely.
 
Last edited:
I think I just got the response part down. http://127.0.0.1:60080/witchess.php?sol=7,2|8,1|8,3&ajax=1&number=5 will post and get a checked solution from the server for puzzle #5 with links at (7, 2), (8, 1), and (8, 3). The response is very simple:

<html><head></head><body>[false,"Nope",null]</body></html>

and can be processed with a matcher or a direct string comparison.
Curiously, the correct response is:

<html><head></head><body>[true,"Not Yet",null]</body></html>

Now what remains is:
  • Figuring out the coordinate system and converting it with L/U/D/R notation
  • Sanity/Correctness checking for solutions
  • Intelligent finding of solutions
 
Last edited:
3,266,598,486,981,642 server hits for an 8x8 doesn't sound too bad.

Okay, so what I'm getting is that an ideal solution probably works bottom-up rather than top-down; build possible solutions in a highly restricted way rather than spam solutions and start eliminating.

Anyway, since we know the rules by now, we can always privately test solutions before submitting them to the server. You'd never have more than 1 unless your code is terrible at testing.

My question is right now, how do we find solutions? What is a non-brute-force way to solve Witchess?
 

heeheehee

Developer
Staff member
There's nothing wrong with pruning branches that cannot potentially yield a solution, but then you need to understand how that works.

I'd suggest working out some of the higher-difficulty puzzles and seeing what sort of tricks you use, then trying to see how to encode that in a systematic fashion.
 

Crowther

Active member
I just used that to say that there has to be a finite number of possibilities, so it has to be possible to solve in finite time; any smarter algorithm is guaranteed not to run infinitely.
This is true for pretty much every problem I can think of, including breaking the cryptography on that iPhone the hard way (brute forcing the 256-bit AES key). There are finite numbers that are so big they may as well be infinite.
 

xKiv

Active member
any smarter algorithm is guaranteed not to run infinitely.

Have you seen the video they linked on twitter: https://twitter.com/asym/status/706672074933170176 ?
The algorithm may be guaranteed to finish in finite time, but that doesn't mean it will finish before the universe does.

Fortunately, there are *some* shortcuts.
For example, a pawn that's too far away from other pawns/oxen/knights can have only one solution along its edges. Bishop and king can have only four. Rook only 6. A witch will probably be best solved by looping over figures to ignore. Bruteforcing those combinations first, trying to stitch them together in a permissible way, may bring the number of combinations down quick enough. Or not.
 

digitrev

Member
If there are no witches or queens, any black/white pieces beside each other will need the path to go in between them.
 
Granted, it is harder to solve than to generate a problem.
However, it's also
In addition, unlike cryptographic hash algorithms, small permutations produce predictably related results. From one almost-solution you can find full solutions, etc.
We just need an efficient way to converge to a solution.

I have two ideas to speed up the process.
One is bottom-up and involves a sort of messed-up A-star graph search, where edges are assigned dynamic weights based on their neighbors. Then at each step, we sort the three new directions' weights (say, left=2, down=0 up=-infty) This will allow us to prevent exploring paths where there is already. If all of those paths prove impossible, then we can back up a step. This can be done pretty easily given an array and something like a list or a stack.
It's a small size list (3) so we can use quick comparisons to sort. If we need to look ahead further than 1 step, I have already a basic insertion sort written that I use for diet purposes. To deal efficiently with edged pieces (like the bishop) we can check for those as neighbors and factor that into the dynamic weight. This won't improve our absolute performance much but will improve theoretical performance.

My other idea is related but top-down: use zoning of oxen and knights and pawns to cut down on the edges. There are a limited number of positions and orientations for all of the pieces like knights and oxen, so we can generate them one at a time, test them for collision (with other colors, other zones, or other pieces), assign higher weights to outer edges, assign "impossible" weights to bisecting edges, and if witches are present, generate random eliminations. For each space-map of the board, we can then start gnerating a path.

This starts to get complicated though if you start to account for touching edges and zones that are set up againsy the border.


Assuming Jick isn't deliberately generating puzzles that such an algorithm is weak to, this should help most of the time. I think.
 

Crowther

Active member
The problem is, just checking a single path to see if it is a valid solution can be hard. Even KoL is having trouble. And some of the boards are HUGE. Even with a good heuristic you're looking at searching a massive problem space.

EDIT: That says, I guess Ezandora wrote one.
 
Last edited:

Crowther

Active member
Where is it?
You're reading the same rumors I am. It is possible that simply because Ezandora made so many solutions to a few puzzles some people assume there is a generalized program doing. Or they have inside information. I don't know Ezandora.

EDIT: Fix bad copy/paste of name.
 
Last edited:

xKiv

Active member
Where is it?

's_law "speculates" it's where all her private scripts are
(in the same thread linked by crowther).

I think I saw her metion it in /hardcore, so I don't doubt the script's existence. I think that solving "how to write a solving script" is easier than solving all the puzzles by hand (but still not easy at all; I mean, for me the target would be "easier than too much work to bother").



Ezandoras.

Nit: her name is Ezandora. The s is absent.
 
Top