Solving Sudoku variant Futoshiki

Software
1

Currently, I like to solve Futoshikis and recently got a very difficult one (not this, this is just how one looks).

Futoshiki - Wikipedia

I searched the web and found on github this solver written in Python script, but it’s mainly for 5x5 and for larger sizes it uses brute force (mine are 6x6)
GitHub - davidswarbrick/futoshiki-solver: A Python script to solve Futoshiki puzzles

There’s a very good online GUI solver showing the next step
Futoshiki solver - shows the next logical step

If someone needs a new task (after the Christmas challenge)
there are many tasks, especially the input

-check if one puzzle is valid
-check if there are more solutions
-create puzzles
-code in BASIC or other language
-input as string
-input as GUI
-using just brute force
-of course the shortest code

…

2 Likes
2

One needs a sort of constraint programming, I think? Constraint solver, that might be the phrase. I do wonder if the retro machines are big enough for the task, but as there is nice (and recent) Suduko program for the BBC Micro, I think it should be possible. For someone with the skills, energy, and patience!

ref: Making reasonable progress with a Sudoku solver
(Can play it online here)

3

There are different ways and terms like mentioned here

Eight queens puzzle - Wikipedia

Structured programming - Wikipedia

logic programming or genetic algorithms. recursive algorithm,

Another task first, how much RAM and other specifications (DIM array size limitation) is needed. Or how large can a Futoshiki be to be solved on home computer xy. Maybe start with 2x2 or 3x3.

1 Like
4

Since only digits 0…9 are permitted in the cells, a 8008 or 4004 version might be possable.

5

I’ve done a few solvers for various problems: Eight Queens, Pentominoes, Sudoku*, etc. for various systems in various languages.

The solvers tend to be inherently recursive, so for languages that don’t support recursive calls, it’s easiest to use arrays or tables or similar to hold the variable values for each ‘depth’ of recursion, and keep track of the current depth in a global variable.

If you want a ‘pure’ BASIC solution, then the memory taken up by the arrays of integers might become a limiting factor on machines with not much RAM. Probably best to use arrays of integer variables (if available) and perhaps compact 4 BCD digits into each integer. If you allow use of POKE and PEEK (which, of course, needs knowledge of the target machine’s memory map) then that might be faster. Again, you could save memory by using BCD to pack decimal digits, two to a byte. For reasonably-sized puzzles, many vintage machines will have plenty of RAM anyway. I might have a go at this problem on the Commodore 64, after Christmas.

  • My latest Sudoku generator, in PHP (which has a solver built-in, to check for multiple solutions) is used to generate a daily online puzzle here: Sudoffle Green ‘clues’ are standard Sudoku. Yellow ‘clues’ show a wrong number for that square. If you enter a conflicting guess for a square (digit already present, non-yellow, in same row, column, or block) then the square goes dark, and you’re locked on that square until you erase or change the value entered.
2 Likes
6

In general, it certainly could be… but in this case, as a board state is just 36 integers, and the max depth of recursion also 36, I’d hope a 32k machine would be enough.

It would be interesting to know what the practical max depth is, for a medium or a hard problem… and of course the run time too. It might be that fully recursing a brute force approach would be just too time consuming.

1 Like
7

Yes, I doubt anyone will try this on a Science of Cambridge MK14, but you never know. :grin:

My general approach is to compute a list of the possible candidates for each square, choose one of the squares with the least candidates, and guess each of the values in turn. After each guess, recurse to the next search depth and repeat. If and when you reach a solution, keep going to check that there aren’t multiple solutions.

1 Like
8

Here’s a Sudoku solver for the Apple ][: Sudoku Solver v2.0 for the Apple II

The description might be useful for implementing solvers on other vintage computers (or on memory-constrained MCUs).

9

Interesting notes on the algorithm and coding in there, thanks. Seems like brute force recursion, efficiently implemented, is a win for speed. (They mention two difficult examples, EVIL01 and VEVIL, which can be found in plain text in this usenet thread. However, what exactly is a difficult example can depend on the rotations reflections and permutations of a puzzle.)

Sudoku patterns

If you think that one’s tough, try this one. It’s much harder, at least
for my algorithm. I don’t know where I got it, but I saved it under the
filename “hints17-2”. I have four files of the form “hints17-x”, all
very tough, but this one is the worst:

…1.2.7…
.5…9.
…4…
.8…5…
.9…
…6…2
…2…
…6…5
…9.83

Not even symmetrical. (Shudder.)

and

I don’t know about most Sudoku solvers, but there are a lot of slow ones
out there. And in terms of taking seconds, I think Michael was talking
about difficult puzzles, not easy ones. Our most frequently used test
puzzle was one we called “evil01”. I loaded this into the solver you
mentioned and it took about 4 seconds on my 3GHz machine. Here’s the
puzzle:

.2…
…6…3
.74.8…
…3…2
.8…4…1.
6…5…
…1.78.
5…9…
…4.

That’s certainly a tough one. I regularly do the puzzles in the local
paper, and this one took me about 1h10m, which is twice as long as the
typical time I take for a “diabolical” puzzle.

10

I was looking online to see if there is a standard way of representing Futoshiki puzzles in an ASCII file. So far, I found nothing. I note that some puzzles have upward and downward pointing ‘arrows’ connecting cells in a vertical manner, so one semi-obvious file format would be to use > < ^ and V (letter V) to represent the constraints, spaces for blank cells, and any other character to fill in any remaining spots not occupied by a number, relationship, or space. To make it more readable/editable for a human, we could begin with a basic empty grid composed of | + - characters, so for a 5x5 Futoshiki, something like this:

+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+
| | | | | |
+-+-+-+-+-+

… and then fill in any clue numbers in some of the spaces, and substitute the relationships in place of some of the existing ‘grid lines’, like this:

+-+-+-+-+-+
| |3| | | |
+-+-+-+-+-+
| < | | | |
+V+-+-+-+-+
| | | | > |
+-+-+-+-+-+
| | | <2| |
+V+-+-+-+-+
| > | < > |
+-+-+-+-+-+

The computer wouldn’t care about the + - and | characters, so you could use any non-relationship characters, though that would likely make the files less readable for a human. There’s no need for the top and bottom lines of each puzzle, nor the left and right columns, so those could be omitted to save space, though the puzzles might not then look as nice to a human.

No need to specify the size of the puzzles - the computer can infer that by the lengths of the lines.

It would be possible to have a big ASCII file, filled with lots of puzzles of various sizes, and the computer solver would then churn its way through the file, spitting out solutions, reports of unsolvable or badly formed puzzles, and the times taken to solve each one.
Of course, the file could also just contain a single puzzle, if that’s all you want to solve.

If anyone can suggest a less clunky format for the puzzle files, maybe an existing one that I’ve not found, that would be a good starting point for writing solvers - and it would make it easy for us to test different solvers on the same input files, to compare their solving times.

11

Could you program a spread sheet to solve a puzzle?

12

Excel (and other Microsoft “office” products) use VBA - Visual Basic for Applications, so… Yes.

-Gordon

13

I would have guessed that even simple early spreadsheets like VisiCalc and sc (originally vc) are Turing complete, so my answer would have been “technically, yes, but not necessarily practically.” But my guess might be wrong… and yet the conclusion still might be right!