Sudoku algorithm, anybody?
Author
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]
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.
Author
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!
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.
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.
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.
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.
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).
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.
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.
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.
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.
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.
@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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
