Impromptus

We define a super sudoku to be a sudoku with extra constraints. If we divide a sudoku board of size 3^2 * 3^2 into “fat rows” and “thin rows” and “fat columns” and “thin columns”, then it takes 4 coordinates to uniquely address a square on the board, so a square’s coordinate will be (fat column, thin column, fat row, thin row).

Using this idea, the regular sudoku constraints can be encoded in a prolog-like way as

for i = 1 .. 3 and j = 1 .. 3
     UNIQUE(i, *, j, *)   # Every square contains ever number
     UNIQUE(i, j, *, *)   # Every column contains every number
     UNIQUE(*, *, i, j)   # Every row contains every number

by symmetry, we can then make three new rules to complete the set:

     UNIQUE(*, i, *, j)
     UNIQUE(i, *, *, j)
     UNIQUE(*, i, j, *)

Note that these 6 rules are all of the possible (4 choose 2) rules for this encoding.

Now, are there any super sudoku squares of size n^2 * n^2 for n = 1,2,3,….? That question was answered in the presentation I learned about the problem as well as (I’m told) in an independent paper written by someone else. If these do exist, how many are there? Well, I wrote code to find this out and preliminary results are:

The code that found these is after the cut, and is O((n²)!^n2-1):

#!/usr/bin/env python
# (c) 2007 Peter Boothe (pboothe @gmail.com)
# Offered up to you under the terms of the GPL
#  - http://www.fsf.org/licensing/licenses/gpl.html

# This code will count the number of super sudoku on an n^2 * n^2 board.  To
# change the value of n, go to line 111
# Already calculated is:
#  n   count
#  1       1
#  2       0
#  3     104
#  4   >1631

from __future__ import division

class SuperSudoku:
    def __init__(self, n):
        self.count = 0
        self.n = n
        self.rows = {}
        self.columns = {}
        self.squares = {}
        self.points = {}
        self.minicolumns = {}
        self.minirows = {}
        self.board = [ [ None for i in range(n*n) ] for i in range(n*n) ]

        for i in range(n*n):
            self.rows[i] = {}
            self.columns[i] = {}
            self.squares[i] = {}
            self.points[i] = {}
            self.minicolumns[i] = {}
            self.minirows[i] = {}

    def okay_to_add(self, val, x,y):
        self.count += 1
        if self.count % 10000 == 0:
            print self.count, 'boards tested so far...'

        if self.board[x][y] != None: return False

        fi, fj, i, j = self.twotofour(x,y)
        if val in self.rows[fi*self.n + i]: return False
        if val in self.columns[fj*self.n + j]: return False
        if val in self.squares[fi*self.n + fj]: return False
        if val in self.points[i*self.n + j]: return False
        if val in self.minicolumns[fi*self.n + j]: return False
        if val in self.minirows[i*self.n + fj]: return False
        return True

    def add(self, val, x, y):
        self.board[x][y] = val
        fi, fj, i, j = self.twotofour(x,y)
        self.rows[fi*self.n + i][val] = None
        self.columns[fj*self.n + j][val] = None
        self.squares[fi*self.n + fj][val] = None
        self.points[i*self.n + j][val] = None
        self.minicolumns[fi*self.n + j][val] = None
        self.minirows[i*self.n + fj][val] = None

    def remove(self, x, y):
        val = self.board[x][y]
        self.board[x][y] = None

        fi, fj, i, j = self.twotofour(x,y)
        del self.rows[fi*self.n + i][val]
        del self.columns[fj*self.n + j][val]
        del self.squares[fi*self.n + fj][val]
        del self.points[i*self.n + j][val]
        del self.minicolumns[fi*self.n + j][val]
        del self.minirows[i*self.n + fj][val]

    def twotofour(self, i ,j):
        return i // self.n, j // self.n, i%self.n, j%self.n

    def __str__(self):
        s = ""
        for y in range(self.n*self.n):
            if y % self.n == 0:
                s += '-' * (self.n*self.n*2 + self.n + 1) + '\n'
            for x in range(self.n*self.n):
                if x % self.n == 0:
                    s += '|'
                if self.board[x][y] != None:
                    s += '%2d' % (self.board[x][y]+1)
                else:
                    s+= ' .'
            s += '|\n'
        s += '-' * (self.n*self.n*2 + self.n + 1)
        return s

def genAllBoards(board, n, x, y):
    if x == n:
        y = y+1
        x = 0

    if y == n:
        yield board
        return

    for potential in range(n):
        if board.okay_to_add(potential, x,y):
            board.add(potential, x, y)
            for b in genAllBoards(board, n, x+1, y):
                yield b
            board.remove(x, y)

n = 5
board = SuperSudoku(n)

for x in range(n*n):
    board.add(x, x, 0)

count = 0
for b in genAllBoards(board, n*n, 0, 1):
    print board
    print count, "so far..."
    count += 1
print count, 'boards are valid - we checked', board.count, 'boards'