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
;