Sudoku Builder NetLogo Model
Produced for the book series "Exercises for Artificial Intelligence";
Author: W. J. Teahan; Publisher: Ventus Publishing Aps, Denmark.
powered by NetLogo
view/download model file: Sudoku-Builder.nlogo
WHAT IS IT?
This model allows the user to fill in a Sudoku puzzle.
WHAT IS ITS PURPOSE?
Its purpose is to demonstrate the use of various NetLogo commands and to show how relatively easy it is to create a non-trivial visual user interface that would require much more work in other languages.
HOW IT WORKS
It does this by creating a separate turtle agent (using a breed called a 'square') for each cell of the 9 by 9 Sudoku grid. Each square turtle agent keeps a number variable for storing the number that has been placed in the cell. Each agent also has two further variables - square-x and square-y - which record the (x, y) position of the square in the grid, where the bottom left square is (1, 1) and the top right is (9, 9). This is used to make it easier for checking the correctness of the placed numbers.
HOW TO USE IT
To set up an empty Sudoku grid, press the setup-sudoku button. To insert a number as specified by the number-to-be-placed slider into the grid, press the insert-number button. To delete a number, press the delete-number button. Pressing the check-sudoku button will check that the placed numbers are placed correctly.
THE INTERFACE
The model's Interface buttons and slider are defined as follows:
- setup-sudoku: This will create an empty Sudoku puzzle without any numbers inside it.
- insert-number: This will insert a number into a cell of the Sudoku puzzle
- delete-number: This will delete a number from a cell of the Sudoku puzzle.
- check-sudoku: This will check whether the placement of numbers in the Sudoku grid is correct or not. That is, there are no duplicate numbers in any horizontal or vertical line, or any 3 by 3 grid.
- number-to-be-placed: This is the number that will be placed when the mouse is clicked after the insert-number button is pressed.
THINGS TO NOTICE
This model provides the user with the ability to create a Sudoku puzzle for themselves, or try to fill in an existing one. Hence, there is not a lot to notice, except to say that if you use this model to try to create your own Sudoku puzzle, you will find it quite difficult. As the grid becomes filled in, it becomes increasingly more difficult to find a correct placement. Often you will find that proceeding further with the current configuration will be impossible, and you will need to backtrack to a point where a solution is still possible. Usually starting again can be the easiest option in this case.
THINGS TO TRY
Try using the model to solve an existing Sudoku puzzle.
Also, try creating your own Sudoku puzzle.
EXTENDING THE MODEL
Try adding some code that will report whether a current configuration has a solution (i.e. the remaining numbers can still be placed correctly).
Try extending the model so that it will automatically create a Sudoku puzzle. The hard bit is to find a configuration that makes it possible for a human to solve it using different levels of difficulty (as occurs with standard puzzles provided in puzzle books, newspapers, and online).
NETLOGO FEATURES
Note the use of the remove-duplicates command in the check-sudoku procedure that makes it easy to check whether a horizontal line, vertical line or 3 by 3 grid has any duplicate numbers in them (which indicates that the placement is incorrect).
CREDITS AND REFERENCES
This model was created by William John Teahan.
To refer to this model in publications, please use:
Sudoku Builder NetLogo model.
Teahan, W. J. (2010). Artificial Intelligence. Ventus Publishing Aps
PROCEDURES
; Sudoku Builder model
;
; Allows the user to create a Sudoku puzzle.
;
; Copyright Bill Teahan (2010)
breed [squares square] ; a square in the 9 by 9 grid
squares-own ; a square in the 9 by grid in which a number from 1 to 9 needs to be placed
[ square-x ; x square position in the grid; 1 is leftmost square; 9 is rightmost
square-y ; y square position in the grid; 1 is bottom square; 9 is top
number ] ; the number placed into the square
to setup-sudoku
clear-all
ask patches [ set pcolor white ] ; make background white
draw-grid
setup-squares ; these are the agents where the numbers are
end
to draw-row [from-x to-x y]
; Draws a horizontal line in the grid.
ask patches
[
if (pxcor >= from-x) and (pxcor <= to-x) and (pycor = y)
[ set pcolor black ]
]
end
to draw-col [x from-y to-y]
; Draws a vertical line in the grid.
ask patches
[
if (pxcor = x) and (pycor >= from-y) and (pycor <= to-y)
[ set pcolor black ]
]
end
to draw-rows [start-y]
let y start-y
draw-row -92 92 y
draw-row -92 92 y + 1
draw-row -92 92 y + 21
draw-row -92 92 y + 41
end
to draw-cols [start-x]
let x start-x
draw-col x -92 92
draw-col x + 1 -92 92
draw-col x + 21 -92 92
draw-col x + 41 -92 92
end
to draw-grid
; Draws the 9 by 9 grid
draw-rows -92
draw-rows -31
draw-rows 30
draw-row -92 92 91
draw-row -92 92 92
draw-cols -92
draw-cols -31
draw-cols 30
draw-col 91 -92 92
draw-col 92 -92 92
end
to setup-squares
; Creates the squares in the grid.
let x 1
let y 1
while [x <= 9]
[
set y 1
while [y <= 9]
[
setup-square x y
set y y + 1
]
set x x + 1
]
end
to-report square-location [this-square-x this-square-y]
; Reports the square x, y location as a list.
report
list
(-99 + this-square-x * 20 + int (this-square-x / 3))
(-103 + this-square-y * 20 + int (this-square-y / 3))
end
to setup-square [this-square-x this-square-y]
; Sets up the square turtle at position (square-x, square-y)
; in the Sudoku grid. (1,1) is left bottom;
; (9,9) is right top.
let location (square-location this-square-x this-square-y)
let x first location
let y last location
create-squares 1
[
set size 0 ; never show it - it is just there to store information
setxy x y
set square-x this-square-x
set square-y this-square-y
set number 0
]
end
to insert-number
; Allows the user to place a number into a square
let this-square nobody
let this-mouse-xcor 0
let this-mouse-ycor 0
if (mouse-down?)
[
set this-mouse-xcor mouse-xcor
set this-mouse-ycor mouse-ycor
set this-square min-one-of squares with [number = 0 or label-color = black]
[distancexy this-mouse-xcor this-mouse-ycor]
if ([distancexy this-mouse-xcor this-mouse-ycor] of this-square < 5)
[
ask this-square
[ set number number-to-be-placed
set label (word number)
set label-color black ]
if not check-sudoku
[ stop ]
]
]
end
to delete-number
; Allows the user to delete a number from a square
let this-square nobody
let this-mouse-xcor 0
let this-mouse-ycor 0
if (mouse-down?)
[
set this-mouse-xcor mouse-xcor
set this-mouse-ycor mouse-ycor
set this-square min-one-of squares with [label-color = black]
[distancexy this-mouse-xcor this-mouse-ycor]
if ([distancexy this-mouse-xcor this-mouse-ycor] of this-square < 5)
[
ask this-square
[ set number 0
set label ""
set label-color black ]
if not check-sudoku
[ stop ]
]
]
end
to-report placed-number [x y]
report [number] of (one-of squares with [square-x = x and square-y = y])
end
to-report check-sudoku
; Checks the numbers in the Sudoku grid to see if they are valid.
; Returns false if they are not.
let these-numbers []
let x 0 let y 0
let ok1 false ; vertical lines check out
let ok2 false ; horizontal lines check out
let ok3 false ; 3 by 3 grids check out
; check vertical lines
set ok1 false
foreach n-values 9 [? + 1] ; [1 2 3 4 5 6 7 8 9]
[
set x ?
set these-numbers n-values 9 [placed-number x (? + 1)]
set these-numbers remove 0 these-numbers ; remove unfilled squares
set ok1 (length these-numbers = length remove-duplicates these-numbers)
if not ok1
[
user-message (word "Error in vertical line " x ", numbers = " these-numbers)
report false
]
]
; check horizontal lines
set ok2 false
foreach n-values 9 [? + 1] ; [1 2 3 4 5 6 7 8 9]
[
set y ?
set these-numbers n-values 9 [placed-number (? + 1) y]
set these-numbers remove 0 these-numbers ; remove unfilled squares
set ok2 (length these-numbers = length remove-duplicates these-numbers)
if not ok2
[
user-message (word "Error in horizontal line " y ", numbers = " these-numbers)
report false
]
]
; check 3 by 3 grids
set ok3 false
foreach [2 5 8] ; x cente of each of the 3 by 3 grids
[ set x ?
foreach [2 5 8] ; y cente of each of the the 3 by 3 grids
[ set y ?
set these-numbers
(list
placed-number (x - 1) (y + 1)
placed-number (x ) (y + 1)
placed-number (x + 1) (y + 1)
placed-number (x - 1) (y )
placed-number (x ) (y )
placed-number (x + 1) (y )
placed-number (x - 1) (y - 1)
placed-number (x ) (y - 1)
placed-number (x + 1) (y - 1)
)
set these-numbers remove 0 these-numbers ; remove unfilled squares
set ok3 (length these-numbers = length remove-duplicates these-numbers)
if not ok3
[
user-message (word "Error in 3 by 3 grid centred at (" x "," y "), numbers = " these-numbers)
report false
]
]
]
report true
end
;
; Copyright 2009 William John Teahan. All rights reserved.
;
; Permission to use, modify or redistribute this model is hereby granted,
; provided that both of the following requirements are followed:
; a) this copyright notice is included.
; b) this model will not be redistributed for profit without permission
; from William John Teahan.
; Contact William John Teahan for appropriate licenses for redistribution for
; profit.
;
; To refer to this model in publications, please use:
;
; Teahan, W. J. (2010). Sudoku Builder NetLogo model.
; Artificial Intelligence. Ventus Publishing Aps
;