Jump to content
  • Advertisement
Sign in to follow this  
silverphyre673

Sudoku algorithm, anybody?

This topic is 4734 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a Sudoku puzzle game. For those of you who don't know, this is how it works. I was wondering if anyone knows an efficient algorithm for generating Sudoku puzzles. I have made one, but it just brute-forces a puzzle, and generally takes around 10-15 seconds on a P4. If not, my only thought was to have the program generate more puzzles in the background while the user runs the program, and to store them on the hard drive for the next game. Anyways, if you have any better ideas, please let me know. Edit: Nevermind. I fixed the algorithm, and now it hasn't finished a puzzle yet. It takes a long time [grin], which makes it even more important, I guess. Thanks for your help! Actually, after doing a bit more research, it looks like the most common method involves applying an algorithm developed by David Knuth called "Dancing Links". I have tried looking for any information on it, but this is apparently a pretty obscure thing. Knuth's website has a paper on it, but it is in a format that I can't use (TeX format...). Anyways, if anyone can point me in the direction of more info on this algorithm, I would really appreciate it. Thanks a bunch! [Edited by - silverphyre673 on September 23, 2005 1:41:38 AM]

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by silverphyre673
Knuth's website has a paper on it, but it is in a format that I can't use (TeX format...).


Of course you can - even if you don't want to install TeX to generate the formatted output, just open it with a text editor.

Edit: You mean Donald Knuth.

Share this post


Link to post
Share on other sites
After doing more research - can't find very much info on Dancing Links at all =(, it looks like the most advocated way to do this is to plug in contrained random numbers into whatever pattern you want, and to try and solve it. If you can solve it, then use that board, otherwise, generate another. It sounds like the best way to solve the board would be a constraint search, by plugging in numbers one at a time into squares. Then eliminate that possibility from the rest of the squares in that row, column, and box. Does this sound right, and would you suggest anything else that might make it a bit faster? Thanks!

Share this post


Link to post
Share on other sites
I'd do the opposite. I'd generate a solved board, then iteratively remove numbers and run the solver until the solver finally choked (i.e. puzzle is too ambiguous to meaningfully try to solve), then put numbers back until it's reasonable to solve.

Of course, this is just me talkin' outta my butt. I'm not as captivated by Sudoku as other folks. Dunno why, but it's just not grabbing me.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I did a search in google for "dancing links". The second page found was a paper written by Knuth about the dancing links technique. It is in postscript format, so you need a postscript viewer to read it. There's a free postscript viewer called GhostScript. Also for some reason postscript files often seem to have a .ps.gz extension, but are not actually zipped files and I just remove the .gz extension and view them with a postscript viewer. I've never bothered to figure out why that is...

Anyway, dancing links is just a technique used for efficiently solving constraint problems. Constraint problem solvers usually use a depth first search. They pick a move, then later they might backtrack. It is usually more efficient to undo the moves while backtracking instead of storing all the states that are encountered. By using linked lists, choices can be unlinked when they are chosen or become invalid choices because of another choice. If the algorithm must backtrack, the choices can be linked back into the list. It is some complicated bookkeeping to improve the performance of the search.

Share this post


Link to post
Share on other sites
A few days ago, I've written a little Sudoku solver as an OCaml exercise for myself. I haven't tested it thoroughly, but it did solve some puzzles correctly, and did so in under a second (puzzles considered hard on the website I took them from).



exception Sudoku_exception of string;;

let rec remove_first lst item =
match lst with
[] -> []
| h::t when h == item -> t
| h::t -> h :: remove_first t item;;

let rec range a b =
if a <= b
then a :: range (a + 1) b
else [];;


module Position =
(
struct
type t = { x:int; y:int }

let create x y = { x = x; y = y }

let x p = p.x
let y p = p.y

let xy p = (p.x, p.y)

let print p = Printf.printf "(%d, %d)" p.x p.y

let compare p q =
if p.x < q.x
then -1
else if p.x > q.x
then 1
else if p.y < q.y
then -1
else if p.y > q.y
then 1
else 0
end
:
sig
type t

val create : int -> int -> t
val x : t -> int
val y : t -> int
val xy : t -> int * int

val print : t -> unit

val compare : t -> t -> int
end
);;

module PositionSet = Set.Make(Position);;

module Grid =
(
struct

type cell = Certain of int
| Choice of int list

type grid = cell array array

let create () =
let result = Array.make_matrix 9 9 (Certain 0)
in
for i = 0 to 8 do
for j = 0 to 8 do
result.(i).(j) <- Choice [1;2;3;4;5;6;7;8;9]
done
done;
result;;

let copy grid =
let copy_row idx =
Array.copy grid.(idx)
in
Array.init 9 copy_row;;

let cluster_cells pos =
let result = ref PositionSet.empty
and (x,y) = Position.xy pos
in
let add x y =
result := PositionSet.add (Position.create x y) !result
in
for i = 0 to 8 do
if x <> i
then add i y
else ();
if y <> i
then add x i
done;
let sx = (x / 3) * 3
and sy = (y / 3) * 3
in
for i = 0 to 2 do
for j = 0 to 2 do
let x' = sx + i
and y' = sy + j
in
if x' != x || y' != y
then add x' y'
done
done;
!result;;

let get (grid : grid) pos =
let (x, y) = Position.xy pos
in
grid.(x).(y);;

let set grid pos n =
let (x,y) = Position.xy pos
in
let remove_choice pos =
let (x, y) = Position.xy pos
in
match grid.(x).(y) with
Certain _ -> ()
| Choice lst -> grid.(x).(y) <- Choice (remove_first lst n)
and influenced_cells = cluster_cells pos
in
match grid.(x).(y) with
Certain _
-> raise (Sudoku_exception "Cell already certain")
| Choice lst when not (List.mem n lst)
-> raise (Sudoku_exception "Not in choice list")
| Choice lst
-> (
PositionSet.iter remove_choice influenced_cells;
grid.(x).(y) <- Certain n
);;

let normalize grid =
let continue = ref true
in
while !continue do
continue := false;
for i = 0 to 8 do
for j = 0 to 8 do
match grid.(i).(j) with
Choice [x] -> set grid (Position.create i j) x;
continue := true
| _ -> ()
done
done
done;;

let print grid =
for j = 0 to 8 do
for i = 0 to 8 do
match grid.(i).(j) with
Certain x -> print_int x
| Choice _ -> print_string "."
done;
print_newline ()
done


let find_least_choice grid =
let count = ref 10
and x = ref 0
and y = ref 0
in
let check i j lst =
let len = List.length lst
in
if !count >= len
then (
x := i;
y := j;
count := len
)
in
for i = 0 to 8 do
for j = 0 to 8 do
match get grid (Position.create i j) with
Choice lst -> check i j lst
| _ -> ()
done
done;
match grid.(!x).(!y) with
Choice _ -> Some (Position.create !x !y)
| _ -> None

end
:
sig
type cell = Certain of int
| Choice of int list

type grid

val create : unit -> grid
val copy : grid -> grid

val get : grid -> Position.t -> cell
val set : grid -> Position.t -> int -> unit

val normalize : grid -> unit

val print : grid -> unit

val find_least_choice : grid -> Position.t option

end
);;

let load_grid file =
let input = open_in file
and grid = Grid.create ()
and x = ref 0
and y = ref 0
in
let next () =
x := !x + 1;
if !x == 9
then ( x := 0; y := !y + 1)
and finished () =
!x == 0 && !y == 9
in
let add_unknown () =
next ()
and add_certain n =
Grid.set grid (Position.create !x !y) n;
next ()
and digit_of_char c =
int_of_char c - int_of_char '0'
in
while not (finished ()) do
let c = input_char input
in
match c with
'.' -> add_unknown ()
| '0' .. '9' -> add_certain (digit_of_char c)
| _ -> ()
done;
close_in input;
grid;;

let rec solve grid =
let grid = Grid.copy grid
in
let rec find_first func lst =
match lst with
[] -> None
| h::t -> (
let result = func h
in
match result with
None -> find_first func t
| Some x -> result
)
in
let branch_at pos =
let solve_with n =
let grid = Grid.copy grid
in
Grid.set grid pos n;
solve grid
in
match Grid.get grid pos with
Grid.Certain _ -> raise (Sudoku_exception "Unexpected error")
| Grid.Choice opts -> find_first solve_with opts
in
Grid.normalize grid;
match Grid.find_least_choice grid with
None -> Some grid
| Some pos -> branch_at pos;;




It works like you described in a previous post: I have a 9x9 grid with items of type "cell" which can be a "Certain x" (meaning it is certain that it contains the number x), or "Choice lst" (meaning it must contain one of the elements in lst). Initially all cells are set to "Choice [1;2;3;4;5;6;7;8;9]".

The "Grid.set grid pos x"-operation sets a certain cell to "Certain x" at position pos, and removes the value x from all Choice-cells in the same "cluster" (= the cells on the same row, column or square). It then scans all cells for Choice-cells with only 1 possible value left, and Grid.sets them to Certitude.

This is repeated as often as possible; when no more Certain-cells can be found this way, the algorithm looks for the cell with the least possible choices. It makes a copy of the grid, Grid.sets one of the possible values, etc. etc. If the guess does not lead to a solution, it will retry with another possibility.

Share this post


Link to post
Share on other sites
Quote:
Original post by silverphyre673
Actually, after doing a bit more research, it looks like the most common method involves applying an algorithm developed by David Knuth called "Dancing Links". I have tried looking for any information on it, but this is apparently a pretty obscure thing. Knuth's website has a paper on it, but it is in a format that I can't use (TeX format...). Anyways, if anyone can point me in the direction of more info on this algorithm, I would really appreciate it. Thanks a bunch!


Here is his tex paper converted into pdf
I'm not sure how long the link will remain active as my domain is due to be transferrred sometime later today though.

Share this post


Link to post
Share on other sites
I'm not sure what you mean by generating a puzzle. A valid board is a[j]=(i+j)%9+1. Every other valid board is a permutation of that board. So you can swap rows and columns of one valid board to arrive at another valid board. Looping 20 times swapping two randomly selected rows then two columns shouldn't take much resources and generate a sufficently random board.

What you need to show to make it uniquely solvable is a bit more difficult. You have to have at least one value from eight rows and eight columns. If two rows don't have values then those two rows can be swapped to arrive at another valid solution. So you have to show at least eight to have a unique solution, but I don't know if eight is sufficent to insure a unique solution.

It seems the true work would be in deciding what to show. Some minimum criteria for a uniquely solvable puzzle is most likely of little use. Even unique doesn't much matter. You just want to entertain the player and give them a sense of accomplishment. Toward that end you may not even want a random board, but rather a pattern the player can recognize.

Share this post


Link to post
Share on other sites
@LilBudyWizer:

Interesting solution.. but it's wrong, unfortunately :) It's in conflict with the third rule, which states that each region (the nine 3x3 squares of the 9x9 board) should contain only one instance of each number.

For example, in your solution (prior to permutation) all three diagonal regions would each contain three instances of number 1, while the other six regions wouldn't contain any instances of that number. [The requirement being that each region contain exactly one instance of each number]

But the solution has potential, since the problem is reduced to finding a permutation which would satisfy this last contraint. At the moment I'm too tired to think much about it, but I'll try to find a complete solution tomorrow.

Share this post


Link to post
Share on other sites
Hehe, guess I should have read the rules :) Ok, so a[j]=(i+3j+j/3)%9+1? Then permute rows/columns within a set of three rows/columns. There are 6 ways you can order three items, but it takes at most two permutations to switch from one ordering to any other. Permuting one set of rows and columns per 3x3 block would most likely be sufficent.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!