Ponder This Challenge - December 2012 - Maximal sum 6x6 grid

Ponder This Challenge:

36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square.

Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1.

Find a configuration of the 36 neighbors where the sum of their numbers is at least 90.

Finding a sum of 90+N will earn you N stars near your name.

As an example, the highest sum we can get in a 3x3 grid is 20:
1 2 1
4 3 4
2 1 2

An accompanying riddle, relating to a generalized version of this problem, appears in this month's Using your Head is Permitted
( http://www.brand.site.co.il/riddles/201212q.html).

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  There are several ways to solve this month's challenge. One method is to start with an all-1 matrix, incrementing random places as long as the result satisfies the rules. Restart when you are stuck and after a while you'll get a solution.

  Another way is to encode the challenge as an optimization problem and solve it using a SAT solver, BDD, CP, or MILP. Some of the solvers can do it in seconds.

  We also received correct solutions that were achieved using manual trial-and-error on an MS-Excel worksheet.

  Deron Stewart was the first to send a solution without 5:

  2 4 1 4 2 1
  1 3 2 3 4 1
  2 4 4 1 4 2
  4 1 3 2 3 4
  3 2 4 4 1 1
  1 3 1 3 2 3

  Mark Mammel was the first to send an optimal solution of 93:

  1 3 2 3 1 3
  2 5 1 4 5 2
  3 4 1 2 3 1
  1 2 3 5 4 1
  3 5 4 1 2 3
  2 1 2 3 4 1

Solvers

• Robin Ryder (11/29/2012 03:48 PM EDT)
• Zilin Jiang (11/29/2012 04:16 PM EDT)
• Peter de Rivaz (11/29/2012 04:18 PM EDT)
• ***David Greer (11/29/2012 04:57 PM EDT)
• ***Deron Stewart (11/29/2012 05:07 PM EDT)
• Chuck Carroll (11/29/2012 05:43 PM EDT)
• *Todd Will (11/29/2012 05:40 PM EDT)
• Mark Perkins (11/29/2012 06:16 PM EDT)
• ***Dan Dima (11/29/2012 06:40 PM EDT)
• Deane Stewart (11/29/2012 07:01 PM EDT)
• *Adrian Orzepowski (11/29/2012 07:30 PM EDT)
• *Philip Cerles (11/29/2012 10:34 PM EDT)
• *Kevin Sham (11/30/2012 01:07 AM EDT)
• ***Levent Erkok (11/30/2012 03:49 AM EDT)
• **Anders Kaseorg (11/30/2012 04:29 AM EDT)
• Kris Reyes (11/30/2012 06:13 AM EDT)
• Jay R. Joshi (11/30/2012 09:29 AM EDT)
• ***Daniel Bitin (11/30/2012 09:50 AM EDT)
• ***Donald Dodson (11/30/2012 01:12 PM EDT)
• Gergely Pataki (11/30/2012 01:51 PM EDT)
• ** (11/30/2012 01:56 PM EDT)
• *Matej Kollar (11/30/2012 01:56 PM EDT)
• *Zhichen Zhao (11/30/2012 04:45 PM EDT)
• János Kramár (11/30/2012 05:00 PM EDT)
• ***Mark Mammel (11/30/2012 07:11 PM EDT)
• Hamidreza Bidar (11/30/2012 07:21 PM EDT)
• Chhavi Gupta (11/30/2012 07:42 PM EDT)
• ***Øyvind Grotmol (11/30/2012 08:12 PM EDT)
• Pataki Gergely (11/30/2012 08:50 PM EDT)
• **Florian Fischer (11/30/2012 09:05 PM EDT)
• *James Hutchinson (11/30/2012 10:56 PM EDT)
• ***Tomek Czajka (12/01/2012 12:03 AM EDT)
• Ashfaque Shaikh (12/01/2012 03:24 AM EDT)
• *Tengyuan Liang (12/01/2012 04:44 AM EDT)
• ***Ben Andken (12/01/2012 01:16 PM EDT)
• Tony Maric & Vicki Kysar (12/01/2012 01:48 PM EDT)
• **Michael Davis (12/01/2012 02:06 PM EDT)
• ***Hakan Summakoglu (12/01/2012 02:14 PM EDT)
• *James Dow Allen (12/01/2012 03:23 PM EDT)
• **Mark Pervovskiy (12/01/2012 03:27 PM EDT)
• ***Siva Dirisala (12/01/2012 06:13 AM EDT)
• Maris Van Sprang (12/01/2012 03:51 PM EDT)
• Anant Sharma (12/01/2012 04:40 PM EDT)
• Adam Kozdron (12/01/2012 05:46 PM EDT)
• Joseph DeVincentis (12/01/2012 08:01 PM EDT)
• ***Aharon Malachi (12/01/2012 08:11 PM EDT)
• **Andy Carle (12/01/2012 10:15 PM EDT)
• ***Guangda Huzhang (12/02/2012 01:31 AM EDT)
• ***Oleg Zlydenko (12/02/2012 03:34 AM EDT)
• ***Dennis Langdeau (12/02/2012 03:54 AM EDT)
• ***Danny Antonetti (12/02/2012 04:29 AM EDT)
• ***Andreas Razen & Radu-Alexandru Todor (12/02/2012 06:50 AM EDT)
• Katarzyna Wojdziak (12/02/2012 01:47 PM EDT)
• **Rahul Bartakke (12/02/2012 01:59 PM EDT)
• *Tulasi Ram Reddy (12/02/2012 02:47 PM EDT)
• *Aditya Utturwar (12/02/2012 03:36 PM EDT)
• *** (12/02/2012 04:14 PM EDT)
• Peter Gerritson (12/02/2012 04:14 PM EDT)
• ***Hubert Kahlert (12/02/2012 04:46 PM EDT)
• ***Alex Wagner (12/02/2012 05:06 PM EDT)
• ***Carlos Henrique Cardonha (12/02/2012 07:00 PM EDT)
• *Lorenzo Gianferrari Pini (12/02/2012 08:51 PM EDT)
• Philipp Horsch (12/02/2012 10:57 PM EDT)
• *Hillel Lee Sing Chun (12/03/2012 04:35 AM EDT)
• Ashish Kumar (12/03/2012 05:33 AM EDT)
• *Jong Wook Kim (12/03/2012 08:51 AM EDT)
• Nachiketa Kumar (12/03/2012 09:10 AM EDT)
• Adrian Liebtrau (12/03/2012 10:29 AM EDT)
• *Andreas Stahl (12/03/2012 12:34 PM EDT)
• *Shengkai Cao (12/03/2012 12:48 PM EDT)
• Latricia Golden (12/03/2012 01:37 PM EDT)
• ***Armin Krauss (12/03/2012 02:17 PM EDT)
• **Yang Jiang (12/03/2012 02:28 PM EDT)
• Tanja Artiga Gonzalez (12/03/2012 02:46 PM EDT)
• **Jan Völkel (12/03/2012 04:04 PM EDT)
• Simon Foster (12/03/2012 06:03 PM EDT)
• Adam Daire (12/03/2012 07:05 PM EDT)
• ***Álvaro Begué (12/03/2012 07:56 PM EDT)
• Gordon Burtch (12/03/2012 08:11 PM EDT)
• ***Rob Pratt (12/03/2012 09:13 PM EDT)
• **Thomas Fleming (12/03/2012 09:51 PM EDT)
• **Boaz Menuhin (12/03/2012 11:00 PM EDT)
• Aaron Friedland (12/03/2012 10:53 PM EDT)
• **Naftali Peles (12/04/2012 12:29 AM EDT)
• **Liubing Yu (12/04/2012 12:41 AM EDT)
• John Colby (12/04/2012 01:18 AM EDT)
• ***Andrew Rochon (12/04/2012 03:04 AM EDT)
• Panagiotis Tsikogiannopoulos (12/04/2012 06:52 AM EDT)
• *Ben Green (12/04/2012 07:13 AM EDT)
• Harsha HS (12/04/2012 08:09 AM EDT)
• Tobias Philipp (12/04/2012 11:57 AM EDT)
• ***Hugo Pfoertner (12/04/2012 01:20 PM EDT)
• ***Irv Lustig (12/04/2012 02:45 PM EDT)
• Hannes Schenck (12/04/2012 04:02 PM EDT)
• ***Frederik Kaster (12/04/2012 04:01 PM EDT)
• ***Christopher E. Marks (12/04/2012 04:55 PM EDT)
• *Aleksey Voroshilov (12/04/2012 05:30 PM EDT)
• ***Roddy Kok (12/04/2012 05:36 PM EDT)
• ***Landon Kryger (12/04/2012 07:08 PM EDT)
• Greg Fritz (12/04/2012 08:26 PM EDT)
• ***Joe Clark (12/04/2012 08:30 PM EDT)
• ***Jamie Jorgensen & Jason Lee (12/04/2012 09:20 PM EDT)
• Graham McHardy (12/04/2012 10:58 PM EDT)
• **Andrzej Janiak (12/04/2012 11:20 PM EDT)
• Matthew Wood (12/05/2012 12:09 AM EDT)
• Shimaa Maher (12/05/2012 02:35 AM EDT)
• ***Janos Csorba (12/05/2012 08:40 AM EDT)
• Gaurav Bajaj (12/05/2012 09:25 AM EDT)
• ***Kevin Bauer (12/05/2012 11:25 AM EDT)
• Amita Sontakke (12/06/2012 12:43 AM EDT)
• Cliff Haithcock (12/06/2012 03:50 AM EDT)
• ***Ofer Reichman (12/06/2012 05:50 AM EDT)
• Luke Anklesaria (12/06/2012 06:16 AM EDT)
• ***Michael Liepelt (12/06/2012 06:33 AM EDT)
• Piny Houri (12/06/2012 11:38 AM EDT)
• ***Chris Davey (12/06/2012 02:43 PM EDT)
• Movin Jain (12/06/2012 03:28 PM EDT)
• ***Stéphane Higueret (12/06/2012 04:38 PM EDT)
• *Rosanna Holdsworth (12/06/2012 05:23 PM EDT)
• *Joel Baker (12/06/2012 10:37 PM EDT)
• *Rastko Anicic (12/06/2012 11:28 PM EDT)
• ***Tony Harrison (12/07/2012 09:32 AM EDT)
• Umut Uludag (12/07/2012 09:44 AM EDT)
• *Jayakumar Hoskere (12/07/2012 12:57 PM EDT)
• Simon Pratt (12/07/2012 02:27 PM EDT)
• Adam Danger (12/07/2012 02:28 PM EDT)
• *** (12/07/2012 06:18 PM EDT)
• Michael Rosola (12/07/2012 06:18 PM EDT)
• Spiegel Sanford (12/07/2012 07:18 PM EDT)
• ***Andrei Zaharescu (12/08/2012 12:32 AM EDT)
• ***Cong Zhao (12/08/2012 04:20 AM EDT)
• ***Greg Bubnis (12/08/2012 10:32 AM EDT)
• Anil Purohit (12/08/2012 11:35 AM EDT)
• Peter Steele (12/08/2012 01:13 PM EDT)
• Luisma Frutos (12/08/2012 09:51 PM EDT)
• *Dan Ignatoff (12/09/2012 04:55 AM EDT)
• Arun Ramachandran (12/09/2012 10:23 AM EDT)
• ***Simin Cheng (12/09/2012 10:56 AM EDT)
• Vibhakar Shukla (12/10/2012 11:54 AM EDT)
• ***Jason Crease (12/10/2012 12:27 PM EDT)
• **Rony Joseph (12/10/2012 12:46 PM EDT)
• ***Serge Gautier (12/10/2012 03:04 PM EDT)
• ***Amos Guler (12/11/2012 05:07 AM EDT)
• ***Puvichakravarthy Ramachandran (12/11/2012 10:15 AM EDT)
• **Nachiketa Kumar (12/11/2012 03:42 PM EDT)
• ***Levon Haykazyan (12/11/2012 03:54 PM EDT)
• *Javier Rodriguez (12/11/2012 07:44 PM EDT)
• Michael Chirozzi (12/11/2012 07:49 PM EDT)
• Phil Benamy (12/12/2012 12:42 AM EDT)
• ***Sridivakar Inakonda (12/12/2012 03:23 AM EDT)
• ***Thomas Egense (12/12/2012 04:49 AM EDT)
• ***Cameron Stewart (12/12/2012 06:51 AM EDT)
• **Srinivasan Iyer (12/12/2012 08:31 AM EDT)
• ***Lars Nagel (12/12/2012 11:31 AM EDT)
• Mert Öztürk (12/12/2012 03:44 PM EDT)
• **Sai Kulkarni (12/12/2012 05:10 PM EDT)
• *Joachim Dörfer (12/12/2012 07:08 PM EDT)
• Nachiket Bapat (12/12/2012 10:03 PM EDT)
• Peter Armitage (12/12/2012 10:45 PM EDT)
• ***Michael D Moffitt (12/12/2012 11:54 PM EDT)
• Victoria Krakovna (12/13/2012 01:16 AM EDT)
• ***Pablo Dal Lago (12/13/2012 04:43 AM EDT)
• **Bartosz Budzanowski (12/13/2012 11:42 AM EDT)
• *Nagendra Gulur Dwarakanath (12/13/2012 12:22 PM EDT)
• Olivier Mercier (12/13/2012 04:15 PM EDT)
• Ryan Ma (12/13/2012 05:50 PM EDT)
• Sri Mallikarjun J (12/14/2012 01:32 AM EDT)
• Brian Thomas (12/14/2012 04:18 AM EDT)
• **Lewei Weng (12/14/2012 07:23 AM EDT)
• Peter Park (12/14/2012 11:40 AM EDT)
• Oliver Lau (12/14/2012 12:06 PM EDT)
• *Nanmu (12/14/2012 02:41 PM EDT)
• ***Martin Husar (12/14/2012 03:56 PM EDT)
• *Rajat Goyal (12/14/2012 06:40 PM EDT)
• *Shi Jin (12/14/2012 07:30 PM EDT)
• Peter Simonyi (12/14/2012 11:01 PM EDT)
• **Edgardo Deza (12/15/2012 01:35 PM EDT)
• ***Mark Stuckel (12/16/2012 05:13 AM EDT)
• **Will Buehler (12/16/2012 01:50 PM EDT)
• **Alex Jeon (12/16/2012 07:26 PM EDT)
• Neil Smeby (12/16/2012 11:12 PM EDT)
• ***Keith Amling (12/17/2012 02:08 AM EDT)
• ***Christian Pape (12/17/2012 08:53 AM EDT)
• ***Heiko Selber (12/17/2012 08:00 AM EDT)
• *Waldek Zdanowicz (12/17/2012 01:08 PM EDT)
• ***Laurent Faureytier (12/17/2012 02:51 PM EDT)
• Benjamin Raibaud (12/17/2012 06:21 PM EDT)
• **David Friedman (12/15/2012 11:51 PM EDT)
• ***Harald Bögeholz (12/17/2012 09:25 PM EDT)
• ***Seth Troisi (12/17/2012 11:42 PM EDT)
• ***Shilei Zang (12/18/2012 02:01 AM EDT)
• **Simon Foster (12/18/2012 08:37 AM EDT)
• **Lucas Galfaso (12/18/2012 10:39 AM EDT)
• ***Halil Bayrak (12/18/2012 02:57 PM EDT)
• ***Johannes Waldmann (12/18/2012 04:58 PM EDT)
• ***John M Fonner (12/18/2012 05:52 PM EDT)
• *Alex Zdanowicz (12/18/2012 07:41 PM EDT)
• Gil Citro (12/18/2012 09:39 PM EDT)
• *Adam Danger (12/18/2012 11:10 PM EDT)
• **Seongwoo Hong (12/19/2012 01:19 PM EDT)
• ***Mark Pervovskiy (12/19/2012 03:48 PM EDT)
• ***Markus von Rimscha (12/19/2012 07:18 PM EDT)
• Vitor Miguel (12/20/2012 03:31 PM EDT)
• Geoff Kallweit (12/20/2012 03:58 PM EDT)
• Maria Helena G. Costa (12/20/2012 05:33 PM EDT)
• ***Amit Bhatia (12/21/2012 06:17 AM EDT)
• *Kipp Johnson (12/21/2012 12:18 AM EDT)
• Ian Smith (12/21/2012 05:49 AM EDT)
• ***Pooja Keswani (12/21/2012 09:07 AM EDT)
• ***Joaquim Neves Carrapa (12/21/2012 09:53 AM EDT)
• ***Fabio Filatrella (12/21/2012 11:38 AM EDT)
• ***Joël Bleuse (12/22/2012 05:56 PM EDT)
• Gueram Sargsyan (12/23/2012 10:46 AM EDT)
• ***Motty Porat (12/23/2012 05:34 PM EDT)
• Troy Prario (12/23/2012 10:51 PM EDT)
• ***Rajendran Thirupugalsamy (12/24/2012 02:52 AM EDT)
• **Aashay Harlalka (12/24/2012 05:41 AM EDT)
• ***Andreas Stiller (12/24/2012 08:31 AM EDT)
• Paul Mandell (12/24/2012 10:35 AM EDT)
• Nicholas Wegman (12/24/2012 02:42 PM EDT)
• **Markus Boettle (12/24/2012 07:31 PM EDT)
• *Andrey Stepin (12/25/2012 03:15 AM EDT)
• ***Geogry Chebanov (12/25/2012 02:55 PM EDT)
• ***Raman Khatri & Ankit Aggarwal (12/25/2012 06:55 PM EDT)
• ***Andrey Stepin (12/26/2012 12:30 AM EDT)
• *Umang Mittal (12/27/2012 06:02 AM EDT)
• Raghu Adari (12/27/2012 07:39 AM EDT)
• ***Tobias Philipp (12/27/2012 08:10 AM EDT)
• ***Marco Quargentan (12/27/2012 09:01 AM EDT)
• Frank Methling (12/27/2012 09:37 AM EDT)
• ***Ioan Marius Popdan (12/27/2012 11:29 AM EDT)
• Adriana Clerici (12/27/2012 01:54 PM EDT)
• **Gundars Kokts (12/28/2012 03:53 AM EDT)
• Vivek Ranjan Nema (12/28/2012 05:41 AM EDT)
• ***Albert Stadler (12/28/2012 06:56 PM EDT)
• *Franciraldo Cavalcante Jr (12/29/2012 03:10 AM EDT)
• Yuchen Wang (12/29/2012 07:18 AM EDT)
• *Aditi Agrawal (12/29/2012 04:00 PM EDT)
• ***Aditya Pal (12/29/2012 06:32 PM EDT)
• Sandeep Navada (12/29/2012 08:40 PM EDT)
• ***Pedro Fonseca (12/29/2012 10:56 PM EDT)
• Seung Min "Brian" Park (12/29/2012 11:43 PM EDT)
• Minxi Jiang (12/31/2012 04:41 AM EDT)
• Shouky Dan & Tamir Ganor (12/31/2012 06:47 AM EDT)
• **Don Gosiewski (12/31/2012 07:03 AM EDT)
• *Sergey Grishaev (12/31/2012 12:37 PM EDT)
• *Daniel Lincke (12/31/2012 05:42 PM EDT)
• ***Renato Fonseca (12/31/2012 07:13 PM EDT)
• Jeff Steele (12/31/2012 10:05 PM EDT)
• **Mutaamba Maasha (12/31/2012 11:18 PM EDT)
• Bradley Sherman (01/01/2013 03:50 AM EDT)
• *Amir Leshem (01/01/2013 07:19 AM EDT)
• Jeffrey Boerner (01/01/2013 02:51 PM EDT)
• ***Manix Rock (01/01/2013 03:35 PM EDT)
• **Danny Lynch (01/02/2013 06:41 AM EDT)
• **Doug Wines (01/02/2013 03:34 PM EDT)