Author |
Message |
pnm ![](fl/ua)
Posted on: Wed Sep 21, 2011 12:37 pm
Posts: 3304 Joined: Thu May 12, 2011 11:58 pm
|
![](./images/icons/misc/thinking.gif) describe your solver
Hello,
Every once in a while, either because somebody writes to me, or I notice something odd in the solving times and ask about it, it turns out a programmer and Calcudoku enthusiast has written a solver.
I'm absolutely fine with people using an automatic solver, and, as a programmer, am always interested in how it works, what language it was written in, etc.
Of course, puzzle etiquette requires that you don't use it to get a good ranking in the "first solved by" list, and the timed puzzle rankings.
That said, I thought it'd be interesting to start a thread about solvers. So if you've written one, do share! How does it work? What puzzles can it (not) do? How fast is it? etc.
I'll join in later and write something about my solver.
Patrick
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
nicow ![](fl/nl)
Posted on: Wed Sep 21, 2011 4:11 pm
Posts: 84 Joined: Fri May 13, 2011 9:37 am
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
Hi, I'am Nicow from the Netherlands.
My solver is made in Excel 2000 and runs in Win XP on an 11-year old machine with PIII on 733 MHz.
For every puzzle size is a workbook. And one workbook with links to them and contains most of the macro's. The macro's are for assisting inputting the puzzles, and for the searching part of the solving process.
All calculation is done by Excel itself. The workbook contains the range for the puzzle itself, for partly solved on cell- row column- and element basis, a field of kandidates, a table of every puzzle element, a table of every cell and a stack for the searching purpose.
The solving is in three stages: recognising, doing logic and searching.
The tabel of every cell calculates remaining candidates, using a user definened formula. Used logic is minimalised to naked pairs. So naked triplets are not recognised.
In this way Excel calculates every possible figure in a certain situation. After a few rounds the solving process wil stop, due to lacking logic or due to the need of trying out possible candidates. When searching is needed, Excel remembers the halfly solved puzzel, and uses this as beginning point of the seaching proces. All tried out candidates are stored in the stack. Sometimes the stack is 12 deep used. The user defined formula can calculate elements up to 7 cells. In this model every cell is calculated apart, which is not time-efficient. Most puzzles are solved in the shortest time bij using up to 4 cells an element.
In the 0-puzzle, -1 is used in stead of empty, to make calculation possible. There is an extra column that calculates the direction of a two-cell element in which there is a null.
So my model is very much a compromise.
A 8x8 puzzle has a typical runtime of 30 seconds. The shortest time was 3 second, the longest 250 seconds. A 12x12 puzzle has a typical runtime of several minutes, from 20 seconds up to several hours.
It's not perfect, but it works!
Edit 29 November 2013: After the introduction of puzzles containing -1, -2 etc, I added an 'extra layer': the model now calculates with indexes in stead of the figures itself. After that I added "puzzle recognition": the model now sees itself, whether 1..6, 0..5, -1..4 and more, is used. Still all done by formulae in Excel. Also complete sets are now recognised: triplets, quadruplets,.., septets, but only if all candidates still are present. This turns out to be simpler! In fact, in that way also hidden pairs, hidden triplets, etc are recognised.
Only for very difficult puzzles I built a macro that eliminates false candidates by checking them all. The problem is, that the difficulty of the puzzles is not calculable, so I did not build it in the solving process. It remains a stand-alone feature, and gives unexpected results.
Last edited by nicow on Fri Nov 29, 2013 11:32 am, edited 1 time in total.
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
Posted on: Fri Sep 23, 2011 7:49 am
Posts: 26 Joined: Fri May 13, 2011 7:57 am
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
Not a solver but a helping hand: Delphi application which give me a list of possible values.
Input: Number of cells, Doubles allowed (checkbox), Operator, possible numbers and expected result value.
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
randomfruit ![](fl/gb)
Posted on: Sat Sep 24, 2011 10:39 pm
Posts: 18 Joined: Mon Jul 25, 2011 7:49 pm
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
I wrote my solver two years ago (July 2009 is the last source file modification), when I was new to KenKen and I hadn't seen Patrick Min's web page. I'm a computer old timer (IBM 370 mainframe, PL/1, Unix, C, 8086 assember, SQL) and so I used C programming language on Cygwin (which makes a PC behave pretty much as if it were a Unix box, complete with a glass teletype) and good-old arrays and structured-programming logic. There are no objects nor messages in my solution.
The program uses some basic solving strategies to work the clues about the cells, such as two cells which sum to 5 can be 1+4 or 2+3; likewise for the other operators. Only cell pairs are allowed for division and subtraction; only the four original operations of add, subtract, multiply and divide are programmed. I'm quite proud of the initial setting up of the cell possible values, using recursion to search for possible number sets. Other simple stratagies are used: all but one of the numbers in a row or column will show the missing value; the last cell in cage can be computed. Much more intelligence could be added: for example, the cross-wing move has not yet been added (i.e. if a row has two cells which must be 1,5 in either order and a row elsewhere above or below has the same two cells, which also must be 3,5 in either order: then no other row in those two columns can have a 5 at all).
The program does basic/simple puzzles quite well, but can't solve difficult puzzles. Sometimes, due to poor coding and a hack-hack development, it makes a mistake. Being written in C, and compiled to assembler, it can go quite fast: mostly I can't perceive how long it took.
The user interface is crude, too. Puzzles must be input by giving row and column numbers of the first cell, the then U,D,L or R letters to mean up, down, left or right in constructing the cages. So, a two cell cage on the top-left of the puzzle that sums to 3 would be typed 3+ 0 0 R (left to right that is: 3 is the cage value, plus is the operator, row 0 col 0 is the first cell, move right to the next cell). Output is just to spray the computed values (or dots for unsolved cells) over the screen in a row/column layout.
Since I don't write programs for a living any more, and I have a full-time job I can't find the effort to make the code any better. I don't have the skills to make a proper windows or broswer interface for a PC, and no desire or resource to learn them at present.
One other technique I've tried is use of SQL (MySQL engine and PC interface named "My SQL query browser). I have tables named a,b,c etc which contain the values 1 to 12; I then write select statements so that the more complex searches of possible cells and cages can be exhaustively tried with minor efforts. For example, to find two-cell cages that multiply to 35 I would write: "select a,b from a,b where a*b=35 and a!=b". This is trivial, but shows those who speak SQL what I mean. Even for simple puzzles (e.g., 6 cells per side) an exhaustive approach to the whole puzzle in one go by the MySQL engine almost always has to be killed since it will go on a long time as it always uses nested loops to solve the problem. (I got bored after 20 minutes one evening, and that's the longest I've let it go on for.)
Part of the joy of KenKen is the "ah!" moment when one finds the 'key' to the puzzle set by a skilled setter, and the puzzle is on its way. The computer program does not give the satisfaction of finding that moment, and so I like to continue solving with pencil and paper.
Great site, Patrick Min, keep up the good work.
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
giulio ![](fl/au)
Posted on: Sat Nov 05, 2011 6:10 am
Posts: 54 Joined: Thu Nov 03, 2011 8:52 am
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
I developed a solver as part of my puzzle generator, to verify that the puzzles I generated had unique solutions. I wrote the programs in plain old C. The solver is pretty straightforward.
As part of my generator, I make lists of all possible combinatios of digits of each cage. These are combinations, not permutations. It means that there is at least one way of ordering the digits in such a way that they satisfy the operation, but there can be several possible orderings. For example, for a straight 3-cell cage with res-op '8x', only the combination 124 is possible, while if the cage is not straight, '118' also becomes possible. The permutations would be 124, 142, 214, 241, 412, 421, and 181.
The Solver simply tries all combinations of all cages, one cage at a time. If a combination causes duplicate digits in a row or column, I try the next combination of the current cage. If I run out of combinations for a particular cage, I backtrack to the previous cage. When I fill the 9x9 grid, it means that I have found a solution. To prove that the solution is unique, I apply the same solving mechanism twice. But the second time, I try the combinations of each cage in the reverse order. If the two solutions are identical, it means that the solution is unique.
As part of the iPad application I have developed to let people solve CalcuDokus, I wanted to include a 'hint' function. To do so, the simple mechanism I have just described was not enough. I wanted to be able to point out what candidates the player could remove, and that required to include in the program the logic to solve CalcuDoku puzzles. I implemented five strategies that together were able to solve more than 95% of the puzzles I generated for the iPad. For the five more difficult puzzles I included in the app, I wrote five pages explaining how to solve them.
To implement logical strategies in code is not easy. That's why I limited myself to five strategies. I used an average of 128 lines of C-code per strategy, but it was tricky.
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
pnm ![](fl/ua)
Posted on: Fri Aug 17, 2012 4:42 pm
Posts: 3304 Joined: Thu May 12, 2011 11:58 pm
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
Now this is the way to do it...: http://www.nadineloveshenry.com/calcudokuJust type in the page link (!!!) ![Scared [scared]](./images/smilies/msp_scared.gif) edit: I did some log file analysis to see how often this solver is used. A few times a day it turns out (less than 5). I can also see which users are involved, but see no point in doing anything about it (unless it's used for the timed puzzles).
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
sneaklyfox ![](fl/ca)
Posted on: Fri Aug 17, 2012 5:40 pm
Posts: 428 Location: Canada Joined: Fri May 13, 2011 2:43 am
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
pnm wrote: Now this is the way to do it...: http://www.nadineloveshenry.com/calcudokuJust type in the page link (!!!) ![Scared [scared]](./images/smilies/msp_scared.gif) edit: I did some log file analysis to see how often this solver is used. A few times a day it turns out (less than 5). I can also see which users are involved, but see no point in doing anything about it (unless it's used for the timed puzzles). Wow, that is really good. (I mean a good solver.) I tried today's 9x9 difficult and it took less than a second to give me the answer (although I already did the puzzle). Edit: It doesn't work for extra puzzles. I guess that's because you only see it if you subscribe.
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
rickt ![](fl/us)
Posted on: Fri Aug 17, 2012 6:52 pm
Posts: 65 Joined: Mon Mar 05, 2012 8:17 pm
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
Google "Henry Laxen"... He is a code freak.. Retired at 33 and probably wrote this solver while sitting on the toilet..Quite a character
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
clm ![](fl/ua)
Posted on: Fri Aug 17, 2012 10:08 pm
Posts: 857 Joined: Fri May 13, 2011 6:51 pm
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
pnm wrote: Now this is the way to do it...: http://www.nadineloveshenry.com/calcudokuJust type in the page link (!!!) ![Scared [scared]](./images/smilies/msp_scared.gif) edit: I did some log file analysis to see how often this solver is used. A few times a day it turns out (less than 5). I can also see which users are involved, but see no point in doing anything about it (unless it's used for the timed puzzles). Bad news, it looks like an strange and "specific" attack against this particular site? And why?. It's much worse than the people using their own solvers to "compete" (though unsportsmanlike, at least in this last case they have made an effort developing their own solvers ... ). The only possibility to maintain the transparency of the page would be to disable those players who use that type of "tools" (obtaining a solution via a "loophole") if you can confirm a repeated use of it. But, I am curious, instead of giving a clear reference to the specific puzzle like actually "www.calcudoku.org/en/2012-08-17/9/3", is it not possible to "encrypt" in some way the "link" to the specific puzzle in such a way of making practically impossible to copy it to the field provided by this nadineloveshenry page?. Another possibility is that you block the access to the puzzles when it comes from that specific page ... but this could start some undesirable "war" ... In the case of timed puzzles this "loophole" would affect the large ones (6x6 or the 8x8 suggested by starling if you provide one in the future) because there is enough time to download and copy the solution (very short time for the small puzzles, 4x4 and 5x5). Perhaps you could implement the idea I gave some time ago of the "4-dimensional calcudoku" ![Laugh :-)](./images/smilies/msp_laugh.gif) , the use of the time axis, that is, for instance, a sequence of 5 different 5x5's, recycling them after a determined number of seconds until the full solution for all five puzzles is complete, etc..
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
pnm ![](fl/ua)
Posted on: Fri Aug 17, 2012 10:37 pm
Posts: 3304 Joined: Thu May 12, 2011 11:58 pm
|
![Post Post](./styles/etech/imageset/icon_topic_latest.gif) Re: describe your solver
clm wrote: Bad news, it looks like an strange and "specific" attack against this particular site? And why? Not really an attack, I'm sure it was done as a programming exercise. clm wrote: But, I am curious, instead of giving a clear reference to the specific puzzle like actually "www.calcudoku.org/en/2012-08-17/9/3", is it not possible to "encrypt" in some way The puzzle is parsed from the page. It is possible to construct the puzzle in such a way that it becomes very difficult to parse. But that requires quite some programming time on my part, and I'd rather spend it on other things clm wrote: Another possibility is that you block the access to the puzzles when it comes from that specific page ... That is easy to do, but maybe it'd be better to talk to the site owners themselves instead. Maybe make it so they modify the page so today's puzzles are never accepted, for example. For the timed puzzles it is not a problem (yet), because you need to be logged in to do a timed puzzle (and their server is not logging in). Patrick
|
|
|
![](./styles/etech/theme/images/spacer.gif) |
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum
|
|