Wednesday, November 30, 2005

Sudoku Solver

This afternoon I wrote a sudoku solver in Prolog. I haven't written a Prolog programme since I was at university nearly ten years ago, so it's a bit of a brute force attack really. I tested it on small grids to start with and it worked ok, but on a full sudoku so far it's taken three hundred and ninety-eight minutes and hasn't returned a result. I'll leave it going overnight, but if it hasn't worked it out by morning I'm giving up. Since I have no desire to learn how to code in Prolog properly. I could probably write something in Java to solve it in a few seconds. (That is, the solving would take a few seconds, not the writing.)

7 comments:

Philip Rodrigues said...

Heh, exactly the reason why I've never attempted a sudoku and don't plan to. Why waste brain power on an exercise in combinatorics when a script can do it? Cryptic crosswords all the way! :-)

quakegamer said...

quick solution, caml

open Facile;;
open Easy;;

let print queens =
let n = 9 in
for i = 0 to n - 1 do
for j = 0 to n - 1 do
let c = Fd.int_value queens.(9*i+j) in
Printf.printf "%d " c
done;
print_newline ()
done;
flush stdout;;

let puzzle = [|
5; 3; 0; 0; 7; 0; 0; 0; 0;
6; 0; 0; 1; 9; 5; 0; 0; 0;
0; 9; 8; 0; 0; 0; 0; 6; 0;

8; 0; 0; 0; 6; 0; 0; 0; 3;
4; 0; 0; 8; 0; 3; 0; 0; 1;
7; 0; 0; 0; 2; 0; 0; 0; 6;

0; 6; 0; 0; 0; 0; 2; 8; 0;
0; 0; 0; 4; 1; 9; 0; 0; 5;
0; 0; 0; 0; 8; 0; 0; 7; 9;
|];;
let myarr = Fd.array 81 1 9;;

for i=0 to 80 do
let value = Array.get puzzle i in
if value > 0 then Cstr.post (fd2e myarr.(i) =~ i2e value);
done;;

(* constraints horizontal, vertical and squares *)
let chooser i x y =
if i=0 then x*9+y
else if i=1 then x+y*9
else (27*(x/3)+3*(x mod 3)) + (9*(y/3)+(y mod 3))
;;

(* add the constraints *)
for c=0 to 2 do
for i=0 to 8 do
let arr = Array.init 9 (fun k -> myarr.(chooser c i k)) in
Cstr.post (Alldiff.cstr arr)
done
done;;

(* solve *)
let goal = Goals.GlArray.labeling myarr in
if (Goals.solve goal) then print myarr
else failwith "no solution found"
;;

Reviewer said...

The fun of Sudoku is for the human mind to solve it, the individual confrontation. On this website, Sudoku Daily at http://www.sudokudaily.net you can select the type of game and store a game that is half-finished. It looks good too.

Jonathan said...

Interesting :)

I also wrote a solver. It is free and it is online here. No need to download and install anything. All you need is your browser. You'll see, it is very easy to use and very fast. It will also tell you if there are more than one solution for your sudoku.

Here is the link again: ]Good Camel's Sudoku Solver!

Happy Sudoku :)

Dany Gunawan said...

Hi all..
I've just also finished developing my sudoku solver.
I've posted it online on www.sudokusolver.co.nr

I wrote it in .NET language and I think it quite fast too as it takes more intelligent checking instead of having to do any time-consumed brute force :)

You're more than welcome to visit it at anytime guys heheheeeee

Thanks..
Viva Sudoku

www.randek-bautech.com said...

http://vbaexcel.eu/vba-macro-code/sudoku-solver

Here is one solver it solves everything but takes a few seconds in some cases.

Bruce Fredman said...

Hi,
We at Chessboss.com strongly believe in necessity of chess to increase both knowledge and understanding. It is unfortunate that the oldest game in the world (Chess) has a very little fan base, ChessBoss.com aims to change that. We understand the importance of blogs and the information made available on them. We are working towards building a strong fan base around our FREE chess server to better increase the use of Chess online. Your blog seems to have a large viewing public and seems to hold great information which I would love to make available to my viewing public.

I have included the code for the ChessBoss.com banner within the body of this email along with textual link information. I would be pleased to offer you the ChessBoss.com featured blogger badge to post on your site, recognizeing your blog as a leading contributor to the Chess community. Thank you for your great work and dedication, we look forward to your response!Please reply me back with subject line of your Url to avoid spam and to make sure YOU get the Award.

Thank you.