# Sudoku program
# Author: Ronald L. Rivest
# Version 1.0
# Last modified: January 14, 2006
# This program is "public domain": you may copy, modify, run,
# publish, distribute, embed, and/or use this program in any way
# whatsoever without prior permission and/or giving me any
# credit or payment whatsoever.
# (Indeed, please don't bother me to ask such permission!)
# It comes "as is" with no warranties or guarantees of any kind.
# It may contain bugs and/or be inconsistent with its internal
# or usage documentation.
# Have fun with it!
# (Of course, this really needs a nice GUI, rather than this
# console interface!)
usage_string = """\
Usage: sudoku.py
may include one or more of:
(note that printing out puzzle always happens)
-f to save this puzzle (only useful with -g option)
filename is random number seed used to generate puzzle
(puzzle is saved in format suitable for reading in later,
in the "puzzles" subdirectory, as a ".txt" file)
-s to solve the puzzle, and print out solution (if possible)
and indicate whether there are no solutions, whether
there is a unique solution, or whether there are multiple
solutions. If a solution exists, one will be printed.
(Solving puzzle is optional, so as not to spoil fun for puzzle
you only want rated.)
-d to turn on "debug printing"
This will explain in detail how a particular
puzzle can be solved, step by step, with reasons for
each step, or how a puzzle was generated.
-r to rate the puzzle's difficulty
by solving it 20 times
and returning the median "score" (measured as
moves_made + 10*guesses_made + 50*guess_depth
a somewhat arbitrary measure).
A score equal to the number of unfilled squares means
that the puzzle requires no backtracking to solve.
If no processing options are given, defaults to -s -r (solve and rate).
Processing options don't really need to be first; they may be
anywhere in argument list, but are treated as if they were first.
specifies one or more puzzles:
-gxxx to generate a puzzle
using arbitrary length string xxx as random number seed
This allows you to regenerate the same
puzzle again easily later.
-g to generate a random puzzle
This uses clock as random number seed.
-i to read puzzle from standard input
filename to read puzzle from file with given filename
from the "puzzles" subdirectory (.txt file)
Some "automation" you may find convenient:
The -gxxx and filename options may include, at the end,
a "+r" extension, where r is a decimal integer > 0 which
specifies how many extra similar generations or filenames
to process. This is like a macro which expands by counting:
-gabc+3 is the same as saying -gabc -gabc1 -gabc2 -gabc3
ttt+5 is the same as saying ttt ttt1 ttt2 ttt3 ttt5 ttt5
-g+6 is the same as saying -g -g -g -g -g -g -g
If you have a directory of puzzles, with filenames indicating page
numbers, say, as in page1 page2 ... page100, you can solve them all
by specifying page1+99 .
Each puzzle input file represents "empty" by ".", otherwise uses 1--9.
If a line contains a sharp sign (#), the # and all following characters
on that line are ignored. Characters other than . or 1-9, including blanks,
are also ignored. Here is an example input file:
# page 1 of puzzle book
5.7...3..
...2...5.
2.3.9.1..
.2.75.8..
.9...4.6.
1...8....
3..5....1
.....3...
4....19.5
At the moment, only 9x9 puzzles are supported.
All puzzles are read/saved in the "puzzles" subdirectory of the current directory.
Examples:
sudoku.py -g # generate, solve, and rate a random puzzle
sudoku.py -g -f # generate a random puzzle and save it
suodku.py -g -s # generate a random puzzle and solve it
sudoku.py -g -r # generate a random puzzle and rate it
sudoku.py -ga12 # generate and print random puzzle with seed a12
sudoku.py -ga12 -s -r # solve and rate random puzzle generated from seed a12
sudoku.py -r pa pb # rate puzzles in files "pa" and "pb"
sudoku.py -s pa pb # solve puzzles in files "pa" and "pb"
sudoku.py pa -d -s # solve and detail reasoning for solving puzzle "pa"
sudoku.py -s pa1+3 # solve puzzles pa1 pa2 pa3 pa4
sudoku.py -g+10 # generate, rate, and solve 10 puzzles
"""
# n is the size of the square and the number of digits in the sudoku alphabet
# a block has nr rows and nc columns, where nr*nc = n
# row indices are in [1,...,n]
# col indices are in [1,...,n]
# blk indices are in [1,...,n] (across rows first, then down)
# values are in [1,...,n] or UNDEFINED (0)
import profile
import random
import string
import sys
import time
# Some global constants
UNDEFINED = 0 # undefined value represented by 0
rating_times = 20 # number of times to solve puzzle to get rating
class Pos:
"""
Implements a sudoku position in the grid, i.e. an individual square.
"""
def __init__(self,r,c):
"""
Construct/initialize position in row r and col c, 1<=r,c<=n.
"""
# STATIC attributes defining general structure of problem
self.r = r # row index 1<=r<=n
self.c = c # col index 1<=c<=n
# self.row # will contain pointer to row object (group)
# self.col # will contain pointer to col object (group)
# self.blk # will contain pointer to blk object (group)
# self.grps # will contain [row,col,blk]
# DYNAMIC attributes that change as puzzle is worked on.
# These two attributes are the ONLY values in this program
# that are dynamic in this sense, so they are the only values
# that need to be saved/restored for backtracking.
self.val = UNDEFINED
self.possibilities = range(1,n+1)
class Group:
"""
Implements a group (i.e. row, col, or block);
a set of n positions constrained to have each value exactly once.
"""
def __init__(self,gt,i):
"""
Construct and initialize a group.
gt = "row","col", or "blk", respectively (group_type)
i = 1 to n, inclusive, giving index of group within group_type
"""
self.group_type = gt # "row", "col", or "blk"
self.index = i # 1 to n
self.posns = [] # positions in this group,
# to be filled in later cross-linking
# Some global variables
#
# T is (n+1)x(n+1) array (0-th col and 0-th row unused)
# T[i][j] is Pos for row i, column j
#
# sudoku_alphabet[i] is the printed version of the i-th symbol
#
# rows = list of all rows
# cols = list of all cols
# blks = list of all blocks
# grps = list of all groups (rows, cols, or blocks)
# posns = list of all positions
def initialize(n0,nr0,nc0):
"""
initialize(n) -- set up for table of size n with nr x nc blocks
"""
global n, nr, nc
global posns, rows, cols, blks, grps
global T, sudoku_alphabet
# save and check n, nr, nc
n = n0
nr = nr0
nc = nc0
assert n >= 1
assert nr >= 1
assert nc >= 1
assert n == nr * nc
assert n < 36
sudoku_alphabet = ".123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[:n+1]
# create all positions
# array of posns T is actualy (n+1) x (n+1)
posns = []
T = [ [0]*(n+1) for r in range(n+1) ]
for r in range(1,n+1):
for c in range(1,n+1):
p = Pos(r,c)
T[r][c] = p
posns.append(p)
# create all groups
rows = [Group("row",i) for i in range(1,n+1)]
cols = [Group("col",i) for i in range(1,n+1)]
blks = [Group("blk",i) for i in range(1,n+1)]
grps = rows+cols+blks
# now cross-link positions and groups
for row in rows:
r = row.index
for col in cols:
c = col.index
p = T[r][c]
# link pos p to groups containing it
p.row = row
p.col = col
blk = blks[((r-1)/nr)*nr + (c-1)/nc]
p.blk = blk
p.grps = [p.row,p.col,p.blk]
# and reverse
row.posns.append(p)
col.posns.append(p)
blk.posns.append(p)
def print_puzzle(file = sys.stdout):
"""
Print out the current puzzle configuration, nicely.
"""
global T
print_block_lines = True
for r in range(1,n+1):
line = ""
for c in range(1,n+1):
line = line + " " + sudoku_alphabet[T[r][c].val] + " "
if print_block_lines and c>file,line
if print_block_lines and r>file,"-"*(3*n+n/nc-1)
file.flush()
def set_pos(r,c,v):
"""
Set position at row r col c to have value v.
Value v may be UNDEFINED (0) or in [1,...,n].
"""
assert 1<=r<=n
assert 1<=c<=n
assert 0<=v<=n
global T, debug_print
p = T[r][c]
p.val = v
# if not setting p to UNDEFINED,
# set p's possibility list to just [v]
# and remove v from possibilities for other positions q in same groups g as p
if v == UNDEFINED:
return
p.possibilities = [v]
for g in p.grps:
for q in g.posns:
if p != q and v in q.possibilities:
q.possibilities = q.possibilities[:]
q.possibilities.remove(v)
# print "remove", q.r, q.c, v, "due to", p.r, p.c, v
# CHECK FOR UNSOLVABILITY:
if len(q.possibilities)==0:
if debug_print:
print "UNSOLVABLE!"
raise "UNSOLVABLE"
def trim(x,alphabet):
"""
Return input string x with all characters not in alphabet removed.
"""
s = ""
for a in x:
if a in alphabet:
s += a
return s
def initialize_from_rows(s):
"""
s is an array of strings, one per row.
"""
global n
initialize(9,3,3) # assumes 9x9 for now
s = [ trim(string.split(x,"#")[0],sudoku_alphabet) for x in s ] # eliminate comments
s = [ x for x in s if len(x)>0 ]
if len(s) != n:
print "Input does not have %d rows"%n
print s
assert len(s) == n
for r in range(1,n+1):
row = s[r-1]
for c in range(1,n+1):
while len(row)>0 and row[0] not in sudoku_alphabet:
row = row[1:]
assert len(row)>0
val = row[0]
val = sudoku_alphabet.find(val)
assert val>=0
set_pos(r,c,val)
row = row[1:]
def initialize_from_string(s):
"""
Input s is a string defining input sudoku puzzle.
Each line describes one row using digits 1--9 and "." for empty
"""
s = string.split(s)
initialize_from_rows(s)
def initialize_from_file(puzzle_filename):
"""
Input puzzle from file.
Leading and trailing blanks on each line are ignored.
Comment lines whose first nonblank is a sharp are ignored.
Example file:
# page 1 of puzzle book
5.7...3..
...2...5.
2.3.9.1..
.2.75.8..
.9...4.6.
1...8....
3..5....1
.....3...
4....19.5
Assumes puzzle is in directory "puzzles".
"""
# First remove any illegal characters from filename
filename_alphabet = string.letters + string.digits + "-_+~."
puzzle_filename = trim(puzzle_filename,filename_alphabet)
assert len(puzzle_filename)>0
try:
puzzle_file = open("puzzles/"+puzzle_filename+".txt","r")
except:
print "Puzzle file '"+puzzle_filename+"' doesn't exist!"
raise "puzzle filename error"
return
lines = puzzle_file.readlines()
initialize_from_rows(lines)
puzzle_file.close()
def write_to_file(puzzle_filename,header_string):
"""
Write current puzzle to the specified file,
with header_string on first line, commented out.
"""
try:
puzzle_file = open("puzzles/"+puzzle_filename+".txt","w")
except:
print "Can't open puzzle file",puzzle_filename,"for writing!"
return
print >>puzzle_file,"#",header_string
print_puzzle(puzzle_file)
puzzle_file.close()
return
def save_state():
"""
Return current state of puzzle solving;
that is, return list of triples: p, p's value, p's possibilities
"""
global posns
return [(p,p.val,p.possibilities[:]) for p in posns]
def restore_state(old_state):
"""
Restore puzzle state to old_state.
"""
global posns
for (p,p_val,p_possibilities) in old_state:
p.val = p_val
p.possibilities = p_possibilities[:]
def number_of_undefined_posns():
"""
Return the number of unfilled (undefined) positions.
"""
global posns
return len( [p for p in posns if p.val == UNDEFINED] )
def compute_possibilities():
"""
Compute possible values for each position.
These are based ONLY on excluding values already
established within the same group (row, col, or blk).
This is a "recompute from scratch" operation.
"""
global posns, debug_print
for p in posns:
if p.val == UNDEFINED:
p.possibilities = range(1,n+1)
for g in p.grps:
for q in g.posns:
if q.val in p.possibilities:
p.possibilities = p.possibilities[:]
p.possibilities.remove(q.val)
# CHECK FOR UNSOLVABILITY:
if len(p.possibilities)==0:
if debug_print:
print "UNSOLVABLE!"
raise "UNSOLVABLE"
else:
p.possibilities = [p.val]
def S1():
"""
Strategy 1:
If a position has only one possibility, choose it.
Returns True if something was forced, else returns False
Stops after forcing the first forcable position.
"""
global debug_print
for p in posns:
if p.val == UNDEFINED and len(p.possibilities) == 1:
set_pos(p.r,p.c,p.possibilities[0])
if debug_print:
print
print "S1", "Row", p.r, "Col", p.c, "can only have a", p.possibilities[0]
print_puzzle()
return True
return False
def S2():
"""
Strategy 2:
If for some group there is a value that can only go in
one place in that group, then chose it.
Returns True if something was forced, else returns False
"""
global debug_print
for g in grps:
for val in range(1,n+1):
cango = [p for p in g.posns if p.val == UNDEFINED and val in p.possibilities]
if len(cango) == 1:
p = cango[0]
set_pos(p.r,p.c,val)
if debug_print:
print
print "S2","In",g.group_type,g.index,",",val,"must go in row",p.r,"col",p.c
print_puzzle()
return True
return False
def S3():
"""
Strategy 3:
If for some group g1 there is a value whose only possibilities
within g1 also lie in some other group g2, then that val may not
go in positions in g2 that lie outside of g1.
Returns True if something was changed, else returns False
"""
global debug_print
something_changed = False
return False
### BASED ON PROFILING STUDIES, IT SEEMS THAT
### S3 IS NOT WORTH ALL THE TIME IT TAKES... SO S3 IS DISABLED.
### OMIT PREVIOUS LINE TO RESTORE S3 TO FUNCTIONING.
for g1 in grps:
for val in range(1,n+1):
cango = [p for p in g1.posns if p.val == UNDEFINED and val in p.possibilities]
if len(cango)>1:
for g2 in cango[0].grps:
g2OK = True
for pos in cango:
if g2 not in pos.grps:
g2OK = False
if g2OK:
# now val can go several places within g1
# but those places are all within g2 as well
# so remove val from places within g2 outside of g1
for pos in g2.posns:
if not g1 in pos.grps and val in pos.possibilities:
pos.possibilities = pos.possibilities[:]
pos.possibilities.remove(val)
if debug_print:
print
print "S3","row",pos.r,"col",pos.c, "may not be",val
print "because in",g1.group_type,g1.index
print "all possibilities for",val, "lie within",g2.group_type,g2.index
print_puzzle()
something_changed = True
# CHECK FOR UNSOLVABILITY HERE:
if len(pos.possibilities)==0:
if debug_print:
print "UNSOLVABLE!"
raise "UNSOLVABLE"
return something_changed
def S4():
"""
Strategy 4:
If for some group there are two positions that have the
exact same two possible values, then those values can not go
other places within that group
Returns True if something was changed, else returns False
"""
global debug_print
something_changed = False
for g in grps:
for p in g.posns:
if len(p.possibilities) ==2:
for q in g.posns:
if q!=p and q.possibilities == p.possibilities:
for val in p.possibilities:
for pos in g.posns:
if pos!=p and pos!=q and val in pos.possibilities:
pos.possibilities = pos.possibilities[:]
pos.possibilities.remove(val)
if debug_print:
print "S4","row",pos.r,"col",pos.c,"may not be",val
print "because in",g.group_type,g.index
print "positions at row",p.r,"col",p.c,"and","row",q.r,"col",q.c
print "have the same possibilities:",p.possibilities
print_puzzle()
something_changed = True
# CHECK FOR UNSOLVABILITY HERE
if len(pos.possibilities)==0:
if debug_print:
print "UNSOLVABLE!"
raise "UNSOLVABLE"
return something_changed
def make_forced_move():
"""
Find a forced move and make it. (at most one move made)
Return True if a forced move was found, else return False.
Strategies S1 and S2 make forced moves;
strategies S3 and S4 are only used if necessary,
to update possibilities; they don't actually make a move,
but facilitate S1 and S2's operations.
All these strategies return True if they make progress.
"""
keep_going = True
while keep_going:
if S1() or S2():
return True
keep_going = S3() or S4()
return False
def solve(numwanted, depth = 0, solns = []):
"""
Solve currently established puzzle.
return list of length 0,...,numwanted giving up to numwanted solutions found
(typically numwanted will be 1 or 2)
depth is recursion (guess) depth level so far;
initial top-level call supplies depth = 0
solns gives solutions found so far in other parts of search tree
"""
global debug_print, moves_made, guesses_made, guess_depth
assert len(solns)1]
L.sort()
numpos = L[0][0]
L = [x for x in L if x[0] == numpos]
L = shuffle(L)
r = L[0][1]
c = L[0][2]
p = T[r][c]
# guess and recurse
state = save_state()
for val in shuffle(p.possibilities):
# print depth,"TRYING by guessing",val,"(from",p.possibilities,") for row",p.r,"column",p.c
if debug_print:
print depth,"TRYING by guessing",val,"(from",p.possibilities,") for row",p.r,"column",p.c
set_pos(p.r,p.c,val)
moves_made += 1
guesses_made += 1
try:
solns = solve(numwanted,depth+1,solns)
if len(solns) == numwanted:
return solns
except:
pass
restore_state(state)
if debug_print:
print depth,"FINISHED guessing",val,"(from",p.possibilities,") for row",p.r,"column",p.c
return solns
def shuffle(L):
"""
Return a random permutation of a copy of the list L.
"""
L = L[:]
random.shuffle(L)
return L
# Some puzzles from books that have been solved with this program:
# Pocket Sudoku (ps): ps1, ps13, ps50, ps76, ps101, ps127, ps147, ps148
# The Ultimate Sudoku Challenge (tusc): tusc23, tusc88, tusc90, tusc190
# The Book of Sudoku, No 2 (bos2p): bos2p132, bos2p21
def simplify_puzzle():
"""
"Simplify" puzzle by removing assignments to positions
if this preserves the unique puzzle solution.
(The puzzle is "simpler" only in that it is now less filled in;
it is probably harder to solve.)
"""
for p in posns:
if p.val != UNDEFINED:
state = save_state()
val = p.val
set_pos(p.r,p.c,UNDEFINED)
compute_possibilities()
nsolns = len(solve(2))
if nsolns == 1:
if debug_print:
print "Removing:",p.r,p.c,val, "OK:"
restore_state(state)
if nsolns == 1:
set_pos(p.r,p.c,UNDEFINED)
compute_possibilities()
if debug_print:
print "Simplified puzzle:"
print_puzzle()
def generate_puzzle():
"""
Make up a sudoku puzzle.
"""
global posns, guess_depth, debug_print, moves_made, guesses_made
initialize_from_string(".........\n"*9)
# pick and fill in random positions that have more than one possibility
for p in [p for p in shuffle(posns) if len(p.possibilities)>1]:
state = save_state()
if debug_print:
print "working on position",p.r,p.c
print "p.possibilities = ",p.possibilities
print_puzzle()
# Find a value v that is results in at least one soln at position p
for v in shuffle(p.possibilities):
restore_state(state)
try:
set_pos(p.r,p.c,v)
if debug_print:
print "Setting:",p.r, p.c, v
print_puzzle()
nsolns = len(solve(2))
if debug_print:
print "Setting:",p.r, p.c, v, "-->", nsolns, "solutions"
except:
if debug_print:
print "this puzzle state is unsolvable... exception raised."
nsolns = 0
if nsolns == 0:
# this value of v didn't work out; keep looking...
continue
elif nsolns==1:
if debug_print:
print "Here is puzzle:"
restore_state(state)
set_pos(p.r,p.c,v)
simplify_puzzle()
if debug_print:
print "Final (simplified) puzzle:"
print_puzzle()
return
else:
# more than one solution exists;
# set v at p and keep going with next p
restore_state(state)
set_pos(p.r,p.c,v)
break
def score(moves_made,guesses_made,guess_depth):
"""
Compute a score for a puzzle, based on parameters from solving it.
"""
return moves_made + 10*guesses_made + 50 * guess_depth
def parse_arg(s):
"""
Here input s is a string of the form tu+r or tu or just t
where
t is a possibly empty string not ending in a digit
u is a maximal length (possibly zero length) string of digits
r is a (possibly zero length) string of decimal digits
Return (t,int(u),int(r)) (string, int, int)
if u or r is missing then a zero value is return for those components.
Example: "x3y4+5" returns ("x3y",4,5)
"""
t = ""
u = ""
r = ""
tu_r = s.split("+")
tu = tu_r[0]
if len(tu_r)>1:
r = tu_r[1]
try:
intr = int("0"+r)
assert 0<=intr<=1000
except:
print "Illegal repetition count",r,"ignored."
intr = 0
for c in tu:
u = u + c
if not c.isdigit():
t = t + u
u = ""
return (t,int("0"+u),intr)
def main():
"""
main routine to interpret command-line arguments.
"""
global debug_print, guesses_made, guess_depth, moves_made
if len(sys.argv)==1:
print usage_string
return
# first collect processing options, wherever they are
processing_options_specified = False
solve_puzzle = False
rate_puzzle = False
save_puzzle = False
debug_print = False
for arg in sys.argv[1:]:
if arg[:2] == "-d":
debug_print = True
elif arg[:2] == "-s":
solve_puzzle = True
processing_options_specified = True
elif arg[:2] == "-r":
rate_puzzle = True
processing_options_specified = True
elif arg[:2] == "-f":
save_puzzle = True
processing_options_specified = True
if not processing_options_specified:
solve_puzzle = True
rate_puzzle = True
# now process each puzzle specified
header_string = "" # file header line for file output option
arglist = sys.argv[1:]
while len(arglist)>0:
arg = arglist[0]
arglist = arglist[1:]
if arg[0] == "-" and arg[:2] not in ["-g","-i"]:
# processing options have already been handled; skip here
continue
print # blank line on output starts each puzzle
if arg[:2] == "-g":
# -gxxx+yy set seeds to xxx and generates yy additional puzzles
# e.g. -gxx5+3 ==> uses seeds xx5 xx6 xx7 xx8
# e.g. -gxx+4 ==> uses seeds xx xx1 xx2 xx3 xx4
(t,u,r) = parse_arg(arg[2:])
if t == "" and u == 0:
t = "%d"%int(time.time())
if u>0:
seed_string = "%s%d"%(t,u)
else:
seed_string = t
random.seed(seed_string)
generate_puzzle()
header_string = "Puzzle generated from seed '" + seed_string + "' :"
print header_string
print_puzzle()
state = save_state()
filename = seed_string
# now prepare for iteration, by stuffing new arg at front of
# arglist that parses to (t,u+1,r-1)
if r>0:
new_arg = "-g%s%d+%d"%(t,u+1,r-1)
arglist = [new_arg]+arglist
elif arg[:2] == "-i":
print "Enter puzzle, followed by a blank line:"
s = ""
while True:
line = sys.stdin.readline()
line = string.strip(line)
if line == "":
break
s = s + line + "\n"
initialize_from_string(s)
state = save_state()
filename = "I%d"%random.randrange(1,999999999)
header_string = "Puzzle read from input:"
print header_string
print_puzzle()
else:
# abc+2 generates abc abc1 abc2
(t,u,r) = parse_arg(arg)
if t == "" and u == 0:
print "argument", arg, "illegal; ignored."
continue
if u>0:
filename = "%s%d"%(t,u)
else:
filename = arg
try:
initialize_from_file(filename)
except:
continue
header_string = "Puzzle read from file: " + filename
print header_string
print_puzzle()
state = save_state()
# now prepare for iteration, by stuffing new arg at front of
# arglist that parses to (t,u+1,r-1)
# e.g. abc3+7 generates filename abc3 and puts abc4+6 at front of arglist
if r>0:
new_arg = "%s%d+%d"%(t,u+1,r-1)
arglist = [new_arg]+arglist
if solve_puzzle:
solns = solve(2) # ask for up to 2 solns, to check for uniqueness
if len(solns)==0:
print "NO SOLUTION EXISTS"
elif len(solns)==1:
print "Puzzle solution:"
restore_state(solns[0])
print_puzzle()
print "SOLUTION IS UNIQUE"
else:
print "MULTIPLE SOLUTIONS EXIST; HERE IS ONE SOLUTION:"
restore_state(solns[0])
print_puzzle()
if rate_puzzle:
score_list = []
random.seed(1) # so rating is deterministic function of puzzle
for i in range(rating_times):
restore_state(state)
solve(1)
score_list += [score(moves_made,guesses_made,guess_depth)]
score_list.sort()
rating = score_list[rating_times/2]
print "Puzzle rating:",rating,
restore_state(state)
if rating == number_of_undefined_posns():
print "(easy)"
elif rating < score(n*n,5,1):
print "(moderate)"
else:
print "(hard)"
if save_puzzle:
if arg[0] != "-":
print "Puzzle read from file '"+arg+"' will not be re-saved."
else:
write_to_file(filename,header_string)
print "Puzzle saved to file: ",filename
# profile.run("main()")
main()