# 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.

## 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 on other sites
Quote:
 Original post by silverphyre673Knuth'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 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 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 on other sites
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 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 on other sites
Quote:
 Original post by silverphyre673Actually, 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 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 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 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.

1. 1
2. 2
3. 3
Rutin
21
4. 4
frob
17
5. 5

• 9
• 33
• 13
• 13
• 10
• ### Forum Statistics

• Total Topics
632582
• Total Posts
3007206

×