Dave Angel <da...@davea.name>: > When in a playful mood, I wonder if all the Sudoku puzzles out there > are just permutations of a few hundred written by Will Shortz.
A sudoku solver can be trivially turned into a puzzle generator: ======================================================================== $ ./sudoku.py --generate >puzzle.dat $ cat puzzle.dat 3 . 2 . 4 . . . . 4 5 . . . 6 . . . 6 . . . 9 . . 8 . . . . . . . 5 . . . 6 4 . . 9 . 3 . . 7 3 5 . . . 4 8 . . . . . . 8 . . . 8 . . 7 . . . 3 . . . . 1 . . . 2 $ ./sudoku.py <puzzle.dat 3 9 2 8 4 7 1 6 5 4 5 8 1 3 6 7 2 9 6 1 7 2 9 5 3 8 4 8 2 1 4 6 3 5 9 7 5 6 4 7 8 9 2 3 1 9 7 3 5 2 1 6 4 8 1 4 9 3 5 2 8 7 6 2 8 5 6 7 4 9 1 3 7 3 6 9 1 8 4 5 2 ======================================================================== ======================================================================== #!/usr/bin/env python3 import sys, random M = 3 N = M * M P = M * N Q = M * P EMPTY = "." buddies = [ [ buddy for buddy in range(Q) if buddy != slot and (buddy % N == slot % N or buddy // N == slot // N or buddy // P == slot // P and buddy % N // M == slot % N // M) ] for slot in range(Q) ] interned = { n : n for n in range(1, N + 1) } candidates = list(interned.values()) def main(): if len(sys.argv) > 1 and sys.argv[1] == "--generate": generate() return board = [] for n in sys.stdin.read().split(): try: board.append(int(n)) except ValueError: board.append(EMPTY) for solution in solve(board): report(solution) def generate(): report(minimize(next(solve([ EMPTY ] * Q)))) def solve(board, slot=0): if slot == Q: yield board[:] elif board[slot] is EMPTY: shuffled = candidates[:] random.shuffle(shuffled) for candidate in shuffled: for buddy in buddies[slot]: if board[buddy] is candidate: break else: board[slot] = candidate yield from solve(board, slot + 1) board[slot] = EMPTY else: yield from solve(board, slot + 1) def minimize(board): while True: nonempty_slots = [ slot for slot in range(Q) if board[slot] is not EMPTY ] random.shuffle(nonempty_slots) for slot in nonempty_slots: removed, board[slot] = board[slot], EMPTY if uniquely_solvable(board): break board[slot] = removed else: return board def uniquely_solvable(board): it = solve(board[:]) next(it) try: next(it) except StopIteration: return True return False def report(board): print("\n".join( " ".join(str(board[row * N + col]) for col in range(N)) for row in range(N))) print() if __name__ == '__main__': main() ======================================================================== Marko -- https://mail.python.org/mailman/listinfo/python-list