Some weeks ago, I mentioned that I was working on a Sudoku solver
program. It did not go as smooth as a would have liked, so I decided
to do much less than I had originally envisioned. Also, other things
intervened, so it took much longer than I had planned. Anyway, you
can find the program at

http://www.complang.tuwien.ac.at/forth/programs/sudoku3.fs

It relies on a number of Gforth words (see the comments at the start).
It is also bigger and slower than Robert Spykerman's program, and it
solves only simple puzzles at the moment. But I am not going to work
on it in the next time, so I am publishing it, so that you can learn
from it, maybe find out what mistakes I made, or maybe improve it.

I am not sure if this is a good basis for continuing, though: The
problems I had with it were that I did not find a good factoring for
dealing with rows, columns, and boxes uniformely; maybe this could be
done better using lookup tables. Also, I found it pretty hard to
debug this stuff; one improvement might be if I used variable indices
instead of variable addresses in most places.

On Sun, 17 Dec 2006 18:57:32 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

Only a side remark:
I found the Prolog code snippet below very interesting. It is so very
compact (cut away the tests) and - at least for me - an example of how
important the selection of the right tool is - here Prolog. If I had
free time to kill I'd perhaps try to mimick that in Joy or Forth. But
... :-(

Prolog code:

%%TO convert to gnuprolog remove the following two lines.
:- use_module(library(clpfd)).
:- use_module(library(lists)).
%%then search and replace all_different to fd_all_different

%%It should all work.

Andreas Kochenburger nospam.com> wrote:

Here's a more concise version:

:- use_module(library(bounds)).

suudoku(P) :-
Rows = [R1,R2,R3,R4,R5,R6,R7,R8,R9],
problem(P, Rows),
flatten(Rows, Vars),
Vars in 1..9,
row_constraint(Rows),
column_constraint(R1, R2, R3, R4, R5, R6, R7, R8, R9),
block_constraint(R1, R2, R3),
block_constraint(R4, R5, R6),
block_constraint(R7, R8, R9),
once(label(Vars)),
display_rows(Rows).

Markus Triska wrote:

[snip]

Prolog looks pretty impressive. Thanks for the example.

Just to show that Forth can deal concisely with problems at a higher
level, I include the following example of a "List of Lists", analagous
to what you recently coded in the Prolog newsgroup. (I have no idea
how to approach the Sudoku problem. I have never solved one and don't
even know what the object of the game is):

*** BEGIN PROLOG POST
I need to create a list of words (divided by spaces) each one is a list

of chars.

Example:

Doug Hoffman wrote:

Not as nice or as fast as the Prolog solution, but here is my
brute-force approach:

: cell- 1 cells - ;
0 value start
0 value end
create colbuf 9 cells allot
create rowbuf 9 cells allot
create blkbuf 9 cells allot
: wipe ( addr -- , erase buffer)
9 cells erase ;
: row ( index -- row...

Krishna Myneni wrote:

I agree. I wasn't aware of the list code. It certainly fits this
problem very well! My approach was a bit more "build-your-own"
starting with a few pre-defined object classes.

Thanks for the example.

Doug Hoffman wrote:

I forgot to mention that the lists package has been tested under gforth as well.
See the files lists.fs, lists-test.fs, and strings.fs in the ftp directory given
below. The file gps.fs is another example of use of the lists package.

ftp://ccreweb.org/software/gforth/

From: "Gerry" jackson9000.fsnet.co.uk>
Newsgroups: comp.lang.forth
Subject: Re: Sudoku3
Date: Sat, 30 Dec 2006 07:27:08 -0800

Anton Ertl wrote:

[snip]

[snip]

I doubt if this approach is what you were looking for but it gives some
idea of how the difficulty of a given puzzle could be assessed. I wrote
a Sudoku solver over a year ago and it followed these steps:

kenney@cix.compulink.co.uk wrote:

I got a Sudoku computer when I stated a c't subscription a month ago (due to
price raise for non-subscription buyers). So I've had now some time to do
sudokus by hand. The computer has three levels (easy/medium/hard), where I
can see little difference. The grade of the level is the number of free
choices you can do, i.e. on easy levels, there's maybe one choice and all
the other numbers fall into places, while on the hard level, there might be
four or five choices.

Since I do this manually, I don't do backtracking, but I rearrange the
numbers that don't fit when I made the wrong choice. This doesn't always
work out (i.e. I sometimes get stuck with the last few numbers, and can't
find a way to shuffle the rest around to solve the sudoku).