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 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).
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
; 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 ;