View unanswered posts | View active topics It is currently Tue Dec 06, 2022 9:12 am



← Back to the Calcudoku puzzle page




Reply to topic  [ 28 posts ]  Go to page Previous  1, 2, 3
 describe your solver 
Author Message

Posted on: Mon Feb 23, 2015 12:44 pm




Posts: 79
Joined: Fri May 13, 2011 9:37 am
Post Re: describe your solver
I am updating my (Excel2007) solver to make it more input-friendly as I'm beginning to get RSI.
It was very easy to let it remember the last operator. In plus-only or multiply-only puzzles, I have to type the operator only once!

Now I am looking for a handy method to code the cages in a simple and fast way to reduce key strokes. A cage of 3 cells used 8 keystrokes, now only 2.

I found out, that it is easy for a macro to determine how a cell is left. That is, a+[enter] can be distinguished from a+[arrow left]. That kind of information can be used! And this opens the way for a kind of 'steno' to specify the form of a multi cell cage!

So far I have made 42 functions. For example v+[enter] is a square, v+Arrow is a parallelogram in that direction. So 5 functions underneath a letter.
c is for correction, a is add cell to cage in that direction. It works fine.

I have to type 70% less!


Profile
User avatar

Posted on: Fri Sep 08, 2017 8:47 am




Posts: 3152
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
Here's a new one:

https://github.com/elterminad0r/Calcudoku


Profile
User avatar

Posted on: Wed Jul 18, 2018 10:55 am




Posts: 3152
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
And another new one :-)

https://github.com/lucrae/kenken-solve


Profile

Posted on: Fri May 24, 2019 7:45 pm




Posts: 3
Joined: Thu Jan 25, 2018 10:57 pm
Post Re: describe your solver
Wrote my solver in c# when I was retiring from Delphi.
It started with writing a little program to show me all the combinations for a cage (from a range from..to...) when I clicked on a cell of the puzzle.
Following operators are supported : +, -, x, /, &, |, ^ and mod (or a puzzle without operators).
And when that seemed to be okay, I tweaked it and added some more stuff to make life a bit more comfortable :-)
Then I wrote a solver because there was one user-puzzle that really drove me mad (a 12x12-puzzle, range 0..11 from kus_theo on 2018-06-09).
Mind you, I rarely click the solve button!!! It depends on the free time I have.
Don't know if the numbers are good, but it solves a 15x15 puzzle under 4 minutes.


Profile

Posted on: Mon Jan 25, 2021 2:02 am




Posts: 60
Joined: Fri May 13, 2011 2:21 am
Post Re: describe your solver
Are their any python experts on here ? I'm not interested in a solver as I like to solve them myself so don't see the point of a solver. I have absolutely no/very little apart from having a rough idea on how to follow easy stuff python ability at all & came up with the idea to put together a possible combination generator to help with the larger puzzles. With the help of my son (who has a basic understanding of python as he did as part of his teaching course through uni) we put together a program that does the job but I have a few more bells & whistles i'd like to add like # of duplicates, must include a certain number etc

I'm sure an expert would change my code around to make a lot smaller in size, run quicker etc but it does the job for me for the most part but would like to tidy up & add a bit t it. I used to use a website that was listed in the forums here years ago that I used for ages but it only did + - / * up to 9. I have it at the moment that it does + - / * ^ | & bit so all bases covered.

Let me know if anyone can help or point me to something similar already done so I'm not reinventing the wheel.


Profile

Posted on: Sun Nov 06, 2022 9:17 pm




Posts: 2
Joined: Sun May 01, 2022 9:43 pm
Post Re: describe your solver
Many years ago, I wrote a Sudoku solver. The goal was not just to solve the problem per se (which is straight forward), but to show step by step how a human should solve the problem. A couple of years ago, I created a program to solve Kakuro problems and then created a third program to solve Kenken. The main inspiration for the Kenken was the problem in your "Ten Hardest Problems" which I found impossible to solve manually.
The programs are all written in C++ and run on a MAC, either desktop or laptop. This machine runs on the new Apple M1 chip and is about 50% faster than my laptop. The graphical interface uses OpenGL library functions.

There are two independent methods can be used to solve the problems.
The first reduces the problem to an exact cover problem and uses Knuth's dancing links algorithm which is essentially a dumb but highly efficient brute force method. It is only used to check if the puzzle has been entered correctly, and it only reports if the the problem has a unique solution. The time for this procedure varies widely, but for two of today's problems, the hard 8x8 was verified in 1.052 milliseconds. The Killer sudoku was verified in 174 milliseconds which is well above average, but still far from the maximum. I also checked two 12x12 and found them to take between 200 and 500 milliseconds to verify.
Some really hard 9x9 problems can take up to a minute to solve with this algorithm. At the other end, the daily sudoku solves consistently in exactly 70 microseconds.

The main solving program has the goal of showing how a human could solve the problem. The user can try to solve the problem themselves but if they find it too difficult, an example solution is produced which the user can scroll back and forth through the solution and examine each logical step on the screen. When the user is solving the problem, the grid is presented showing the possible remaining candidate values each point can have and the user can remove them one by one until each square is left with only one possible value. There is a little housekeeping assistance provided only in order to save time, but no other assistance is provided. When a point is assigned a value, the value is removed from other points in the same row, column. If a linear cage of length n has exactly n different candidates, there is a command to remove those candidates from the remaining points in the line. While solving, a position can be bookmarked so that the user can recover from an error down the road. If a dead end is reached, the user can return to the bookmark.

The way the program solver works is
(1) Create a set of "constraints". One for each row, column, cage and 3x3 box in the killer sudoku case. For cages, any combination of operators can occur in the same puzzle, including mystery (+-*/). The operations supported are all the ones I have seen in the CalcuDoku site plus "bitwise and" and nim sum (bitwise xor).
(2) The program starts with all values possible for each point and proceeds in steps. Each step attempts to reduce the number of possibilities. The problem is solved when each point has only one remaining value.

Solving algorithm:
For each step the program tries various methods, proceeding with the easiest and going to harder ones when the easier ones do not bear fruit. The easy methods are the normal steps familiar to sudoku solvers (hidden pairs, xwing etc,) and the main workhorse is applying a single constraint to simplify the position based on only the candidates values of the points in the cage.
The more complex methods involve combining two or more constraints together. Particularly useful is the case where several cages are all contained in a single row or column.
There are also methods that look at rectangular regions with known total values and check on the total or parity of the values of the cages which are entirely or partially in the region. These are useful when the sum (or parity) of the values in the cages are known for most cages in the region. For problems that consist entirely of sums and differences, the parity is known and deductions can be made regarding the parity of certain points.
As a last resort there is a trial and error method where we try eliminating one of the possible candidates and see if it leads to a ready contradiction. If so the program can show the steps leading to the contradiction. This is regarded as rather unsatisfactory and it is preferred to analyze the situation and create a new solving method that makes trial and error unnecessary.

The program solves a large variety of problems, but there are definitely some problems that it cannot solve. It gets to a position where it can't make any more progress with the methods that have been programmed. Then I say congratulations to the problem setter.
The time taken to solve a problem of any size is generally less than one second except when the heavy handed trial and error method is necessary.

The scope of the program was originally size 6-9 with only the operators (+-*/) but it has been expanded to sizes 4-12.
Operations like subtraction and division now allow more than two points in a cage. The origin (lowest number possible in a cell) is now flexible. The program can handle cages of any connected shape up to nine cells. Larger cages are permitted but the program ignores them for the purpose of solving the problem.


Profile
User avatar

Posted on: Sun Nov 06, 2022 9:30 pm




Posts: 3152
Joined: Thu May 12, 2011 11:58 pm
Post Re: describe your solver
crabmouse wrote:
Many years ago, I wrote a Sudoku solver. The goal was not just to solve the problem per se (which is straight forward), but to show step by step how a human should solve the problem. A couple of years ago, I created a program to solve Kakuro problems and then created a third program to solve Kenken. The main inspiration for the Kenken was the problem in your "Ten Hardest Problems" which I found impossible to solve manually.
The programs are all written in C++ and run on a MAC, either desktop or laptop.


This sounds like a sophisticated piece of software [blink]

And yes, there's a lot of work involved in programming "human" solving methods, instead of "computer style" constraint solvers.

It would be cool to see the UI you describe, maybe you could post a video?


Profile

Posted on: Sun Nov 06, 2022 9:44 pm




Posts: 147
Location: Canada
Joined: Thu Aug 04, 2011 7:40 pm
Post Re: describe your solver
Very impressive crabmouse!


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 28 posts ]  Go to page Previous  1, 2, 3

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

Search for:
Jump to:  
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.