marcov wrote:

very cool

I'm checking it out now

one small note: the ultra-high res scan of the Volkskrant puzzle really blows up the size of the repository

(below a 1:1 part of that scan (!))

so maybe better to crop it, scale it down to ~ 1600 pixels wide maybe, and convert to JPEG

]]>

See https://github.com/MarcoVad/anydoku-sudoku-solver

The reason for this effort was basically that I came across an old sheet of paper with a very large puzzle: the famous Elektor penta-hexadoku. (https://www.elektormagazine.com/magazin ... 1207/19950)

I remember that I started with it several times but it didn't work out. The sheet of paper was actually a hand-drawn copy from the magazine in a larger size. It was showing conflicts.

When I saw it again, years later, I decides it give it one more try, but now with help of the computer. This time it was successful.

Now I had the algorithm in places, I took the challenge to let it solve different variants and features as well. The Calcudoku was quite a challenge I have to admit.

Currently it supports regular Sudokus, extrafields, oddeven, diagonal, jigsaw, calcudoku, killer, twin killer. Board size is not limited, and also multi-board is supported.

If you are interested or have good suggestions, please let me know! BUT, please don't cheat on this site...

]]>

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

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?

]]>

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.

]]>

Here's a link: https://www.youtube.com/watch?v=NOtngFnRZOY

]]>

pnm wrote:

paulv66 wrote:

So is the order only relevant if there are three different numbers in the cage? Or are you saying that 65,536 is not an acceptable answer for 2,2,4?

65536 definitely is an acceptable answer, because the evaluation order is right-to-left.

And as with cages with 3 cells or more with subtraction/division,

(not the ordering of the numbers)

(this is maybe a cause of confusion)

Thanks Patrick.

My confusion was caused by the fact that I was assuming that the evaluation order was left to right, in which case the only acceptable answer would be 256. I’ve no idea why I made that assumption when the instructions clearly say right to left. I can only assume that it’s because I often struggle to distinguish left from right and find myself having to correct what I say when I’m giving directions.

]]>

paulv66 wrote:

So is the order only relevant if there are three different numbers in the cage? Or are you saying that 65,536 is not an acceptable answer for 2,2,4?

65536 definitely is an acceptable answer, because the evaluation order is right-to-left.

And as with cages with 3 cells or more with subtraction/division,

(not the ordering of the numbers)

(this is maybe a cause of confusion)

]]>

pnm wrote:

paulv66 wrote:

Now I’m confused. If either of the above answers is valid, it means that the order of evaluation is irrelevant.

For 2,2,4, and the result 256, yes.

So is the order only relevant if there are three different numbers in the cage? Or are you saying that 65,536 is not an acceptable answer for 2,2,4?

]]>

paulv66 wrote:

Now I’m confused. If either of the above answers is valid, it means that the order of evaluation is irrelevant.

For 2,2,4, and the result 256, yes.

]]>

4^2^2 = (4^2)^2 = 16^2 = 256

2^4^2 = (2^4)^2 = 16^2 = 256

2^2^4 = (2^2)^4 = 4^4 = 256

Not a big difference. Though with the current way of calculation it is possible to get 65536 with 2, 2 and 4.

Might be more clear with 2, 3 and 5.

]]>

pnm wrote:

guidocram wrote:

So when there are 2, 2, and 4 inside the box, it still can be:

4^2^2 = 4^(2^2) = 4^4 = 256

2^4^2 = 2^(4^2) = 2^16 = 65536

2^2^4 = 2^(2^4) = 2^16 = 65536

Correct?

4^2^2 = 4^(2^2) = 4^4 = 256

2^4^2 = 2^(4^2) = 2^16 = 65536

2^2^4 = 2^(2^4) = 2^16 = 65536

Correct?

yes, all correct

Now I’m confused. If either of the above answers is valid, it means that the order of evaluation is irrelevant. What am I missing?

]]>

guidocram wrote:

So when there are 2, 2, and 4 inside the box, it still can be:

4^2^2 = 4^(2^2) = 4^4 = 256

2^4^2 = 2^(4^2) = 2^16 = 65536

2^2^4 = 2^(2^4) = 2^16 = 65536

Correct?

yes, all correct

]]>