Outputs difficult games with solutions.
Python, 170 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 | #!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Sudoku game maker
"""
__author__ = 'Ripley6811'
__contact__ = 'python at boun.cr'
__copyright__ = ''
__license__ = ''
__date__ = 'Thu Aug 30 10:09:06 2012'
__version__ = '0.1'
#===============================================================================
# IMPORT STATEMENTS
#===============================================================================
from numpy import *
#===============================================================================
# METHODS
#===============================================================================
def new_block():
return random.permutation(arange(1,10)).reshape(3,3)
def test_rowcol(S):
retval = True
for row in S:
if len(set(row).difference([0])) < count_nonzero(row):
retval = False
break
for col in S.T:
if len(set(col).difference([0])) < count_nonzero(col):
retval = False
break
return retval
def generate_grid(S=None, verbose=False):
#PART 1: SET FIRST THREE ROWS AND FIRST THREE COLUMNS
available = set(range(1,10))
if S == None:
S = new_block()
if verbose: print S
while True:
Srow = append(append(S,new_block(),1),new_block(),1)
if test_rowcol(Srow):
if verbose: print Srow
break
while True:
Scol = append(append(S,new_block(),0),new_block(),0)
if test_rowcol(Scol):
Scol = append(Scol[3:],zeros((6,6),int),1)
if verbose: print Scol
break
S = append(Srow,Scol,0)
#PART 2: FILL IN THE REST OF GRID FROM PART 1. [3:,3:]
if verbose: print '.',
while True:
S[3:6,3:6] = new_block()
if test_rowcol(S[:6,:6]):
break
while True:
S[6:,6:] = new_block()
if test_rowcol(S):
break
for i in range(3,9):
for j in range(3,9):
if S[i,j] == 0:
subset = available.difference( set(S[i]) ).difference( set(S[:,j]) )
if len(subset) == 1:
S[i,j] = subset.pop()
else:
S[3:,3:] = 0
return generate_grid(S, verbose)
if verbose: print '\n', S
return S
def reduce_options(board, Pcube):
row,col = where(board == 0)
playoption = []
for i in range(9):
for j in range(9):
if board[i,j] != 0:
Pcube[i,j,Pcube[i,j]!=board[i,j]] *= 0
for i,j in zip(row,col):
exclude = set(board[i])
exclude = exclude.union(board[:,j])
exclude = exclude.union(board[i/3*3:i/3*3+3,j/3*3:j/3*3+3].flat)
for each in exclude:
Pcube[i,j,Pcube[i,j]==each] = 0
for layer in Pcube.T: # probable layers 1 through 9
for i in range(9):
rowsfilled = sum(layer[i,:3])>0, sum(layer[i,3:6])>0, sum(layer[i,6:])>0
if sum(rowsfilled) == 1:
rowsfilled = repeat(rowsfilled,3)
layer[i/3*3+(i+1)%3,rowsfilled] *= 0
layer[i/3*3+(i+2)%3,rowsfilled] *= 0
layer = layer.T
for i in range(9):
rowsfilled = sum(layer[i,:3])>0, sum(layer[i,3:6])>0, sum(layer[i,6:])>0
if sum(rowsfilled) == 1:
rowsfilled = repeat(rowsfilled,3)
layer[i/3*3+(i+1)%3,rowsfilled] *= 0
layer[i/3*3+(i+2)%3,rowsfilled] *= 0
# print str(Pcube.T).replace('0','~')
for i,j in zip(row,col):
if count_nonzero(Pcube[i,j]) == 1:
playoption.append( (i,j,sum(Pcube[i,j])) )
return playoption
def generate_game(S, verbose=False):
gametest = S.copy()
for each in range(200):
i = random.randint(81)
temp = gametest.flat[i]
gametest.flat[i] = 0
if not isSolvable(gametest):
gametest.flat[i] = temp
return gametest
def isSolvable(testgame):
board = testgame.copy()
P = ones((9,9,9),int)
for i in arange(9):
P[:,:,i] *= i+1
print 'GAME\n', str(board).replace('0','_')
playorder = []
laststate = sum(P)
while sum(board == 0) > 0:
#REDUCE OPTIONS FOR EACH HOLE
playoptions = reduce_options(board, P)
print playoptions
# print str(board).replace('0','_')
for i,j,v in playoptions:
board[i,j] = v
thisstate = sum(P)
if thisstate == laststate:
break
else:
laststate = thisstate
return True if sum(board == 0) == 0 else False
def main():
"""Description of main()"""
solution = generate_grid(verbose=True)
sudoku = generate_game(solution, verbose=True)
print 'Solution\n', solution
print 'Sudoku\n', str(sudoku).replace('0','_')
print sum(sudoku == 0), 'blanks (', int(sum(sudoku == 0)/.81), '%)'
if __name__ == '__main__':
main()
|
Started playing Sudoku a few weeks ago and decided to try to write a game generator.
I don't know how to rank difficulty and I don't know if the generated games have more than one solution, but the three times I've tried are all solvable and difficult.
The output is text. Maybe I'll create output images later. Ideas for improvement:
- Output printable images of games with upside down small solution image
- Add difficulty option
Solution creation algorithm:
- Randomly generate top three and left three cells (cell = 3x3)
- Based on the five cells, find a solution by filling in the rest. Repeating until a solution is found. Hypothesis is that there must be at least one solution, so the first five are not regenerated. 2a. Randomly generate middle and right bottom cells until it fits. 2b. The values in the last two cells are filled in logically. If there is any conflict then go back to '2a'.
Game creation algorithm:
- Randomly remove a value from the board.
- Test if it is still solvable. True: goto 1. and try removing another. False: replace the removed value and goto 1.
- Terminate after a number of iterations (I chose 200).
Solving algorithm:
- Create a list of all possible values in a 9x9x9 array 1a. indices i and j are board position and k is the array of available numbers
- For each filled space, set all but the used number to zero in the available list
- For each empty space, remove values found in the row,col and cell from the available list.
- For each layer of the possibility cube, see if there is a row with values available only in one cell. If so, remove the values from the other two rows of the same cell with the values. 4a. Transpose the layer and repeat.
