Contest: Do you Sudoku? (with solutions and winners)

Winners!

We have winners! We have decided to offer TWO prizes each week. The first prize will go to the submission with the highest score. The second prize will go to the most clever and/or unusual submission.

See the contest rules for our grading rubric.

The winners are:
For best entry, the winner is Bill Tierny, with his Visual Basic submission and a combined score of 18.5.
The prize for most unusual submission goes to Rob Wiese, for his DOS batch script entry.
Both are posted below.
Congratulations!

The Problem

The game of Sudoku is played on a 9x9 grid subdivided into nine 3x3 regions. Each grid call can contain a single number 1-9. There can be no repeated numbers in each row of the larger grid, each column of the larger grid, and within each 3x3 region. As you may know, the larger grid is only partially filled out to begin with and the object of the puzzle is to fill in the rest of the cells given the constraints listed.

You solve the puzzle by filling in the empty cells. As you play, you are constantly checking to see which numbers are available for you to choose from. That is, given a list of numbers which are already used in a particular row, column, or 3x3 region, you want to know which ones are still available.

Specification

Method/function name: sudoku

Input: List or array of integers. The list can be of any length, although no input will have more than 30. The numbers can be any integer, including negatives.

Returns: List or array of integers, each in the range 1-9, which are not in the input list. The returned list does not need to be sorted.

Examples

Input: 4, 2, 9, 1, 7
Returns: 3, 5, 6, 8

Input: (empty list)
Returns: 1, 2, 3, 4, 5, 6, 7, 8, 9

Input: 6, 9, 1, 2, 3, 8, 7, 5, 4
Returns: (empty list)

Input: 2, 9, 2, 18, 8, -45, 9, 1, 7, 456, 12, 3, 2, 8, 100, 5
Returns: 4, 6

Please note that this program does not actually solve a Sudoku game.

What To Submit

Your program must be submitted in one of the following formats:

  • A single source file (text only) with comments that include your name(s) and instructions on how to load, compile, and run your program.
  • For Java submissions, a JAR file containing your .java files and a README file listing your name(s) and instructions on how to run your program or give input to your method.
  • For all others, Zip file containing the source files and a README file listing your name(s) and instructions on how to load, compile, and run your program or give input to the method/function

All submissions must by in by 11:59pm on Monday, April 6. Send your submissions to contest@cs.sierracollege.edu with the subject "CONTEST: Sudoku". Be sure to read the contest rules and guidelines before submitting your entry.

Feel free to discuss this contest by adding your comments below!

Bill Tierny's Solution

'Programmer: Bill Tierney CS27   Email: tallbillsemail@gmail.com
Public Class sudokuNumbersForm
    Private Sub goButton_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles okButton.Click
        Me.outLabel.Text = Sudoku(inTextBox.Text.Split(" "c, ","c, ";"c, ":"c)).TrimEnd(" "c, ","c)
    End Sub
    Private Function Sudoku(ByVal numbersUsedString() As String) As String
        Sudoku = ""
        For validInteger As Integer = 1 To 9
            Dim matchBoolean As Boolean = False
            For Each numberString As String In numbersUsedString
                If numberString = validInteger.ToString() Then
                    matchBoolean = True : Exit For
                End If
            Next
            If Not matchBoolean Then
                Sudoku &= validInteger.ToString() & ", "
            End If
        Next
    End Function
End Class

Rob Wiese's Solution

@echo off
::##################################################################
::#  Sudoku helper
::# 
::##################################################################
::# Written by Rob Wiese
::# April 6, 2009 
::# Programming Contest.
::# Language:  Windows NT batch language. 
::# Compatible with NT 5.1 kernel.  Should work with more recent versions.  YMMV
::# Instructions:  Save file as c:\temp\sudoku.cmd
::# Open a command prompt
::# Type cd /d c:\temp
::# Command line usage:
::# sudoku 
::# Like:
::# sudoku 5 3 9 8 1
::# or
::# sudoku 1
::#################################################################

::	Setup the Environment
setlocal ENABLEDELAYEDEXPANSION
set TITLE= Sudoku Helper
set VERSION=.03
set results=
if exist .\sudoku.tmp del .\sudoku.tmp	

:: Create the universe of good numbers:

	for %%a in (1 2 3 4 5 6 7 8 9) do (set db_%%a=%%a)

:start

	TITLE=%TITLE%
	echo:
	echo Sudoku Helper
	echo =========================================================
	echo:

::  Test command line input and assign to variables.  

	if .%1==. @echo Congratulations - You have solved the puzzle and need no further help^^!  & goto exit
	
	for %%b in (%*) do call :args %%b

::  Determine what is missing	based on the command line arguments.
::  Remove in boundary numbers from the universe of good numbers.

	for /f %%d in (soduku.tmp) do (
		for %%c in (1 2 3 4 5 6 7 8 9) do (	
			if %%c == %%d set db_%%c=))

::  Assign whats left to a variable
	
	for %%e in (%db_1% %db_2% %db_3% %db_4% %db_5% %db_6% %db_7% %db_8% %db_9%) do set results=!results! %%e

:: Let the user know what they can still use to solve the puzzle:
		
	@echo You can still use:  %results%

	goto exit	
	

::##################################################################
::# Sub  args
::# purpose evaluate command line args 
::#
::#################################################################
:args

::	Throw away out of boundary arguments
:: Save in boundary arguments

	if %1 GTR 9 goto :eof
	if %1 LSS 1 goto :eof
	echo %1 >> .\sudoku.tmp	
  goto :eof

:exit
	if exist .\sudoku.tmp del .\sudoku.tmp
	echo:
	echo =========================================================	
	echo Sudoku Helper	- Finished.
	echo:

Other Solutions

I've cooked up solutions in several programming languages. There were two approaches to solving the problem.

In one solution, you run through the list of given numbers (we'll call it G) and build a second list (N) of the numbers 1-9 that appear in G. Then you loop from 1-9, displaying that number if it does not appear in N.

In the second approach, you start with a list N of the numbers 1-9 (which could be represented by an array of Booleans, with "true" indicating that the number is in the N list). Then you run through G, removing the number from N (by setting the value to false) as you go. Finally, you run through N, printing out the remaining numbers.

There are, of course, other ways of doing this problem.

Without further ado, here are some of my solutions.

Java

/**
 * 
 * @author Barry Brown
 * @version 4/3/2009
 * 
 * This is a basic implementation of the algorithm using a boolean[]
 * (array of booleans). The array represents which numbers have been
 * seen in the input.
 * 
 * Initally, the array of ten elements (0..9) is set to all false.
 * As we walk through the argument array, we set the corresponding entry
 * to true, indicating that the number has been seen.
 * 
 * When done, we walk through the boolean array, printing out the index
 * if the corresponding entry is false.
 *
 */

public class Sudoku
{

    public static void main(String[] args) {
        boolean[] isSeen = new boolean[10];
        for (int i = 0; i < 9; i++) {
            isSeen[i] = false;
        }

        // Walk through args, setting the corresponding entry in isSeen to true
        for (int i = 0; i= 1 && num <= 9) {
                isSeen[num-1] = true;
            }
        }

        // Display what's left in the array. If the entry is false, the index
        // hasn't been seen and we should display it.
        for (int i = 0; i < 9; i++) {
            if (isSeen[i] == false) {
                System.out.print(i+1 + " ");
            }
        }
        System.out.println();

    }

}

Perl

#! /usr/bin/perl

# Read numbers from the command line. If they are in the range 1-9, store
# a 1 at the corresponding location of the @sudoku array.
foreach $num (@ARGV) {
    if ($num >= 1 and $num <= 9) {
        $sudoku[$num] = 1;
    }
}

# Run through the @sudoku array, displaying the index if the value
# stored there is 0.
for $i (1 .. 9) {
    print "$i " unless $sudoku[$i];
}
print "\n";

Scheme

; A convenience variable that contains all the numbers 1-9
(define whole-list '(1 2 3 4 5 6 7 8 9))

; The top-level function
; sudoku the-list (list of numbers) --> list of numbers
; Given a list of numbers, return a list of the numbers 1-9 that are not
; in the given list.
; All this function does is invoke sudoku2 with the given list and the
; whole-list.
(define (sudoku the-list)
  (sudoku2 the-list whole-list))

; The function that does most of the work
; sudoku2 : remove-list (list of numbers), sudoku-list (list of numbers)
;    --> list of numbers
; Given a two lists of numbers, remove the numbers in remove-list from
; the numbers in sudoku-list.
(define (sudoku2 remove-list sudoku-list)
  (cond [(empty? remove-list) sudoku-list]
        [(empty? sudoku-list) '()]
        [(cons? remove-list) (sudoku2 (rest remove-list) 
                                      (remove (first remove-list) sudoku-list))]
        ))

; A helper function.
; remove : num (number), lon (list of numbers) --> list of numbers
; Remove all occurences of num from lon
(define (remove num lon)
  (cond [(empty? lon) '()]
        [else (cond [(= (first lon) num) (remove num (rest lon))]
                    [else (cons (first lon) (remove num (rest lon)))]
                    )]
        ))

; Examples
(sudoku '())
(sudoku '(1 2 3 4 5 6 7 8 9))
(sudoku '(4 2 9 1 5 2 4))
(sudoku '(-8 18 2 4 2 9 5 456 45 200 1 5 2))

bash and grep

#! /bin/bash

TMPFILE=/tmp/sudokunumbers

# Create a file with the numbers 1 .. 9 in it, one per line.
# Uses a "here-document" to put the numbers into the file.
cat >$TMPFILE <<DONE
1
2
3
4
5
6
7
8
9
DONE

# Go through the command line arguments, using grep
# to display the lines (numbers) that do not match the
# argument.
for i in "$@"
do
    grep -v $i $TMPFILE > $TMPFILE.new
    mv -f $TMPFILE.new $TMPFILE
done

# Display what's left in the file and remove it.
cat $TMPFILE
rm $TMPFILE

Perl (again)

#! /usr/bin/perl

# Start with the list of all numbers 1 through 9
@sudoku = (1 .. 9);

# For each command line argument, remove the number from @sudoku
# by *keeping* the elements that are not equal to the given argument.
for $arg (@ARGV) {
    @sudoku = grep { $arg != $_ } @sudoku;
}

# Display what's left
print "@sudoku\n";

bash and regular expressions

#! /bin/bash

TMPFILE=/tmp/sudokunumbers

# Create a file with the numbers 1 .. 9 in it, one per line.
# Uses a "here-document" to put the numbers into the file.
cat >$TMPFILE <<DONE
1
2
3
4
5
6
7
8
9
DONE

# Convert the command line arguments into a regular expression.
# For example: 4 9 1 56 -100 2
# becomes: 4|9|1|56|-100|2
# Do this by replacing one-or-more spaces by a pipe
pattern=$(echo "$*" | sed -E 's/ +/|/g')

# Remove the comment character below to see the pattern
#echo $pattern

# Use grep to display the lines (numbers) that do not match the
# pattern.
egrep -v "$pattern" $TMPFILE

# Clean up after ourselves
rm -f $TMPFILE