Page 1 of 1 1
Topic Options
#191555 - 2009-01-02 03:37 PM Sudoku solver
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
The attached script is a simple brute-force / backtracking solver for Sudoku puzzles.

It will always find a solution (if there is one), but depending on the grid it may take a very long time.

As it is brute force it does not use a recognisable human technique to solve the grid, so is not useful for learning how to solve puzzles.

A blank starting grid will generate a random completed puzzle - useful if you are interested in creating your own puzzles.

The solving algorithm is based on Emanuele Feronato's PHP code found here with only minor modifications to make it work in KiXtart.

Optimising for KiXtart is a lesson left to the reader...

[edit]
I've just re-read Emanuele's page and he states that the algorithm *is* emulating a human method of solving the grid. It looks more like an optimised brute force solve to me, but then I'm not a people person ;\)
[/edit]


Attachments
solve_sudoku.kix (291 downloads)
Description:




Edited by Richard H. (2009-01-02 04:03 PM)

Top
#191886 - 2009-01-23 04:37 PM Re: Sudoku solver [Re: Richard H.]
BillBarnard Offline
Starting to like KiXtart

Registered: 2007-03-14
Posts: 141
Loc: Leighton Buzzard, Bedfordshire...
I'm getting this error when I run it. I can't see anything obvious yet.

Starting grid: Pass #353 Time: 294 seconds
+---+---+---+ +---+---+---+
|6..|..5|..7| |624|185|..7|
|9..|7..|..6| |9..|724|..6|
|.1.|.3.|4..| |81.|.3.|4..|
+---+---+---+ +---+---+---+
|...|8..|.1.| |...|8..|.1.|
|2.9|...|..5| |2.9|...|..5|
|.6.|..2|...| |.6.|..2|...|
+---+---+---+ +---+---+---+
|..2|.9.|.5.| |..2|69.|.5.|
|5..|..3|7.1| |5..|..3|7.1|
|1..|4..|..3| |1..|4..|..3|
+---+---+---+ +---+---+---+

ERROR : invalid method/function call: missing comma!
Script: U:\158.KIX
Line : 213

My line 213 is:-

$y=UBound($aPossibilities[$x])

In the Function udfGetCellWithLeastSolutions($aPossibilities)

Anyone else tried it out yet?
_________________________
Bill

Top
#191908 - 2009-01-26 10:08 AM Re: Sudoku solver [Re: BillBarnard]
Richard H. Administrator Offline
Administrator
*****

Registered: 2000-01-24
Posts: 4946
Loc: Leatherhead, Surrey, UK
Thanks for the bug report.

I'll take a look as soon as I get some free time.

Top
Page 1 of 1 1


Moderator:  Glenn Barnas, NTDOC, Arend_, Jochen, Radimus, Allen, ShaneEP, Ruud van Velsen, Mart 
Hop to:
Shout Box

Who's Online
0 registered and 353 anonymous users online.
Newest Members
Praveer, Ollero, rayyo, Foxlicht, DonChild
17742 Registered Users

Generated in 0.03 seconds in which 0.012 seconds were spent on a total of 14 queries. Zlib compression enabled.

Search the board with:
superb Board Search
or try with google:
Google
Web kixtart.org